How Can Two Strangers Agree on a Secret in Public?

Powers seem better. If Sita calls out “2 to the power of my number is 1,024”, the class has to find the power. But powers of 2 grow steadily, 2, 4, 8, 16, …, so the class can home in: 2¹⁰ = 1,024, done. That is what logarithms are for. A power is hard to undo only if its answers jump about, so that being close tells you nothing.

There is a way to make powers jump about: keep only the remainder. On a clock with 7 hours, numbered 0 to 6, a number lands on the hour it leaves over on dividing by 7. Take the powers of 3 and keep only the remainders on dividing by 7:

Power	3¹	3²	3³	3⁴	3⁵	3⁶
Value	3	9	27	81	243	729
Remainder on dividing by 7	3	2	6	4	5	1

The remainders jump about, 3, 2, 6, 4, 5, 1, visiting every hour from 1 to 6 once. Each comes from the last by multiplying by 3 and keeping the remainder (6 × 3 = 18 leaves 4), so you never need the big numbers.

Now try the slow direction.

That is the whole idea in small: forwards is a few multiplications, backwards is a walk round the clock.

Clock arithmetic

Counting round a clock and keeping only what is left over is modular arithmetic, and the number of hours is the modulus. In the Grades 6–8 topic What Day of the Week Will Your 100th Birthday Be?, the week is a clock of 7. Mathematicians write

$$3^{4} \equiv 4 \pmod{7}$$

and read it “3⁴ is congruent to 4, modulo 7”: 81 and 4 leave the same remainder on dividing by 7 (81 − 4 = 77 = 11 × 7).

Why you may take the remainder at every step

The table above threw the big numbers away. Is that safe? Take 23 × 19 = 437, which leaves 3 on dividing by 7. Now use only the remainders: 23 leaves 2, 19 leaves 5, and 2 × 5 = 10 leaves 3. The same.

It always works. Picture the product as a rectangle with sides (some sevens + 2) and (some sevens + 5), cut into four pieces. Three of them contain a whole number of sevens, so they land on hour 0; only the corner piece, 2 × 5, decides the remainder. The same holds for any clock, so in a chain of multiplications you may replace any number by its remainder at any step.

Big powers quickly: square and multiply

To find 3¹⁷ on a 31-hour clock, there is a faster way than multiplying by 3 again and again, from the laws of indices: squaring a power doubles it, since $(3^{8})^{2} = 3^{16}$. Square again and again, taking the remainder each time:

Power	3¹	3²	3⁴	3⁸	3¹⁶
Remainder on dividing by 31	3	9	19	20	28

(9² = 81 leaves 19; 19² = 361 leaves 20; 20² = 400 leaves 28.) Then 3¹⁷ = 3¹⁶ × 3, so 28 × 3 = 84, which leaves 22. Four squarings and one multiplication, five in all, instead of sixteen.

This is square and multiply (or repeated squaring). Any power is a sum of 1, 2, 4, 8, 16, …, as in binary (22 = 16 + 4 + 2), so each binary digit of the power costs at most two multiplications. A power with 600 digits has about 2,000 binary digits: at most about 4,000 multiplications, a blink for a computer.

The slow way back

Going back, from 22 to “which power of 3?”, is called the discrete logarithm problem: a logarithm, because it asks for a power, and discrete, because on a clock the answers jump about instead of growing smoothly. The powers of 3 on the 31-hour clock go

3, 9, 27, 19, 26, 16, 17, 20, 29, 25, 13, 8, 24, 10, 30, 28, 22, 4, 12, 5, 15, 14, 11, 2, 6, 18, 23, 7, 21, 1

and 22 is the 17th. To find it, you walk the list. There are cleverer ways than walking every hop (below), but on a well-chosen clock even the best known is unimaginably slower than going forwards. Nobody has proved that no fast way exists: the whole internet bets on it.

First a picture people often use. Sita and Ram agree out loud on yellow paint. Each mixes in a secret color, red for Sita and blue for Ram, and holds up the mixture. Each then stirs their own secret color into the other’s mixture: both now have yellow + red + blue. The class saw yellow + red and yellow + blue, but paint can’t be unmixed. On a clock, mixing is raising to a power; unmixing is the discrete logarithm.

The game, with numbers

1. Out loud, Sita and Ram agree on a clock, 31, and a base, 3.
2. In secret, Sita picks a power, a = 17, and Ram picks b = 22.
3. Out loud, Sita calls out $3^{17}$, which on the 31-hour clock is 22. Ram calls out $3^{22}$, which is 14.
4. In secret, Sita raises Ram’s 14 to her own power 17. Ram raises Sita’s 22 to his own power 22. Both get 10.

The class, and any eavesdropper (Grade 9 Computing calls her Eve), heard 31, 3, 22 and 14. The secret 10 was never said. This is the Diffie–Hellman key exchange, published in 1976.

Why do both get the same number? Sita worked out $(3^{22})^{17}$ and Ram $(3^{17})^{22}$. By the law of indices both are $3^{22 \times 17} = 3^{374}$:

$$(g^{b})^{a} = g^{ab} = (g^{a})^{b}$$

and since remainders can be taken at any step, the clock doesn’t change that. The class has $g^{a}$ and $g^{b}$, but multiplying them gives $g^{a+b}$, the wrong power. Nobody knows a way to make $g^{ab}$ from them without first finding a or b.

How big is big enough?

On a 40-digit clock, Eve walking a billion powers a second would need around 3 × 10²³ years. Real clocks are far bigger, because Eve has better methods than walking. In 2015 the researchers behind an attack called Logjam prepared, in a week on several thousand computer cores, for one widely used 512-bit clock (about 155 digits), and could then find secret powers on it in about a minute each. They estimated that a 1,024-bit clock would cost around 100 million US dollars to prepare for, and recommended at least 2,048 bits, about 617 digits. Even then, Sita’s side is a few thousand multiplications.

The widget showed something it didn’t explain: on a clock with a prime number of hours, every base comes back to 1, never later than one hop short of the number of hours. Why?

Take the 7-hour clock and the base 3. Multiply each hour from 1 to 6 by 3 and keep the remainder:

Hour	1	2	3	4	5	6
× 3 lands on	3	6	2	5	1	4

The same six hours, shuffled. They must be. None lands on 0, because 7 is prime and divides neither 3 nor any hour from 1 to 6, so it can’t divide their product. And if two hours x and y landed together, 7 would divide 3(x − y); since 7 doesn’t divide 3, it would have to divide x − y, impossible for two different hours from 1 to 6. (Both steps use one fact about primes: a prime that divides a product divides one of its factors, which follows from every number being built from primes in only one way, as in Is There a Biggest Prime Number?)

Multiply each row together: the bottom row is the same numbers reordered, so its product is the same:

$$(3 \times 1)(3 \times 2)(3 \times 3)(3 \times 4)(3 \times 5)(3 \times 6) \equiv 1 \times 2 \times 3 \times 4 \times 5 \times 6 \pmod 7$$

The left side is $3^{6} \times 720$, the right side 720. Their difference, $(3^{6} - 1) \times 720$, is a multiple of 7, and 7 doesn’t divide 720 = 1 × 2 × … × 6, so by the same fact it divides $3^{6} - 1$:

$$3^{6} \equiv 1 \pmod 7$$

Nothing used anything special about 3 or 7, only that the clock is prime and the base isn’t a multiple of it. So for any prime p and any base a that isn’t a multiple of p:

$$a^{p-1} \equiv 1 \pmod p$$

This is Fermat’s little theorem, and it explains the widget. A base that first comes back after k hops repeats its cycle and must still be at 1 after p − 1 hops, so k divides p − 1. A base that visits every hour first is a generator (or primitive root) of the clock: 3 is one for the 31-hour clock, which is why Sita and Ram used it.

Grade 9 Computing’s padlock, RSA (1977), lets anyone lock a message with Ram’s public numbers that only Ram can open. It rests on Fermat’s little theorem too. With toy primes:

Ram secretly picks two primes, 11 and 17, and multiplies them: 187. He works out (11 − 1) × (17 − 1) = 160, picks a locking power, 7, and an unlocking power that multiplies with it to one more than a multiple of 160: 7 × 23 = 161, so 23. He publishes 187 and 7, his open padlock, and keeps 23.

Sita’s message is the number 42. She locks it: $42^{7}$ on the 187-hour clock is 15, and she sends 15. Ram unlocks: $15^{23}$ on the same clock is 42.

Why? Ram has worked out $42^{7 \times 23} = 42^{161} = 42^{160} \times 42$. On the 11-hour clock, $42^{10} \equiv 1$ by Fermat, so $42^{160} = (42^{10})^{16} \equiv 1$. On the 17-hour clock, $42^{16} \equiv 1$, so $42^{160} = (42^{16})^{10} \equiv 1$. A number 1 more than a multiple of 11 and of 17 is 1 more than a multiple of 187, since 11 and 17 share no factor. So $42^{160} \equiv 1 \pmod{187}$, and $42^{161} \equiv 42$: the message comes back.

To find 23, Eve needs 160, so the two primes. With 187 that takes a minute; a real clock is two primes each hundreds of digits long, and Grade 9 Computing’s The mathematics behind the padlock shows why finding them is hopeless. (Computers also use remainders on the two primes separately to make Ram’s side faster; How Many Eggs Were in the Basket? tells how.)

A base that visits too few hours

On the 31-hour clock the base 2 visits only 5 hours, so whatever the secrets, the key is one of 5 numbers and Eve tries them all. Since a cycle divides p − 1, a clock where p − 1 is twice a prime has no short cycles except those of the bases 1 and p − 1 (lengths 1 and 2), which nobody would choose; every other base visits at least half the hours (the widget’s 40-digit clock is one).

The stranger in the middle

Suppose Eve can stop Sita’s and Ram’s calls and speak in their voices. She swaps keys with Sita, pretending to be Ram, and with Ram, pretending to be Sita, then reads everything and passes it on. The arithmetic is perfect; Diffie–Hellman alone just can’t tell who is calling. That is why a website also signs its numbers, and why your phone checks the signature against a certificate (Grade 9 Computing, HTTPS and certificates).

A new kind of computer

In 1994 the mathematician Peter Shor found a method by which a quantum computer, if one big enough could be built, would solve the discrete logarithm and find the primes behind RSA quickly. As of 2026 none comes close: the demonstrations so far have only handled tiny numbers, such as factoring 21, and even those were simplified using the answer known in advance. To be ready, in August 2024 the United States’ standards agency, NIST, published ML-KEM, a way for two parties to agree on a key over a public channel that rests on a different hard problem, and Google Chrome since version 131, with websites that support it, agrees its keys with ML-KEM and a Diffie–Hellman exchange (X25519, below) together.

• What Don’t Mathematicians Know About Prime Numbers? The primes that every padlock is built from, and the questions about them nobody can answer yet.
• How Many Eggs Were in the Basket? The Chinese remainder theorem: one number from its remainders on several clocks, and how it speeds up RSA.
• Can You Write a Message Only a Friend Can Read? (Grades 6–8) The old ciphers, where both friends must share a key first: the problem this topic solves.
• Is There a Biggest Prime Number? (Grades 6–8) Why primes never run out, and why every number is built from them in one way only.
• Grade 9 Computing, Secrets and Security: the padlock picture, digital signatures, HTTPS and end-to-end encryption, the uses of everything on this page.
• Grade 10 Math, Indices: the laws of indices that make $(g^{a})^{b} = (g^{b})^{a}$.