0:00

Another transposition cipher, that is more complex

than rail fence, is Permutation Cipher.

We are given a key,

which is a permutation of numbers between 1 and N,

so that each number only occur once and the numbers are in random order.

Given the key of N numbers,

a permutation cipher constructs a matrix that has N columns.

On the other hand, the number of rows grow according to the plain text length.

Therefore, the number of columns depends on the key.

Permutation cipher takes the plain text alphabets and populate them element by element;

from the top row to the bottom row,

and from the left column to the right column.

Let's look at an example.

Again using the plain text, MEET ME LATER.

The key is given as 4 3 1 2.

Because the key is four alphabets long or four numbers song,

you can construct a matrix of alphabets that are four columns long.

You populate the alphabet one by one,

from the top row to the bottom row,

and from left column to the right.

So that the first row is M-E-E-T,

and the second row is and M-E-L-A,

and the third row is T-E-R. More rows get added,

if there are more plain text alphabets.

As is the case here,

the plain text length,

may not be nicely divisible by the number of columns.

And this can result in an empty alphabet element in the matrix.

When this happens, you can also arbitrarily fill the empty element.

For example, Alice and Bob,

can agree on a fixed alphabet before the encryption and decryption process;

such as the letters C which has the lowest frequency of occurrence.

Or Alice and Bob can agree on a rotation of a fixed set of alphabets,

such as the rotation of the four letters of Z Q X J. Alternatively,

Alice and Bob can agree on a pseudo random alphabet generation,

to pad or fill in the alphabets.

You get the picture.

However, for this example,

we will consider the case where there is no padding and we leave it as blank.

Let's focus on the key for a moment.

The key is given as 4 3 1 2,

which is a permutation of numbers between 1 and 4.

For example, the key could have been 3 2 4 1,

1 4 2 3 and even 1 2 3 4.

In this case, how many possible keys exist?

The answer is 4 factorial.

Which is equal to four times, three times,

two times, one, which equals to 24.

The logic goes like this,

for the first position,

you can choose an integer between 1 and 4,

which provides you 4 options, 1 2 3 4.

After you choose the first number,

you can now choose an integer out of three options for the second number,

because you cannot duplicate a number that you chose for the first position.

Therefore, for the first and the second numbers,

you have four times three,

which is equal to 12,

12 number of options.

For the third position,

you now have four minus two or two possible integers to choose from.

And for the fourth option,

you have four minus three, which is equal to one integer options to choose from.

Therefore, when the permutation is on a set of size four,

then there are four factorial possible options.

Four times, three times,

two times, one possible options.

This logic may sound familiar to you,

because the number of possible permutation options is a common application of factorial.

In fact, it may have been how you were motivated when you learned about factorial.

This logic can be generalized to any size permutations set.

For example, if the key is N alphabet's long,

and these alphabets appear only once,

then the number of possible permutations,

which will produce different ordering of alphabets, is N factorial.

Where N factorial equals the multiplication between all the integers between one and N.

Let's go back to the actual encryption process,

with the input plain text of MEET ME LATER.

For the permutation cipher encryption,

we take the columns,

one by one, to generate the cipher text alphabets.

And the order of the columns is specified by the key.

In this example, because the key is 4 3 1 2,

the first column you will take,

corresponds to the column with the letters E

L R. Then the second column for encryption is on the far right,

according to the key.

And the next two alphabets are T and A.

The empty element is ignored,

although it can alternatively be padded,

as we discussed before.

The third column corresponds to E E and E,

which also get appended on the cipher text.

And the last row appends the letters M,

M, and T on the cipher text.

While transposition cipher, is a class of ciphers that re-order the alphabets,

permutation cipher is a specific implementation of transposition cipher.

You can actually generalize transposition cipher using a permutation cipher with a key,

whose length is equal to that of the plain text.

However, this approach is not how other types of transposition ciphers are

implemented in practice because the key length can become quite big.