Elliptic curve cryptography

Elliptic curve cryptography (ECC) is an approach to public-key cryptography based on the mathematics of elliptic curves. The use of elliptic curves in cryptography was suggested independently by Neal Koblitz and Victor Miller in 1985.

The main benefit of ECC is that under certain situations it uses smaller keys than other methods — such as RSA — while providing an equivalent or higher level of security. Another benefit of ECC is that a bilinear map between groups can be defined, based on the Weil pairing or the Tate pairing; bilinear maps have recently found numerous applications in cryptography, for example identity-based encryption. One drawback, however, is that the implementation of encryption and decryption operations may take longer than in other schemes.

Contents

1 Key exchange 1.1 Galois field 2 Encryption 3 Recommendations 4 See also 5 References 6 External links

Key exchange

There are several slightly different versions of elliptic curve cryptography, all of which rely on the widely believed difficulty of solving the discrete logarithm problem for the group of an elliptic curve over some finite field.

Galois field

The most popular finite fields for this are the integers modulo a prime number (see modular arithmetic) GF(p), or a Galois field of characteristic two GF(2^m). Galois fields of size of power of some other prime have also been proposed, but are considered a bit dubious among cryptanalysts.

Given an elliptic curve E, and a field GF(q), we consider the abelian group of rational points E(q) of the form (x, y), where both x and y are in GF(q), and where the group operation "+" is defined on this curve as described in the article elliptic curve. We then define a second operation "*" | Z×E(q) → E(q): if P is some point in E(q), then we define 2*P = P + P, 3*P = 2*P + P = P + P + P, and so on. Note that given integers j and k, j*(k*P) = (j*k)*P = k*(j*P). The elliptic curve discrete logarithm problem (ECDLP) is then to determine the integer k, given points P and Q, and given that k*P = Q.

It is believed that the usual discrete logarithm problem over the multiplicative group of a finite field (DLP) and ECDLP are not equivalent problems; and that ECDLP is significantly more difficult than DLP.

In cryptographic use, a specific base point G is selected and published for use with the curve E(q). A private key k is selected as a random integer; and then the value P = k*G is published as the public key (note that the purported difficulty of ECDLP implies that k is hard to determine from P). If Alice and Bob have private keys k_A and k_B, and public keys P_A and P_B, then Alice can calculate k_A*P_B = (k_A*k_B)*G; and Bob can compute the same value as k_B*P_A = (k_B*k_A)*G.

This allows the establishment of a "secret" value that both Alice and Bob can easily compute, but which is difficult for any third party to derive. In addition, Bob does not gain any new knowledge about k_A during this transaction, so that Alice's private key remains private.

Encryption

The actual methods used to then encrypt messages between Alice and Bob based on this secret value are adaptations of older discrete logarithm cryptosystems originally described for use on other groups. These include:

• Diffie-Hellman — ECDH
• MQV — ECMQV,
• ElGamal discrete log cryptosystem — ECElGamal
• DSA — ECDSA.

Doing the group operations needed to run the system is slower for an ECC system than for a factorization system or modulo integer discrete log system of the same size. However, proponents of ECC systems believe that the ECDLP problem is significantly harder than the DLP or factorisation problems, and so equal security can be provided by much smaller key lengths using ECC, to the extent that it can actually be faster than, for instance, RSA. Published results to date tend to support this belief, but some experts are skeptical.

ECC is widely regarded as the strongest asymmetric algorithm at a given key length, so may become useful over links that have very tight bandwidth requirements.

Recommendations

NIST and ANSI X9 have set minimum keysize requirements of 1024 bits for RSA and DSA and 160 bits for ECC, corresponding to a symmetric block cipher key size of 80 bits. NIST has published a list of recommended elliptic curves for protection of 5 different symmetric keysizes (80, 112, 128, 192, 256). In general, ECC over a binary field requires an asymmetric key size of twice that of the corresponding symmetric key.

Certicom is the major commercial proponent of ECC, owning over 130 patents, and having licensed the technology to the National Security Agency (NSA) in a US$25 million deal. They have also sponsored several challenges to the ECC algorithm. The most complex to have been solved was a 109 bit key, which was broken by a team of researchers near the beginning of 2003. The team which broke the key used a massive parallel attack based on the birthday attack, using over 10,000 Pentium class PCs running continuously for over 540 days. The minimum recommended key size for ECC, 163 bits, is currently estimated to require 10⁸ times the computing resources as that required for the 109 bit problem.

On 16 February, 2005, the NSA announced that it had decided on a strategy of adopting elliptic curve cryptography as part of a US government standard in securing sensitive-but-unclassified information. The NSA are recommending a group of algorithms called Suite B, including Elliptic-Curve Menezes-Qu-Vanstone and Elliptic-Curve Diffie-Hellman for key agreement, and the Elliptic Curve Digital Signature Algorithm for digital signatures. The suite also includes AES and SHA.

See also

• Standards for Efficient Cryptography Group (SECG)

References

• Neal Koblitz, "Elliptic curve cryptosystems", Mathematics of Computation 48, 1987, pp203–209
• V. Miller, "Use of elliptic curves in cryptography", CRYPTO 85, 1985.
• Blake, Seroussi, Smart, "Elliptic Curves in Cryptography", Cambridge University Press, 1999
• Hankerson, Menezes, Vanstone, "Guide to Elliptic Curve Cryptography", Springer-Verlag, 2004
• L. Washington, "Elliptic Curves: Number Theory and Cryptography", Chapman & Hall/CRC, 2003

External links

• Recommended Elliptic Curves for Government Use, NIST document (PDF file) (http://csrc.nist.gov/CryptoToolkit/dss/ecdsa/NISTReCur.pdf)
• Certicom press release regarding 109 bit ECC challenge (http://www.certicom.com/index.php?action=company,press_archive&view=121)
• Certicom Online ECC Tutorial (http://www.certicom.com/index.php?action=ecc_tutorial,home)
• Digital Signature Standard; includes info on ECDSA (http://csrc.nist.gov/cryptval/dss.htm)
• See Wikisource:Cryptography (http://wikisource.org/wiki/Wikisource:Cryptography) for curve arithmetic routines and some test vectors for the NIST curves
• libecc: Open source ECC library (http://libecc.sourceforge.net/)
• Demo of elliptic curve point counting and domain parameter generation (http://www.cryptomathic.com/labs/ellipticcurvedemo.html)
• Primer on elliptical curve cryptography (http://linuxdevices.com/articles/AT7211498192.html)de:Elliptische-Kurven-Kryptosystem

ja:楕円曲線暗号 es:Criptografía_de_curva_elíptica