What is the difference between a permutation and a shuffle (transposition cipher) A non-cryptographic definition of a permutation is &quot;2a: the act or process of changing the lineal order of an ordered set of objects. 2b: an ordered arrangement of a set of objects
The Wikipedia article on Random permutation states that &quot;A good example of a random permutation is the shuffling of a deck of cards: this is ideally a random permutation of the 52 cards.&quot;
An ideal block cipher is a pseudorandom permutation.
Shuffling a deck of identical cards would result in output indistinguishable from the input. Applying an ideal block cipher to an all-zero (or all-one) plaintext block would yield a random ciphertext block, not the same all-zero (or all-one) input block!
What's an easy-to-understand difference between a shuffle (equivalently a transposition cipher) and a permutation in the sense meant by cryptographers?
A shuffle (or transposition function) re-arranges elements of the input. A permutation re-arranges the entire output domain.
For example, compare the following transposition function and pseudorandom permutation:
The transposition takes in a 4-digit number, and re-arranges the digits. 1234 might become 4213, but never 1692.
A pseudorandom permutation has a shuffled list of all possible 4-digit numbers, and an unshuffled list of all possible 4-digit numbers. It looks up the input number in the unshuffled list, finds the corresponding number in the shuffled list, and outputs that. 1234 might become 1692.