ElGamal Example p is a prime, g is a primitive root of p, a is a random secret number. p = 2789; g = 10; a = 2351 g^a % p = 10^2351 (% 2789) ≡1980 Now we have what is known as a 'public key' (p, g, g^a%p). The public key is P = (p ← 2789, g ← 10, g^a%p ← 1980), the secret key is a (2351). Next, we encrypt a message m = 832 as follows (k is randomly chosen, m has to be less than p): k = 1520 γ = 10^1520 (% 2789) ≡ 2300 δ ≡ 832 x 1980^1520 (% 2789) ≡ 2271 c = (γ ← 2300, δ ← 2271) The ciphertext, c, is then sent to the recipient. The recipient can then calculate m from this. The message is calculated by: m ≡ 2300^(2789-1-2351) x 2271 ≡ (2300^437) x 2271 (% 2789) ≡ 832