ElGamal encryption turns Diffie–Hellman key exchange into public-key encryption: a sender derives a shared secret from the recipient’s public key, then masks plaintext with that secret. section 8.3.1
The scheme uses two values in its ciphertext and reverses the masking during decryption:
- Encryption sends c = (B, m · S mod p), where B = g^b mod p and S = g^(ab) mod p. section 8.3.1
- Decryption recomputes S with the recipient’s private key a, calculates S⁻¹ in Zp*, and recovers m = c₂ · S⁻¹ mod p. section 8.3.1
- Security relies on the difficulty of recovering exponents from public group values through the discrete logarithm problem. section 8.3.1
Sender-to-recipient flow
Bob uses Alice’s published public key and his private exponent to form B and the shared secret S; Alice uses her private key to reconstruct S and undo the multiplication. section 8.3.1
Equation 8.7
\[\begin{aligned} c &= (c_1, c_2) \notag\\ &= (B, m \cdot S \bmod p) \notag\\ &= (g^b \bmod p, m \cdot g^{ab} \bmod p) \label{equation:elgamal-encrypt} \end{aligned}\]Inspect the ciphertext equation showing the two transmitted components and their shared-secret construction. section 8.3.1
