Block Ciphers - Modern Cryptanalysis: Techniques for Advanced Code Breaking - page 86

Now, the nifty part of the Feistel structure we can see here at the end: If we have the ciphertext, L 3 and R 3 , then
that means we also have R 2 (since L 3 = R 2 ). The party doing the decrypting will also know the key and thus will
then know the appropriate value of the key schedule, K 3 , allowing the party to calculate f ( R 2 , K 3 ). Now note that
from the above encryption. We can then rewrite this (by exchanging L 2 and R 3 due to the symmetry of XOR) to
obtain
We thus obtain the previous round's intermediate ciphertext, L 2 and R 2 . Repeating this again and again will
eventually reveal the original plaintext, as shown in the following example:
We can now generalize the decryption operation to work with any number of rounds.
Basic Feistel Decryption Algorithm
Computes a basic Feistel operation of r rounds, with a round function f , and key schedule ( K 1 , K 2 , ... , K r ).
1. Split the ciphertext, C , into two halves: The “left half” ( L r ) consists of the most significant bits, and the
“right half” ( R r ) consists of the least significant bits.
2. For each round, i = r - 1, ... , 0, do the following:
(a) Set R i = L i +1 .
(b) Set L i = R i +1 ⊕ f ( R i , K i +1 ).
As we can see, for decryption, the operations are nearly identical to the encryption algorithm. The primary
difference is that the keys (Ki) are submitted in reverse order.
Ciphers that use the above Feistel structure have several notable properties.
• The round function can be relatively simple, as the structure is normally iterated numerous times. Typic-
ally 4, 8, 16, and 32 rounds are common.
• Encryption and decryption, for the most part, can use identical structures: The round function does most
of the work for both operations. (Encryption and decryption can still differ by more. For example, some
ciphers with Feistel structures have different forms for their initial or final rounds, such as initial and
final permutations.)