Talk:Digital Signature Algorithm

431: 421: 400: 203: 1186:

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.

632: 776: 758: 282: 540: 509: 608: 848: 140: 80: 53: 1937:

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)

22: 694: 193: 172: 1830:

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

997:

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.

1348:

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,

1936:

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,

1069:

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

966:

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

1061:

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

1065:

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,

1185:

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

1249:

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

1434:

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

998:

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

1323:. 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. 1447:

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.

1335:

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

1205:

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

1470:

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.

957:

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

1514:

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.

987:

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

370: 2150: 816: 2130: 822: 130: 1943:

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.

725: 1987:

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.

967:

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.

1066:

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.

2145: 2110: 2125: 646: 2045: 154: 1005:

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

1891: 1610: 1600: 915:

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

2050: 1990:

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.

1985: 1965: 1772: 1768: 1754: 1662: 1658: 1644: 2035: 120: 1105:. 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? 1500:

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?

2155: 491: 2120: 2080: 481: 2095: 2055: 2040: 598: 588: 1245:

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

2160: 2105: 2085: 792: 622: 1300:

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

2135: 1209: 659: 641: 523: 96: 2065: 2030: 457: 259: 249: 149: 63: 2075: 1546: 1516: 1501: 1449: 783: 763: 564: 2090: 2070: 1213: 930: 2100: 1478: 1187: 87: 58: 1750:

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

1350: 1122:

so frequently that they forget to include pointers to the relevant pages. I've added links to some articles that should be helpful.

444: 405: 1611:

https://web.archive.org/web/20140606050814/http://csrc.nist.gov/publications/nistpubs/800-57/sp800-57-Part1-revised2_Mar08-2007.pdf

1601:

https://web.archive.org/web/20140606050814/http://csrc.nist.gov/publications/nistpubs/800-57/sp800-57-Part1-revised2_Mar08-2007.pdf

1740: 225: 1584: 2140: 2060: 1423: 547: 514: 328: 2115: 617: 519: 334: 1438:

The article's description is consistent with what a "DSA signature" is considered to consist of in, for example, RFC 3279. –

1614: 1604: 1254:

Can anyone elaborate on what this weakness is, and (although off topic) why is RSA any worse/better than DSA for TLS? --

1815: 1705: 1408:

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?

294: 33: 1276:

be cryptographically random, be kept secret, and never reused. If an attacker (who knows the public key) can guess the

971:

Is this viewpoint not held by anyone, even a minority? (If so, it should be reinserted into the article in some form).

1724: 1568: 1090: 856: 216: 177: 1850:

libsodium is listed as an implementation of DSA, however I cannot find any indication that it is. libsodium uses the

1530: 1234: 1027: 1022: 734:

Create the Project Navigation Box including lists of adopted articles, requested articles, reviewed articles, etc.

1771:

to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the

1661:

to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the

1453: 708: 1550: 1520: 1505: 1326:

An RSA signer does not have this problem, because no random value is needed for its basic signing primitive. –

1217: 934: 1806: 1732: 1696: 1576: 1482: 1191: 341: 1940:

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

1354: 560: 1089:

I don't know squat about math, but when trying to implement DSA signing using the sequence of steps here

1790:

If you have discovered URLs which were erroneously considered dead by the bot, you can report them with

1778: 1680:

If you have discovered URLs which were erroneously considered dead by the bot, you can report them with

1668: 1349:

there are quite a few people that prefer the randomized RSA signatures over the deterministic variants.

1177: 1123: 355: 221: 39: 1731:. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit 1575:. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit 1047: 1042:

NIST claims that they reviewed Schnorr's patent and concluded that DSA is not infriging the patent in

1635: 1474: 1439: 1411: 1327: 1109: 926: 852: 1415: 1255: 21: 1419: 1259: 1145: 791: