Substitution Cipher | Sahithyan's Notes

A classical and 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.

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.

The key space equals the number of permutations of the alphabet, $26! \approx 4.03 \times 10^{26} \approx 2^{88}$ . A massive key space does not make the substitution cipher unbreakable. Statistical techniques based on language characteristics still apply.

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.

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.