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.

Â