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).

Along similar lines, someone down below has helpfully pointed out the fantastic "Operation ORCHESTRA" briefing PHK gave at FOSDEM 2014, which is equally funny and pointed. That video is on YouTube: https://youtu.be/fwcl17Q0bpk - http://phk.freebsd.dk/_downloads/FOSDEM_2014.pdf