C[omp]ute

From: andrew cooke <andrew@...>

Date: Sat, 12 Oct 2013 04:51:06 -0300

This is a simple intro to Elliptic Curve Crypto (or, at least, my current
understanding of it).


Let's start with DH key exchange and the discrete logarithm problem (DLP).

Alice and Bob want to generate a shared secret in public view.  They choose a
small number x and a big number N.  Then Alice chooses a random value a, while
Bob chooses a random value b.

Alice sends Bob x^a % N and Bob sends Alice x^b % N.  Note that it's hard to
go from x^y % N back to y (this is the DLP).  Think of things spinning round
lots of times.  But it's easy to calculate x^y % N using double and add.  So
this is a kind of one-way function.

Now Alice and Bob can both calculate x^ab % N, but no-one else can (for
example, in Alice's case, she knows a and received x^b).  So they have a
shared secret.

So we have a cute trick that gets shared secrets from the DLP.


Now ECC is simply a different way of doing the maths.  You can do the maths
above on anything where you can define both addition and multiplication (so
that you can double and add).

And it turns out that if you have a "curve" that's a kind of circular blob
next to a vertical wiggly line, you can define both of those in terms of
joining points with a straight line (that's addition).  For example, any two
points on the circular blob can be jined by a straight line that eventually
cuts the vertical wiggle.  So those two points add (more or less) to the point
on the wiggle.

So the maths is an interated jumping around from point to point on this
curve.  And once you get to some point (equivalent to raising the starting
point to some power) it's hard to work ut where you started.  The DLP.

Then you can use that to do things like DH key exchange.

Andrew