Recently, there has been a lot of news about DUAL EC DRBG (Dual Elliptic Curve Deterministic Random Bit Generator) on of the supposedly cryptographically secure pseudo random number generators standardized by the NIST and promoted by the NSA. Many experts have questioned the security of DUAL_EC_DRBG especially after reports that NSA being aware of backdoors in the algorithm, may have paid the company RSA for making it the default in their crypto libraries. In this post we will not discuss about the DUAL_EC_DRBG but will try to provide an introduction of how Elliptic curve cryptography (ECC) works.
Elliptic curve cryptography (ECC) was discovered in 1985 independently by Victor Miller (IBM) and Neil Koblitz (University of Washington) as an alternative mechanism for implementing public-key cryptography. Different public-key cryptography algorithms are based on the intractability of certain mathematical problems. For example, RSA algorithm is based on the difficulty of factoring large integers composed of two(or more) large prime factors, while the security of DSA, El Gamal and Diffie Hellman algorithms relies on the fact that there are no efficient algorithms for computing discrete logarithm. Similarly, ECC is based on the difficultly of the “elliptic curve discrete logarithm problem” or ECDLP. So what is the ECDLP? Similar to other public-key cryptography algorithms, the idea is to find a function which is easy to compute in one direction using public information (the public key) but hard to solve in the other direction without a trap-door (the private key). In case of ECC, the function is the addition (and consequently multiplication) operation on points from a carefully chosen elliptic curve.
(Read More: Using 80/20 rule in Application Security Management)
For current cryptographic purposes, an elliptic curve is a plane curve which consists of the points satisfying the equation
Here is what an elliptic curve looks like:
ECC relies on point addition on an Elliptic curve. To add 2 points P & Q on the Elliptic curve, we need to trace a line between them and locate the other point on the curve that the line intersects. From this point, if we trace a vertical line (parallel to y-axis) we get our answer.
Point multiplication on an elliptic curve is nothing but repeated additions. This is precisely the function that ECC uses. It is easy to compute the point multiplication in an elliptic curve; however, it is very difficult to compute the multiplicand given the original and the final points. So in a way, to draw an analogy to the discrete logarithm problem, point addition on an Elliptic curve is analogous to modular multiplication while point multiplication is analogous to modular exponentiation.
One point to note is that for cryptographic purposes, not all elliptic curves are suitable. Ordinary elliptic curves may lead to very imprecise point additions due to floating point errors which slowly accumulate as you do more additions. Thus, ECC uses elliptic curves with 2 modifications. Firstly, the equation is
y2 ≡ x3 + ax + b (mod p) , which means y2 = x3 + ax + b + kp , where k can be any integer and p is some large prime number. Secondly, x and y must be integers so that they satisfy the equation, so that we can avoid rounding errors. These 2 modifications retain the difficulty of recovering the multiplicand given the original and the final points while making point multiplication easier and precise.
The elliptic curve is denoted by the sextuple (a, b, p, G, n, h) where a, b, are as mentioned above, G is a generator point (Gx,Gy) on the curve, n denotes the order of the ellipse and h is the co-factor of the curve.
The private key is any random number d
Public key consists the point Q such that Q = d * G
Free Research Report: How secure are the Security Products?
Let m be the message. From m, we calculate a point M on the elliptic curve. We also randomly select an integer k in the range 1 to p-1 and compute
C1 = k * G
C2 = M + k * Q
Thus the cipher-text consists of the points C1 and C2.
In order to get back the message, we compute:
M = C2 – d * C1
From M we can recover m.
The generation of domain parameters is not usually done by each participant since this involves counting the number of points on a curve which is time-consuming and troublesome to implement. As a result several standard bodies published domain parameters of elliptic curves for several common field sizes. Such domain parameters are commonly known as “standard curves” or “named curves”; a named curve can be referenced either by name or by the unique object identifier defined in the standard documents:
- NIST, Recommended Elliptic Curves for Government Use
- SECG, SEC 2: Recommended Elliptic Curve Domain Parameters
- ECC Brainpool, ECC Brainpool Standard Curves and Curve Generation
Largely, usable elliptic curves fall into two categories: “pseudorandom” curves and Koblitz curves. In case of pseudorandom curves, the parameters a and b are chosen by a specified algorithm (usually a hash) from a certain “seed”. For example, the NIST recommended Curve P-192 uses the 160-bit seed s = 3045ae6f c8422f64 ed579528 d38120ea e12196d5 as input to a SHA1 based algorithm to derive c = 3099d2bb bfcb2538 542dcd5f b078b6ef 5f3d6fe2 c745de65
From c, b is calculated such the b2c ≡ -27 (mod p)
a is chosen to be -3 for purposes of efficiency of computation
p is chosen to be 6277101735386680763835789423207666416083908700390324961279
In the light of recent news regarding US NSA’s interest in cryptographic libraries developed by RSA (the company), there are speculations that the NIST recommended seeds were somehow deliberately chosen in order to make the resulting curves weak in ways that only NSA knows.
The primary advantage of ECC over other schemes is a smaller key size thus reducing storage and transmission requirements. The security provided by a 256-bit ECC public key is comparable to that provided by a 3072-bit RSA public key