Score:3

Crypto

Why is a Feistel Network invertible?

Xinyu Tu

10/10/22, 1:06 PM

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?

225

2 + 2

des

feistel-network

Paul Uszak

10/10/22, 1:17 PM

Draw the full schematic of DES instead and follow the plain/cipher text through it carefully. Function F $\ne$ the whole network.

fgrieu

10/10/22, 1:59 PM

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

9/18/23, 4:27 PM

TL;DR: the Feistel _structure_ always yields a reversible transformation, regardless of if the _round functions_ $f_i$ are reversible or not. To prove this, 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.

Score:2

Crypto

jjj

10/10/22, 3:20 PM

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$

0 + 0

Score:1

Crypto

Fractalice

10/10/22, 1:19 PM

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

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

0 + 1

Xinyu Tu

10/10/22, 1:20 PM

Oh yes, I am so stupid! :(