ElGamal Example (explained easier) This scheme requires several variables. a is a secret key less than the value of p. We will assume it is 304 since p must be greater than it. g is the generator variable. Nokia has told us its value is 10. p is a large prime number that Nokia have told us is >304. For our situation, p is the most important. It is a prime number that must have 'g' as a primitive root. For fun, we will select 2789. m is our encrypted message (if there is one) that has to be less than p. For fun we'll choose 832 (from taxi) k is a prime number used for encrypting the message. It also has the condition it must be less than p and gcd(k, p − 1) = 1. For fun, we will choose 15 (from truck). So let's do it. Generate Public Key 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). Encrypt Message Next, we encrypt a message m = 832 as follows: k = 15 γ = 10^15 (% 2789) ≡ 1063 δ ≡ 832 x 1161^15 (% 2789) ≡ 181 c = (γ ← 1063, δ ← 181) The ciphertext, c, is then sent to the recipient. Decrypt Message The recipient can then calculate m from this. The message is calculated by: m ≡ 1063^(2789-1-304) x 181 ≡ (1063^2484) x 181 (% 2789) ≡ 832 In summary -- to get your 6 digits for the competition: Generating Public Key <p><10><10^a % p> (6 digits) In this situation, p is most likely 3 digits. Also, a or y is likely 15 (where else would it be used?) This means you can get p from the list below: 313, 337, 367, 379, 383, 389, 419, 433, 461, 487, 491, 499, 503, 509, 541, 571, 577, 593, 619, 647, 659, 701, 709, 727, 743, 811, 821, 823, 857, 863, 887, 937, 941, 953, 971, 977, 983. Generating Cipher Key <10^k % p><m*(10^a%p)^k %p> (6 digits) In this situation, p is most likely 4 digits. This means Nokia has given us the p from the 'colors on the wall'.