# Permutation in Block Ciphers

I was reading some e-books to understand the basics of block ciphers and how it works in AES. As i understood, Permutation plays a big part in AES and Block Ciphers,

Here is what i understood by permutation,

``````A permutation is an ordered arrangement of the elements of some set S
Let S = {a, b, c}
c, b, a is a permutation of S
b, c, a is a different permutation of S
``````

Now, There was a power-point slide on Block ciphers i was reading and according to which,

Why did they call it a permutation, Could anyone please explain ?

• Think "shuffling" of the same deck of cards, and how many variations in their order there might be - that's permutations. I.e. multiple arrangements of the same set of elements. The right image is not a permutation, because its function of x `f(x)` adds and removes from to the topmost set. In our previous example of a deck of cards, you'd have to remove some, and replace them with cards from another deck to end up with the same number of cards that are not a permutation of a complete deck of cards. This is however not really a question on scope for Information Security. ;) – TildalWave Sep 24 '13 at 23:56

In the example you have given S has a,b and c. It's permutation must have exactly the same number of elements of the same type. One a, one b and one c. In total it has to have 3 elements and order of elements can be different.

In the second example, x has these values:

• a 00
• a 01
• a 10
• a 11

It's permutation, f(x) can have these values with the same count. So the left f(x) is a permutation because it has a 00, a 01, a 10 and a 11. Right f(x) is NOT, because it has 2x 11, a 01, and a 10 which is different than the x values.