Cryptography Reference
In-Depth Information
Chapter 5
The Discrete Logarithm
Problem
Let
p
be a prime and let
a, b
be integers that are nonzero mod
p
. Suppose we
know that there exists an integer
k
such that
a
k
≡ b
(mod
p
)
.
The classical
discrete logarithm problem
is to find
k
.Since
k
+(
p −
1) is
also a solution, the answer
k
should be regarded as being defined mod
p −
1,
or mod a divisor
d
of
p −
1if
a
d
≡
1(mod
p
).
More generally, let
G
be any group, written multiplicatively for the moment,
and let
a, b ∈ G
. Suppose we know that
a
k
=
b
for some integer
k
.Inthis
context, the discrete logarithm problem is again to find
k
. For example,
G
could be the multiplicative group
F
q
of a finite field. Also,
G
could be
E
(
F
q
)
for some elliptic curve, in which case
a
and
b
are points on
E
and we are
trying to find an integer
k
with
ka
=
b
.
In Chapter 6, we'll meet several cryptographic applications of the discrete
logarithm problem. The security of the cryptosystems will depend on the
diculty of solving the discrete log problem.
One way of attacking a discrete log problem is simple brute force: try all
possible values of
k
until one works. This is impractical when the answer
k
can be an integer of several hundred digits, which is a typical size used in
cryptography. Therefore, better techniques are needed.
In this chapter, we start by discussing an attack, called the index calculus,
that can be used in
F
p
, and more generally in the multiplicative group of a
finite field. However, it does not apply to general groups. Then we discuss the
method of Pohlig-Hellman, the baby step, giant step method, and Pollard's
ρ
and
λ
methods. These work for general finite groups, in particular for elliptic
curves. Finally, we show that for special classes of elliptic curves, namely
supersingular and anomalous curves, it is possible to reduce the discrete log
problem to easier discrete log problems (in the multiplicative group of a finite
field and in the additive group of integers mod a prime, respectively).
Search WWH ::
Custom Search