Elliptic Curve Cryptography for Beginners 328 points by deafcalculus on Oct 11, 2017 | hide | past | favorite | 30 comments

 So far, the best single-page elliptic curve primer for generalist programmers I know of is Adam Langley's:https://www.imperialviolet.org/2010/12/04/ecc.htmlI understand the urge to try to get a high-level grok of curves without much math, but I spent years bouncing off the outermost surface of curve understanding by trying to start with the curve picture and the intuitive geometry of curve shape, and what finally made curves click for me (and quickly) was to simply take the curve equation --- which is itself high school math! --- and play with it a bit.So if you're a programmer and you want a baseline understanding how curves work, do what you'd do with any other subject you're trying to understand: pop open an editor, take the Weierstrass curve equation, pick a y, solve for x; then do it in a finite field (ie, mod a prime). Then write an "add", then a "scalar mult". It's a couple hours of noodling, tops.As always, but particularly with curves, remember that the basic understanding of what's going on is nowhere nearly enough to ever use them safely!
 Honestly, I'm not sure you want to get me started here.Believe it or not, libsodium's implementation of Argon2 is an example of libsodium going off the rails. Libsodium began as a cross-platform easy-to-build repackaging of Nacl, a crypto library designed and written by cryptographers with carefully chosen primitives. Libsodium has gradually expanded it into a kitchen sink of shiny cryptography, and as a result now libsodium users have to worry about the pitfalls of AES-GCM. Why does libsodium implement Argon2? Hell if I know. As an interface, it's actually worse than JCE, which at least had the self-respect to pretend it had a "password based encryption" abstraction.It gets worse though, if you really want to climb down this rabbit hole with me, because I'm not totally sure why Argon2 exists either. The "bug" he found in Argon2 has actually no practical impact, so much so that the reference implementation decided not to bother fixing it. But that's because very little in password hashes actually matter. Scrypt was the last important thing to happen to password hashes, and bcrypt still works just fine.If we want to keep touring all the weird shit that happens because people pointlessly reimplement things many of which don't need to exist in the first place, we can keep doing it all the way back to unpadded RSA-512 off a broken browser RNG, which (a) existed and (b) got me gameover on a pentest once. Maybe I should be happy about that, but I mostly find it frustrating.My point here, though, is that you aren't going to learn nearly enough from a tutorial of any sort to safely implement curves.
 > the pitfalls of AES-GCMCan you elaborate a little on this? I ask because Noise protocol standardizes on AES-GCM or ChaChaPoly, will apps using Noise with AES-GCM face "pitfalls"?
 I found this discussion which is perhaps germane, about sensitivity to nonce repetition: https://www.imperialviolet.org/2017/05/14/aesgcmsiv.html
 This is pretty good! The arithmetic of elliptic curves gets very complex, but I like how you arrived at points on an elliptic curve just by defining groups and fields. It might be a slight improvement to give a short, Rudin-style explanation of the difference between a set and a field. You could do this from first principles of set theory without being so terse as to be incomprehensible or diving into the axioms; I think the stated goal of little math is fine for the audience, but at the same time such an audience might not immediately understand what “field = set with addition and multiplication defined on it” means. I think a small expansion of the treatment on why the ECDLP is hard would also be good. It's intuitively easy to follow that hard problems can exist, but maybe continue on in showing why this particular hardness assumption works for cryptography (because there are many that do not).Places to go from here if you enjoyed reading this and want to learn more about elliptic curves and cryptography related to them:More on an elliptic curve and constructing a hypothetical one.Elliptic curve pairings.An intro to supersingular isogeny cryptography, which has a basis in elliptic curves as a mathematical structure, but is fundamentally different from elliptic curve cryptography.
 If you want to see a "from scratch" implementation using existing algorithms, here's short working snippet of elliptic curve cryptography (specifically Bitcoin's) without 3rd party libraries:https://github.com/wyc/haschain/blob/master/Secp256K1.hsThe implementation doesn't concern itself with groups or fields, but they're still very useful to make sense of the code at all. Actually, I should add some types and implement an instance of Data.Group when I have more time.Of course, it's for fun and not production use. I didn't give the slightest thought to timing attacks, optimized performance, etc.
 As nice as it is, integers are not a field (i.e. most of them don't have multiplicative inverses, or 1/n usually isn't integral).Another good writeup: http://andrea.corbellini.name/2015/05/17/elliptic-curve-cryp...
 Came here to see if anyone noticed this. You can actually make a field of Z using a bijection to the rationals Q, which do exist. But then you aren't using the standard operations, but using the ones inherited from the particular mapping to Q.
 True, perhaps the author meant rationals.
 It's usually integers modulo p (p prime), which is a field.Edit: but yes, the OP writes "integers (Z) are a field", which is wrong. Integers form a ring.
 I think integers mod p (p prime) is a field
 more in depth and just as gentle: https://jeremykun.com/2014/02/08/introducing-elliptic-curves...
 In case anyone here is interested in Cryptography as it pertains to Cryptocurrency specifically, here's a talk I gave recently that might be interesting to you: https://www.youtube.com/watch?v=Fyqtl7eGQZY&t=1062s
 here are some videos from dan boneh on cryptography, https://www.youtube.com/playlist?list=PL9oqNDMzcMClAPkwrn5dm...
 In the image for A+A=C (multiply by 2) I see the intersection point C, but what if you wanted to multiply by 3? That would be A+C=D and I don't see any point on the curve that the line through A and C intersects. In fact it looks like for any A you choose, adding A+A gives a C which has that property (in other words A*3=0 for any A). This is just by visual inspection. What am I missing?
 Seems to have labelled "C" and "-C" in a very misleading manner. Take point A. Draw a tangent, that cuts the curve at point C. That's not the point 2A. That's the point C.Reflect C across the X axis, and that's point 2A.So you're not missing anything, the article is misleading at best.In short, to take the sum of two points A and B, draw a line through them both to find a third point on the curve, reflect that point across the X-axis, and the result (which will also be on the curve) is A+B.If A and B coincide then use the tangent at A.The point at (vertical) infinity plays the role of the zero.
 Ohh OK! Thank you. Makes more sense now.
 The article gives a nice intuition about how encryption works using elliptic curves without going too deep into the math.I'm curious for a similar explanation for how decryption would work though; a trapdoor function is nice and all, but it's only half of the story if there is no 'way out'.
 As far as I can see there's no mention to encryption, the OP describes how scalar multiplication works on elliptic curves.To encrypt/decrypt, for example, you can use the ElGamal scheme: https://en.wikipedia.org/wiki/ElGamal_encryption (note that wikipedia uses the multiplicative notation, while in ECC typically additive notation is preferred, so you'll have to translate every A^x into xA -- but it's a good exercise.)
 This is a great response! But I think the person you replied to understands all this, and is wondering about the exact method (or a layman's explanation) of the same process in terms of elliptic curve crypto rather than the traditional RSA (I'm wondering the same thing).
 I always get a bit annoyed when someone tries to explain ECC with an image of an elliptic curve over the reals. The whole point of ECs over finite fields in cryptography is that they don't have any regular structure like that!
 What do you mean? Elliptic curves over finite fields have tons of structure themselves, and to my knowledge, the discrete logarithm problem for ECs over reals is just as hard as for finite fields.
 I'm afraid I don't have a neat answer to why your first question. I did find the Koblitz paper I meant earlier but it's more about why one particular attack won't work: https://link.springer.com/article/10.1007/s001459900040There are other reasons beyond efficiency why I would prefer people to switch their DLOG crypto to EC in practice: it's hard enough to implement - even with introductory blog posts with images - that your average developer leaves the details to an expert. libsodium for example is very well designed and written and few people think "I know, I'll write my own Curve25519 implementation" but lots of people seem to think that they understand finite fields well enough to build crypto, after all they have a bignum library and a modexp function, what could possibly go wrong?. I've seen finite-field discrete log software that is supposed to be production ready with the following problems:`````` * Non-constant time implementation of "schoolbook" square-and-multiply. * Forgetting to check if points really are in the group, e.g. you're supposed to be working in a q-order subgroup of Z^*_p where q | (p-1)/2 but the software accepts any integer less than p as a group element. * Crash or infinite loop if you pass 0 as a "group element". * Parameters can be specified or overridden by the sender of a message and set to tiny values. * Not checking whether the modulus is prime.``````