Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

It has been well known for a long time that NSA played a primary role in the development of the Digital Signature Algorithm (DSA).

DSA is a sort of hybrid of the ElGamal and Schnorr signature schemes.

My question is this. Based on what we know now, why did NSA invent a new scheme rather than just adopt ElGamal or Schnorr? I am looking for informed speculation based on what is known today about the relative strengths and weaknesses of these schemes, with references. (References for the strengths and weaknesses, I mean, not for the speculation.)

If your speculation is that NSA did something to weaken DSA, what could they possibly have gained other than the ability to forge signatures?

Or was DSA just the result of IP concerns? If so, I would like to see a reference for that, too.

share|improve this question
add comment

1 Answer

up vote 8 down vote accepted

Apparently, Schnorr was quite adamant, at that time, about the applicability of his patent to DSS. See this message and that one. These are from 1998, but the controversy had begun earlier; see for instance this bulletin from NIST, from late 1994, where references to it can be found in the "Patent Issues" section. Interestingly, NIST not only tried to avoid Schnorr's patent, but they also filed their own patent. Also, see this message for another analysis.

It must be recalled that when NIST began pushing standards for asymmetric cryptography, RSA was already taking the lion's share of the market; what really deserves an explanation is not why NIST preferred DSA over Schnorr signatures, but why they used the DH/DSA pair instead of RSA. IP issues are a very plausible explanation; as the references above show, there indeed was some bitter strife in those years.

As for ElGamal signatures: that scheme is more expensive. ElGamal signatures work modulo a prime $p$ and require one modular exponentiation (for generation) or two (for verification) with exponents as big as $p$; and the signature is two integers modulo $p$. This contrasts with DSA and Schnorr, which both work in a subgroup, traditionally a 160-bit subgroup for a 1024-bit modulus. DSA and Schnorr are 6 times faster than ElGamal, and produce signatures which are 6 times smaller. This difference in performances is enough to explain not choosing ElGamal. Indeed, the short size of DSA and Schnorr signatures has long been the selling point for these algorithms when compared to RSA.

share|improve this answer
    
Great set of links (especially "see this message for another analysis"). It looks to my non-expert eye like Schnorr had a pretty strong case, since the use of a "Schnorr group" to reduce the signature size is a pretty important idea in both the patent(s) and the DSA. Anyway it appears the answer to my question is "NSA did not like RSA and wanted an IP-free alternative for signatures." Whether IP concerns alone explain that dislike is harder to say, I think... RSA's applicability to encryption as well as signing is also plausible. –  Nemo Sep 17 '13 at 17:12
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.