Elliptic Curve Cryptography
and Scott Vanstone
The Guide was published in 2004. This page collects selected updates,
but is clearly only a sampling of relevant material released since
Pages 18 and 22. ECC2-109 claimed, April 2004. "Chris Monico, an
assistant professor at Texas Tech University, and his team of
mathematicians have successfully solved the Certicom Elliptic Curve
Cryptography (ECC)2-109 Challenge. The effort required 2600 computers
and took 17 months." See the announcement.
Advances in Elliptic Curve Crytography
by I. Blake, G. Seroussi, N. Smart (with contributions by
D. Brown, A. W. Dent, E. Oswald, M. Joye, F. Vercauteren, P. Gaudry,
F. Hess, S. Galbraith, and K. G. Paterson) is expected April 2005.
Page 60, below Algorithm 2.50. Techniques to enlarge the class of
"suitable polynomials" are noted in:
Field inversion and point halving revisited (Fong, Hankerson, López,
and Menezes), Transactions on Computers 53(8):1047-1059, 2004. This also
adds data related to pages 222-223.
Page 72. Normal basis arithmetic in software implementations is
explored futher in:
- Arash Reyhani-Masoleh,
Efficient algorithms and architectures for field
multiplication using Gaussian normal bases,
Technical Report CACR 2004-04, University of Waterloo, Canada, 2004.
- Haining Fan and Yiqi Dai,
Two Software Normal Basis Multiplication Algorithms for GF(2n),
Cryptology ePrint Archive,
Report 2004/126, 2004,
- R. Dahab, D. Hankerson, F. Hu, M. Long, J. López and A. Menezes,
Software Multiplication using Normal Bases,
Technical Report CACR 2004-12, University of Waterloo, Canada, 2004.
Page 103, Algorithm 3.40. Steps 3 and 4 appear to require two field
divisions. B. Poettering (on Sep 6, 2004) suggested the the following
organization to eliminate a divsion. Let X0/Z0 and X1/Z1 be the
x-coords of kP and (k+1)P, resp.
T = Z0*Z1
Z0 = Z0*x + X0
Z1 = Z1*x
X0 = X0*Z1
Z1 = (Z1 + X1)*Z0
Z0 = (x2 + y)*T + Z1
T = (T*x)-1
Z0 = Z0*T
X0 = X0*T
return (X0, y + (X0 + x)*Z0)
Page 285. Reference  appears in slightly abbreviated form in
IEEE Transactions on Computers 53(8):1047-1059, 2004.
Page 295. Reference  appears in Topics in Cryptology - CT-RSA 2004,
Lecture Notes in Computer Science 2964:366-386, 2004.
Guide to Elliptic Curve Cryptography /
Illustration by Helen D'Souza /
Last updated on March 3, 2005