Substitution Cipher

3 min read#cryptography

Replace each letter by any other under a fixed scrambled alphabet — an enormous keyspace that frequency analysis still cracks.

Contents

Substitution Cipher

A substitution cipher replaces every letter with another according to a fixed but arbitrary permutation of the alphabet. Unlike the Caesar Cipher, which only rotates the alphabet, here the mapping can be any scramble at all:

plain:  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
cipher: Q W E R T Y U I O P A S D F G H J K L Z X C V B N M

So HELLO becomes ITSSG. Decryption just runs the table backwards. Because each plaintext letter always maps to the same ciphertext letter, this is called a monoalphabetic cipher.

A staggering keyspace

How many keys are there? Any of the 26 letters can map to the first slot, any of the remaining 25 to the next, and so on — a full permutation:

26! = 403{,}291{,}461{,}126{,}605{,}635{,}584{,}000{,}000 \approx 4 \times 10^{26}.

That is about 88 bits of key, more than 10^{26} possibilities. Brute force is utterly hopeless — you could try a billion keys a second since the Big Bang and not scratch it. Surely this one is secure?

The crack: frequency analysis

In English, letters are wildly uneven. E alone is about 12.7% of text; T, A, O, I, N follow; J, Q, X, Z are rare. A monoalphabetic cipher renames the letters but cannot change their counts: whatever symbol stands for E will be the most common symbol in the ciphertext. Match the ciphertext's histogram against English's, throw in common pairs (TH, HE) and one-letter words (A, I), and the message unravels.

English letter frequencies (%)
The fingerprint of English. A substitution cipher relabels the bars but never flattens them — so the tallest ciphertext bar is almost certainly E.

This is exactly why the cipher is weak despite its colossal keyspace: it has high key entropy but leaks almost everything about the plaintext's structure. The connection to Entropy is the lesson — what matters is not how many keys exist, but how much the ciphertext still tells you about the message. The only way to truly plug the leak is to make the key as informative as the message itself, which leads to the One-Time Pad.

Why is a substitution cipher breakable even though 26! keys make brute force impossible?

See also

Related topics

  • Caesar CipherShift every letter of the alphabet by a fixed amount — the oldest cipher, and one of the easiest to break.
  • EntropyThe average surprise of a random source, measured in bits — and the hard floor on how far it can be compressed.
  • One-Time PadXOR a message with a truly random key as long as itself — the only cipher proven unbreakable, and the only one almost nobody can use.
  • CryptographyThe art and mathematics of keeping secrets and proving identity — from a Roman shift cipher to the public-key algebra that secures the modern web.
  • Modular ArithmeticArithmetic that wraps around a fixed modulus — the finite-ring algebra that makes public-key cryptography possible.
  • Systems, Signals & ComputationAn interactive field guide to how things change, oscillate, propagate, and compute — from a swinging pendulum to chaos, waves, networks, and learning machines.

Referenced by