Applied Cryptography, Second Edition: Protocols, Algorthms, and Source Code in C (cloth)
(Publisher: John Wiley & Sons, Inc.)
Author(s): Bruce Schneier
ISBN: 0471128457
Publication Date: 01/01/96

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)
k choose at random, less than q
r (signature) = (gk mod p) mod q
s (signature) = (k-1 (H(m) + xr)) mod q
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

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
[an error occurred while processing this directive]