Why is the XOR operation irreversible

Feistel networks

Feistel networks are the basis of many modern block ciphers; they are used e.g. in DES, Blowfish, Twofish, CAST, FEAL, MARS, Khufu, Khafre, LOKI, GOST and others. The concept was developed by the IBM employee Horst Feistel. The principle is very simple:

The input text is first divided into encryption blocks of the same size (often e.g. 64 bits; in this program, for the sake of clarity, it is only 32 bits). Each block is then divided into two equally sized halves L and R. The encryption then takes place iteratively in several rounds, in that the output of the (i + 1) th round is determined by that of the i th round. Here the right and left blocks are swapped; the right block from round (i-1) becomes the left block in round i, the left block from round (i-1) becomes the right block in round i. The right block (and just this!) is also XOR-linked with a value, which is made up of the current lap key and the right half of the lap (i-1) (which has now moved to the left half) using an algorithm-specific non-linear function f (R, K) is obtained:

L.i = Ri-1 R.i = Li-1 ⊕ f (Ri-1, Ki) where ⊕ denotes the XOR operator, f (R, K) is an arbitrary (nonlinear) function and Ki is the lap key of the i-th lap; this is calculated from the specified key before encryption.

The great advantage of Feistel networks is that the function f (R, K) can be arbitrarily complex; it does not even have to be reversible (for deciphering). One simply uses the fact that an XOR operation applied twice results in the original value again:

R.i-1 = Li L.i-1 = Ri ⊕ f (Ri-1, Ki) = Ri ⊕ f (Li, Ki)

For practical implementation, it is advisable to swap the left and right blocks when deciphering before and after the operation. Then the encryption routine can also be used for decryption by simply inverting the order of the round keys.

In this script, an 8th degree polynomial is used for both the round function and the key function. The functions are chosen arbitrarily; any other function could also be used. The only important thing about the round function f (R, K) is that it is (not too weak) non-linear, since the reliability of the algorithm is determined by the choice of this function.

It is possible to display the difference to the last input or output. The difference is defined as the XOR link between the two values; i.e., the difference bit is set at all places where a bit has changed.

The entry can be made either as a number or as a bit mask (with the checkboxes). For a better overview, the input fields and the introduction can be hidden.