I have a question that I have not found the answers to in many books.

Does the expansion permutation have to map values to the same space? For example, in DES, 32 bits are expanded into 48 bits via an expansion permutation where the values are shuffled around but do not change.

Expansion table

Consider the following expansion function for 4 bits into 6 bits


Is this a legal permutation? or is it not cause it can map to new values in which we didn't posses before, for example 1001 can be mapped into a new value 110011 that didn't exist before.

I understand the encryption would encrypt regardless, but is using that permutation allows for us to reverse the encryption by running the keys in reverse?

  • 1
    $\begingroup$ Decryption does not involve inverting the expansion permutation so you would still be able to decrypt. The expansion permutation is (I believe) largely a diffusive step -- something which is designed towards the end of having each bit of the cipher text a function of each bit of the plain text. $\endgroup$ Dec 30 '16 at 0:28
  • $\begingroup$ Thank you, it is actually a diffusive step as stated in my book, however I did not translate it properly into English and that's why I was stuck. $\endgroup$
    – user2733996
    Dec 30 '16 at 0:44
  • $\begingroup$ Welcome to crypto, I hope you don't mind that I flagged it for migration, the question didn't contain any implementation / development related component. $\endgroup$
    – Maarten Bodewes
    Dec 30 '16 at 12:46

A "permutation", by definition, must have the same domain and range, i.e., the same possible inputs and possible outputs. You can look at it as either as a bijective function from some domain onto the same domain, or as a reordering of that domain. Any reordering of things may also be referred to as a "permutation".

The DES "expansion permutation" is called a permutation, because it rearranges bits, but it is not a permutation at all, because it copies bits as well.

The purpose of the expansion permutation is to make sure the S-boxes have overlapping keys... for some arcane reason. It's part of providing "confusion and diffusion", and it has nothing to do with ensuring that the encryption can be reversed.

It is the Feistel structure itself that ensures that the encryption is reversible no matter what the Feistel function $f$ is. That gives the designers of encryption algorithms lots of leeway to do whatever they want without having to worry about using only reversible operations.

Mapping $(A,B)$ onto $(A \oplus f(B),B)$ is easily reversed just by doing it again: $$(A \oplus f(B),B) -> (A\oplus f(B) \oplus f(B),B) = (A,B)$$

where $\oplus$ is the XOR operation.

Since DES is encryption is essentially a sequence of Feistel rounds, it can be decrypted by performing the same Feistel operations in reverse order.

  • $\begingroup$ Very clear explanation, especially the last paragraph. $\endgroup$ Dec 30 '16 at 0:30
  • $\begingroup$ You made this clearer to me by stating that the structure of the F function doesn't have to be revertible and by doing the example. Thank you. $\endgroup$
    – user2733996
    Dec 30 '16 at 0:44

Your Answer

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