Feistel Networks: Building Blocks of Modern Ciphers

In the early 1970s, Horst Feistel at IBM Research was working on the Lucifer cipher when he developed a fundamental insight: you can build an invertible cipher using a non-invertible round function.

This was revolutionary because designing invertible functions that are also secure is hard. Feistel's construction sidesteps this requirement entirely, allowing the use of arbitrarily complex, one-way round functions.

In a Feistel cipher, the input block is split into two equal halves: L (left) and R (right). Each round applies the round function F to R, XORs the result with L, then swaps the halves.

After n rounds, the two halves are recombined to produce the ciphertext. The swapping ensures both halves are processed in alternating rounds, mixing them thoroughly.