For those like me, who are confused by the acronym DHMW, it's another name for 'Diffie-Helman'.
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.
Cocks and Ellis developed what we know as RSA, Malcolm Williamson developed what most people call Diffie-Hellman.
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.
Nobody should get credit for inventing something in secret. You make your decision — invent for corporations or the military industrial complex and get the big bucks or the jingoistic frisson, or for academia and get the accolades. No way a person should double dip.
Credit for what? The theoretical work for which Turing is most known - the concept of Turing machines and undecidability - was published publicly and before the war. He did not contribute to the design of a physical computer until after the war. Colossus, the code-breaking "computer", was not of his design (and the man who did design it is not at all famous for it).
The thing I like best about this article is that it touches on elliptic curves over finite fields in more than a cursory way. But I would love to see an introduction to elliptic curves that completely ignores the behavior in the real numbers, and instead focuses on driving the motivations from the finite field perspective.
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.
I can recommend https://www.amazon.com/Elliptic-Tales-Curves-Counting-Number.... It goes in-depth into the motivating use cases for elliptic curves (as well as their group law) and explains some very elegant theorems (Bézout's theorem) as well as open problems in Maths (the Birch-Swinnerton-Dyer conjecture).
Take the elliptic curve y^2 = x^3 - 5 that has no rational solutions [1]. But it's easy to see (from brute force) that, for example, 3^2 - 5 = 22 = 27^2 (mod 101).
I don't have much experience in cryptography, so this may be a stupid question, but I've always wondered about whether Elliptic Curve cryptography opens up some possibilities for partially decentralizing encryption standards.
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?
> 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.
There are all sorts of pitfalls and potential attacks even if the curves are truly random[1]. Some curves also require you to verify whether public keys are valid points on the curve (and their security breaks if you don't do so). So they're harder to implement safely. Others are hard to implement in a way that avoids timing attacks.
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.
It's misleading to claim that 25519 pubkeys don't require validation: In some applications validation isn't required, in other applications validation is simpler but still required.
Marketing bullet points aren't a replacement for careful cryptographic review.
While I don't know enough about this stuff to answer your main question, I will point out that there are some popular curves which aren't tied to any one nation or agency.
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!
There have been attempts in this direction, it's absolutely doable to use a shared seed where many people contribute a random value.
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.
It's great that people enjoy this-- but I've never seen explanations that centered on the group law as actually being especially useful for building insight producing understandings complex cryptosystems.
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).
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.
This is a fine comment but is a little like saying "the best way to understand elliptic curves is not to study elliptic curves", which, sure, a first course in abstract algebra will be more profitable for designing entirely new constructions (or evaluating them from first principles) --- which most practitioners don't actually do.
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.
I think it would be more precise to say "The best way to understand elliptic curve cryptography is to study discrete log cryptography, not to study elliptic curves".
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.
They're not meant to be useful from the perspective of cryptography, in the same way as learning textbook RSA is not useful in that sense. They're useful in the sense that people want to have some faint clue of what's happening.
Maybe it's just a difference in how I look at it, but knowing what group law is doing is not a useful clue to me.
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.
I was at a Graduation in London, Ontario Canada, This lady had given a speech to the new graduates. Known for her contributions to ECC https://en.wikipedia.org/wiki/Kristin_Lauter
* 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.