Cryptography Reference
In-Depth Information
For a random logarithm
x
, we do expect to find the correct solution after checking
half of all possible
x
. This gives us a complexity of
) steps
2
, where
O
(
|
G
|
|
G
|
is the
cardinality of the group.
To avoid brute-force attacks on DL-based cryptosystems in practice, the cardi-
nality
of the underlying group must thus be sufficiently large. For instance, in
the case of the group
|
G
|
Z
p
,
p
prime, which is the basis for the DHKE, (
p
−
1)
/
2tests
are required on average to compute a discrete logarithm. Thus,
1 should
be at least in the order of 2
80
to make a brute-force search infeasible using today's
computer technology. Of course, this consideration only holds if a brute-force attack
is the only feasible attack which is never the case. There exist much more powerful
algorithms to solve discrete logarithms as we will see below.
|
G
|
=
p
−
Shanks' Baby-Step Giant-Step Method
Shanks' algorithm is a time-memory tradeoff method, which reduces the time of
a brute-force search at the cost of extra storage. The idea is based on rewriting the
discrete logarithm
x
= log
α
β
in a two-digit representation:
x
=
x
g
m
+
x
b
for 0
≤
x
g
,
x
b
<
m
.
(8.1)
The v
alu
e
m
is chosen to be of the size of the square root of the group order, i.e.,
m
=
|
x
=
x
g
m
+
x
b
which
G
|
. We can now write the discrete logarithm as
β
=
α
α
leads to
α
−
m
)
x
g
=
x
b
.
β
·
(
α
(8.2)
The idea of the algorithm is to find a solution (
x
g
,
x
b
) for Eq. (8.2), from which the
discrete logarithm then follows directly according to Eq. (8.1). The core idea for the
algorithm is that Eq. (8.2) can be solved by searching for
x
g
and
x
b
separatedly, i.e.,
using a divide-and-conquer approach. In the first phase of the algorithm we compute
and sto
re a
ll values
x
b
, where 0
α
≤
x
b
<
m
. This is the
baby-st
ep p
hase
that requires
≈
|
≈
|
m
group elements.
In the
giant-step phase
, the algorithm checks for all
x
g
in the range 0
G
|
steps (group operations) and needs to store
m
G
|
≤
x
g
<
m
whether the following condition is fulfilled:
?
=
α
−
m
)
x
g
x
b
β
·
(
α
x
b
that was computed during the baby-step phase. In case of
for some stored entry
α
α
−
m
)
x
g
,
0
=
x
b
,
0
for some pair (
x
g
,
0
,
x
b
,
0
), the discrete logarithm is
a match, i.e.,
β
·
(
α
given by
x
=
x
g
,
0
m
+
x
b
,
0
.
(
) computational steps and an
equal amount of memory. In a group of order 2
80
, an attacker would only need
The baby-step giant-step method requires
O
|
G
|
2
We use the popular “big-Oh” notation here. A complexity function
f
(
x
) has big-Oh notation
O
(
g
(
x
)) if
f
(
x
)
≤
c
·
g
(
x
) for some constant
c
and for input values
x
greater than some value
x
0
.
