Elliptic Curve Cryptography
The Mathematics of Elliptic Curve Cryptography
Elliptic Curve Cryptography has a reputation for being complex and highly technical. This isn't surprising when the Wikipedia article introduces an elliptic curve as "a smooth, projective algebraic curve of genus one". Elliptic curves also show up in the proof of Fermat's last theorem and the Birch and Swinnerton-Dyer conjecture. You can win a million dollars if you solve that problem.
To get a basic understanding of ECC, you need to understand four things:
The definition of an elliptic curve.
The elliptic curve group.
Scalar multiplication over the elliptic curve group.
Finite field arithmetic.
Essentially, elliptic curves are points on that satisfy an equation with the form:
y2 = x3 + ax + b
Figure 1 shows a picture of an elliptic curve over the real numbers where a is –1 and b is 1. Elliptic curves satisfy some interesting mathematical properties. The curve is symmetric around the x axis, so that if (x,y) is a point on the curve, then (x,–y) is also on the curve. If you draw a line between any two points on the line with different x coordinates, they will intersect the line at a unique third point. Finally, for each point on the curve, if you draw a straight line tangent to the cover from that point, it will intersect the curve once again at another point.
Figure 1. Elliptic Curve over Real Numbers
Mathematicians use these properties to form a structure called a group from the points on the elliptic curve. A group consists of a set of elements containing a special point (denoted 0), an operation for negating an element (denoted –x), and an operation for adding two elements (denoted x + y). The elements in the group defined by an elliptic curve consist of the points on the curve plus an additional point for 0 that is not on the curve, but as you'll see below is easiest to visualize as a line on the x-axis. To negate a point, you just negate the y-coordinate of the point, and adding a point to its negation is defined to return 0 (Figure 2). To add two points P and Q with different x-coordinates, draw a line connecting the two points and extending beyond them. This line should intersect the curve at a third point. The sum R = P + Q is the negation of the third point. Finally, to add a point P to itself, draw the line tangent to P (Figure 3). The sum R = 2P is the negation of the point that line intersects (Figure 4).
Figure 2. Negating a Point
Figure 3. Adding Two Points
Figure 4. Doubling a Point
Once the group is defined, we can talk about scalar multiplication—the fundamental operation that makes elliptic curves useful in cryptography. The kth scalar multiple of P is the point obtained by adding P to itself k times. This can be done efficiently by representing k as a binary number and using a double-and-add multiplication method. If you are familiar with RSA, scalar multiplication plays a similar role in ECC that modular exponentiation plays in RSA.
The real numbers used in diagrams for explaining ECC are not practical to use in actual implementations. Real numbers can have an arbitrary number of digits, and computers have only a finite amount of memory. Most applications, including OpenSSL, use elliptic curves over coordinates that use modular arithmetic, where the modulus is a large prime number. Figure 5 shows the elliptic curve with the same equation as in Figure 1, but where arithmetic is performed modulo 19.
Figure 5. Elliptic Curve over Prime Field (mod 19)
For the different key sizes in Table 1, NIST recommends a specific elliptic curve with a prime modulus for that key size (see the Binary Fields sidebar). For each key size, NIST specifies three things:
The coefficients in the elliptic curve equation.
The size of the underlying field for representing x and y.
A base point that is a point of the curve to be used when calling scalar multiplication.
Joe Hendrix is a security researcher who works in Portland, Oregon, for Galois, Inc. His main interest is in applying formal verification techniques to real security problems.