Elliptic Curve Cryptography

CS 463/480 Lecture, Dr. Lawlor

Why should you care about elliptic curve cryptography?

Elliptic Curves

An "elliptic curve" comes from setting a quadratic in y equal to a cubic in x.  For example, 
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 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(2m), but most of the fast operations are patented, so 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).

Interactive Elliptic Curve Point Addition in the 2D Real Plane

Interactive elliptic curve calculator built in Desmos graphing tool.

Mathematics of Elliptic Curve Addition and Multiplication

"Curve point 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.  This makes our operation commutative.
  2. Intersect the line with the elliptic curve.  This makes our operation's output be a curve point (closed).
  3. Mirror the intersection point about the x axis.  This makes our operation an interesting group.
Why?  Step 2 is there so you get outputs that are always on the curve.  Compare this with something simpler, like vector addition, where adding two curve points doesn't even keep you on the curve.

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

Addition Step 1: Draw a line between the two points

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

Addition Step 2: Intersect line and elliptic 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 + 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
    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

Addition Step 3: Mirror the Intersection Point

To make the operation work correctly, we need to flip this 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). 

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

Different Points
   m = dy/dx = (y1-y2) / (x1-x2)
Same Point (tangent)
   m = dy/dx = (3 x ^2 + a) / (2 y)
   v = y1 - m*x1
    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/Z2 and y=Y/Z3.  This produces a point addition function with several more multiplications, but no divisions until you extract the final x,y.


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 y2=x3 mod 509 (this is a curve where a=b=0)

Rational points on elliptic curve y^2 = x^3 mod 509
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 y2=x3 there are at most two possible y values.  Because not every x3 is a perfect square, some columns have no valid y values.

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 {
	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;
		// 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
		if (denom==0) { x=P; return; } // identity case
		bigint m=divide(num%P, denom); // slope
		bigint v=(y+P-(m*x)%P)%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]; }

(Try this in NetRun now!)

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