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?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Draw the full schematic of DES instead and follow the plain/cipher text through it carefully. Function F $\ne$ the whole network. $\endgroup$– Paul UszakJun 10, 2021 at 13:17
-
$\begingroup$ 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. $\endgroup$– fgrieu ♦Sep 18, 2022 at 16:27
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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$
$\begingroup$
$\endgroup$
1
how can fi(Li) == fi(Ri-1)
Simply because $L_i = R_{i-1}$. It is clearly visible on your pictures.
