Cryptography Reference
In-Depth Information
Again we present an example with small numbers for clarification: Let
a
= 123
,
b
= 456
,
n
= 789
,
r
=2
10
.Then
n
=
−n
−
1
mod
r
= 963
,
a
= 501
,
and
p
=
a
×
b
=69=
ab
mod
n
.
Since the precalculation of
r
and
n
in steps 1 and 2 is very time-
consuming and Montgomery reduction in this version also has two long-number
multiplications on its balance sheet, there is actually an increased computational
expenditure compared with “normal” modular multiplication, so that the
computation of
individual
products with Montgomery reduction is not
worthwhile.
However, in cases where
many
modular multiplications with a
constant
modulus are required, for which therefore the time-consuming precalculations
occur only once, we may expect more favorable results. Particularly suited for
the Montgomery product is modular exponentiation, for which we shall suitably
modify the
M
-ary algorithm. To this end let once again
e
=(
e
m
−
1
e
m
−
2
...e
0
)
B
and
n
=(
n
l
−
1
n
l
−
2
...n
0
)
B
be the representations of the exponent
e
and
the modulus
n
to the base
B
=2
k
. The following algorithm calculates powers
a
e
mod
n
in
Z
n
with odd
n
using Montgomery multiplication. The squarings
that occur in the exponentiation become Montgomery products
a × a
,inthe
computation of which we can use the advantages of squaring.
Exponentiation modulo
n
(
n
odd) with the Montgomery product
1.
Set
r ← B
l
=2
kl
. Calculate
1=
rr
− nn
with the Euclidean algorithm.
2.
Set
a ← ar
mod
n
. Calculate and store the powers
a
3
, a
5
,...,a
2
k
−
1
using
×
in
R
(
r, n
)
.
the Montgomery product
(
a
u
)
2
t
.
=0
, factor
e
m
−
1
=2
t
u
with odd
u
.Set
p
3.
If
e
m
−
1
←
If
e
m
−
1
=0
, set
p ← r
mod
n
.
In each case set
i
2
.
4.
If
e
i
=0
,set
p ← p
2
k
=
←
m
−
2
p
2
2
2
(
k
-fold squaring
p
2
=
p×p
)
.
···
···
=0
, factor
e
i
=2
t
u
with odd
u
.Set
p ←
p
2
k
−
t
× a
u
2
t
If
e
i
.
5.
If
i
≥
0
,set
i
←
i
−
1
and go to step 4.
6.
Output the Montgomery product
p
×
1
.
Further possibilities for improving the algorithm lie less in the exponentiation
algorithm than in the implementation of the Montgomery product itself, as
demonstrated by S. R. Dussé and B. S. Kaliski in [DuKa]: In calculating the
Montgomery product on page 108, in step 2 we can avoid the assignment
m ← tn
mod
r
in the reduction modulo
r
. Furthermore, we can calculate with
n
0
:=
n
mod
B
instead of with
n
in executing the Montgomery reduction.
