| Previous | Table of Contents | Next |
Proofs for the mathematical relationships are found in [1154]. Table 20.1 provides a summary.
Speed Precomputations
Table 20.2 gives sample software speeds of DSA [918].
Real-world implementations of DSA can often be speeded up through precomputations. Notice that the value r does not depend on the message. You can create a string of random k values, and then precompute r values for each of them. You can also precompute k-1 for each of those k values. Then, when a message comes along, you can compute s for a given r and k-1.
This precomputation speeds up DSA considerably. Table 20.3 is a comparison of DSA and RSA computation times for a particular smart card implementation [1479].
| Table 20.1 DSA Signatures | |
|---|---|
| Public Key: | |
| p 512-bit to 1024-bit prime (can be shared among a group of users) | |
| q 160-bit prime factor of p – 1 (can be shared among a group of users) | |
| g = h(p - 1)/q mod p, where h is less than p – 1 and h(p - 1)/q mod p > 1 (can be shared among a group of users) | |
| y = gx mod p (a p-bit number) | |
| Private Key: | |
| x < q (a 160-bit number) | |
| Signing: | |
| k choose at random, less than q | |
| r (signature) = (gk mod p) mod q | |
| s (signature) = (k-1 (H(m) + xr)) mod q | |
| Verifying: | |
| w = s-1 mod q | |
| u1 = (H(m) * w) mod q | |
| u2 = (rw) mod q | |
| v = ((gu1 * yu2) mod p) mod q | |
| If v = r, then the signature is verified. | |
DSA Prime Generation
Lenstra and Haber pointed out that certain moduli are much easier to crack than others [950]. If someone forced a network to use one of these "cooked" moduli, then their signatures would be easier to forge. This isn't a problem for two reasons: These moduli are easy to detect and they are so rare that the chances of using one when choosing a modulus randomly are almost negligible—smaller, in fact, than the chances of accidentally generating a composite number using a probabilistic prime generation routine.
In [1154] NIST recommended a specific method for generating the two primes, p and q, where q divides p – 1. The prime p is L bits long, between 512 and 1024 bits long, in some multiple of 64 bits. The prime q is 160 bits long. Let L – 1 = 160n + b, where L is the length of p, and n and b are two numbers and b is less than 160.
| Table 20.2 DSA Speeds for Different Modulus Lengths with a 160-bit Exponent (on a SPARC II) | |||
|---|---|---|---|
| 512 bits | 768 bits | 1024 bits | |
| Sign | 0.20 sec | 0.43 sec | 0.57 sec |
| Verify | 0.35 sec | 0.80 sec | 1.27 sec |
| Table 20.3 Comparison of RSA and DSA Computation Times | |||
|---|---|---|---|
| DSA | RSA | DSA with Common p, q, g | |
| Global Computations | Off-card (P) | N/A | Off-card (P) |
| Key Generation | 14 sec | Off-card (S) | 4 sec |
| Precomputation | 14 sec | N/A | 4 sec |
| Signature | .03 sec | 15 sec | .03 sec |
| Verification | 16 sec | 1.5 sec | 10 sec |
| 1–5 sec off-card (P) | 1–3 sec off-card (P) | ||
| Off-card computations were performed on an 80386 33 mHz, personal computer. (P) indicates public parameters off-card and (S) indicates secret parameters off-card. Both algorithms use a 512-bit modulus. | |||
| Previous | Table of Contents | Next |