Feistel Block Cipher | Feistel Cipher | What is a Feistel Cipher ?

Feistel cipher named after block cipher pioneer Horst Feistel, is a general cipher design principle. It is a design model or structure used to build various symmetric block ciphers, such as DES. A cryptographic system based on the Feistel cipher structure uses the same algorithm for both encryption and decryption.

 

The Feistel structure is based on the Shannon structure proposed in 1945, demonstrating the confusion and diffusion implementation processes. Confusion produces a complex relationship between the ciphertext and encryption key, which is done by using a substitution algorithm. On the other hand, diffusion creates a complex relationship between plain text and cipher text by using a permutation algorithm.  

 

The Feistel cipher proposed the structure that implements substitution and permutation alternately. Substitution replaces plain text elements with ciphertext. Permutation changes the order of the plain text elements rather than being replaced by another element as done with substitution.  

 

Feistel Cipher Encryption 

The Feistel cipher encryption process involves numerous rounds of processing plain text. Each round includes the substitution step and then the permutation step.

 

 

The plain text block is divided into two equal halves. The left half of the plain text block will be represented as LE0, and the right half of the block will be RE0. Both halves of the plain text block (LE0 and RE0) will go through numerous rounds of processing and then combine to produce the ciphertext block.

For every round, a function is applied on the right half REi of the plain text block plus the key Ki. The function results are then XORed with the left half LEj. The XOR function results become the new right half for the next round RE i+1. The previous right half REi becomes the new left half LEi+1 for the next round.

Every round will execute the same function, in which a substitution function is implemented by using the round function to the right half of the plain text block. The result of this function is XORed by using the left half of the block. Then, a permutation function is used by switching the two halves. The permutation results are provided for the next round. Indeed, this is how the Feistel cipher model implements the substitution and permutation steps alternately,

 

The Feistel cipher structure depends on the following parameters and design features:

Block size: Block ciphers are considered more secure when the block size is larger. Though, larger block sizes reduce the execution speed for the encryption and decryption process. Typically, block ciphers have a block size of 64-bits, but modern blocks like AES (Advanced Encryption Standard) are 128-bits. 

Key size: Like the block size, larger key sizes are considered more secure but may decrease encryption and decryption speed.

Number of rounds: The number of rounds can also impact the security of a block cipher. While more rounds increase security, the cipher is more complex to decrypt. Thus, the number of rounds depends on a business’s desired level of data protection.  

Subkey generation function: The more complex a subkey generation functions is, the more difficult it is for expert cryptanalysts to decrypt the cipher.

Round function: A complex round function helps boost the block cipher’s security. More complex function is harder for the cryptanalyst to attack.

 

Feistel Cipher Decryption:

The Feistel cipher model uses the same algorithm for encryption and decryption. There are a couple of key rules to consider during the decryption process:  

The cipher text block contains two halves, the left (LD0) and the right (RD0).

Like the encryption algorithm, the round function is executed on the right half of the cipher block with the key K16. The function’s result is XORed with the left half of the cipher text block. The XOR function’s output becomes the new right half (RD1), while RD0 switches with LD0 for the next round. Indeed, every round uses the same function, and once the fixed number of rounds is executed, the plain text block is achieved.