Iterated block ciphers encrypt a plaintext block by a process that has several rounds. In each round, the same transformation (also known as a round function) is applied to the data using a subkey. The set of subkeys is usually derived from the user-provided secret key by a special function. The set of subkeys is called the key schedule. The number of rounds in an iterated cipher depends on the desired security level and the consequent tradeoff with performance. In most cases, an increased number of rounds will improve the security offered by a block cipher, but for some ciphers the number of rounds required to achieve adequate security will be too large for the cipher to be practical or desirable.
Feistel ciphers [Fei73] are a special class of iterated block ciphers where the ciphertext is calculated from the plaintext by repeated application of the same transformation or round function. Feistel ciphers are sometimes called DES-like ciphers (see Section 3.2).
Figure 2.1: Feistel Cipher (click for a larger image)
In a Feistel cipher (see Figure 2.1), the text being encrypted is split into two halves. The round function f is applied to one half using a subkey and the output of f is XORed with the other half. The two halves are then swapped. Each round follows the same pattern except for the last round where there is no swap.
A nice feature of a Feistel cipher is that encryption and decryption are structurally identical, though the subkeys used during encryption at each round are taken in reverse order during decryption. More precisely, the input in the decryption algorithm is the pair (Rr,Lr) instead of the pair (L0, R0) (notations as in Figure 2.1), and the ith subkey is kr-i+1, not ki. This means that we obtain (Rr-i, Lr-i) instead of (Li, Ri) after the ith round. For example, R1 is replaced with
Rr ÅF(kr,Lr) = Rr ÅF(kr,Rr-1) = Rr Å(Rr ÅLr-1) = Lr-1.
It is of course possible to design iterative ciphers that are not Feistel ciphers, yet whose encryption and decryption (after a certain re-ordering or re-calculation of variables) are structurally the same. Some examples are IDEA (see Question 3.6.7) and several of the candidates for the AES (see Section 3.3).