Permutation Cipher | Sahithyan's Notes

A classical, transposition cipher. Reorders the plaintext letters. 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.

\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 4 & 1 & 3 & 5 \end{pmatrix}

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$ .

Key Space

For a fixed block length $n$ , every key is a permutation in $S_n$ . The key space has $n!$ members. If $n$ is secret as well, the complete key space is the union of these spaces over the permitted block lengths.

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)$ .

c_{\sigma(i)} = m_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.

m_i = c_{\sigma(i)}

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.

Solution Reveal Hide

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.