Cryptography Reference
In-Depth Information
t
i
n
0
modulo
B
, multiply it by
n
, scale by the factor
B
i
, and add to
t
. To calculate
ab
mod
n
with
a, b < n
the modulus
n
has the
representation
n
=(
n
l
−
1
n
l
−
2
...n
0
)
B
We can create a digit
m
i
←
as above, and we let
r
:=
B
l
as well as
rr
− nn
=1
and
n
0
:=
n
mod
B
.
Calculation of the Montgomery product
a
×
b
à la Dussé and Kaliski
1.
Set
t ← ab
,
n
0
← n
mod
B
,
i ←
0
.
2.
Set
m
i
← t
i
n
0
mod
B
(
m
i
is a one-digit integer).
3.
Set
t ← t
+
m
i
nB
i
.
4.
Set
i ← i
+1
;if
i ≤ l −
1
,gotostep2.
5.
Set
t ← t/r
.
6.
If
t ≥ n
, output
t − n
and otherwise
t
.
Dussé and Kaliski state that the basis for their clever simplification is the
method of Montgomery reduction to develop
t
as a multiple of
r
, but they offer no
proof. Before we use this procedure we wish to make more precise why it suffices
to calculate
a × b
. The following is based on a proof of Christoph Burnikel [Zieg]:
In steps 2 and 3 the algorithm calculates a sequence
t
(
i
)
i
=0
,...,l
by means
of the recursion
t
(0)
=
ab,
(6.16)
t
(
i
+1)
=
f
t
(
i
)
B
i
B
i
,
i
=0
,...,l
−
1
,
(6.17)
where
f
(
t
)=
t
+
(
t
mod
B
)
−n
−
1
mod
B
mod
B
n
is the already familiar function that is induced by the Montgomery equation (cf.
(6.13), and there set
r ← B
in
f
(
t
)
). The members of the sequence
t
(
i
)
have the
properties
t
(
i
)
≡
0mod
B
i
,
(6.18)
t
(
i
)
≡ ab
mod
n,
(6.19)
t
(
l
)
r
abr
−
1
mod
n,
≡
(6.20)
t
(
l
)
r
<
2
n.
(6.21)
Properties (6.18) and (6.19) are derived inductively from (6.14), (6.15), (6.16),
and (6.17); from (6.18) we obtain
B
l
t
(
l
)
t
(
l
)
. From this and from
|
⇔
r
|
