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
(1) Choose an arbitrary sequence of at least 160 bits and call it S. Let g be the length of S in bits. (2) Compute U = SHA(S) ⊕ SHA ((S + 1) mod 2g), where SHA is the Secure Hash Algorithm (see Section 18.7). (3) Form q by setting the most significant bit and the least significant bit of U to 1. (4) Check whether q is prime. (5) If q is not prime, go back to step (1). (6) Let C = 0 and N = 2. (7) For k = 0, 1,..., n, let Vk = SHA ((S + N + k) mod 2g) (8) Let W be the integer W = V0 + 2160V1 +...+ 2160(n - 1)Vn - 1 + 2160n(Vn mod 2b) and let X = W + 2L - 1 Note that X is an L-bit number. (9) Let p = X – ((X mod 2q) – 1). Note that p is congruent to 1 mod 2q. (10) If p < 2L - 1, then go to step (13). (11) Check whether p is prime. (12) If p is prime, go to step (15). (13) Let C = C + 1 and N = N + n + 1. (14) If C = 4096, then go to step (1). Otherwise, go to step (7). (15) Save the value of S and the value of C used to generate p and q. In [1154], the variable S is called the “seed,” C is called the “counter,” and N the “offset.” The point of this exercise is that there is a public means of generating p and q. For all practical purposes, this method prevents cooked values of p and q. If someone hands you a p and a q, you might wonder where that person got them. However, if someone hands you a value for S and C that generated the random p and q, you can go through this routine yourself. Using a one-way hash function, SHA in the standard, prevents someone from working backwards from a p and q to generate an S and C. This security is better than what you get with RSA. In RSA, the prime numbers are kept secret. Someone could generate a fake prime or one of a special form that makes factoring easier. Unless you know the private key, you won’t know that. Here, even if you don’t know a person’s private key, you can confirm that p and q have been generated randomly. ElGamal Encryption with DSA There have been allegations that the government likes the DSA because it is only a digital signature algorithm and can’t be used for encryption. It is, however, possible to use the DSA function call to do ElGamal encryption. Assume that the DSA algorithm is implemented with a single function call:
        DSAsign (p,q,g,k,x,h,r,s)
You supply the numbers p, q, g, k, x, and h, and the function returns the signature parameters: r and s. To do ElGamal encryption of message m with public key y, choose a random number, k, and call
        DSAsign (p,p,g,k,0,0,r,s)
The value of r returned is a in the ElGamal scheme. Throw s away. Then, call
        DSAsign (p,p,y,k,0,0,r,s)
Rename the value of r to be u; throw s away. Call
        DSAsign (p,p,m,1,u,0,r,s)
Throw r away. The value of s returned is b in the ElGamal scheme. You now have the ciphertext, a and b. Decryption is just as easy. Using secret key x, and ciphertext messages a and b, call
        DSAsign (p,p,a,x,0,0,r,s)
The value r is ax mod p. Call that e. Then call
        DSAsign (p,p,1,e,b,0,r,s)
The value s is the plaintext message, m. This method will not work with all implementations of DSA. Some may fix the values of p and q, or the lengths of some of the other parameters. Still, if the implementation is general enough, this is a way to encrypt using nothing more than digital signature function. RSA Encryption with DSA RSA encryption is even easier. With a modulus n, message m, and public key e, call
        DSAsign (n,n,m,e,0,0,r,s)
The value of r returned is the ciphertext. RSA decryption is the same thing. If d is the private key, then
        DSAsign (n,n,m,d,0,0,r,s)
returns the plaintext as the value of r. Security of DSA At 512-bits, DSA wasn’t strong enough for long-term security. At 1024 bits, it is.
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.