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

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 axgkx (mod p), and b/axykM/axgxkM/gxkM (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

[an error occurred while processing this directive]