How can you make an invertible function out of non-invertable parts? Why would you want to? Encryption functions must be invertible.
If the intended recipient can’t decrypt the message then the encryption method is useless.
Of course you want an encryption function to be really hard to invert without the key.
It’s hard to think all at once of a function that’s really hard to invert.
It’s easier to think of small components that are kinda hard to invert.
Ideally you can iterate steps that are kinda hard to invert and create a composite that’s really hard to invert.
So how do we come up with components that are kinda hard to invert? One way is to make small components that are non-linear, and that are in fact impossible to invert.
But how can you use functions that are impossible to invert to create functions that are possible to invert? It doesn’t seem like this could be done, but it can.
Feistel networks, named after cryptographer Horst Feistel, provide a framework for doing just that.
Many block encryption schemes are based a Feistel network or a modified Feistel network: DES, Lucifer, GOST, Twofish, etc.
The basic idea of Feistel networks is so simple that it may go by too fast the first time you see it.
You take a block of an even number bits and split it into two sub-blocks, the left half L and the right half R.
The nth round of a Feistel cipher creates new left and right blocks from the left and right blocks of the previous round by Here ⊕ is bitwise XOR (exclusive or) and f(Rn-1, Kn) is any function of the previous right sub-block and the key for the nth round.
The function f need not be invertible.
It could be a hash function.
It could even be a constant, crushing all input down to a single value.
It is one of the non-invertible parts that the system is made of.
Why is this invertible? Suppose you have Ln and Rn.
How could you recover Ln-1 and Rn-1? Recovering Rn-1 is trivial: it’s just Ln.
How do you recover Ln-1? You know Rn-1 and the key Kn and so you can compute The main idea is that XOR is it’s own inverse.
No matter what f(Rn-1, Kn) is, if you XOR it with anything twice, you get that thing back.
At each round, only one sub-block from the previous round is encrypted.
But since the roles of left and right alternate each time, the block that was left alone at one round will be encrypted the next round.
When you apply several rounds of a Feistel network, the output of the last round is the encrypted block.
To decrypt the block, the receiver reverses each of the rounds in the reverse order.
More cryptography posts Inside the AES S-box Curve 25519 From now until quantum.