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 efficient 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 modular integers": coordinates are of the form (x,y) where both x and y 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).

- Draw a line
between the two points.
*This makes our operation commutative.*

- Intersect the
line with the elliptic curve.
*This makes our operation's output be a curve point (closed).*

- Mirror the
intersection point about the x axis.
*This makes our operation an interesting group.*

The surprising operation here is the mirroring--if you leave out the mirroring, then if a+b=c, a+c=b, because a, b, and c are all co-linear. This is bad, because it means a=0, for any a!

With mirroring, "point addition" comes out associative (a+b)+c=a+(b+c) and even commutative a+b=b+a, giving us the statement "Elliptic curve points under curve point addition form an abelian group".

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 + a x + b, the total derivative is: 2 y dy = 3 x^2 dx + a dx Which rearranges to: m = dy/dx = (3 x ^2 + a) / (2 y) |

In either case, if we would divide by zero while calculating m, we instead give up and say the sum is a special "identity" point, also known as a "point at infinity", which plays the role of 0 (the additive identity).

We can use the slope to solve for the Y intercept:

v = y1 - m*x1

We now have the coefficients m and v for the line between the two points.

y = m x + v (on the line)

y^2 = x^3 + a x + b (on the curve)

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 + a x + b

Collecting terms onto the right side, we have:

0 = x^3 - m^2 x^2 + (a - 2 m v) x + (b - v^2)

This is a cubic polynomial in x, and it's actually fairly 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 these 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

Now that we have x3, we can calculate the y coordinate of the line-curve intersection from the line equation:

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

The bottom line to add points (x1,y1) to (x2,y2):

Different Pointsm = dy/dx = (y1-y2) / (x1-x2) |
Same Point (tangent)m = dy/dx = (3 x ^2 + a) / (2 y) |

x3 = m^2 - x1 - x2

y3 = - (m x3 + v)

From this point addition primitive operation, you can repeat it to build multiplication, preferably using something smart like the bitwise Peasant Multiplication to get decent performance for large numbers.

The beautiful part about elliptic curve point addition is it's commutative and associative. This means we can perform Diffie-Hellman key exchange, or any other crypto operation that relies on commutativity or associativity.

For performance, rather than doing division in the slope calculation at every step, high performance elliptic curve implementations use a three-coordinate Jacobian point representation (X,Y,Z), where x=X/Z

In the real plane, the set of elliptic curve points, and the
operation of addition, are both quite smooth. In a prime
field, both operations are very non-smooth. There's a decent
visualization
of this at linuxjournal, and a better
animation at arstechnica.

For example, here's the set of points where y^{2}=x^{3}
mod 509 (this is a curve where a=b=0)

I've shifted this so y=0 is in the middle of the image, which makes Y's positive-negative symmetry visible. x=0 on the left, and x=P-1 on the right. For each column, because y

On the very left, you can see the increasing values of the first few cubes, and then wraparound kicks in, resulting in basically gibberish for the remaining points.

To draw an image like this, I need to pick a "generator" point (Gx,Gy) that lies on the curve, and then start performing curve additions to walk around the curve. This code measures the period of each generator before it cycles back to the start.

/** Represent a general elliptic curve of this form: y^2 = x^3 + a x + b All arithmetic is modulo the prime P. */ template <class bigint> class elliptic_curve { public: bigint a,b; // curve coefficients bigint P; // prime bigint Gx,Gy; // generator (starting point) elliptic_curve(const bigint &a_,const bigint &b_,const bigint &P_) :a(a_%P_), b(b_%P_), P(P_), Gx(1), Gy(0) {} // Find generator point (Gx,Gy) bool find_generator(bigint startx=2) { // Build square root table mod P // (only works for small P) bigint sqrtModP[P]; for (int i=0;i<P;i++) sqrtModP[i]=-1; for (int i=0;i<P;i++) { long i2=(i*i)%P; sqrtModP[i2]=i; } // Find a "generator" or starting point on the curve: for (bigint x=startx;x<P;x++) { bigint y2=(((x*x%P)*x%P)+a*x+b)%P; bigint y=sqrtModP[y2]; if (y>1) { Gx=x; Gy=y; if (!point_on_curve(Gx,Gy)) std::cout<<"Fell off curve at generator "<<Gx<<", "<<Gy<<"\n"; return true; } } return false; // generator not found! } // Prime field division: return a/b mod P bigint divide(bigint a,bigint b) const { // Faster algorithm: extended euclidean algorithm bigint bi; // b's modular inverse for (bi=0;bi<P;bi++) if ((bi*b)%P==1) return (a*bi)%P; std::cerr<<"Division failure: "<<b<<" % "<<P<<"\n"; return -1; } // Line operation: void point_lineop(bigint &x,bigint &y,const bigint &x2, const bigint &num,bigint denom) const { denom=denom%P; if (denom==0) { x=P; return; } // identity case bigint m=divide(num%P, denom); // slope bigint v=(y+P-(m*x)%P)%P; x=((m*m)%P+(P-x)+(P-x2))%P; y=(P-(m*x)%P+P-v)%P; } // Elliptic curve point doubling void point_double(bigint &x,bigint &y) const { if (!point_on_curve(x,y)) std::cout<<"Fell off curve before doubling "<<x<<", "<<y<<"\n";

if (x==P) return; // doubling identity point_lineop(x,y,x, (3*x*x)%P + a, 2*y); if (!point_on_curve(x,y)) std::cout<<"Fell off curve after doubling "<<x<<", "<<y<<"\n"; } // Elliptic curve point addition void point_add(bigint &x,bigint &y, const bigint &x2,const bigint &y2) const { if (!point_on_curve(x,y)) std::cout<<"Fell off curve before adding "<<x<<", "<<y<<"\n";

if (x==P) { x=x2; y=y2; return; } // adding identity if (x2==P) { return; } // adding identity point_lineop(x,y,x2, y+P-y2, x+P-x2); if (!point_on_curve(x,y)) std::cout<<"Fell off curve after adding "<<x<<", "<<y<<"\n"; } // Verify this point lies on the curve bool point_on_curve(const bigint &x,const bigint &y) const { if (x==P) return true; // special identity point bigint y2x=(((x*x%P)*x%P)+a*x+b)%P; bigint y2a=(y*y)%P; return y2x==y2a; } }; void foo(long P) { // Initialize image to white unsigned char img[P][P]; for (int y=0;y<P;y++) for (int x=0;x<P;x++) img[y][x]=255; // white // Darken pixels sitting on the elliptic curve, // by repeatedly adding the generator. elliptic_curve<long> curve(read_input(),read_input(),P); while (curve.Gx<P/2) { if (!curve.find_generator(curve.Gx+1)) break; std::cout<<"Generator point: "<<curve.Gx<<", "<<curve.Gy<<": "; long x=curve.Gx, y=curve.Gy; curve.point_double(x,y); for (int i=0;i<10*P;i++) { // if (i<10) std::cout<<"Curve point: "<<x<<", "<<y<<"\n"; curve.point_add(x,y, curve.Gx,curve.Gy); if (x<P) { img[(y+P/2)%P][x]=0; // black pixel (y==0 in middle) } // Check wraparound if (x==curve.Gx) { // wraparound! std::cout<<"period "<<1+i<<"\n"; break; } } } // Write the image data: std::ofstream out("out.ppm",std::ios_base::binary); out<<"P5\n" <<P<<" "<<P<<"\n" <<"255\n"; for (int y=0;y<P;y++) for (int x=0;x<P;x++) out<<(unsigned char)img[y][x]; }

In practice,
it's much safer to start with a known good generator and curve,
which we'll start next week!