"Protocols and constructions should be designed to minimize dependence on randomness, the way DJB's EdDSA does:"
I think a lot of the reason that ECDSA/DSA are so inelegant was that they were designed to get around the patent on the (quite elegant) Schnorr signature algorithm, which EdDSA is based on. Thankfully, the patent expired in 2008, so moving to better signature algorithms that don't rely on per-message randomness is a matter of institutional inertia at this point.
Hmmm… and ElGamal's signing scheme didn't qualify? I don't think that's a reason, or even an excuse: Schnorr actually did claim his patent read on DSA. (That obviously never went anywhere, and the US Government, in a show of force via the NSA, filed their own patent on DSA.)
The NSA also really doesn't seem to have had much of a problem negotiating the licensing of patents with industry participants in the past! It is, after all, in an extraordinarily strong bargaining position: an awful lot of public money to throw around (openly, via on-the-book government contracts, and otherwise); the backing of a 'superpower' government and its negotiators; a remarkably good idea of what the position of those its bargaining with is (it is a signals intelligence agency…!); and is even able to classify patents and other nonsense like that.
DSA was sceptically received at the time, and there was widespread suspicion about its complexity and critical dependency on random k. (Even just two or three predictable leading bits of k can cause disaster!) Sizes above 1024 bit were not specified for way too long, and I would consider a 1024-bit DSA key most definitely crackable by the computing resources available to the NSA (or perhaps anyone else with a budget and a chip fab on contract after-hours!) today. (Those with DSA PGP signing keys may wish to take note and replace them, I suggest, with 4096-bit RSA keys.)
I think perhaps the only reason DSA got any popularity was because of the RSA patent, which it wasn't subject to, and the US cryptographic export restrictions which were the style at the time (remember the PGP source code "type-in listing" book publication?), which DSA avoided ostensibly because you couldn't encrypt with it but mainly because the US Government wanted you to use it. (ElGamal's encryption scheme was commonly used in tandem with it in practice, for example by some PGP versions.)
ECDSA has been accepted in a more sanguine fashion overall, although I'm not sure why that has been. Just like DSA, it definitely works correctly if it's done properly - but one tiny slip and you're toast.
Why was ECDSA better-received than DSA? Time may have helped; so is what they were seen to have done in the meantime. "Suite B-eatification" (as Kevin put it!) I think might've made people a little less sceptical of the NSA's intentions overall; also SHA (which as far as we know is not backdoored and has never been), and (via NIST) their arms-length involvement in reviewing candidates for the AES process. That introduced its "Information Assurance" mission (the one to protect classified US Government data - anyone else's data, or unclassified US Government data, is Not Their Problem). With Suite B, they wanted to be able to use more off-the-peg commercial providers for that purpose (rather than their bespoke, if a bit haute couture weird and distinctly old-looking, in-house stuff, which they referred to by contrast as "Suite A"). And people - perhaps foolishly - trusted that, despite the "equity" tension between their two missions, they would never risk compromising the same encryption systems they'd use for top secret US Government data. (It appears that trust may have been sadly misplaced… and, thanks to Snowden's bold willingness to go on-the-record about their unethical actions, they have permanently destroyed that trust now.)
We can, indeed, do better now, happily. I wonder if we will?
This talk was a fun "thinking-like-the-enemy" thought experiment, interlaced with the kinds of things djb's been generally warning about for years - I think it's up on YouTube somewhere, and like many slides makes more sense with the talk, although I sadly can't find it now (and I recall the audio quality wasn't great).
I'm only 10 minutes into the first youtube vid... holy shit this is the most terrifying thing I've ever seen.
No wonder our patent reform is so broken... literally the government is using it to it's advantage. Screw the cloak and daggers shit when we can just hire some lawyers to bury people and everyone acts like it's common place... wow. WOW WOW WOW.
I think a lot of the reason that ECDSA/DSA are so inelegant was that they were designed to get around the patent on the (quite elegant) Schnorr signature algorithm, which EdDSA is based on. Thankfully, the patent expired in 2008, so moving to better signature algorithms that don't rely on per-message randomness is a matter of institutional inertia at this point.