Layman's Guide to Elliptic-Curve Digital Signatures (2014)(royalfork.org)
royalfork.org
Layman's Guide to Elliptic-Curve Digital Signatures (2014)
https://www.royalfork.org/2014/09/04/ecc/
4 comments
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 :)
Total aside: when I was writing this, you answered a lot of my questions in #bitcoin. Thanks for helping me out :)
I'll describe the discrete logarithm problem; the elliptic curve discrete logarithm problem is like it, but harder (different group operation).
Pick a prime number p.
Pick a positive integer x < p
Then every positive integer < p can be written in the form: x^n (mod p), for some positive integer n < p.
For example if p is 5 and x is 2: 2^1 ≡ 2 (mod 5); 2^2 ≡ 4 (mod 5); 2^3 ≡ 3 (mod 5); 2^4 ≡ 1 (mod 5);
Try it with larger p or different x's and try to find a pattern. The discrete logarithm problem says: given c, x, and p, find y such that x^y ≡ c (mod p). In English, what power do I have to raise x to, in order to get a number that is equivalent to c, modulo p. The "modulo p" thing is what makes it hard - without that you just have x^y = c, so ln(x^y) = ln(c) and therefore y = ln(c)/ln(x)
Pick a prime number p.
Pick a positive integer x < p
Then every positive integer < p can be written in the form: x^n (mod p), for some positive integer n < p.
For example if p is 5 and x is 2: 2^1 ≡ 2 (mod 5); 2^2 ≡ 4 (mod 5); 2^3 ≡ 3 (mod 5); 2^4 ≡ 1 (mod 5);
Try it with larger p or different x's and try to find a pattern. The discrete logarithm problem says: given c, x, and p, find y such that x^y ≡ c (mod p). In English, what power do I have to raise x to, in order to get a number that is equivalent to c, modulo p. The "modulo p" thing is what makes it hard - without that you just have x^y = c, so ln(x^y) = ln(c) and therefore y = ln(c)/ln(x)
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?
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).
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).
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?
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?
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?
First off, I don't understand why anyone would want to talk about "curve sigs". Unless there's some fundamental new property being conveyed by the use of elliptic curves (e.g., pairing-based signatures) then you don't want to start with elliptic curves at all. All of these signatures were initially designed to work in (e.g., Schnorr-type) finite-field groups. The use of elliptic curves instead of FF is at most an efficiency/security optimization that you tack on to the existing algorithms. It's interesting -- and you can get lost in the details -- but it's not fundamental.
The three goals I would aim for are:
* Explain groups and group operations, exponentiation and DL * Describe the interactive Schnorr identification protocol and explain why/how it works * Show how this can be flattened into a (non-interactive) signature using a hash function, and why that works * (Optionally, show how [EC]DSA is just a bastardization of Schnorr/Elgamal) * (Optionally, describe the proof techniques and the Forking Lemma, but maybe nobody really cares.)
Then as icing on the cake you could explain how elliptic curve subgroups are instantiated, and why they represent an improvement over the Schnorr groups. But unless you're actually developing new EC software (and you probably shouldn't) that's more informational. Besides, there are a ton of tutorials on that out on the Internet, and not a lot of explanations that cover the operation and security of actual signature schemes.
The three goals I would aim for are:
* Explain groups and group operations, exponentiation and DL * Describe the interactive Schnorr identification protocol and explain why/how it works * Show how this can be flattened into a (non-interactive) signature using a hash function, and why that works * (Optionally, show how [EC]DSA is just a bastardization of Schnorr/Elgamal) * (Optionally, describe the proof techniques and the Forking Lemma, but maybe nobody really cares.)
Then as icing on the cake you could explain how elliptic curve subgroups are instantiated, and why they represent an improvement over the Schnorr groups. But unless you're actually developing new EC software (and you probably shouldn't) that's more informational. Besides, there are a ton of tutorials on that out on the Internet, and not a lot of explanations that cover the operation and security of actual signature schemes.
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 interactive example. Sure enough, doing so crashes the page.
Is there just, like, limitations to where you can place the points? As in, you can place them anywhere so long as you're not creating a vertical line?
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 interactive example. Sure enough, doing so crashes the page.
Is there just, like, limitations to where you can place the points? As in, you can place them anywhere so long as you're not creating a vertical line?
You are thinking in terms of affine coordinates i.e. (x,y) coordinates. The math is better explained (but not as easily to visualize) in projective coordinates. The conversions work as follows:
(x,y) --> (x : y : 1) (x : y : z) --> (x/z, y/z)
In that case, the "vertical line" will intersect the elliptic curve at (0 : 1 : 0), which is the identity element of the group.
Tangent lines are considered to intersect the curve "twice," (EDIT: "twice" at the point where the line is tangent and one more time at a third point) which is analogous to a polynomial equation having a double root. There is also a triple intersection case (EDIT: "triple" at a single point, all lines intersect the curve three times), which is possible at (0 : 1 : 0).
I'll leave it to the "reader" to work out the group law in projective coordinates based on the conversions given above. One neat trick: you can avoid inversions in the field by using projective coordinates and cleverly using the Z coordinate; this is a common optimization used in practice.
(x,y) --> (x : y : 1) (x : y : z) --> (x/z, y/z)
In that case, the "vertical line" will intersect the elliptic curve at (0 : 1 : 0), which is the identity element of the group.
Tangent lines are considered to intersect the curve "twice," (EDIT: "twice" at the point where the line is tangent and one more time at a third point) which is analogous to a polynomial equation having a double root. There is also a triple intersection case (EDIT: "triple" at a single point, all lines intersect the curve three times), which is possible at (0 : 1 : 0).
I'll leave it to the "reader" to work out the group law in projective coordinates based on the conversions given above. One neat trick: you can avoid inversions in the field by using projective coordinates and cleverly using the Z coordinate; this is a common optimization used in practice.
Any time the line is tangent to the curve, you treat that one point as a double intersection. You can show this by setting the line equation equal to the elliptic curve and solving for the x coordinates of the 3 intersections. The double intersection's x coordinate is a double root, just like x=0 in x^2 = 0.
A vertical line is perfectly valid (could be tangent or not), and in this case the "sum" is the "infinity point", which isn't any specific location in the grid but is a useful idea to make the math work. The infinity point is the additive identity: P + inf = P. For the amount of detail in this article, it should have mentioned this.
A vertical line is perfectly valid (could be tangent or not), and in this case the "sum" is the "infinity point", which isn't any specific location in the grid but is a useful idea to make the math work. The infinity point is the additive identity: P + inf = P. For the amount of detail in this article, it should have mentioned this.
I should really fix the browser crash, but I always thought it fitting that graphing infinity crashes the browser.
We should really work in the projective plane, so as to have a point “at infinity” which resolves this issue and serves as the identity element for the group.
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).
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.
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.
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...
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...
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.
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.
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.
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.
"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).
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).
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.
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.
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 except in a false-knowledge monkey-see-monkey-do sense without a substantial amount of number theory education that these sorts of tutorials never provide; and which aren't really that useful except for implementers (and if an implementer is learning it from one of these tutorials I fear for the security of the result).
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.