Permutation cipher - Definition and Overview

In classical cryptography, a permutation cipher is a transposition cipher in which the key is a permutation.

To apply a cipher, a random permutation of size e is generated (the larger the value of e the more secure the cipher). The plaintext is then broken into segments of size e and the letters within that segment are permuted according to the key.

In theory, any transposition cipher can be viewed as a permutation cipher where e is equal to the length of the plaintext; this is too cumbersome a generalisation to use in actual practice, however.

Identifying the cipher

Because the cipher doesn't change any of the characters, the ciphertext will have exactly the same letter frequencies as the underlying plaintext. This means that the cipher can in many cases be identified as a transposition by the close similarity of its letter statistics with the letter frequencies of the underlying language.

Breaking the cipher

Because the cipher operates on blocks of size e, the plaintext and the ciphertext have to have a length which is some multiple of e. This causes two weakness in the system: firstly, that the plaintext may have to be padded (if the padding is identifiable then part of the key is revealed) and secondly, information relating to the length of the key is revealed by the length of the ciphertext. To see this, note that if the ciphertext is of length i then e must be one of the divisors of i. With the different possible key sizes different possible permutations are tried to find the permutation which results in the highest number of frequent bigrams and trigrams as found in the underlying language of the plaintext. Trying to find this permutation is essentially the same problem encountered when analysing a columnar transposition cipher: multiple anagramming.

See also: Topics in cryptography.