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".

- 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.

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

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).

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.

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
pointsThe 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.

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

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

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).

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!