The solution is b = 3, and the signature is the pair: a = 6 and b = 3.

To verify a signature, confirm that

y^aa^b mod p = g^M mod p

3⁶ 6³ mod 11 = 2⁵ 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 = g^k mod p

b = y^kM 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/a^x mod p

Since a^x ≡ g^kx (mod p), and b/a^x ≡ y^kM/a^x ≡ g^xkM/g^xk ≡ 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 y^k.

Speed

Table 19.7 gives sample software speeds of ElGamal [918].

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 d_H(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 d_H(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.