[chocolatebunny]

I always found Elliptic Curve Cryptography easier to understand than RSA. RSA just seems like a bunch of math I can't fully follow. But with ECC, you can see a curve and you can see how you're bouncing around the curve in a difficult to follow way. You can also see that calculating nG is just O(log n) but figuring out what n is from nG would take O(n).

[aerovistae]

Really?? How surprising, I always found it the opposite. Possibly because my math background is sufficiently underdeveloped that the method of addition for the two points on the curve seems absurdly arbitrary, as if someone made it up on the spot.

If you put 2 and 2 together, you get 4, a toddler can see that, but how on earth did anyone arrive at the conclusions that (-2.0, 1.4) + (1.9, 2.3) = (0.1, -1.9) via drawing a line, finding a third point, then reflecting across the X-axis? Makes no sense to me at all.

If you could explain that it'd be great. Likewise I'm sure you can ask almost anything about RSA here and myself or someone else has a decent chance of knowing the answer.

[agency]

The short answer is that this definition of addition is defined so that under this operation elliptic curves form a group[0]. There is a field of mathematics called abstract algebra concerned with algebraic structures like groups. I would attempt to motivate them this way: There are a lot of things in mathematics that seem to have a similar structure. You have a set of "things", and some operation that combines "things" and produces another "thing" of the same type. To be a group the elements of this set and the operation need to obey a couple of other constraints (an identity element exists, and elements have an inverse which when combined under this operation produce that identity element). Examples of groups are the integers under addition (identity = 0) and square matrices of a given rank under multiplication (identity = identity matrix).

Why bother with all of this? Since things with this structure abound in math, this turns out to be a useful abstraction. If you can prove some property of groups based only on this group structure, you have proved this proposition "for free" for any group.

Elliptic curves turn out to have a lot of interesting relationships with other fields of mathematics. For example, the proof of the famous Fermat's Last Theorem was actually a proof that FLT was equivalent to (or, implied by) a conjecture about a particular class of elliptic curves. This other conjecture had been proven about a decade prior so proving the connection proved FLT.

The connection to cryptography is less clear. I don't have a particularly good explanation for that except that cryptography is very interested in operations that are easy to perform but very difficult to reverse. As best as we can tell this group operation for elliptic curves over finite fields is _very_ difficult to reverse.

[0] https://en.wikipedia.org/wiki/Group_(mathematics)#Definition...

[tptacek]

To really sort of grok the context here, it's helpful to compare not RSA but "conventional" DH in Z/pZ --- so the fundamental key exchange algorithm is the same, and what you're doing is swapping in a different group.

Where this starts to get tricky is in understanding how dlog algorithms that are effective on multiplicative group Diffie Hellman --- notably index calculus --- are ineffective on elliptic curves.

We are way off the edge of my understanding of the theory here but the point I'd make is that the distinction between the two groups --- Z/pZ and a curve --- involves domain knowledge that you wouldn't get in a first course on abstract algebra.

[betterunix2]

Actually, index calculus attacks can be applied to certain elliptic curves; for example, supersingular curves. This is one of the reasons why we use standardized curve parameters that have been checked for known weaknesses.

There is also a really interesting class of curves for which the index calculus attack is exactly as hard the "direct" ECDLOG attacks (e.g. Pollard's rho). Those are the "pairing friendly" curves and there are a whole bunch of really interesting applications.

[betterunix2]

"If you put 2 and 2 together, you get 4, a toddler can see that, but how on earth did anyone arrive at the conclusions that (-2.0, 1.4) + (1.9, 2.3) = (0.1, -1.9) via drawing a line, finding a third point, then reflecting across the X-axis? Makes no sense to me at all."

Actually, that is the simplified version of the group law which is not what is actually "derived" in the theory. To derive the group law you work with rational functions defined on the elliptic curve (i.e. defined on the coordinates of points on the curve). The group itself is actually the "divisor class group" of the curve, which you can read about (but it is fairly advanced material).

[xyzzyz]

But RSA is exactly the same, really. Instead of point, you just have a number, and instead of adding it together n times, you raise it to n-th power modulo.

[betterunix2]

Except that things are not that simple; have you ever looked a Schoof's algorithm or pairings? Pairings are fascinating but visualizing what is happening is quite difficult IMO.