Substitution Cipher | Sahithyan's Notes

A classical, mono-alphabetic cipher. The key is a proper permutation of the plaintext alphabet.

You can find an implementation of the substitution cipher in sahithyandev/ciphers.

Key Expansion

A keyword can construct the permutation. Write its distinct letters first, then append the unused alphabet letters in order. For lobster, this gives LOBSTERACDFGHIJKMNPQUVWXYZ.

Key Space

The key is a permutation of the 26-letter alphabet. The key space has $26! \approx 4.03 \times 10^{26} \approx 2^{88}$ members. Statistical cryptanalysis still breaks the cipher without searching this space.

Encryption

The key is a permutation of the alphabet. Each plaintext letter is replaced by the letter mapped to it by the key. The same letter always maps to the same ciphertext letter.

Decryption

The receiver inverts the key permutation, mapping each ciphertext letter back to the plaintext letter that produced it.

Attacking

Frequency analysis recovers the key without searching the key space. Might fail on short messages, as the sample size is too small. A few hundred characters is usually sufficient.

Steps:

Count the frequency of each ciphertext letter.
Match the most frequent ciphertext letters to the most frequent letters of the plaintext language. In English, e, t, a, o, i, n are the most common.
Compare digram (such as th, in) and trigram (such as the) counts against known language statistics.
Use word boundaries when spaces are retained. Single-letter words are $a$ or $I$ . Common short words are $the$ , $of$ , $to$ , $and$ .
Fix the confident mappings, then fill the rest by trial, checking that partially decrypted words are valid.

Worked Example

Key alphabet LOBSTERACDFGHIJKMNPQUVWXYZ, so plaintext a maps to L, b to O, c to B, and so on.

Solution Reveal Hide

Each plaintext letter is looked up in the key alphabet.

h maps to A
o maps to J
w maps to W
y maps to Y

Plaintext howyoudoin gives ciphertext AJWYJUSJCI.

The inverse map sends each ciphertext letter back.

A maps to h
J maps to o
W maps to w
Y maps to y

Ciphertext AJWYJUSJCI gives plaintext howyoudoin.

For a longer ciphertext in this key, a frequency count leads the recovery.

The most frequent ciphertext letter is matched to e, the next to t, and so on down the English frequency rank.
The digram QA recurs, matched to th, which fixes Q to t and A to h.
QAT then reads the, fixing T to e.
Remaining letters are filled by trial, checking that partially decrypted words are valid.