Cryptography Reference
In-Depth Information
Faster modular reduction
Using Newton's method to compute
a/n
one can compute
a
(mod
n
) using only mul-
O
(
n
2
) then the complexity is
O
(
M
(log(
n
))). See Exercises
3.35, 3.36 of [
497
] and Section 9.1 of [
220
] for details. For large
a
, the cost of computing
a
(mod
n
) remains
O
(log(
a
)log(
n
)) as before. This idea gives rise to Barret reduction; see
Section 9.2.2 of [
150
], Section 2.3.1 of [
95
], Section 14.3.3 of [
376
], Section II.1.3 of [
60
]
or Section 10.4.1 of [
16
].
tiplication of integers. If
a
=
Special moduli
For cryptography based on discrete logarithms, especially elliptic curve cryptography,
it is recommended to use primes of a special form to speed up arithmetic modulo
p
.
Commonly used primes are of the form
p
2
k
=
−
c
for some small
c
∈ N
or the
NIST
2
n
k
w
2
n
k
−
1
w
2
n
1
w
primes
p
16
,
32 or 64. In these cases, it is
possible to compute reduction modulo
p
much more quickly than for general
p
. See Section
2.2.6 of [
248
], Section 14.3.4 of [
376
] or Section 10.4.3 of [
16
] for examples and details.
=
±
±···±
±
1 where
w
=
Modular inversion
1. One can compute
a
−
1
Suppose
a,n
∈ N
are such that gcd(
a,n
)
=
(mod
n
)usingthe
extended Euclidean algorithm: computing integers
s,t
∈ Z
such that
as
+
nt
=
1gives
a
−
1
s
(mod
n
). Hence, if 0
<a<n
then one can compute
a
−
1
(mod
n
)in
O
(log(
n
)
2
)
bit operations, or faster using subquadratic versions of the extended Euclidean algorithm.
In practice, modular inversion is significantly slower than modular multiplication. For
example, when implementing elliptic curve cryptography it is usual to assume that the cost
of an inversion in
≡
F
p
is between 8 and 50 times slower than the cost of a multiplication in
F
p
(the actual figure depends on the platform and algorithms used).
Simultaneous modular inversion
One can compute
a
−
1
1
(mod
n
)
,...,a
−
m
(mod
n
) with a single inversion modulo
n
and
a number of multiplications modulo
n
using a trick due to Montgomery. Namely, one
computes
b
a
m
(mod
n
), computes
b
−
1
=
a
1
···
(mod
n
) and then recovers the individual
a
−
1
i
.
Exercise 2.5.5
Give pseudocode for simultaneous modular inversion and show that it
requires one inversion and 3(
m
−
1) modular multiplications.
2.6 Chinese remainder theorem
The Chinese remainder theorem (CRT) states that if gcd(
m
1
,m
2
)
=
1 then there is a unique
solution 0
1
,
2. Computing
x
can be done in
polynomial-time in various ways. One method is to use the formula
≤
x<m
1
m
2
to
x
≡
c
i
(mod
m
i
)for
i
=
c
1
)(
m
−
1
1
x
=
c
1
+
(
c
2
−
(mod
m
2
))
m
1
.
