# Why is a Feistel Network invertible?

As it is depicted above, the Feistel Network uses random function fi which is not required to be invertible. However, if fi is not invertible, how can fi(Li) == fi(Ri-1)? Furthermore, why Feistel Network is invertible?

• Draw the full schematic of DES instead and follow the plain/cipher text through it carefully. Function F $\ne$ the whole network. – Paul Uszak Jun 10 at 13:17
• Hint: use the properties of XOR. It's commutative, associative, and every element is it's own inverse. Also, by definition, a function always has the same output for any given input. – fgrieu Jun 10 at 13:59

## 2 Answers

how can fi(Li) == fi(Ri-1)

Simply because $$L_i = R_{i-1}$$. It is clearly visible on your pictures.

• Oh yes, I am so stupid! :( – 涂新宇 Jun 10 at 13:20

You don't need to invert the $$f_i$$ to invert the whole function. You know $$L_d$$, so you know $$R_{d-1}$$ and the the input of $$f_d$$. The xor can reverse itself. So you get $$L_{d-1}$$ by simply calculating $$R_d$$ xor $$f_d(L_d))$$. With this steps you just keep going until you know $$R_0$$ and $$L_0$$