Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Layman's Guide to Elliptic-Curve Digital Signatures (2014)

royalfork.org

Post reply on HN
Print view View original

11–20 of 23 posts

Re: Layman's Guide to Elliptic-Curve Digital Signatures (2014)

#11

Post by betterunix2 »

chocolatebunny wrote: post #3

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 n G is just O(log n) but figuring out what n is from n G would take O(n).

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.

Re: Layman's Guide to Elliptic-Curve Digital Signatures (2014)

#12

Post by agency »

aerovistae wrote: post #5
chocolatebunny wrote: post #3

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 n G is just O(log n) but figuring out what n is from n G would take O(n).

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 drawin…

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...

Re: Layman's Guide to Elliptic-Curve Digital Signatures (2014)

#13

Post by xyzzyz »

chocolatebunny wrote: post #3

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 n G is just O(log n) but figuring out what n is from n G would take O(n).

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.

Re: Layman's Guide to Elliptic-Curve Digital Signatures (2014)

#14

Post by tptacek »

agency wrote: post #12
aerovistae wrote: post #5

Earlier quoted context omitted.

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 drawin…

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 "thin…

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.

Re: Layman's Guide to Elliptic-Curve Digital Signatures (2014)

#15

Post by tptacek »

apo wrote: post #6
nullc wrote: post #2

Here is a suggestion: If you're going to write yet another tutorial on elliptic curve digital signatures and you find yourself explaining the operation of the group law: you've probably messed up. ECDSA and friends work fine in an abstract group model. Virtually everything interesting about the signature algorithm is indifferent to the details of the group. Moreover, the group operator will remaining largely opaque e…

So I recommend: just present the idea of an abstract group and its relevant properties, then continue on with the high level algebra. For most people this would be a lot more informative. Are there any treatments like this that you'd recommend?

The best single-web-page treatment I've read is AGL's:

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

It describes the group mechanics but only briefly and then moves on to how, once you stipulate the group exists and has the operations you expect, you'd actually use it.

Another way to frame the critique above is: the tutorial here has pretty basic coverage of the group mechanics and almost no coverage at all of how signing schemes with curves work --- and curve signing is actually pretty interesting! So: you'd kind of want the tutorial to pick one of those things --- the fundamental mechanism of elliptic curves as an abstract algebra concept, or curve crypto signing --- and do a better job on just that thing.

For signing, the best I've read on a single page is DJB's:

https://blog.cr.yp.to/20140323-ecdsa.html

Someone could probably do some good fleshing out each of these sections for laypersons.

(I'm spitballing).

Re: Layman's Guide to Elliptic-Curve Digital Signatures (2014)

#16

Post by matthewdgreen »

tptacek wrote: post #15
apo wrote: post #6

Earlier quoted context omitted.

So I recommend: just present the idea of an abstract group and its relevant properties, then continue on with the high level algebra. For most people this would be a lot more informative. Are there any treatments like this that you'd recommend?

The best single-web-page treatment I've read is AGL's: https://www.imperialviolet.org/2010/12/04/ecc.html It describes the group mechanics but only briefly and then moves on to how, once you stipulate the group exists and has the operations you expect, you'd actually use it. Another way to frame the critique above is: the tutorial here has pretty basic coverage of the group mechanics and almost no coverage at all of…

Those are two very detailed explanations of how elliptic curves work, with a side helping of side-channel attack resistance just to make things more confusing for the beginner.

A better explanation to me would take you through the basic group theory, the overall design of a Schorr signature and then maybe a sketch of the security argument. Unfortunately doing that requires random oracles and so it’s messy. But what’s the point otherwise?

Re: Layman's Guide to Elliptic-Curve Digital Signatures (2014)

#17

Post by tptacek »

matthewdgreen wrote: post #16
tptacek wrote: post #15

Earlier quoted context omitted.

The best single-web-page treatment I've read is AGL's: https://www.imperialviolet.org/2010/12/04/ecc.html It describes the group mechanics but only briefly and then moves on to how, once you stipulate the group exists and has the operations you expect, you'd actually use it. Another way to frame the critique above is: the tutorial here has pretty basic coverage of the group mechanics and almost no coverage at all of…

Those are two very detailed explanations of how elliptic curves work, with a side helping of side-channel attack resistance just to make things more confusing for the beginner. A better explanation to me would take you through the basic group theory, the overall design of a Schorr signature and then maybe a sketch of the security argument. Unfortunately doing that requires random oracles and so it’s messy. But what’s…

What are three practical goals you'd want to achieve --- at a higher level than "demonstrating the design of a Schnorr signature" --- in a curve sig tutorial for beginners?

Re: Layman's Guide to Elliptic-Curve Digital Signatures (2014)

#18

Post by betterunix2 »

tptacek wrote: post #14
agency wrote: post #12

Earlier quoted context omitted.

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 "thin…

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 ar…

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.

Re: Layman's Guide to Elliptic-Curve Digital Signatures (2014)

#19

Post by royalfork »

nullc wrote: post #2

Here is a suggestion: If you're going to write yet another tutorial on elliptic curve digital signatures and you find yourself explaining the operation of the group law: you've probably messed up. ECDSA and friends work fine in an abstract group model. Virtually everything interesting about the signature algorithm is indifferent to the details of the group. Moreover, the group operator will remaining largely opaque e…

For RSA, most non-experts have an intuitive feel for why the cryptosystem is secure: we all know that factoring numbers is hard. Do you think it's possible to give a concise explanation for why ECC is secure aside from "hand wavey black box" + understandable algebra = security?

Total aside: when I was writing this, you answered a lot of my questions in #bitcoin. Thanks for helping me out :)

Re: Layman's Guide to Elliptic-Curve Digital Signatures (2014)

#20

Post by royalfork »

aerovistae wrote: post #4

Great guide but I run into a question almost immediately when it says "This line always intersects the elliptic curve at a 3rd point" and then subsequently "This line always intersects the elliptic curve at a 2nd point." Both of those statements seem false, since it's possible to pick points such that you get a vertical line near the left, like by putting the point on the X-axis (0 on the Y-Axis) in the second intera…

I should really fix the browser crash, but I always thought it fitting that graphing infinity crashes the browser.
Post reply on HN