Cryptography

Lesson 1 of 81883–19497 min

Classical ciphers and why they fail

In 1883 Auguste Kerckhoffs, a Dutch-born linguist teaching in Paris, published La cryptographie militaire, a long article on what a field cipher for the telegraph age should look like. Among his six requirements was one that sounded almost reckless: the system must not depend on being secret, and it must be able to fall into the enemy's hands without harm.

Every serious cipher designed since follows that rule. The algorithm is public; only the key is secret. The ciphers before it show why.

Substitution, and why a huge key space is not enough

A shift cipher (the Caesar cipher) replaces each letter with the one k places later in the alphabet. With 26 letters there are only 25 useful keys, so an attacker simply tries them all: a brute-force or exhaustive key search. A monoalphabetic substitution cipher uses any permutation of the alphabet as the key, giving 26! ≈ 4 × 10²⁶ keys, roughly 2⁸⁸, far beyond brute force. It falls anyway, to frequency analysis: each plaintext letter always becomes the same ciphertext letter, so the statistics of the language survive. In English E, T and A dominate; in Spanish, E and A. Match the most frequent ciphertext symbols to them, use common pairs and short words to confirm, and the text unravels in minutes. The lesson is general: a large key space is necessary, but a cipher that leaks structure is broken however many keys it has.

python
def caesar(text, k):
    # shift each capital letter k places, leave everything else alone
    return "".join(chr((ord(c) - 65 + k) % 26 + 65) if c.isalpha() else c for c in text)

ct = caesar("MEET AT NOON", 3)
print(ct)                          # PHHW DW QRRQ
for k in range(1, 26):             # brute force: only 25 keys to try
    print(k, caesar(ct, -k))       # k = 3 gives MEET AT NOON
A shift cipher and the exhaustive key search that breaks it.

Polyalphabetic ciphers

The Vigenère cipher (16th century) hides the frequencies by changing the shift from letter to letter according to a keyword: letter i of the plaintext is shifted by letter i mod m of a key of length m. For centuries it was called indecipherable. In 1863 Friedrich Kasiski published a general attack: repeated fragments of plaintext that happen to line up with the same part of the key produce repeated fragments of ciphertext, and the distances between them are multiples of m. Once m is known, the ciphertext splits into m separate shift ciphers, each broken by frequency analysis.

Worked exercise

Encrypt with Vigenère

Encrypt NETWORK with the key KEY, numbering letters A = 0 to Z = 25. Then explain what an attacker who knows the key length gains.

Try it first, then reveal the solution one step at a time.

The one-time pad and perfect secrecy

Take the idea to its limit: a key as long as the message, chosen uniformly at random and never reused, combined with the plaintext by XOR (or addition mod 26). Gilbert Vernam patented the teleprinter version, granted in 1919. In 1949 Claude Shannon proved that such a one-time pad has perfect secrecy: the ciphertext gives no information at all about the plaintext, because every plaintext of that length is equally consistent with it. He also proved the price: perfect secrecy needs at least as much key as message. That is why practical ciphers aim for computational security instead, and why reusing a pad is fatal: C₁ ⊕ C₂ = P₁ ⊕ P₂, and the key disappears.

Key terms

Key space
The set of all possible keys; its size bounds a brute-force attack.
Frequency analysis
Breaking substitution by matching symbol frequencies to those of the language.
Polyalphabetic cipher
A cipher whose substitution changes with position, such as Vigenère.
Kerckhoffs's principle
A cipher must stay secure even if everything about it except the key is public.
Perfect secrecy
The ciphertext reveals nothing about the plaintext; requires a key at least as long as the message.

Check what you learned

  1. 1.A monoalphabetic substitution cipher has about 2⁸⁸ keys. Why is it still insecure?

  2. 2.What does Kerckhoffs's principle require?

  3. 3.Two messages were encrypted with the same one-time pad. What can an eavesdropper compute from the ciphertexts alone?

Practise it for the exam

Sources