EarthWeb   

HomeAccount InfoLoginSearchMy ITKnowledgeFAQSitemapContact Us
     

   
  All ITKnowledge
  Source Code

  Search Tips
  Advanced Search
   
  

  

Applied Cryptography, Second Edition: Protocols,  Algorthms, and Source Code in C 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
  Buy ItBookmark It

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 = ((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

Copyright © John Wiley & Sons, Inc.

HomeAccount InfoSubscribeLoginSearchMy ITKnowledgeFAQSitemapContact Us
Products |  Contact Us |  About Us |  Privacy  |  Ad Info  |  Home

Use of this site is subject to certain Terms & Conditions, Copyright © 1996-2000 EarthWeb Inc. All rights reserved. Reproduction in whole or in part in any form or medium without express written permission of EarthWeb is prohibited. Read EarthWeb's privacy statement.