------------------------------------------------------------------------------
This is a precise, slightly technical description of what our
pseudo-random iteration is, of which points are considered distinguished,
and of the format for sending them in.
It is intended that with this information, others can write client programs
compatible with ours and work with us. Working together makes sense for
"birthday paradox" algorithms since the number of pairs grows as the square
of the work done. Rather than two groups doing a^2 and b^2 pairs
respectively, it's much better to work together and get (a+b)^2 pairs.
Rob
(Robert.Harley@inria.fr)
------------------------------------------------------------------------------
Consider the points (x:y:1) with y^2+x*y = x^3+1 in the field
(Z/(2))[t] / (t^97+t^6+1), and the point "at infinity" (0:1:0).
Let g = 2^95-94562993267977. There are 4*g points. Under the usual
chord-and-tangent operation, they form a group. We will work in the
subgroup of order g.
We are given two points P and Q and want to find the discrete logarithm of
Q to the base P i.e., the integer l modulo g such that Q = [l]P, where this
notation indicates repeating the chord-and-tangent operation l times.
For the ECC2K-95 problem:
P = (0x08A84FB02034F7771DC940097 : 0x1D2F10A471D48A720F18F6339 : 1)
Q = (0x0E0BC08AC5818F303E2B05E90 : 0x134C028FC3393124D673E6F8E : 1)
The coefficients are encoded as hex integers by "setting t to 2".
Start by taking random u and v with 0 <= u,v < g, such that R = [u]P+[v]Q
is finite. Then do:
main loop:
Let R = [u]P+[v]Q, get its x-coordinate, write it in the basis
{ (t+1)^(2^k) | 0 <= k < 97 } over Z/2Z and count the non-zero
coefficients, giving m.
If m is 20 then R is "distinguished" so output it, quit the loop and
start from scratch.
Multiply u and v by 2, 6, 88, 90 or 92 modulo g, according to m = 0,
1, 2, 3 or 4 modulo 5.
end loop.
The format for distinguished points is a single line:
ECC2K-95|i|<12>|u|<25>|v|<25>|x|<25>|y|<25>||||||||
Here indicates a hexadecimal number of n hex digits, padded with zeroes
if necessary. The values are:
i: the number of iterations performed for this point,
u, v: the multipliers reduced mod g,
x, y: coordinates of R reduced mod t^97+t^6+1
Furthermore indicates the name of the client program,
indicates its version and so on. None of these fields should contain the |
character.
Here is a sample line:
ECC2K-95|i|000003CAA36C|u|0429A7359C073562CF5BFB90D|v|037CEBBAE69347D2DA96508F5|x|18117939C5998990AD2DE3B26|y|19404AC36113516C438303E30|RobsECDL|Alpha 110|Robert Harley|INRIA|corton|alpha|Linux|500 MHz 21164a
Such lines should be sent by email to:
ecdl@pauillac.inria.fr
or, if that fails, to:
robert@vlsi.cs.caltech.edu
If you find any disagreements between this description and the
sample implementation at:
http://pauillac.inria.fr/~harley/ecdl5/Alpha_111/source/ecdl2K-95.c
http://pauillac.inria.fr/~harley/ecdl5/Alpha_111/source/ecdl2K-95.c.gz
please let me know!
------------------------------------------------------------------------------
Notes:
* Of course when the initial R is chosen at random it is overwhelmingly
likely to be finite. By checking that it really is we can ignore the
z coordinate since it will always be 1:
loop:
u := random.
v := random.
R := [u]P+[v]Q.
while R is infinite.
* For efficiency avoid computing R every main loop iteration, but do it
incrementally something like:
f := 1.
i := 0.
main loop:
If R is distinguished set u,v := f*u,f*v, output i,u,v,x,y and restart.
Multiply f by 2, 6, 88, 90 or 92 modulo g and update R accordingly.
i := i+1.
end loop.
* Those weird coefficients are chosen because 6 = -w^5-w, 88 = w^13-w^3,
90 = w^13+w and 92 = w^13-w^2 where w = (-1+sqrt(-7))/2. Multiplication
by w is the Frobenius endomorphism which can be computed quickly by
squaring the x and y coordinates. This choice is quite ad-hoc but roughly
doubles the iteration speed compared to choosing, say, 2, 3, 5, 7 and 11.
(In general the multipliers could be any integers of Q(sqrt(-7)), but
choose them multiplicatively independent up to sign and powers of w).
* Instead of actually multiplying f by 2,..,92 you can just keep track of
the powers of 2,..,92 that it contains. Furthermore since sign and powers
of w don't affect the pseudo-random iteration, you can use 6 ~= w^4+1,
88 ~= -w^10+1 etc. to reduce the number of squarings. Then when a
distinguished point is found, compute f, update u,v := f*u,f*v, get
the true value of R := [u]P+[v]Q, output i,u,v,x,y and restart.
* You can use any basis you like for the arithmetic; the sample
implementation uses the polynomial basis { t^k | 0 <= k < 97 } throughout.
But for checking distinguishedness you must use the { (t+1)^(2^k) } one
(in general any normal basis would do).
* If this algorithm seems a little complicated, it is because instead of
iterating on points, we are "really" iterating on orbits of points under
the involution [-1] and the Frobenius endomorphism [w]. The iterations
take about 150% as long as when iterating directly on points but there are
sqrt(2*97) fewer iterations needed so overall it's a big win.
In general we could consider using extra automorphisms on curves with
j-invariant 0 or 1728, using complex multiplication, etc. I suggest
reading Chapters III and V of Joseph Silverman's book for ideas.
* I would like to point out that this algorithm is not based on the two
recent papers by Wiener and Zuccherato on one hand and Gallant, Lambert
and Vanstone on the other. This is independent work designed, implemented
and tested on thousands of small examples prior to those being released.
Any resemblance between our three independent discoveries of similar
algorithms is probably due to the fact that they become blindingly obvious
after staring at the problem for several months =8-)
* I would like to thank Ari Singer for not believing me back in February
when I said that clustering the points gave no practical improvement for
ECCp-97. I was right but he forced me to think about the matter more!
I would also like to thank Rob Zuccherato for sending his and
Michael Wiener's paper, "Faster Attacks on Elliptic Curve Cryptosystems".
* It seems that there is no asymptotic improvement to be had for ECDL's
over GF(2^n), with curves over GF(2), as n grows. An elliptic curve
operation takes time O(n^(1+epsilon)) when using a polynomial basis but
changing basis or working directly in a normal basis takes O(n^2).
Thus asymptotically we lose a factor O(n^(1/2-epsilon)) :-(
For "small" cases there may be a constant-factor speedup in practice.
The sample implementation for ECC2K-95 gains a factor of 10 or so compared
to some test code for ECC2-97.
* Fire up those Alphas!
------------------------------------------------------------------------------