Elliptic Curve Cryptography: The Basics

CS 463 Lecture, Dr. Lawlor

Why should you care about elliptic curve cryptography?

According to the NSA, elliptic curve crypto uses far fewer bits than RSA to provide the same level of security. Fewer bits means less network traffic and less computer time. As the general security level increases, the distance between them grows.
Quantum computers can solve factorization problems in polynomial time, but no algorithms are known for *some* elliptic curve problems. This makes some elliptic curve ciphers "quantum-resistant".

Elliptic Curves

An "elliptic curve" comes from setting a quadratic in y equal to a cubic in x. For example,

y^2 = x^3 - 3 x + b, where b is a large integer constant, was recommended for government use by NIST as "P-256".
y^2 = x^3 + 7, is used by BitCoin. It's from the "Standards for Efficient Cryptography (SEC)" group, named SECp256k1.

x and y are chosen from a field. Elliptic curves are actually not too interesting over real numbers, but they have really interesting and useful mathematical properties when x and y are restricted to integers, rational numbers, or finite fields.

For cryptography, the most popular definition is "elliptic curves over the rational field of modular integers": coordinates are of the form x=a/b where both a and b are integers modulo some big prime p. Some folks also use rational numbers over the Galois binary field like GF(2^m), but the prime fields are more common.

Defined over the reals, elliptic curves are smooth and differentiable; but in these integer fields, the cryptographically interesting curves are highly non-smooth, which makes interpolation difficult. In fact, the hard problem on elliptic curves is just division, which is confusingly called the "discrete logarithm problem" (by analog to the RSA version).

Mathematics of Elliptic Curve Addition and Multiplication

"Addition" on elliptic curves is defined in a very weird and interesting way. To add two curve points (x1,y1) and (x2,y2), we (1) draw a line between the two points, (2) intersect the line with the elliptic curve, and (3) mirror the intersection point about the x axis.

Why? Because this works out to give you outputs that are always on the curve, and this "addition" comes out associative and even commutative: "Elliptic curve points under 'addition' form an abelian group". Compare this with something simpler, like vector addition, where adding two curve points doesn't even keep you on the curve.

Addition Step 1: Draw a line

One equation for a line is:
y = m*x + v
(Note we're already using "b" above, so we switched to v for the constant.)

Step 1a: Draw a line between two points

The slope of the line is
m = dy/dx = (y1-y2)/(x1-x2)

Step 1b: Draw a tangent line at one point.

If you're adding a point to itself, you don't have two points to take a finite difference, so you take the infinitesimal slope dy/dx.

For the P-256 curve above, y^2 = x^3 - 3 x + b, the total derivative is:
2 y dy = 3 x^2 dx - 3 dx
Which rearranges to:
m = dy/dx = (3 x ^2 - 3) / (2 y)
The BitCoin secp256k1 is the same, without the "-3".

In either case, if we would divide by zero while calculating m, we instead give up and say the sum is a special point named "infinity".

We can use the slope to solve for the intercept:
v = y1-m*x
We now have the coefficients m and v for the line.

Addition Step 2: Intersect line and curve

We just need to find the point x,y that lies on both the line and the curve:
   y = m x + v   (on the line)
   y^2 = x^3 - 3 x + b    (on the NIST curve P-256)

Step one is to square the line equation:
   y^2 = (m x+v) = m^2 x^2 + 2 m v x + v^2
Since y^2 is also on the curve, we have:
   m^2 x^2 + 2 m v x + v^2 = x^3 - 3 x + b

Collecting terms onto the right side, we have:
0 = x^3 - m^2 x^2 - (3 + 2 m v) x + (b - v^2)

This is a cubic polynomial in x, and it's actually quite nasty to solve via the general cubic Cardano's method. But assuming there are exactly three solutions, you can always write the polynomial in this form, exposing the roots:
0 = (x - x1) * (x - x2) * (x - x3)
    = x^3 - (x1+x2+x3) x^2 + (x1 x2 + x2 x3 + x1 x3) x - x1 x2 x3

x1 and x2 are our input points, which are known. x3 is our output intersection point. Because these two polynomials are equal, by matching the coefficient on the x^2 term we have:
    x1+x2+x3 = m^2
so
    x3 = m^2 - x1 - x2
(Turns out this works fine for the Bitcoin curve too.)

Now that we have x3, we can calculate the y coordinate from the line equation:
    y3 = m x3 + v

Addition Step 3: Mirror the Intersection Point

To make the math work out, we need to flip the intersection point around the x axis. This is easy, just make the y coordinate negative:
y3 = - (m x3 + v)

That's it! We've now added (x1,y1) and (x2,y2) to give a new on-curve point (x3,y3). From this addition, you can build multiplication, preferably using something smart like the bitwise Peasant Multiplication. I use

C++ Implementation

First, you need a big integer class.

Now pull out each of the red equations from the pile of math above, and you can add elliptic curve points. There are several ways to handle the division step in calculating the slope:

Use a rational number class. This is what I did during lecture, and it works fine, but it's not that common for crypto.
Do the division by multiplying by the modular multiplicative inverse. This is slower than a rational number class, but at least there's a polynomial time algorithm for this (the Extended Euclidean Algorithm, 2000+ years old).

Here's some handwavy code (I found a bug in my big integer division, so the real version is coming later.)

typedef BigInteger ECcoord; // one X or Y coordinate

// One elliptic curve point, represented by 2D rational coordinates (x,y).
class ECpoint {
public:
   ECcoord x,y; // coordinates of point
   static ECpoint infinity; // the "point at infinity".

   // Add us to o, under the action of this curve.
   ECpoint add(const ECpoint &o,const ECcurve &curve) const {
       ECcoord m=(y-o.y) * (x-o.x).modInverse(curve.P); // ==(y-o.y)/(x-o.x), the slope of line (default case)

       if (x-o.x==0) { // special case for same X coordinate
            if (y-o.y==0) { // adding point to itself--take tangent
                m=curve.tangent(x,y);
            } else { // adding additive inverses--return "infinity"
                return infinity; // infinity = 1/0
            }
       }
       m=m.mod(p); // modular arithmetic, to speed things up here
       BigRat v = y-m*x; // line's y intercept

       BigRat x3 = (m*m - x - o.x).mod(p); // comes from matching x^2 terms
       BigRat y3 = (-(m*x3+v)).mod(p); // from line equation, plus mirroring

       return ECpoint(x3,y3);
   }

   ...
};

Full example coming soon here!