Math Detours · Grade 9 · Around the corner · 24

The unbreakable code

Add a random key, bit by bit, and the message could be anything. Reuse the key once and it falls apart.

Name ____________________Date ____________

Tonight's idea

The ciphers in grade 6 fall to letter counting, because they scramble every letter the same way. The one-time pad, used properly, cannot be broken at all.

Write the message in bits. Here a letter is its place in the alphabet as five bits: A = 1 = 00001, H = 8 = 01000, Z = 26 = 11010. The key is a string of random bits, one per message bit, made by coin flips and shared in advance.

Combine message and key bit by bit with XOR, written \(\oplus\): 1 if the two bits differ, 0 if they match. To decode, XOR with the key again. A bit matches itself, so the key cancels.

cipher text = message \(\oplus\) key.   message = cipher text \(\oplus\) key.

Why unbreakable? Take any message of the right length. One key turns it into the cipher text you intercepted: cipher text \(\oplus\) that message. Every key is equally likely, so the cipher text fits every message equally well. The cipher text gives away only the length.

The catch is in the name: use each key once.

Watch one: sending HI

message 0 1 0 0 0 0 1 0 0 1 key 1 0 1 1 0 0 0 1 1 1 cipher text 1 1 1 1 0 0 1 1 1 0 H = 8 I = 9 ⊕
The cipher text has a 1 wherever message and key differ.

H is 01000 and I is 01001. Ten coin flips give the key 10110 00111. XOR each column: the cipher text is 11110 01110.

The receiver XORs that with the same key and gets 01000 01001 back, which is 8 and 9: H, I.

Turn numbers into bits and back with the switches at mathdetours.com/demos/binary.html.

Your turn

  1. Work out (a) \(10110 \oplus 01101\); (b) \(11111 \oplus 10101\); (c) \(01010 \oplus 01010\). What does XOR with 11111 do to a string?
  2. You receive 11101 11100. Your copy of the key says 11010 10011. Decode the two-letter message.
  3. A spy intercepts the one-letter cipher text 10011. (a) Which key would make the message Y (25 = 11001)? (b) Which key would make it N (14 = 01110)? (c) Both keys are equally likely coin-flip results. What has the spy learned about the answer?
  4. A careless sender uses the same five-bit key for two answers, each Y or N. The cipher texts are 10011 and 00100. (a) XOR the two cipher texts. (b) Compare your result with \(\text{Y} \oplus \text{N}\). What does the spy now know, without the key? (c) Explain why the key dropped out. (d) The spy later hears that the first answer was Y. Find the key and the second answer.

Stretch: try every key

A 100-letter message needs 500 key bits. How many different keys are there? Use \(2^{10} \approx 10^3\) to write the number roughly as a power of 10. A spy with unlimited computer time decodes the cipher text with every one of them. Why is the spy no wiser?

Answers

  1. (a) 11011. (b) 01010. (c) 00000. XOR with 11111 flips every bit.
  2. \(11101 \oplus 11010 = 00111 = 7\), which is G. \(11100 \oplus 10011 = 01111 = 15\), which is O. The message is GO.
  3. (a) \(10011 \oplus 11001 = 01010\). (b) \(10011 \oplus 01110 = 11101\). (c) Nothing. Each answer fits the cipher text with one key, and the two keys are equally likely.
  4. (a) \(10011 \oplus 00100 = 10111\). (b) \(\text{Y} \oplus \text{N} = 11001 \oplus 01110 = 10111\), the same. Two equal answers would give 00000. So the spy knows the two answers were different, though not yet which was which. (c) \((m_1 \oplus k) \oplus (m_2 \oplus k) = m_1 \oplus m_2\), because \(k \oplus k\) is all zeros. Reusing a key leaks the XOR of the two messages. (d) Key \(= 10011 \oplus 11001 = 01010\). Second answer \(= 00100 \oplus 01010 = 01110\), which is N.

Stretch. \(2^{500} = (2^{10})^{50} \approx (10^3)^{50} = 10^{150}\) keys. Trying them all produces every possible 500-bit string exactly once. Every 100-letter message is in that pile, each from its own key, and nothing marks the true one. The search hands back the list of all messages, which the spy already had.

← PreviousNext: When the calculator lies →