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
Pick a curve and starting point.
Pick a prime p and generator g
Local secret:
Pick a secret a
Local compute:
A = a * g
(Scalar multiply)
A = ga mod p
(Modular exponentiation)
Send A, receive B
After exchange:
S = b * A
S = Ab mod p

Why does it work?
a * (b * g) = b * (a * g)
ga*b = gb*a
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:
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.