Layman's Guide to Elliptic-Curve Digital Signatures (2014)
1–10 of 23 posts
Re: Layman's Guide to Elliptic-Curve Digital Signatures (2014)
#2Here 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 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.
Re: Layman's Guide to Elliptic-Curve Digital Signatures (2014)
#3I 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).
Re: Layman's Guide to Elliptic-Curve Digital Signatures (2014)
#4Great 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?
Re: Layman's Guide to Elliptic-Curve Digital Signatures (2014)
#5I 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 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.
Re: Layman's Guide to Elliptic-Curve Digital Signatures (2014)
#6Here 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?
Re: Layman's Guide to Elliptic-Curve Digital Signatures (2014)
#7Great 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…
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.
Re: Layman's Guide to Elliptic-Curve Digital Signatures (2014)
#8Great 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…
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.
Re: Layman's Guide to Elliptic-Curve Digital Signatures (2014)
#9Great 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…
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.
Re: Layman's Guide to Elliptic-Curve Digital Signatures (2014)
#10If the author bought bitcoin instead of writing that post, he would have made 35x his investment.