Feistel cipher

A Feistel cipher is a block cipher with a particular structure (known as a Feistel network).

Feistel networks and similar constructions combine multiple rounds of repeated

• bit-shuffling
• simple non-linear functions (often called S boxes)
• linear mixing (in the sense of modular algebra) using XOR

to produce a function with large amounts of what Claude Shannon described as "confusion and diffusion".

Feistel networks were invented by IBM cryptography researcher Horst Feistel, and first commercially seen in IBM's Lucifer cipher, designed by Feistel and Don Coppersmith. Feistel networks gained respectability when the US Federal Government adopted the DES (a cipher based on Lucifer, with improvements made by the NSA). Like other components of the DES, the iterative nature of the feistel construction makes implementing the cryptosystem in hardware easier (particularly on the limited hardware available at the time of DES' design).

Most modern (non-military) symmetric block ciphers are based on feistel networks, and the structure and properties of feistel ciphers have been extensively explored by cryptographers.

Split the plaintext block into two equal pieces, (L0, R0)

For each round i =1,2,...,n, compute

    Li = Ri-1
    Ri = Li-1 ⊕ f(Ri-1, Ki)

where f is the round function and Ki is the sub-key.

Then the ciphertext is (Ln, Rn).

Regardless of the function f, decryption is accomplished via

    Ri-1 = Li
    Li-1 = Ri ⊕ f(Ri-1, Ki)

Unbalanced Feistel ciphers use a modified structure where L0 and R0 are not of equal lengths. The Skipjack encryption algorithm is an example of such a cipher.