Elliptic Curve

Overview#

Elliptic Curve cryptography (ECC) is an approach to Public Key cryptography based on the algebraic structure of Elliptic Curves over finite fields.

One of the main benefits in comparison with non-ECC cryptography (with plain Galois fields as a basis) is the same level of security provided by keys of smaller size.

Elliptic Curve cryptography can be used for Key-Exchange, Asymmetric Key encryption, or for Digital Signature,, pseudorandom generators and other tasks.

Elliptic Curves are also used in several integer factorization algorithms that have applications in cryptography, such as Lenstra elliptic curve factorization.

Among widely implemented Public Key primitives, elliptic curves offer the best resistance to Cryptanalysis attacks on classical computers, and as a result can be used with smaller key sizes than RSA or finite field based discrete logarithm schemes.

From a high level, Crypto++ offers a numbers of schemes and algorithms which operate over Elliptic Curve.

Fields include both Fp and F2m, and schemes include:

What Is an Elliptic Curve?#

Elliptic Curves are a class of curves that satisfy certain mathematical criteria. Specifically, a planar curve is elliptic if it is smooth and takes the commonly used “Weierstrass form” of 
y2=x3+Ax+B
where 
4A3+27B2≠0
You’ll often see these curves depicted as planar slices of what might otherwise be a 3D plot.

Elliptic Curve and Trapdoor Function#

There does not appear to be a shortcut that is narrowing the gap in a Trapdoor Function based around Elliptic Curve. This means that for numbers of the same size, solving Elliptic Curve discrete logarithms is significantly harder than factoring. Since a more Computational Hardness Assumption means a stronger cryptographic system, it follows that Elliptic Curve cryptosystems are harder to break than RSA and Diffie-Hellman.

To visualize how much harder it is to break, Lenstra, Kleinjung and Thome introduced in 2013 the concept of "Global Security."; You can compute how much energy is needed to break a cryptographic algorithm, and compare that with how much water that energy could boil. This is a kind of cryptographic carbon footprint. By this measure, breaking a 228-bit RSA key requires less energy to than it takes to boil a teaspoon of water. Comparatively, breaking a 228-bit elliptic curve key requires enough energy to boil all the water on earth. For this level of security with RSA, you'd need a key with 2,380-bits.

Elliptic Curve Security Considerations#

There have been some questions and uncertainties that have held them back from being fully embraced by everyone in the industry.

The Dual Elliptic Curve Deterministic Random Bit Generator (Dual_EC_DRBG), a Pseudorandom number generator standardized by the National Institute of Standards and Technology (NIST) and promoted by the NSA which generates random-looking numbers using the mathematics of Elliptic Curves. There have been reports are that it could have been designed with a backdoor, meaning that the sequence of numbers returned could be fully predicted by someone with the right secret number.

There has been progress in developing curves with efficient arithmetic outside of NIST, including Curve25519 created by Daniel Bernstein (djb) and more recently computed curves by Paulo Baretto and collaborators.

Elliptic Curve and Intellectual Property (Patents)#

Another uncertainty about ECC is related to patents. There are over 130 patents that cover specific uses of elliptic curves owned by BlackBerry (through its 2009 acquisition of Certicom). Many of these patents were licensed for use by private organizations and even the NSA. This has given some developers pause over whether their implementations of ECC infringe upon this patent portfolio. In 2007, Certicom filed suit against Sony for some uses of Elliptic Curves, but that lawsuit was dismissed in 2009. There are now many implementations of ECC that are thought to not infringe upon these patents and are in wide use.

Elliptic Curve Random Number#

The ECDSA Digital Signature has a drawback compared to RSA in that it requires a good source of entropy. Without proper randomness, the Private Key could be revealed. A good source of random numbers is needed on the machine making the signatures. Dual_EC_DRBG is NOT RECOMMENDED.

More Information#

There might be more information for this subject on one of the following:

Please see our Copyright And Intellectual Property Page and Standard Disclaimer Pages!