A relatively easy to understand primer on elliptic curve cryptography (2013)

This is pretty good. You can probably skip to the "Strange Symmetry" section and read from there.

Learning about elliptic curves made a lot of abstract algebra click for me, in ways it hadn't when I was just working with multiplicative groups for RSA and the like. That in turn made a lot of linear algebra make sense for me.

The right place to start with elliptic curves with with standard Diffie Hellman, which you can nail down in 10 minutes with in a Ruby or Python REPL. The first part of this old blog post has a step-by-step:

http://www.securityfocus.com/blogs/267

When you get a feel for how DH works with simple multiplicative groups, to get to elliptic curve, you can just sort of abstract DH out from "numbers modulo a prime" to "things that behave like numbers modulo a prime". Think of both residues mod-p and points on a elliptic curve mod-p as subclasses of a parent class with an abstract method like "multiply". As long as you have an object with a compatible interface, you can theoretically do DH on it (though not necessarily securely).

So for ECDH, instead of raising a generator number to a secret power and sharing the residue, we multiply an pre-agreed, standardized curve point by a secret scalar number and share the resulting point.

Another thing I found relieving when I was first learning ECC was to be reminded that most implementors don't write ECC point multiplication from first principles. There are cheat sheets, like the Explicit Formulas Database, where people have already worked out the fastest way to perform basic operations on curves:

https://hyperelliptic.org/EFD/

For instance, here's the addition and doubling formulas for points on Montgomery curves:

https://hyperelliptic.org/EFD/g1p/auto-montgom.html

The reason ECC keys are shorter than RSA and DH keys is that there are techniques, most notably index calculus, that can solve problems on simple finite field multiplicative groups but can't effectively solve them with curve points.† That's why we use elliptic curves, of all things, in cryptography: they're a mathematical object that be coaxed into behaving like simple multiplicative groups, for the purposes of Diffie Hellman and Schnorr signatures, that resist a set of mathematical techniques that are driving key sizes for RSA and DSA up.

Adam Langley wrote my favorite intro to curves, here:

https://www.imperialviolet.org/2010/12/04/ecc.html

There's a little bit of material that you might want to pull from Nick Sullivan's post into this, to have the best possible curve explanation. Both things are worth reading.

† There are also tricky attacks against some curve structures that attempt to reframe problems against the underlying finite field of the curve.

So wait, how does a point dot with itself? I get it for two points, but how can a public point dot with itself to form a line? That doesn't make sense to me.

oldy, but a goody!