Total aside: when I was writing this, you answered a lot of my questions in #bitcoin. Thanks for helping me out :)
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)
Are there any treatments like this that you'd recommend?
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).
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?
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.
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.