# ElGamal public-key encryption

The EIGamal public-key encryption scheme can be viewed as Diffie-Heilman key agreement (§12.6.1) in key transfer mode (cf. Note 8.23(i)). Its security is based on the intractability of the discrete logarithm problem (see §3.6) and the Diffie-Heilman problem (§3.7). The basic EIGamal and generalized EIGamal encryption schemes are described in this section.

## Basic ElGamal encryption

8.17 Algorithm Key generation for EIGamal public-key encryption

SUMMARY: each entity creates a public key and a corresponding private key.

Each entity A should do the following:

• 1. Generate a large random prime p and a generator a of the multiplicative group Z* of the integers modulo p (using Algorithm 4.84).
• 2. Select a random integer a, 1 < a < p - 2, and compute a" mod p (using Algorithm 2.143).
• 3. A’s public key is (p, a, a"); A’s private key is a.

8.18 Algorithm EIGamal public-key encryption

SUMMARY: В encrypts a message m for A, which A decrypts.

• 1. Encryption. В should do the following:
• (a) Obtain A’s authentic public key (p. a, a").
• (b) Represent the message as an integer m in the range {0,1,... ,p - 1}.
• (c) Select a random integer к, 1 < к < p - 2.
• (d) Compute 7 = ak mod p and S = m ■ (aa)k mod p.
• (e) Send the ciphertext c = (7, S) to A.
• 2. Decryption. To recover plaintext m from c, A should do the following:
• (a) Use the private key a to compute yp 1 0 mod p (note: yp 1 0 = y~a = a~ak).
• (b) Recover m by computing (7-0) • S mod p.

Proof that decryption works. The decryption of Algorithm 8.18 allows recovery of original plaintext because 8.19 Example (EIGamal encryption with artificially small parameters)

Key generation. Entity A selects the prune p = 2357 and a generator a = 2 of Ъ*2ггл. A chooses the private key a = 1751 and computes A’s public key is (p = 2357, a = 2, a° = 1185).

Encryption. To encrypt a message m = 2035, В selects a random integer к = 1520 and computes and В sends 7 = 1430 and S = 697 to ,4.

Decryption. To decrypt, A computes and recovers m by computing 8.20 Note (common system-wide parameters) All entities may elect to use the same prune p and generator a, in which case p and a need not be published as part of the public key. This results in public keys of smaller sizes. An additional advantage of having a fixed base a is that exponentiation can then be expedited via precomputations using the techniques described in §14.6.3. A potential disadvantage of common system-wide parameters is that larger moduli p may be warranted (cf. Note 8.24).

• 8.21 Note (efficiency o/ElGamal encryption)
• (i) The encryption process requires two modular exponentiations, namely ak mod p and (aa)'; mod p. These exponentiations can be sped up by selecting random exponents к havmg some additional structure, for example, having low Hamming weights. Care must be taken that the possible number of exponents is large enough to preclude a search via a baby-step giant-step algorithm (cf. Note 3.59).
• (ii) A disadvantage of ElGamal encryption is that there is message expansion by a factor of 2. That is, the ciphertext is twice as long as the corresponding plaintext.
• 8.22 Remark (randomized encryption) ElGamal encryption is one of many encryption schemes which utilizes randomization in the encryption process. Others include McEliece encryption (§8.5), and Goldwasser-Micali (§8.7.1), and Blum-Goldwasser (§8.7.2) probabilistic encryption. Deterministic encryption schemes such as RSA may also employ randomization in order to circumvent some attacks (e.g., see §8.2.2(ii) and §8.2.2(iii)). The fundamental idea behind randomized encryption (see Definition 7.3) techniques is to use randomization to increase the cryptographic secirrity of an encryption process through one or more of the following methods:
• (i) increasing the effective size of the plaintext message space;
• (ii) precluding or decreasing the effectiveness of chosen-plaintext attacks by virtue of a one-to-many mapping of plaintext to ciphertext; and
• (iii) precluding or decreasing the effectiveness of statistical attacks by leveling the a priori probability distribution of inputs.
• 8.23 Note (security of ElGamal encryption)
• (i) The problem of breaking the ElGamal encryption scheme, i.e., recovering m given p, a, a", 7, and 5, is equivalent to solving the Diffie-Heilman problem (see §3.7). In fact, the ElGamal encryption scheme can be viewed as simply comprising a Diffie- Hellman key exchange to determine a session key aak, and then encrypting the message by multiplication with that session key. For this reason, the security of the El- Gamal encryption scheme is said to be based on the discrete logarithm problem in Z*, although such an equivalence has not been proven.
• (ii) It is critical that different random integers к be used to encrypt different messages. Suppose the same к is used to encrypt two messages mi and m2 and the resulting ciphertext pairs are (71, <5r) and (72, <\$2)- Then d'x/82 = mi/m2, and m2 could be easily computed if mi were known.
• 8.24 Note (recommended parameter sizes) Given the latest progress on the discrete logarithm problem in Z* (§3.6), a 512-bit modulus p provides only marginal security from concerted attack. As of 1996, a modulus p of at least 768 bits is recommended. For long-term security, 1024-bit or larger moduli should be used. For common system-wide parameters (cf. Note 8.20) even larger key sizes may be warranted. This is because the dominant stage in the index-calculus algorithm (§3.6.5) for discrete logarithms in Z* is the precomputation of a database of factor base logarithms, following which individual logarithms can be computed relatively quickly. Tints computing the database of logarithms for one particular modulus p will compromise the secrecy of all private keys derived using p.