Permutation Cipher

One specific classical cipher in the transposition category. The category as a whole is also called permutation ciphers. This note covers the concrete construction that carries the name, in the same way the shift cipher is one concrete cipher in the mono-alphabetic category.

Reorders the plaintext letters rather than substituting them, so every single-letter frequency is preserved unchanged.

Requires a block length $n$, typically small, and a permutation $\sigma \in S_n$ as the secret key.

The bottom row gives $\sigma(i)$ for each input position $i$ in the top row. Here $\sigma(1) = 2$, $\sigma(2) = 4$, $\sigma(3) = 1$, $\sigma(4) = 3$, $\sigma(5) = 5$.

Encryption

Split the plaintext into blocks of $n$ characters. Pad the final block with filler characters if it is short.

Within each block, the character at position $i$ moves to position $\sigma(i)$.

Here:

• $m_i$: plaintext character at position $i$ in the block
• $c_j$: ciphertext character at position $j$ in the block

Decryption

The receiver knows $\sigma$. Within each block, position $i$ of the plaintext is read from position $\sigma(i)$ of the ciphertext.

This is encryption under the inverse permutation $\sigma^{-1}$.

Attacking

Single-character frequencies in the ciphertext match the standard language distribution, since the permutation only moves characters. A ciphertext whose frequencies match the standard distribution but which does not decrypt as a substitution cipher points to a permutation cipher.

The attack recovers $n$ first, then $\sigma$.

Recovering the block length $n$:

• A plaintext word that repeats at the same offset within its block is permuted the same way each time, so it produces an identical character group in the ciphertext.
• Measure the gap between the start positions of 2 such repeated groups. The gap is a multiple of $n$.
• Take the gcd of several such gaps. That gcd is $n$, or a small multiple of it.

Recovering the permutation $\sigma$:

• Cut the ciphertext into blocks of length $n$.
• Try each of the $n!$ candidate permutations, applying its inverse to every block.
• Keep the candidate that turns every block into readable text.

Worked Example

Key: $\sigma(1) = 2$, $\sigma(2) = 4$, $\sigma(3) = 1$, $\sigma(4) = 3$, $\sigma(5) = 5$. Plaintext GETTOTHECHOPPER splits into 3 blocks of 5: GETTO, THECH, OPPER.

Encryption places $m_i$ at position $\sigma(i)$ within each block. For the first block:

• $m_1 = \text{G} \to$ position 2
• $m_2 = \text{E} \to$ position 4
• $m_3 = \text{T} \to$ position 1
• $m_4 = \text{T} \to$ position 3
• $m_5 = \text{O} \to$ position 5

Reading positions 1 to 5: T, G, T, E, O.

The other 2 blocks follow the same rule.

• THECH becomes ETCHH.
• OPPER becomes POEPR.

Ciphertext: TGTEOETCHHPOEPR.

Decryption reads $m_i$ from position $\sigma(i)$ of each block, recovering GETTO, THECH, OPPER.

Plaintext: GETTOTHECHOPPER.

The attack starts from ciphertext blocks with the block length unknown. With a longer message under the same key, a plaintext word repeating at the same offset within its block would produce an identical ciphertext group each time, letting the gcd of the gaps between occurrences recover $n$, as described above. Once $n = 5$ is fixed:

• Cut the ciphertext into blocks of 5.
• Each of the $5! = 120$ candidate permutations is applied in inverse to every block.
• The candidate $\sigma(1) = 2$, $\sigma(2) = 4$, $\sigma(3) = 1$, $\sigma(4) = 3$, $\sigma(5) = 5$ turns every block into readable text and is kept.