Layman's Guide to Elliptic-Curve Digital Signatures (2014) • Hacker News Board

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

#21

Post by betterunix2 » Fri, Dec 15, 2017, 5:16 AM UTC

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…

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

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

#22

Post by defen » Fri, Dec 15, 2017, 5:36 AM UTC

royalfork wrote: post #19

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 :)

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 Then every positive integer 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)

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

#23

Post by matthewdgreen » Fri, Dec 15, 2017, 1:21 PM UTC

tptacek wrote: post #17

matthewdgreen wrote: post #16

Earlier quoted context omitted.

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?

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.