What is the difference between Substitution Cipher and Permutation Cipher?

In a substitution cipher I have seen that there is a random choice of 26 alphabet characters for encryption and decryption and that it can't be broken by brute force attacks because the sample space for key encryption is 2**88 which is very large. Hackers can use frequency analysis to get the encrypted message.

What about permutation cipher, then? What is this and why it comes under poly-alphabetic and substitution comes under mono-alphabetic?

  • $\begingroup$ This is perhaps more suited for the cryptography stack exchange $\endgroup$
    – J.A.K.
    Jan 24 '17 at 19:02

Substitution Ciphers

Substitution ciphers replace units of plaintext with units of ciphertext.

A simple example is the Caesar cipher, which specifies the substitution of each plaintext letter with the letter which is found some fixed number of places away in the alphabet. The Caesar cipher is easily broken by trying all possible offset values, where the number of offset values is equal to the alphabet size.

For example, if the offset value is $s = 3$, then the plaintext $caesar$ will be encoded as the ciphertext $fdhvdu$.

The class of cipher's to which the Caesar cipher belongs is the monoalphabetic substitution ciphers.

Another class of substitution cipher are polyalphabetic substitution ciphers. The Vigenère cipher is a simple example which substitutes plaintext values for ciphertext values using a series of Caesar ciphers which are defined by a keyword.

The keyspace $|K| \approx 2^{88}$ mentioned in your question can be derived from a Vigenère cipher with a 26 character alphabet and a keyword $k \in K$ which is 26 characters long. The calculation is $26!$ which tells us the number of different configurations in which we can arrange 26 characters.

This brings us to the concept of brute force complexity. Brute force complexity is a measure of the computational effort which is required exhaustively find a solution to a problem. In order for brute force complexity to be meaningful in a cryptographic context it is necessary that there aren't any shortcuts which can be taken to reduce the space which must be searched.

The Vigenère cipher does not usually meet this requirement. If the length of the plaintext is greater than 26 characters, or the same keyword is used to encrypt multiple messages, then an attacker can use frequency analysis techniques to recover information about the encrypted messages.

Both of these constructions are very old. Claude Shannon's information theory and it's application to cryptographic systems as information-theoretic security is sometimes credited with transforming cryptography from an art into a science and is an important foundation in modern cryptography.

Essentially Shannon sought to quantify information leakage in the context of cryptography, and proved that the one-time-pad satisfied a property known as perfect secrecy - it cannot be broken by any adversary, even one given unlimited computational power and time.

Permutation Ciphers

Permutation ciphers attempt to hide information from an adversary by rearranging the plaintext so that it can no longer be recognised. A simple example is the rail fence cipher which transposes a plaintext by arranging it diagonally into a number of rails. In practice this is highly insecure since the number of rails is small and can be attacked by brute force.

Modern Block Ciphers

Some modern Ciphers such as AES apply both substitution and permutation repeatedly in rounds by applying a construction known as a substitution-permutation network (SPN). AES is much more secure than any of the ciphers mentioned above, and is not vulnerable to frequency analysis in the same way as alphabetic ciphers are. For a better understanding of AES I recommend reading: A Stick Figure Guide to the Advanced Encryption Standard (AES)

  • $\begingroup$ It may be worth clarifying that AES is a derivative of a SPN as there is also a round key factored in between substitutions and permutations. The round key allows a variable user key to be implemented, otherwise the SPN cipher would be hard coded and invariant. Consequently AES is not exactly a SPN per se, but rather founded upon one. $\endgroup$
    – Paul Uszak
    Jan 25 '17 at 2:31
  • $\begingroup$ Thanks @Paul Uszak. I feel like the answer is slightly meandering so I didn't want to add too much detail which deviates from the original question. I've tweaked it a bit. $\endgroup$
    – Chris
    Jan 25 '17 at 11:04

Not the answer you're looking for? Browse other questions tagged or ask your own question.