6
$\begingroup$

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

$e[{a_0}{a_1}{a_2}{a_3}]={a_0}{a_0}{a_1}{a_2}{a_3}{a_3}$

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?

$\endgroup$

migrated from stackoverflow.com Dec 30 '16 at 10:55

This question came from our site for professional and enthusiast programmers.

  • 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$ – John Coleman 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
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Very clear explanation, especially the last paragraph. $\endgroup$ – John Coleman 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