[matthewdgreen]

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?

[tptacek]

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?

[matthewdgreen]

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.