Elliptic Curve Cryptography Explained
fangpenlin.com
fangpenlin.com
* Choose an Elliptic Curve (EC) and a large prime;
* The rational points on the EC modulo the prime give you a group;
* Your private key is a large integer N;
* Perform Diffie-Hellman-Merkle-Williamson (DHMW) in the group;
* You now have a shared point in the EC;
* Use a symmetric cipher using the shared point as the key.
Performing DHMW goes as follows:
* A and B agree on a point P in the EC;
* A and B each choose a large number as their secret key;
* For simplicity, or confusion, we'll say that X's secret key is X;
* They compute AP and BP as their public keys and exchange them;
* When A receives BP they compute A(BP), B does likewise;
* Now they share a point: (AB)P.
If you have the language of groups, and understand DHMW in that context, ECDHMW is trivial, as is (this version of) EC PK-Cryptography.
TL;DR : ECC is simply Symmetric Cryptography using a key that's been agreed by using DHMW in an Elliptic Curve group.
Diffie and Helman felt that the entire scheme was based on work that Ralph Merkle did (same guy as Merkle Trees), and so should be included in the scheme name, and I think that Williamson refers to Malcolm J. Williamson, a GHCQ employee, who had secretly developed the same system 7 years before Diffie and Helman. What I don't know is why Williamson and not Cocks and Ellis are part of the acronym.
I did give the full version before the acronym on the fifth line of my comment, so if people are confused it might be why I'm referring to DHMW and not just DH. Reading up about it all it's pretty clear that Merkle and Williamson should get more credit than they do.
There are exercises that can help you learn it from scratch.
There are elements that seem particularly interesting to me around this, especially since even elliptic curves with no rational points on them still have points in finite fields, and how to think about what it means for points to be on a line, and derive things like point addition and point doubling from that perspective.
I'm familiar enough with EC math to hand wave around these issues, but it's still something that I struggle with.
That’s interesting. How is that possible?
[1] https://kconrad.math.uconn.edu/blurbs/gradnumthy/mordelleqn1...
[0]: https://andrea.corbellini.name/2015/05/17/elliptic-curve-cry...
Another, slightly more topical / simple explanation [0] was posted by Cloudflare almost exactly 6 years ago, I still point people to it as well.
[0] https://blog.cloudflare.com/a-relatively-easy-to-understand-...
My understanding is that end-users of ECC have to decide which curves to use, and constructing a curve de-novo isn't a choice laymen or crypto end-users should ever make, so a set of standardized curves are issued by standards bodies, such as NIST.
Cryptographers endorse the math of ECC as not known to be decipherable, provided that the chosen curve (defined eg by 4 points) isn't specifically constructed to be easily compromised; and the problem becomes whether the curve-issuing standards bodies, such as NIST, are acting in the interests of state security agencies (for argument's sake, lets say NSA) who have vested interests in crypto users adopting curves that NSA can break.
Could an international, decentralized curve be constructed by standards bodies from several geopolitical adversaries such as US, China, Russia and Turkey all simultaneously issuing 1 point each to create a combined 4-point curve, so that no single standards body has opportunity to purposely make the result insecure?
The process would be a little more complicated than simply choosing 4 points, but yes you could do something close enough to this in theory.
In actual practice there's really only two sets of curves most people [0] implement, and just about everyone agrees to use:
- The NIST p curves
- Curve25519/Curve448 by Bernstein &c.
Which you use tends to fall on what side of the crypto divide you fall on:
- NIST p curves if you care about governmental compliance such as FIPS
- Bernstein &c's curves if you care about security and distrust NIST created curves.
I personally fall on the latter side but spend most of my time doing software for the former. :) A promised later revision to FIPS will standardize Bernstein &c's curves.
Almost nobody implements negotiating arbitrary curves. That's really unsafe.
So, as 'tptacek would say... just use Curve25519.
[0]: I'm talking about major software such as TLS, VPNs, SSH, Kerberos... etc.
This is one of the reasons more paranoid people have generally preferred Curve25519 over the NIST curves -- the NIST curves have very arbitrary base point values which (in theory) could have been backdoored. NIST later published a proof that if you hashed some other arbitrary values, you get the base points -- but then the follow up question is where did the other arbitrary values come from.
Marketing bullet points aren't a replacement for careful cryptographic review.
That's the case I know of.
Basically you mathematically design a curve that makes it look like it's random numbers but the numbers aren't actually random.
Ed25519 specifically has major contributions from 5 different people from multiple nationalities.
It's not quite the decentralized ideal you talk about, but it's somewhat close!
However ultimately a different approach was chosen that solves the same problem: You don't choose an arbitrary curve, instead you define a set of properties that you want your curve to have, based on security, speed and ease of implementation. Then you end up picking the very first curve that fulfils that property.
That's how Curve25519 was created. There's very little wiggle room in there.
Also it should be said that the hypothesies of choosing a "bad" curve that noone can spot are very hypothetical. We know these NIST curves have an unexplained random seed, but noone has an idea how this could've been used for a backdoor.
I find RSA really simple to understand, but ECC has always seemed a lot harded to grok - I think I finally get it!
I think it's a lot more useful to start from a generic group: e.g. you have some group G generated by g, and a group operator ... plus a way to (de)serialize members, a method to identify the additive identity, maybe a hash function and not much else.
From that point you can build a pretty solid understanding of real cryptosystems.
Knowledge of how to implement a particular group law is necessary to build one from scratch-- which people should almost never be doing, esp as it requires a serious amount of number theory to do well-- but it doesn't give any real insight into the cryptography, not even any intuition as to why the DL problem in some groups is believed to be hard.
I think that understanding ECC starting at group law is kind of like understanding quick sort by studying CMOS logic: you can't implement quicksort in practice without (someone) building some digital logic, but if you're down in the trees it's not particularly easy to see the forest.
When I've trained people on the subject I've enjoyed using a sequence that goes like:
1. Generic group, how we can construct efficient 'multiplication' from only addition (I prefer to call the group operator addition, but I talk about both notations and how both are equally valid). General intuition about how algebra essentially JustWorks(tm) in finite fields.
2. CDH and Diffe-hellman, the fact that the hardness of the DL problem (in particular groups) is a strong assumption.
3. Constructing a pedersen commitment using the additive homomorphism 'in the exponent', establishing the security assumption in pedersen commitments that the two generators have an unknown DL between them.
4. Constructing a chameleon hash function-- a trap-door hash function where someone knowing a secret can freely construct collisions at will-- by violating the pedersen security assumption.
5. Constructing a schnorr digital signature by feeding the output of a chameleon hash back into itself, creating an impossible causal loop that can only be resolved using the trapdoor.
6. Extending the causal loop: creating an OR proof (A signature that shows I know at least one of two secrets).
[FWIW, we cover 4,5,6 in this paper https://pdfs.semanticscholar.org/4160/470c7f6cf05ffc81a98e8f... for the purpose of describing a more efficient than typical OR proof.]
7. From there extending into other more elaborate protocols like range proofs (built from OR proofs of related secrets), private set-intersection (built from polynomial evaluation in-the-exponent), etc.
8. And critically, interesting attacks on these systems, with a particular focus on how fragile they can be:
8a. Linearly related nonce attacks against signatures. (unfortunately, these attacks are easier taught if the signature algorithm is understood as a hidden linear system, then the attack is just a 'as many knows as unknowns attack', but I strongly prefer the causal loop understanding of signatures for the intuition it creates for more complex protocols).
8b. Random-modular-subset sum attacks on naive blind signatures and naive multi-signature.
8c. At least one attack that break the generic group abstraction. I'm fond of invalid key attacks on DH with twist-insecure curves. (This is probably the only example that I think is important to teach that requires some group law understanding).
If I do get into group law, I think it's interesting to talk about optimizations. Particularly, projective coordinates, precomputation, addition/subtraction ladders and signed digit representations, doubling sharing for multi-exp.
Bos-coster for sum-of-many products is an especially fun and easy algorithm to implement (similar kind of fun as implementing the peeling algorithm for decoding sparse linear codes in F(2)).
I'd like to have a 9 on that list that goes into the building blocks of proof techniques for these systems e.g. programmable oracles/forking lemma... but that is enough out of my area of expertise that I don't know how to teach it effectively.
Some people are just interested in curves themselves. That's the point of an article like this. If you want to learn how to build a signature scheme, there are good sources for that as well.
There is a tremendous amount of ECC tutorials that walk people mechanically through the group law, I think I've seen a dozen new ones posted on HN in the past year. I don't think I've ever see an article on actual elliptic curve cryptography (beyond briefly explaining DH, as this one does).
Like-- say the article were instead explaining elliptic curves as part of factoring, how would it differ? (This one would omit the DH part, but many don't even have that.)
Personally, I think they're not that useful from the perspective of cryptography. This level of article doesn't bring you to number theory insight or anything like that. They are useful for slavishly coding your own ECC thing without any understanding, but the results of doing that are inevitably totally insecure toys. Hopefully that isn't something "most practitioners" are doing-- hopefully they're linking libsodium or something. :)
If you like it, great! I think I provided a pretty useful curriculum that someone could self-study if they wanted to actually dive deep on the cryptography.
From being able to apply group law you couldn't predict the properties or (most of) the vulnerabilities. (or even performance, since these things don't generally cover projective coordinates).
At least the way I see it is if you asked about how a spell checker worked, and then I set out and explain how a digital adder circuit works from the gate level. You can't build a spell checker without adders yet you wouldn't be informed. :)
This sort of thing also strikes me as the sort of thing that more "feeling of understanding" without creating much understanding. I seldom think it's good to do that, though it isn't always harmful.
But learning styles is certainly something that differs a lot between people, so I certainly don't think my experience is universal by any means.
I can say that personally learning to ignore the machinery made my understanding grow 100x faster and directly resulted in constructing more than a few publishable (and widely deployed) designs.