General alphabetic substitution

Caesar’s cipher has a small number of possibilities because it has only 25 keys. A natural idea: instead of shifting the letters, let’s replace each letter with any other, according to a freely chosen mapping.

clair    A B C D E F ...
chiffré  Q W E R T Y ...

A vast key space

The key is now the entire permutation of the 26 letters. How many are there?

26 ! = 26 × 25 × 24 × ... × 2 × 1 ≈ 4 × 10^26

That’s around 400 million billion billion keys. A brute-force attack is completely out of the question, even for every computer on the planet.

But does that mean the system is secure? No. And that’s the most important lesson of this course.

What substitution does not hide

It changes the name of the letters, but not their behaviour. If E is the most frequent letter in French, then the letter that replaces it will be the most frequent in the ciphertext.

Everything that makes up the structure of the language survives the encryption:

• the frequency of each letter;
• repeated letters (SS, LL, TT) remain repeated;
• the length of words, if spaces are retained;
• frequent groups (QU, ES, ENT).

A large key space is therefore not enough. The ciphertext must not reveal any information about the plaintext.