DES and Feistel Cipher

Question

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.

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?

Answer 1

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.