Cryptography Reference
In-Depth Information
Example 13.2.3
Let
p
=
19
,g
=
2 and
h
=
5. The aim is to find an integer
a
such that
h
≡
g
a
(mod
p
). Note that
p
3
2
. We first find
a
modulo 2. We have (
p
−
1
=
2
·
−
1)
/
2
=
9so
g
9
h
9
define
g
0
=
≡−
1 (mod 19) and
h
0
=
≡
1 (mod 19). It follows that
a
≡
0(mod2).
g
2
Now we find
a
modulo 9. Since (
p
−
1)
/
9
=
2 we first compute
g
0
=
≡
4(mod19)
h
2
and
h
0
≡
≡
6 (mod 19). To get information modulo 3 we compute
g
0
≡
7 (mod 19) and
h
0
≡
g
1
=
7(mod19)
.
It follows that
a
≡
1 (mod 3). To get information modulo 9 we remove the modulo 3 part
g
a
1
1
by setting
h
1
=
h
0
/g
0
=
6
/
4
≡
11 (mod 19). We now solve
h
1
≡
(mod 19), which has
the solution
a
1
≡
2 (mod 3). It follows that
a
≡
1
+
3
·
2
≡
7(mod9).
Finally, by the Chinese remainder theorem we obtain
a
≡
16 (mod 18).
Exercise 13.2.4
Let
p
22. Solve the discrete logarithm problem of
h
to the base
g
using the Pohlig-Hellman method.
=
31,
g
=
3 and
h
=
We recall that an integer is
B
-smooth if all its prime factors are at most
B
.
Theorem 13.2.5
Let g
∈
G have order N. Let B
∈ N
be such that N is B-smooth Then
Algorithm
12
solves the DLP in G using O
(log(
N
)
2
B
log(
N
))
group operations.
2
+
Proof
One can factor
N
using trial division in
O
(
BM
(log(
N
))) bit operations, where
M
(
n
) is the cost of multiplying
n
-bit integers. We assume that
M
(log(
N
)) is
O
(1) group
operations (this is true for all the algebraic groups of interest in this topic). Hence, we may
assume that the factorisation of
N
is known.
Computing all
l
e
i
i
(
h
) can be done naively in
O
(log(
N
)
2
) group operations,
butweprefertodoitin
O
(log(
N
)loglog(
N
)) group operations using the method of
Section
2.15.1
.
Lines5to13run
i
=
1
e
i
=
(
g
) and
l
e
i
i
2, we have
i
=
1
e
i
≤
log
2
(
N
). The computation of
u
in line 6 requires
O
(
e
i
log(
l
i
)) group operations. Together
this gives a bound of
O
(log(
N
)
2
) group operations to the running time. (Note that when
N
O
(log(
N
)) times and, since each
l
i
≥
O
(log(
N
)
2
) group operations.)
Solving each DLP in a cyclic group of order
l
i
using naive methods requires
O
(
l
i
)
group operations (this can be improved using the baby-step-giant-step method). There are
≤
2
e
then the cost of these lines is
e
2
log(2)
=
=
log
2
(
N
) such computations to perform, giving
O
(log(
N
)
B
) group operations.
The final step is to use the Chinese remainder theorem to compute
a
, requiring
O
(log(
N
)
M
(log(
N
))) bit operations, which is again assumed to cost at most
O
(log(
N
))
group operations.
Due to this method small primes give no added security in discrete logarithm systems.
Hence, one generally uses elements of prime order
r
for cryptography.
2
By this, we mean that the constant implicit in the
O
(
·
) is independent of
B
and
N
.
