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 = g^{x} mod p (a p-bit number)
| |

Private Key: | |

x < q (a 160-bit number)
| |

Signing: | |

k choose at random, less than q
| |

r (signature) = (g^{k} mod p) mod q
| |

s (signature) = (k^{-1} (H(m) + xr)) mod q
| |

Verifying: | |

w = s^{-1} mod q
| |

u_{1} = (H(m) * w) mod q
| |

u_{2} = (rw) mod q
| |

v = ((g1 * ^{u}y2) mod ^{u}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 = 160*n* + *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 |