Talk:Digital Signature Algorithm

DSA Security

I'm not qualified to do this but would it be possible to have a section to describe the security of DSA? I think it rests on the fact that an attacker cannot derive k or x from a signature or public key because of the hardness of Discrete Logarithm Problem (DLP). — Preceding unsigned comment added by 159.196.168.4 (talk) 21:15, 13 August 2023 (UTC)

DSA and encryption

Recently removed from the article:

It was designed at the NSA as part of the Federal Government's attempt to control high security cryptography. Part of that policy included prohibition (with severe criminal penalties) of the export of high quality encryption algorithms. The DSS (Digital Signature Standard) was intended to provide a way to use high security digital signatures across borders in a way which did not allow encryption. Those signatures required high security asymmetric key encryption algorithms, but the DSA (the algorithm at the heart of the DSS) was intended to allow one use of those algorithms, but not the other. It didn't work. DSA was discovered, shortly after its release, to be capable of encryption (prohibited high quality encryption, at that) but to be so slow when used for encryption as to be even more than usually impractical.

Is this viewpoint not held by anyone, even a minority? (If so, it should be reinserted into the article in some form). User:Ww? — Matt 22:53, 5 Sep 2004 (UTC)

Schneier, Applied Cryptography, 2nd ed:

There have been allegations that the government likes the DSA because it is only a digital signature algorithm and can’t be used for encryption. It is, however, possible to use the DSA function call to do ElGamal encryption. — Matt 23:17, 5 Sep 2004 (UTC)

I would say the view is held not by a minority, but by everyone! We're not talking about some secret conspiracy here; NSA officials such as Bill Crowell spelled it out in Congressional testimony. The speculative part is whether or not DSA was specifically meant to hamper the commercialization of RSA. I think there is less agreement here, but it is still a pretty widely held opinion. And of course, the reasons that it failed (if that was the plan) are much more complex than the observation that it is possible to bludgeon DSA into doing encryption (very slowly). Securiger 06:22, 24 Sep 2004 (UTC)

I would at least point to the fact that DSA can be used for encryption (RSA and Elgamal) by choosing special inputs to the sign function (As described by Schneier). --Tobias 11:20, 20 December 2005 (UTC)

Schnorr patent dispute

The two links disputing the Schnorr patent claim are 404's:

http://www.privacy.nb.ca/cryptography/archives/coderpunks/new/1998-08/0006.html

http://www.privacy.nb.ca/cryptography/archives/coderpunks/new/1998-08/0009.html

Anyone has another source? Could not find a working archive.. --Tobias 11:18, 20 December 2005 (UTC)

NIST claims that they reviewed Schnorr's patent and concluded that DSA is not infriging the patent in http://csrc.nist.gov/publications/nistbul/csl94-11.txt. 24.228.93.22 00:48, 17 February 2006 (UTC)

Hmm, this looks like wide spread opinion

Interesting stuff, I will have to admit that paragraph will likely never stay on the front page for long. Too many people will think you are making it up unfortunately. In fact, the first time I had of it, was on a cryto related thread on lkml (Linux kernel mailing list) Even there, the suggestion was finding a lot of resistance.

Then, a month ago, I was in TLUG (Toronto Linux user group) and there was a discussion of ssh. The one thing everybody seemed to agree on is using DSA is a bad idea. RSA should be used whenever possible. Some books like UNIX System Administration Handbook (3rd Edition) (Paperback) by Evi Nemeth, Garth Snyder, Scott Seebass, Trent R. Hein don't advice it use, but others like Professional Red Hat Enterprise Linux 3 (Wrox Professional Guides) (Paperback) advice on its use.

In short, DSA has a perception issues whether one accept this as a fact is a different story. I guess we will have to wait until more people support the hypothesis before that paragraph can move in the front article. Remember people used to believe the world is flat until reality dawned at them one day. Here is to hoping it will happen again

DSA standard revised. Article needs updating.

See here: http://sdp.opendawn.com/index.php/DSA2_support

A little bit more info for signing description

I don't know squat about math, but when trying to implement DSA signing using the sequence of steps here Digital_Signature_Algorithm#Signing, it was not obvious to me that k^-1 = the multiplicative inverse of k mod q. I had to go to the spec to figure that out. Does it make sense to add a small bit of verbiage to that effect, or is that something that should be obivous?

--Geechorama 17:15, 4 August 2006 (UTC)

You have a good point here. Cryptographers use modular arithmetic so frequently that they forget to include pointers to the relevant pages. I've added links to some articles that should be helpful. 67.84.116.166 15:25, 16 August 2006 (UTC)

k is not a nonce

Calling the variable k a nonce might mislead some readers. Specially the description of a nounce says

it should be time-variant (including a suitably granular timestamp in its value) ...

Including a timestamp intok would make some bits of k predictable. This might allow lattice based attacks that can recover the secret key x. k or even parts of k must not be predictable. 67.84.116.166 23:44, 14 September 2006 (UTC)

You are correct, the k-value is a more complicated beast that we don't have a proper term for. I expanded the notes about the k-value to include all the security requirements (secrecy, uniqueness & unpredictability) that I know of and gave a reference that shows the math for how DSA can be attacked if you mess it up. It's critical to the security of the algorithm that people need to know that they can't reuse a k, even if they keep it secret, that they have to use a good random source to choose their k, and that they have to make sure that k remains secret. There have been two major screw-ups concerning the k-value already (the Debian PRNG flaw & the hacking of the PS3), so I think that more people need to know about this. 72.1.186.174 (talk) 05:03, 31 December 2010 (UTC)

data type....

hey guys.... i just wanted to know the data type in java that can support the global variables in DSS...the length of 'p' cud vary from 512 bits to 1024 bits....i m confused as to how shall i proceed with the project.... —The preceding unsigned comment was added by 125.23.19.220 (talk) 15:27, 8 January 2007 (UTC).

DSA weakness?

Upon reading PuTTYgen's docs on selecting a key type, I came across this line:

The PuTTY developers strongly recommend you use RSA. DSA has an intrinsic weakness which makes it very easy to create a signature which contains enough information to give away the private key! This would allow an attacker to pretend to be you for any number of future sessions. PuTTY's implementation has taken very careful precautions to avoid this weakness, but we cannot be 100% certain we have managed it, and if you have the choice we strongly recommend using RSA keys instead.

Can anyone elaborate on what this weakness is, and (although off topic) why is RSA any worse/better than DSA for TLS? -- PaperWiki (talk) 22:10, 18 November 2007 (UTC)

It sounds like they refer to the fact that the per-message value k must be cryptographically random, be kept secret, and never reused. If an attacker (who knows the public key) can guess the k used to sign any single message, possibly by tricking the signer into using a k of his choosing, it is a matter of simple arithmetic for him to recover the full private key, as x is then the only unknown in the equation for s. Similarly, if the same k is ever used to sign two different messages, an attacker can (1) immediately see that this is the case because the two signatures will have the same r, (2) find the value of the reused k by dividing the difference of the message hashes by the difference of the s values, (3) recover the private key as before.

This means that the security of a DSA signing routine is at the mercy of the security of the PRNG it uses to generate k. Deploying a PRNG such that it cannot be fooled or predicted is surprisingly tricky; one has to either trust an OS-provided source of randomness, or do complex and easy-to-get-wrong platform-dependent stuff in order to gather entropy from the environment oneself.

An RSA signer does not have this problem, because no random value is needed for its basic signing primitive. –Henning Makholm 00:03, 19 November 2007 (UTC)

There are some comments in the file sshdss.c of Putty's implementation, which amount to what you just mentioned. Apparently Putty's implementors don't trust their own pseudorandom number generator, hence they use a method that derives k deterministically from the private key x and the message m by hashing these values. Such a method has been analyzed in the paper "Computational Alternatives to Random Number Generators" by M’Raihi, Naccache, Pointcheval, Vaudenay presented at SAC'98. Since RSA also needs to be implemented very carefully, I don't agree with the strong preference above. Also, there are quite a few people that prefer the randomized RSA signatures over the deterministic variants. 85.2.78.238 (talk) 06:34, 19 November 2007 (UTC)

As an interesting aside, that's what happened because of CVE-2008-0166. Since the PRNG was extremly weak, any DSA key merely used on a buggy system should be considered compromised[1]. --cesarb (talk) 02:49, 3 June 2008 (UTC)

Statement that the signature=(r, s)

It is stated that the signature is (r, s), but shouldn't this be (r, s, H(M)) as the verifier must calculate Hw mod q? —Preceding unsigned comment added by James mcl (talk • contribs) 14:23, 3 January 2008 (UTC)

The statement assumes that the recipient of the signature knows, by means external to the signature itself, which message it is supposed to sign. He can therefore compute H(M) himself. If he tries to do the calculation with the hash of a different message, he will simply find that it fails.

The article's description is consistent with what a "DSA signature" is considered to consist of in, for example, RFC 3279. –Henning Makholm 01:25, 6 January 2008 (UTC)

Indeed, the WHOLE POINT of a signature is the recipiant calculates H(M) from the message and therefore in verifying the signature verfies not only that the signature is internally consistent but that the received message is the same one the sender signed. 130.88.108.187 (talk) 12:48, 15 February 2012 (UTC)

DSA vs Elliptic Curve DSA

DSA article almost entirely contains the Elliptic Curve DSA article. Also the Elliptic Curve DSA article describes Elliptic Curve DSA as a variant of DSA whereas it is the only algorithm described in the DSA article. —Preceding unsigned comment added by 141.84.28.46 (talk) 13:04, 23 June 2008 (UTC)

Advantage compared to Elgamal

I cannot see any, it is just more complicated, I think.

It is true, (p-1) must have a large prime factor which is smaller or equal to q= (p-1)/2. But why not choosing a safe prime with q=(p-1)/2 is a prime number? 109.90.224.162 (talk) 17:51, 11 September 2015 (UTC)

Choosing a value of p much larger than q is complete nonsense, because the security does not depend on the size of p only on the size of q. It means calculation becomes more difficult without rising the security. 109.90.224.162 (talk) 18:32, 11 September 2015 (UTC)

Hmmmmm - I didn't read this Discrete_logarithm_records before. So, p must have at least 1000 bits, that's true, but still it is possible to use a safe prime, meaning q = (p-1)/2 or just use Elgamal with that safe prime. 109.90.224.162 (talk) 09:53, 7 October 2015 (UTC)

External links modified

Hello fellow Wikipedians,

I have just modified 4 external links on Digital Signature Algorithm. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20130109092551/http://www.certicom.com/index.php/dr-david-kravitz to http://www.certicom.com/index.php/dr-david-kravitz
• Corrected formatting/usage for http://csrc.nist.gov/groups/SMA/ispab/documents/94-rpt.txt
• Added archive https://web.archive.org/web/20140606050814/http://csrc.nist.gov/publications/nistpubs/800-57/sp800-57-Part1-revised2_Mar08-2007.pdf to http://csrc.nist.gov/publications/nistpubs/800-57/sp800-57-Part1-revised2_Mar08-2007.pdf
• Added archive https://web.archive.org/web/20140606050814/http://csrc.nist.gov/publications/nistpubs/800-57/sp800-57-Part1-revised2_Mar08-2007.pdf to http://csrc.nist.gov/publications/nistpubs/800-57/sp800-57-Part1-revised2_Mar08-2007.pdf

When you have finished reviewing my changes, please set the checked parameter below to true or failed to let others know (documentation at {{Sourcecheck}}).

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 02:24, 13 December 2016 (UTC)

External links modified

Hello fellow Wikipedians,

I have just modified one external link on Digital Signature Algorithm. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20131226115544/http://csrc.nist.gov/publications/fips/fips1861.pdf to http://csrc.nist.gov/publications/fips/fips1861.pdf

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 03:42, 27 July 2017 (UTC)

Range of k

The article used to specify 0<k<q, which was consistent with FIPS 186-4 (see the 'Output' clauses in B.2). Currently the article says 1<k<q, which isn't necessarily a bad idea but isn't consistent with the spec and doesn't tell you what the implementations actually do. I think the article should reflect the spec. Anyone agree/disagree? Ewx (talk) 11:54, 24 November 2017 (UTC)

Implementations: libsodium?

libsodium is listed as an implementation of DSA, however I cannot find any indication that it is. libsodium uses the Ed25519 signature scheme, which is more comparable to an elliptic curve version of Schnorr signatures, though also often considered a variant of ECDSA. But it certainly isn't (multiplicative group of $Z_{p}$) DSA. Aragorn2 (talk) 10:29, 14 June 2019 (UTC)

Agreed. I've removed it. Ewx (talk) 10:29, 15 June 2019 (UTC)

k is not calculated

I find this revert puzzling.

The current text says: " A message {\displaystyle m}m is signed as follows:

Choose an integer {\displaystyle k}k randomly from {\displaystyle \{1\ldots q-1\}}{\displaystyle \{1\ldots q-1\}} Compute {\displaystyle r:=\left(g^{k}{\bmod {\,}}p\right){\bmod {\,}}q}{\displaystyle r:=\left(g^{k}{\bmod {\,}}p\right){\bmod {\,}}q}. In the unlikely case that {\displaystyle r=0}r=0, start again with a different random {\displaystyle k}k. Compute {\displaystyle s:=\left(k^{-1}\left(H(m)+xr\right)\right){\bmod {\,}}q}{\displaystyle s:=\left(k^{-1}\left(H(m)+xr\right)\right){\bmod {\,}}q}. In the unlikely case that {\displaystyle s=0}s=0, start again with a different random {\displaystyle k}k. The signature is {\displaystyle \left(r,s\right)}\left(r,s\right)

The calculation of {\displaystyle k}k and {\displaystyle r}r amounts to creating a new per-message key. "

That is, first it says that 'k' is chosen randomly and 'r' and 's' are computed. Then it talks about the calculation of 'k' and 'r'. 'k' cannot both be calculated and chosen randomly.

You reverted it to say "The calculation of $r$ and $s$ amounts to creating a new per-message key. ". That's incorrect: s is not part of a key. Hence the revert. If you object to the sentence then you need to do more than change k to s.

In reality k isn't just plucked out of the air; there will normally be some computation involved - running an RBG and (in the B.2.1 strategy) a modular reduction.

Ewx (talk) 14:41, 7 August 2021 (UTC)

--Ettrig (talk) 08:11, 6 August 2021 (UTC)