ElGamal

The ElGamal scheme [518,519] can be used for both digital signatures and encryption; it gets its security from the difficulty of calculating discrete logarithms in a finite field.

To generate a key pair, first choose a prime, p, and two random numbers, g and x, such that both g and x are less than p. Then calculate 

        y = gx mod p

The public key is y, g, and p. Both g and p can be shared among a group of users. The private key is x.

ElGamal Signatures

To sign a message, M, first choose a random number, k, such that k is relatively prime to p - 1. Then compute 

        a = gk mod p
and use the extended Euclidean algorithm to solve for b in the following equation: 
        M = (xa + kb) mod (p - 1)

The signature is the pair: a and b. The random value, k, must be kept secret.

To verify a signature, confirm that 

        yaab mod p = gM mod p

Each ElGamal signature or encryption requires a new value of k, and that value must be chosen randomly. If Eve ever recovers a k that Alice used, she can recover Alice's private key, x. If Eve ever gets two messages signed or encrypted using the same k, even if she doesn't know what it is, she can recover x.

This is summarized in Table 19.5.

For example, choose p = 11 and g = 2. Choose private key x = 8. Calculate 

	  y = gx mod p = 28 mod 11 = 3
The public key is y = 3, g = 2, and p = 11.

To authenticate M = 5, first choose a random number k = 9. Confirm that gcd(9, 10) = 1. Compute 

	  a = gk mod p = 29 mod 11 = 6
and use the extended Euclidean algorithm to solve for b: 
        M = (xa + kb) mod (p - 1)
	5 = (8 * 6 + 9 * b) mod 10
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
        3663 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 Diffle-Hellman key exchange (see Section 22. 1), except that y is part of the key, and the encryption is multiplied by yk. 


	      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
This page from Bruce Schneier, Applied Cryptography 2nd Ed, 1996, John Wiley & Sons. Section 19.3, Pages 476 - 478. To order, click here.