in length, and p and q should be approximately half the size of n in bits.
Random Number Generation
FIPS 186-2 includes algorithms for the generation of a user's private key, x, and a user's per message secret number, k. These values must be generated randomly or pseudorandomly and must have values between 0 and the 160-bit prime q (as specified in the standard). Techniques for generating x and k are provided in Appendix 3 of the standard.
Recently, an unpublished attack on DSA[1] was found that relies on the non-uniformity of the pseudorandom number generators (PRNGs) specified in Appendix 3 of the standard. The attack has a workfactor of 264 and requires 222 known signatures. This attack can be defended against by either limiting the number of signatures created using a specific key pair to no more than 2 million signatures while using the PRNGs specified in FIPS 186-2, or by modifying the PRNGs.
If the PRNGs currently defined in FIPS 186-2 are used, the user should be provided with clear guidance about the limitation to the number of signatures that should be created.
Alternatively, the following modifications of the PRNGs may be used in lieu of those PRNGs specified in FIPS 186-2. These modifications reduce the non-uniformity of the PRNGs and do not affect interoperability.
The two algorithms described below use a one-way function G(t,c), where t is 160 bits, c is b bits and G(t,c) is 160 bits. Two methods for constructing G are defined in FIPS 186-2: using SHA-1 as defined in FIPS 180-1, and using the Data Encryption Standard (DES) as defined in FIPS 46-3. If G is constructed using SHA-1, b is between 160 and 512 bits (160 ≤ b ≤ 512); if G is constructed using DES, b is equal to 160 bits.
1. Revised Algorithm for Computing m values of x (Appendix 3.1 of FIPS 186-2)
Let x be the signer's private key. The following may be used to generate m values of x:
- Step 1. Choose a new, secret value for the seed-key, XKEY.
- Step 2. In hexadecimal notation let
- This is the initial value for H0 || H1 || H2 || H3 || H4 in the SHS [FIPS 180-1].
_________________________
- ↑ The attack was discovered by Dr. Daniel Bliechenbacher of Lucent Technologies, Bell Labs, Murray Hill, NJ. See a February 25, 2001 press article at http://www.lucent.com/press/0201/010205.bla.html.
72
