How ElGamal works
Taher Elgamal's system rests on a different hard problem from factoring: the discrete logarithm. Working out gx mod p is quick. Going backwards from the answer to find x is very slow when p is big.
Making the keys (the receiver)
- Pick a large prime p and a base g. Both are public.
- Pick a secret number x. This is the private key.
- Publish y = gx mod p. The public key is (p, g, y).
Locking a message (the sender)
- Pick a fresh random number k for this message only, and keep it secret.
- Send c1 = gk mod p. On its own this reveals nothing.
- Make the shared secret s = yk mod p, and send c2 = m × s mod p. The ciphertext is the pair (c1, c2).
Unlocking (the receiver)
- Rebuild the shared secret from the other side: s = c1x mod p. It's the same number, because (gk)x = (gx)k.
- Divide it back out: m = c2 × s−1 mod p, where s−1 is the number that gives remainder 1 when multiplied by s.
Breaking it: two ways in
An eavesdropper needs s, so they need either secret. They can find the receiver's x from y = gx, or the sender's k from c1 = gk. Each is a discrete logarithm, and either one gives the same s.
A discrete log is only practical when p − 1 splits into fairly small primes. The Pohlig–Hellman method then breaks the search into one small search per prime factor and glues the answers together with the Chinese Remainder Theorem. Puzzles pick primes like that.
The whole thing with tiny numbers
What the puzzle gives you
An ElGamal puzzle gives a public key (p, g, y) and a ciphertext that comes as a pair of numbers. Names vary a lot between write-ups, so each box lists the usual ones.
Already know x or k?
If the puzzle hands you either secret, fill it in and the worksheet skips the search.
Choose a way in
Either secret unlocks the message. Pick the one whose number you trust you copied correctly; the answer is the same.
Break p − 1 into primes
The discrete-log search splits into one smaller search for each prime factor of p − 1. The biggest factor decides how long it takes, so that's the first thing to find out.
The discrete logarithm
Show the Pohlig–Hellman pieces
For each prime power dividing the order of the base, the page raises both sides to a power that leaves a much smaller problem. Small pieces are solved by baby-step giant-step, a lookup table of powers. Big pieces are solved by Pollard's rho, which takes random-looking walks on every processor core until two walks land on the same number. The Chinese Remainder Theorem then glues the pieces into one exponent.
The shared secret, and the message
With one secret in hand, rebuild the shared secret s and divide it back out of c2.
Read the message
m is a number, and the puzzle decides how it turns back into words or coordinates. Try the readings below. If the puzzle says how the message was encoded, use that one.
If none of these look like anything
Decryption scrambles everything when even one digit of an input is off, so a wrong input doesn’t give a slightly wrong answer; it gives noise. Recount the digits of each number against the puzzle (the counts are shown next to every box).
If the inputs are right, the message may use a different encoding: the puzzle text usually says which one. Lining the blocks up from the end, or skipping some digits first, helps when a short message is tacked onto something else.
If every digit matches the puzzle and every reading is still noise, you may be using the wrong system. Check that the puzzle really describes this one: what it calls each number, how many public numbers it gives, and how it says the message was locked.