14
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ Crypto, by Steven Levy, is a fantastic exploration of the history of public key, and touches on these issues. $\endgroup$
    – Ethan
    Commented Sep 4, 2014 at 22:20
  • $\begingroup$ Also see Security Difference Between DSA and Schnorr’s Signature $\endgroup$
    – user10496
    Commented Feb 7, 2018 at 19:07

1 Answer 1

Reset to default
29
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – Nemo
    Commented Sep 17, 2013 at 17:12
  • $\begingroup$ I count three modular exponentiations for the verification of ElGamal signatures (and one for signing). The performance of the key generation doesn't seem crucial to me. $\endgroup$
    – Kaspar Etter
    Commented Aug 25, 2021 at 8:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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