Click Here! |

Brief Full Advanced Search Search Tips
|  |  | To access the contents, click the chapter and section titles. 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 Search this book:
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 = ((gu 1 * yu 2) 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
[an error occurred while processing this directive]

| Products | Contact Us | About Us | Privacy | Ad Info | Home Use of this site is subject to certain Terms & Conditions, Copyright © 1996-1999 EarthWeb Inc. All rights reserved. Reproduction whole or in part in any form or medium without express written permision of EarthWeb is prohibited.