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
The solution is b = 3, and the signature is the pair: a = 6 and b = 3. Table 19.5 ElGamal Signatures
| Public Key:
p | prime (can be shared among a group of users)
g | <p (can be shared among a group of users)
y | = gx mod p
| Private Key:
x | <p
| Signing:
k | choose at random, relatively prime to p - 1
a | (signature) = gk mod p
b | (signature) such that M = (xa + kb) mod (p - 1)
| Verifying:
Accept as valid if yaab mod p = gM mod p
To verify a signature, confirm that yaab mod p = gM mod p 36 63 mod 11 = 25 mod 11 A variant of ElGamal for signatures is in [1377]. Thomas Beth invented a variant of the ElGamal scheme suitable for proofs of identity [146]. There are variants for password authentication [312], and for key exchange [773]. And there are thousands more (see Section 20.4). ElGamal Encryption A modification of ElGamal can encrypt messages. To encrypt message M, first choose a random k, such that k is relatively prime to p - 1. Then compute a = gk mod p b = ykM mod p The pair, a and b, is the ciphertext. Note that the ciphertext is twice the size of the plaintext. To decrypt a and b, compute M = b/ax mod p Since ax ≡ gkx (mod p), and b/ax ≡ ykM/ax ≡ gxkM/gxk ≡ M (mod p), this all works (see Table 19.6). This is really the same as Diffie-Hellman key exchange (see Section 22.1), except that y is part of the key, and the encryption is multiplied by yk. Speed Table 19.7 gives sample software speeds of ElGamal [918]. Table 19.6 ElGamal Encryption
| Public Key:
p | prime (can be shared among a group of users)
g | < p (can be shared among a group of users)
y | = gx mod p
| Private Key:
x | < p
| Encrypting:
k | choose at random, relatively prime to p - 1.
a | (ciphertext) = gk mod p
b | (ciphertext) = ykM mod p
| Decrypting:
M (plaintext) = b/ax mod p
Patents ElGamal is unpatented. But, before you go ahead and implement the algorithm, realize that PKP feels that this algorithm is covered under the Diffie-Hellman patent [718]. However, the Diffie-Hellman patent will expire on April 29, 1997, making ElGamal the first public-key cryptography algorithm suitable for encryption and digital signatures unencumbered by patents in the United States. I can hardly wait. ### 19.7 McEliece In 1978 Robert McEliece developed a public-key cryptosystem based on algebraic coding theory [1041]. The algorithm makes use of the existence of a class of error-correcting codes, known as Goppa codes. His idea was to construct a Goppa code and disguise it as a general linear code. There is a fast algorithm for decoding Goppa codes, but the general problem of finding a code word of a given weight in a linear binary code is NP-complete. A good description of this algorithm can be found in [1233]; see also [1562]. Following is just a quick summary. Let dH(x,y) denote the Hamming distance between x and y. The numbers n, k, and t are system parameters. The private key has three parts: G’ is a k * n generator matrix for a Goppa code that can correct t errors. P is an n * n permutation matrix. S is a k * k nonsingular matrix. The public key is a k * n matrix G: G = SG’P. Plaintext messages are strings of k bits, in the form of k-element vectors over GF(2). To encrypt a message, choose a random n-element vector over GF(2), z, with Hamming distance less than or equal to t. c = mG + z To decrypt the ciphertext, first compute c’ = cP-1. Then, using the decoding algorithm for the Goppa code, find m’ such that dH(m’ G, c’) is less than or equal to t. Finally, compute m = m’S-1. In his original paper, McEliece suggested that n = 1024, t = 50, and k = 524. These are the minimum values required for security. Table 19.7 ElGamal Speeds for Different Modulus Lengths with a 160-bit Exponent (on a SPARC II)
| 512 bits | 768 bits | 1024 bits
--- | --- | --- | ---
Encrypt | 0.33 sec | 0.80 sec | 1.09 sec
Decrypt | 0.24 sec | 0.58 sec | 0.77 sec
Sign | 0.25 sec | 0.47 sec | 0.63 sec
Verify | 1.37 sec | 5.12 sec | 9.30 sec
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.