Shamus Software Limited

Elliptic Curves

MIRACL offers full support for Elliptic Curve Cryptography (ECC) over the prime field GF(p), and the field GF(2^m), including four programs for point-counting. For more information on ECC see "Elliptic Curves in Cryptogaphy", Blake, Seroussi & Smart, London Mathematical Society Lecture Notes Series 265, Cambridge University Press, ISBN 0 521 65374 6. This can be ordered directly from the publisher. Another good source of information is from the IEEE P1363 standards documents.

Elliptic Curves over GF(p) and GF(2^m) offer many advantages over standard methods such as RSA.

• An Elliptic Curve provides an ideal match for the AES (Advanced Encryption Standard) block encipherment (which is implemented within MIRACL). Using a 256 bit prime provides the same security as 128-bit AES. Similarly 384 bit ECC matches 192-bit AES, and 512 bit ECC matches 256-bit AES. Note that to offer the same level of security as 512-bit ECC would require the use of RSA with keys in excess of 10,000 bits.

• If using a general random prime p of no special form, the method is not patented (which perhaps explains why no big companies are pushing it!). For more information on ECC "patents" see http://cr.yp.to/nistp224/faq.html

• The performance cross-over with standard methods already occurs with 160 bit ECC vs 1024-bit RSA/El Gamal. For higher security, ECC is much faster.

• The only extra leap-of-faith required is that there exists no sub-exponential algorithm for solving the general discrete logarithm problem in ECC.

The first approach is to use the so-called Complex Multiplication method, described in Annex A of the P1363 standard. This is implemented by the free Windows '95/NT/XP command prompt utility cm.exe (and the latest version from V4.81 is up to 50 times faster!). However curves found in this way have a certain limited structure, and this is generally thought to be a bad thing. Better perhaps to generate a completely random curve and directly count the points on it. In that case you might consider schoof.exe which implements Schoof's Algorithm. In the book referenced above this is described as "far too inefficient", and "unacceptably slow". But with careful implementation, its really not too bad. The number of points on a 160-bit curve can be counted in under 15 minutes on a 180MHz Pentium Pro.

The best performance can be obtained from the Schoof-Elkies-Atkin algorithm. This is much faster. It is supported by the utilities mueller.exe, process.exe, modpol.exe and sea.exe. See the comments at the start of the source file sea.cpp for instructions for use and for benchmark timings. This method can be used to generate suitable 512-bit curves, which are well beyond the reach of the original Schoof algorithm. This can be done using relatively modest home computing facilities.

For GF(2^m) curves, use the utility schoof2.exe which implements the plain vanilla Schoof algorithm.

An alternative is to use "standard" curves generated by others, such as those suggested below. Standard curves are also published by the American NIST. MIRACL can now exploit the special simple form of moduli used by these curves (for example p=2¹⁹²-2⁶⁴-1) for even greater speed.

The full source code for all four methods can be found in the MIRACL library, from where they can be re-compiled for other platforms. MIRACL includes full source code for a fast software implementation of the the ECDSA Elliptic Curve analogue of the Digital Signature Standard.