Public-key cryptography is useful because it allows the production of two related cryptographic keys; one which may remain private, while only the corresponding public key must be made known to another party. This increases the security of the private key since the private key may be used without sharing that key with any other party.

There are two main popular algorithms used in asymmetric (public key) cryptography:

* “RSA” (initials of its inventors Rivest, Shamir and Adelman )

* “EC”, or elliptic curve

The security of these algorithms depend upon two different specific mathematical things being “hard” to compute:

* RSA depends on it being computationally difficult to generate “prime

factors”

* EC depends on the hardness of solving the “discrete logarithm” problem over an “elliptic curve” (where a curve is the result of computing a function over a set of numbers called a “field”)

In practice, mathematical advances (number field sieve functions) have led to it becoming ever easier to factor prime numbers, lowering the computational cost. This has led to the need to continually increase the size of RSA keys in order to continue to make RSA cryptography hard to break. Increasing the size of keys, generally-speaking, will

decrease performance of a crypto-system.

Since EC cryptography does not depend on the difficulty of factorization, and also because it is much computationally harder to solve the elliptic curve discrete logarithm problem (ECDLP) with much smaller key sizes than are needed to provide equivalent security with

RSA, EC has recently become popular.

Some potential problems exist with EC-based systems:

* The security of EC-based systems does not depend solely on ECDLP. As EC has been little used or analyzed (relative to RSA), it is likely that there exist significant flaws in EC implementations (e.g. OpenSSL). It is not clear though whether these are of any more

consequence than previous non-EC-related flaws, such as the OpenSSL Heartbleed bug — so far, they have not been.

* In order to enable interoperability between implementations, standards exist for which curves should be used for EC cryptography. These standards have, so far, been published by NIST, a US government agency, currently in disrepute due the Snowden revelations. It is alleged that NSA representatives chose particular facets of the NIST standards in order to weaken crypto-systems using these curves. There is no actual evidence of this, although there is evidence, in the standards themselves, that the particular curves

chosen were chosen more for “efficiency” than “security”. Some reputable cryptographers (Lange, Bernstein) have provided plausible explanations for why _implementations_ of the NIST curves may be insecure. As of the writing of this document though, no known

practical attacks have been revealed.

* There have been few implementations of cryptography based on EC, and there appears little interoperability between implementations (except where they rely on the same library – ie. OpenSSL). Further, encryption using EC is poorly standardized (ECIES is the only “standard” I can find)

* The NIST-standardized DUAL_EC_DRBG random number generator, which is also based on hardness of ECDLP, has a significant documented weakness, which has led to the widespread belief that this RNG has been backdoored by NSA. It should be noted that just because this RNG uses the same mathematical properties as EC cryptography, this does not imply that there is necessarily any property which transfers to non-RNG uses of ECDLP.

Recommendations

————————-

* Do not use the DUAL_EC_DRBG random number generator in your own code, since it is proven insecure (ie. do not use OpenSSL FIPS module, BSAFE or the MSFT S-Connect libraries). It is also possible to use EC cryptography WITHOUT using the DUAL_EC_DRBG RNG., since DUAL_EC_DRBG is only one of the NIST-approved RNGs.

* TLS clients: do not negotiate TLS EC ciphersuites with SSL/TLS servers since you cannot be sure that the server is not using the DUAL_EC_DRBG? @@TODO: investigate this some more! Is DUAL_EC_DRBG an option for non-EC ciphersuites?

* If you wish to have interoperability with external partners, use the NIST-specified EC curves (FIPS 186-4), as implemented in OpenSSL and BouncyCastle; specifically the P-244 curve appears to be a reasonable choice for efficiency.

* If you control all parties in the crypto-system, you may use Bernstein’s p25519 curve, but will be on your own when it comes to implementing encryption, since there is no current standard for encryption that uses curves other than the NIST curves.

* Unless your threat model includes attack by state actors, it is probably safe to assume that you are currently safe from other attacks that rely on any fundamental weakness in EC cryptography, or particular curves. You are less safe from implementation flaws in

any library or code you are using, but this is a common problem in all use of cryptography, no matter how commonly used (see Heartbleed).

References

—————

“What a difference a prime makes” – https://www.imperialviolet.org/2010/12/21/eccspeed.html

“NIST FIPS 186-4″ – http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf

“Safe Curves” http://safecurves.cr.yp.to/

“Random Curves” – http://books.google.com/books?id=p2QalcsaNtIC&pg=PA312&lpg=PA312&dq=Jerry+Solinas+nsa&source=bl&ots=E0OF9z4lpJ&sig=V033idQQ4XafSzj70GvjPtcOpT8&hl=en&sa=X&ei=6c4RVM7WDqW1sQTwqYLwAg&ved=0CB0Q6AEwADgK#v=onepage&q=Jerry%20Solinas%20nsa&f=false

“Openssl ECIES example” – http://stackoverflow.com/questions/1152555/encrypting-decrypting-text-strings-using-openssl-ecc

“Google End-to-End” – https://code.google.com/p/end-to-end/

“OpenPGP ECC standard” – http://tools.ietf.org/html/rfc6637

“Dual EC in TLS” – https://projectbullrun.org/dual-ec/documents/dualectls-20140606.pdf