Cryptography Reference
In-Depth Information
14.4.3 Practical experience with the distributed rho algorithm
Real computations are not as simple as the idealised analysis above: one does not know
in advance how many clients will volunteer for the computation; not all clients have the
same performance or reliability; clients may decide to withdraw from the computation at
any time; the communications between client and server may be unreliable etc. Hence, in
practice one needs to choose the distinguished points to be sufficiently common that even
the weakest client in the computation can hit a distinguished point within a reasonable time
(perhaps after just one or two days). This may mean that the stronger clients are finding
many distinguished points every hour.
The largest discrete logarithm problems solved using the distributed rho method are
mainly the Certicom challenge elliptic curve discrete logarithm problems. The current
records are for the groups
E
(
F
p
) where
p
≈
2
108
+
2
107
(by a team coordinated by Chris
Monico in 2002) and where
p
=
(2
128
−
3)
/
76439
≈
2
111
+
2
110
(by Bos, Kaihara and
Montgomery in 2009) and for
E
(
F
2
109
) (again by Monico's team in 2004). None of these
computations used the equivalence class
.
We briefly summarise the parameters used for these large computations. For the 2002
result the curve
E
(
{
P,
−
P
}
2
108
2
107
. The number of processors
F
p
) has prime order so
r
≈
+
2
−
29
. The number of distinguis
hed p
oints found was
68 228 567, which is roughly 1
.
32 times the expected number
θ
√
πr/
2 of points to be
collected. Hence, this computation was unlucky in that it ran about 1.3 times longer than
the expected time. The computation ran for about 18 months.
The 2004 result is for a curve over
was over 10,000 and they used
θ
=
2
108
.The
F
2
109
with group order 2
r
where
r
≈
2
−
30
computation used roughly 2000 processors,
θ
=
and the number of disti
nguished
points found was 16 531 676. This is about 0
.
79 times the expected number
θ
π
2
108
/
2.
This computation took about 17 months.
The computation by Bos, Kaihara and Montgomery [
85
] was innovative in that the work
was done using a cluster of 200 computer game consoles. The random walk used
n
S
=
16
1
/
2
24
. The total number of group operations performed was 8
.
5
10
16
and
θ
=
×
(which is
10
9
1
.
02 times the expected value) and 5
×
distinguished points were stored.
Exercise 14.4.1
2
Verify that the parameters above
s
atisfy the requirements that
θ
is much
larger than 1
/
√
r
and
N
P
is much smaller than
θ
√
r
.
There is a close fit between the actual running time for these examples and the theoretical
estimates. This is evidence that the heuristic analysis of the running time is not too far from
the performance in practice.
14.5 The kangaroo method
This algorithm is designed for the case where the discrete logarithm is known to lie in a
short interval. Suppose
g
g
a
where
a
lies in a short interval
∈
G
has order
r
and that
h
=
b
≤
a<b
+
w
of width
w
. We assume that the values of
b
and
w
are known. Of course,
