ElGamal Example p is a prime, g is a primitive root of p, a is a random secret number (must be less than p). p = 2789; g = 10; a = 304 g^a % p = 10^304 (% 2789) ≡ 1161 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 ← 1161), the secret key is a (304). 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 1161^1520 (% 2789) ≡ 83 c = (γ ← 2300, δ ← 83) 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-304) x 83 ≡ (2300^2484) x 83 (% 2789) ≡ 832
When looking for 6 digit numbers, it will either be the public key, the cipher text or, possibly, p. Possible primes, p > 304, with a prime root of 10: 313, 337, 367, 379, 383, 389, 419, 433, 461, 487, 491, 499, 503, 509, 541, 571, 577 ...