Elliptic Curve Diffie-Hellman-Merkle key exchange

CS 463 Lecture, Dr. Lawlor

We covered the RSA-style Diffie-Hellman-Merkle before. The elliptic curve version just replaces exponentiation with multiplication. This works because division seems hard on elliptic curves.

	Elliptic Curve Style	RSA style
Startup:	Pick a curve and starting point.	Pick a prime p and generator g
Local secret:	Pick a secret a	same
Local compute:	A = a * g (Scalar multiply)	A = g^a mod p (Modular exponentiation)
Exchange:	Send A, receive B	same
After exchange:	S = b * A	S = A^b mod p
Why does it work?	a (b * g) = b * (a * g)*	g^ab = g^ba
Why is it secure?	Division on Elliptic Curve seems hard.	Discrete Logarithm problem seems hard.

I added this to "ecc_dh.cpp" in the bigint_OSL library: Zip, Tar-gzip. (License is BSD. Also includes all previous crypto examples.)

Where do you get a curve?

There are three popular published sources of elliptic curve coefficients:

NIST curves, like the NIST P-256 I use in my library, are common and documented well. Being from the US Government, not everybody trusts these implicitly.
Certicom publishes curves as "Security Group" or SECG. BitCoin used secp256k1. For the generator point,
the leading "04" means they're representing the generator point's X,Y parts explicitly. The compressed "02" form means storing only x; you compute Y.
A German group "ECC Brainpool" also publishes their own curves.

It's possible to generate your own curves, but there are several subtle pitfalls--curves that look and work OK, but are vulnerable to known attacks. Hence it's better to rely on official curves.