Introduction to the

Feistel cipher, also known as Luby — Rackoff block cipher, is used to construct the symmetric structure of block encryption algorithms. It was invented by Horst Feistel, a German cryptographer, when he was working at IBM. Feistel Cipher is also known as the Feistel Network.

Many packet encryption algorithms are developed on the basis of Feistel Cipher, such as the famous DES algorithm.

In Feistel Cipher, the operations for encryption and decryption are very similar and usually require multiple rounds of encryption and decryption operations.

The principle of Feistel network

A round function is used in Feistel network, which receives two input parameters, namely the packet data (half of the original data) and the sub-key, and then generates the data of the same length as the packet data.

The data generated from the previous round and the other half of the original data are then used for XOR XOR operations as input to the next round function.

And so it goes round and round and finally generates the encrypted data.

The decryption process is similar to the encryption process, but the encryption is reversed.

The number of rounds in the Feistel network can be increased at will. No matter how many rounds can be decrypted properly.

Decryption is independent of the wheel function f, which does not need to have an inverse function. The wheel function can be designed to be duplicated.

Encryption and decryption can be implemented using exactly the same structure. From what we have said above, we can see that there is no difference between encryption and decryption.

Examples of Feistel networks

Let’s use a diagram to show how Feistel works:

In the figure above, F stands for round function.

K0,K1,K2… ,Kn represents sub-keys, which are respectively used as inputs of each round.

The original data is divided into left and right equal parts, (L0,R0)

Each round does the following:

• L_i+1 = R_i
• R_i+1 = L_i XOR F(R_i,K_i)

The result of the encryption is (Ri+1,Li+1).

The decryption process is the reverse order of the encryption process, and each round of decryption carries out the following operations:

• R_i = L_i+1
• L_i = R_i+1 XOR F(L_i+1,K_i)

And we end up with our original data (R0,L0)

Theoretical study of Feistel network

Michael Luby and Charles Rackoff demonstrated that if the round function is a pseudo-random function that uses Ki as the cryptographic security of the seed, then after three rounds of operation, the generated block cipher is already pseudo-random. After four rounds of operation, a “strong” pseudo-random arrangement can be generated.

What is a pseudo-random number?

Consider if you generate random numbers in a computer, because the data in a computer is made up of zeros and ones, and all the data is deterministic, either zeros or ones, so a computer program can’t generate truly random numbers.

If you want a computer to generate random numbers, the usual way is to calculate the input through some algorithmic function to get the processed number.

If the algorithm function is deterministic, that is, the same input can yield the same output, then the number is not generated randomly, and the number is called pseudo-random.

Pseudo random number is a sequence of random numbers from [0,1] uniformly distributed by deterministic algorithm. It is not really random, but has statistical characteristics similar to random numbers, such as uniformity, independence, etc.

Because of the importance of Luby and Rackoff’s research, the Feistel cipher is also known as the Luby-Rackoff cipher.

Expansion of Feistel Network

In addition to DES, which we described earlier, many algorithms use the Feistel network architecture, such as Blowfish, Twofish, and so on.

Because of the symmetric nature and simple operation of Feistel network, it is very simple to implement Feistel network through hardware, so the application of Feistel network is very extensive.

This article has been included in http://www.flydean.com/feistel-cipher/

The most popular interpretation, the most profound dry goods, the most concise tutorial, many you do not know the tips to wait for you to discover!

Welcome to pay attention to my public number: “procedures those things”, understand technology, more understand you!