|
 |
|
Applied Cryptography, Second Edition: Protocols, Algorthms, and Source Code in C
by Bruce Schneier
Wiley Computer Publishing, John Wiley & Sons, Inc.
ISBN: 0471128457 Pub Date: 01/01/96 
|
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 isnt 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 negligiblesmaller, 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
|
| 15 sec off-card (P)
| 13 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.
|
|