6
$\begingroup$

In security, and specifically Block Cipher (AES, DES, etc), when we talk about pseudo random permutations, is the term "permutation" refer to the same meaning as in discrete mathematics. That is, the random shuffling of elements?

So let's the input of DES has n 1s and m 0s, is the output gonna be n 1s and m 0s as well?

$\endgroup$
  • 4
    $\begingroup$ It's a permutation, but of the $2^{64}$ possible 64 bit blocks, not of the 64 bits within a single block. If a blockcipher were no permutation, you couldn't decrypt a block. $\endgroup$ – CodesInChaos May 24 '15 at 22:12
4
$\begingroup$

Formally, a block cipher is a family of permutations, indexed by the key. More specifically, let $P$ be the set of all permutations (shufflings of elements as you put it) on the set of $n$ bit strings, i.e. the Symmetric Group $Sym(\{0,1\}^n)$. The $n$-bit block cipher $B$ is a subset of $P$. The key specifies which element of the subset $B$ is to be used in the encryption/decryption process.

As CodesInChaos points out in a comment, you are confusing the idea of transposition of the $n$ individual bits of the input with a permutation over the set of $n$-bit strings. Think of DES as being like a monoalphabetic substitution cipher, except instead of having an alphabet of 26 letters it has an alphabet of all $2^{64}$ 64-bit strings. More precisely (following the formal definition above), DES is a family of $2^{56}$ different monoalphabetic ciphers, and the 56 bit key specifies which monoalphabetic cipher will be used for encryption/decryption.

| improve this answer | |
$\endgroup$
  • $\begingroup$ "Pseudorandom X" always refers to a family of Xs, as far as I know (if it's not a family, a distinguisher is trivial). $\endgroup$ – cpast May 24 '15 at 23:06
  • $\begingroup$ @cpast - That is true, but it is also true that you can have families of permutations (i.e. block ciphers) that are not pseudorandom. In the Standard model, a block cipher $B$ (as a family of permutations on the set $\{0,1\}^n$) is a pseudorandom permutation if a uniformly-randomly-selected element of the family is "indistinguishable" from a uniformly-randomly-selected element of $Sym(\{0,1\}^n)$. So yes, being a family is necessary for being pseudorandom, but it is not sufficient. $\endgroup$ – J.D. May 24 '15 at 23:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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