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

Elliptic Curves

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

Interactive Elliptic Curve Point Addition in the 2D Real Plane

Mathematics of Elliptic Curve Addition and Multiplication

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.
   

Addition Step 1: Draw a line between the two points

Addition Step 2: Intersect line and elliptic curve

Addition Step 3: Mirror the Intersection Point

Visualization

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

/**
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];
}

(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!