Cryptography Reference
In-Depth Information
is clear that
r
0
=
s
0
=
0 and a straightforward induction shows that the subsequent
values for the exponents are given by:
⎧
⎨
⎧
⎨
r
i
+
1mod
n
if
x
i
∈
S
1
,
s
i
if
x
i
∈
S
1
,
r
i
+
1
=
2
r
i
mod
n
if
x
i
∈
S
2
,
s
i
+
1
=
2
s
i
mod
n
if
x
i
∈
S
2
,
⎩
⎩
r
i
if
x
i
∈
S
3
.
s
i
+
1mod
n
if
x
i
∈
S
3
.
g
r
i
a
s
i
for all
i
0. As we did in the case of the rho
factoring method, we can use Floyd's cycle-finding algorithm to find a collision
x
i
Then we have that
x
i
=
≥
x
2
i
, so that
g
r
i
a
s
i
g
r
2
i
a
s
2
i
and
a
s
i
−
s
2
i
g
r
2
i
−
r
i
. Taking base-
g
logarithms
=
=
=
we obtain
)
but the probability is small. In this extreme case the previous congruence gives no
information whatsoever and any value in
(
s
i
−
s
2
i
)
log
g
a
≡
(
r
2
i
−
r
i
)(
mod
n
)
. It may happen that
s
i
≡
s
2
i
(
mod
n
Z
n
may be the logarithm so that searching
all the possibilities would amount to a brute-force attack. Thus, when this happens,
the best strategy is to restart the algorithm with different values of
x
0
,
r
0
and
s
0
.
On the other hand, if 0
=
t
=
(
s
i
−
s
2
i
)
mod
n
and
u
=
(
r
2
i
−
r
i
)
mod
n
we
have a congruence
t
log
g
a
u
and, using the extended Euclidean algorithm, we may find an integer
w
such that
tw
≡
u
(
mod
n
)
. Then, if
d
=
gcd
(
t
,
n
)
we see that
d
|
≡
d
(
mod
n
)
. Multiplying the congruence involving log
g
a
by
w
we obtain a
congruence:
d
log
g
a
≡
uw
(
mod
n
),
in which
d
has
d
solutions (see,
e.g., [194, Theorem 5.7]) which are the members of the following set:
uw
d
+
|
uw
. Then the linear equation
dx
≡
uw
(
mod
n
)
1
j
n
d
|
j
=
0
,
1
,...,
d
−
.
One of these solutions must be log
g
a
and we can find which one by trying all the
possibilities. This is usually easy because
d
is small and, in fact, we often have that
d
=
1. Indeed, in most cryptographic applications either
n
=
p
is prime or
n
has
a large prime factor. In the first case, either
t
=
0 which, as already mentioned, is
unlikely, or 0
1 giving a unique solution. In
case
n
is not prime, it is unlikely that
t
will be divisible by the large prime factor of
n
and hence
d
will also be small—and, if
d
is too large, the algorithm can be restarted
with different initial values as in the case
t
<
t
<
p
which implies
d
=
gcd
(
t
,
p
)
=
. The reason of choosing
n
in this way is precisely to make the DLP problem hard for, as we shall soon see, there
is an algorithm—the Pohlig-Hellman algorithm—that essentially reduces the DLP
in a group of order
n
(whose prime factorization is known) to the DLP in groups of
prime order. Observe also that, once the Pohlig-Hellman algorithm is available, it
suffices to apply the rho method to groups of prime order.
There are many possible ways to choose the subsets
S
1
,
S
2
,
S
3
and, indeed, there is
no reason to choose precisely three subsets. In other variants of the algorithm, many
more subsets—often called
branches
—are chosen (see, e.g., [97] where additive
≡
0
(
mod
n
)
