Can You Write a Message Only a Friend Can Read?

A note a stranger finds

A message written in a hidden way is a cipher (the secret rule) turned into ciphertext (the scrambled message). Anisha’s rule, moving every letter the same number of places, is the shift cipher, and the number of places is its key. Your teacher has the ciphertext but not the key.

Here is the stranger’s problem for you. On the way home you find a note on the bus stop bench:

SIZEX KYV TIZTBVK SRK FE JRKLIURP

You don’t know the shift. Turn the wheel until it reads.

So the stranger needs at most 25 tries, and with a little cleverness, one. That is the first lesson of secret writing: a cipher with few keys is no secret at all.

Going round the end

Something odd happens near the end of the alphabet. Move X three places: Y, Z, and then? There is no letter after Z, so the alphabet starts again: X becomes A, Y becomes B, Z becomes C. The alphabet is not a line but a circle, like the numbers on a clock.

To do sums with it, give each letter a number. Start at 0, as a clock’s hand starts at the top: A is 0, B is 1, C is 2, and so on to Z, which is 25.

Now a shift of 3 is just adding 3. M is 12, and 12 + 3 = 15, which is P. But X is 23, and 23 + 3 = 26: there is no letter 26.

Go round the clock and look where you land. After 25 (Z) comes 0 (A) again, so 26 lands on 0, 27 on 1, 28 on 2. Grade 6’s division says exactly where: divide by 26 and keep the remainder. 26 = 26 × 1 + 0, so 26 lands on A. 28 = 26 × 1 + 2, so Z + 3 is C. And 30 = 26 × 1 + 4 lands on E, however you got to 30.

The rule for any shift, then, is: change the letter to its number, add the key, divide by 26 and keep the remainder, and change it back to a letter.

Undoing a shift

To read Anisha’s note you moved every letter 3 places back. But there is another way, with no going backwards at all: move every letter 23 places forward. The two are the same, because 3 + 23 = 26, a full turn of the clock, which brings every letter back where it started.

Check it on D: D is 3, and 3 + 23 = 26, which leaves 0: A, the letter D came from. Every shift has an undo shift that adds up with it to 26: 1 and 25, 2 and 24, 10 and 16. And one shift is its own undo: 13, since 13 + 13 = 26.

Remainders do the counting

What you have been doing has a name. Arithmetic where you divide by a fixed number and keep only the remainder is modular arithmetic, or clock arithmetic, and the fixed number is the modulus. Topic 4, Why Do the Divisibility Tests Work?, used it with modulus 9; here the modulus is 26, the number of letters. Mathematicians write “30 mod 26 = 4” for “30 leaves 4 when divided by 26”, and say “30 and 4 are the same, mod 26”.

An ordinary clock is the same arithmetic with modulus 12. If the hour hand points to 7 now, then in 8 hours it points to 3, because 7 + 8 = 15, and 15 leaves 3 when divided by 12.

Why does keeping only the remainder never go wrong? Because a full turn of the clock changes nothing. Any number is some whole turns of 26 plus a remainder: 30 is one turn and 4 more. The whole turns bring you back to where you started, so only the remainder decides where you land. That is also why two shifts add up: 20 places, then 10 more, is 30 places, which is one turn and 4.

Why only 25 keys?

Now the stranger’s easy job makes sense. A shift of 26 is a full turn, the same as a shift of 0. A shift of 27 is the same as 1, a shift of 28 the same as 2. Every whole number lands on one of the 26 remainders, 0 to 25, so there are only 26 different shift ciphers, and one of them (0) leaves the note as it was. Twenty-five keys that hide anything, and a stranger can try them all before her tea gets cold.

Times instead of plus

If adding gives only 25 keys, what about multiplying? Here is a new cipher: change each letter to its number, multiply by 3, divide by 26 and keep the remainder.

So NEPAL becomes NMTAH. Not a shift: N stays N, E jumps 8 places, P only 4. The whole secret alphabet, with A to Z on top and their secret letters underneath, is jumbled:

Look along the bottom row: every letter of the alphabet is there, each exactly once. That matters. When Anisha’s friend sees a secret T, only one plain letter could have made it (P), so the note can be read back.

Now try multiplying by 2 instead. Then B (1) becomes 2, C. But O (14) becomes 28, which leaves 2: C again. B and O have the same secret letter, and when your friend sees a C, she can’t tell which one you meant. Worse, CAT and PNG both come out as EAM. A cipher your friend can’t read back is no use.

Why the odd ones, but not 13?

The multipliers that fail are the even ones and 13. And 26 = 2 × 13. So a multiplier fails exactly when it shares a factor with 26. Why?

When it shares a factor, two letters clash. Take any even multiplier, say 2. Multiply N (13) by it: 2 × 13 = 26, a full turn, so N lands on 0, the same place as A. Every even number times 13 is a multiple of 26 (4 × 13 = 52 = 2 × 26), so for every even multiplier, N lands on A. For 13, C (2) does it: 13 × 2 = 26, so C lands on A too. A shared factor lets some letter other than A make a whole number of turns, and land on A.

When it shares no factor, nothing clashes. Suppose two different letters, numbered a and b, did land in the same place when multiplied by k. Then k × a and k × b leave the same remainder, so their difference, k × (a − b), is a whole number of turns: a multiple of 26 = 2 × 13. 2 and 13 are primes, and a prime that divides a product of two numbers divides one of them (a rule Euclid proved, which topic 5, Is There a Biggest Prime Number?, meets), so the 2 and the 13 must each come from k or from a − b. If k has no 2 and no 13 in it, they must both be in a − b, so a − b is a multiple of 26. But a and b are numbers from 0 to 25, so they are less than 26 apart. The only multiple of 26 that small is 0, so a = b: it was the same letter after all. No two different letters can clash.

Two numbers that share no factor except 1 are called coprime. The rule is: multiplying by k makes a cipher, mod 26, exactly when k and 26 are coprime.

Undoing a multiplication

To undo a shift you add the undo shift. To undo multiplying by 3, you multiply again, by a number that brings every letter home. Which number? One where 3 × it is one more than a whole number of turns: 3 × 9 = 27 = 26 + 1. So multiplying by 3 and then by 9 is the same as multiplying by 27, which leaves 1: every letter back where it was. Check it on NMTAH: N (13) × 9 = 117 leaves 13, N; M (12) × 9 = 108 leaves 4, E. NEPAL comes back.

Each of the twelve good multipliers has its own undo number. For 7 it is 15, since 7 × 15 = 105 = 4 × 26 + 1. An even multiplier has none: an even number times anything is even, and an even number can never be one more than a multiple of 26, which is even too. Nor has 13: 13 times anything is a multiple of 13, and so is every multiple of 26, so the two are never just 1 apart.

Multiply, then shift

Put the two ciphers together: multiply by one of the 12 good numbers, then shift by any of 26. That makes 12 × 26 = 312 keys, more than twelve times as many as the shift cipher. Better, but a patient stranger with a pencil could still try them all in an afternoon, and a computer does it in less than a blink.

Add a space, and 3 stops working

Anisha decides that spaces give too much away (a three-letter word is probably THE), so she hides them too: the space becomes a 27th symbol, numbered 26, and her modulus becomes 27. Is multiplying by 3 still safe?

No. Now 27 = 3 × 3 × 3, and 3 shares a factor with it. A (0) gives 0. J (9) gives 27, a full turn: 0 again. S (18) gives 54, two full turns: 0 again. Three letters on one place. With 27 symbols the good multipliers are the 18 numbers from 1 to 26 that 3 doesn’t divide, and 2, which failed with 26 letters, now works.

A different shift for every letter

The shift cipher fails because every letter moves the same way: E always becomes the same secret letter, and a word guessed opens the whole note. So move each letter by a different shift, taken in turn from a key word. With the key word MOMO, the shifts are M (12), O (14), M (12), O (14), then round again:

SEE YOU AT NINE becomes ESQ MAI MH ZWZS. The two E’s of SEE have become different letters, S and Q, and the S at the end of the secret note came from an E, not an S. This is the idea of the Vigenère cipher (named after the Frenchman Blaise de Vigenère, though the Italian Giovan Battista Bellaso described it first, in 1553), and it is much harder to crack than any shift. Still, a short key word repeats, and its repeating pattern can be found (Grade 9 Computing shows how ciphers are broken by counting letters). But with a key as long as the message, chosen at random, kept secret and used only once, it becomes the one-time pad, which can’t be broken at all.

• What Day of the Week Will Your 100th Birthday Be? Clock arithmetic with modulus 7, on the calendar.
• Why Do the Divisibility Tests Work? Remainders mod 9 and mod 11, and why the digits know.
• Is There a Biggest Prime Number? The primes, which make a modulus where nothing clashes, never run out.
• How Can Two Strangers Agree on a Secret in Public? (Grades 9–12) Clock arithmetic with powers, and how the internet keeps messages safe.
• How Does a Barcode Catch a Typing Mistake? (Computing, Going Further) Remainders that catch mistakes instead of hiding messages.
• How Does a Computer Roll a Die? (Computing, Going Further) Multiply, add, keep the remainder, over and over.
• Secrets and Security (Grade 9 Computing) The Caesar cipher in Python, breaking ciphers by counting letters, keys and their lengths, and the encryption on your phone.