THE FEISTEL NETWORK split, mangle one half, swap; decryption is free
Split a block in two halves; each round replaces (L, R) with (R, L ⊕ F(R, key)) for some round function F. The magic: F can be anything — it need not be invertible, or even injective — and the whole cipher is still perfectly reversible, because XOR undoes itself. Decryption is the same network with the round keys in reverse order. DES, Blowfish and Twofish are all Feistel.
THE TECHNIQUE (L,R) -> (R, L xor F(R,k)); reverse keys to decrypt
Encrypt a block with a deliberately non-invertible round function, then decrypt by running the same rounds with the keys reversed. The plaintext comes back exactly — the structure, not F, carries the reversibility: live demo
HISTORY & CREDIT Horst Feistel, IBM, 1973
“The round function F must be invertible for the cipher to decrypt.” — no, and that is the whole point. Because the round is (R, L ⊕ F(R,k)), XOR reverses it whatever F does; F is free to be a wildly non-linear, non-invertible mess — which is exactly what makes it secure. cited
1971–73 · Horst Feistel (IBM) — the Lucifer cipher and “Cryptography and Computer Privacy” (Scientific American, 1973): the split-mangle-swap structure now named for him. 1977 · DES — IBM/NBS standardise a 16-round Feistel cipher; the structure goes worldwide. 1988–98 · Luby & Rackoff (1988) prove a 3–4 round Feistel with pseudorandom F is a secure pseudorandom permutation — the theorem behind the practice.
Decrypt is encrypt: run the identical network with the subkeys in reverse. So the same hardware, the same code, ciphers both ways — a structural involution, symmetric by construction. Feistel 1973
RECOMMEND FOR I-13 reversible from a non-invertible F, computed
On the canonical compiler a Feistel cipher round-trips a block even though its F is not invertible — pure XOR, shift and mask:
$ i13 run feistel.i13 # F(r,k) = (3r + k) mod 256 (NOT invertible); 2 rounds
pt = 4660
ct = 49554 -- encrypted
back = 4660 -- decrypt = same network, keys reversed -> exact recovery
Recommend: the Feistel network is LIT and a natural fit for I-13 — verified a 2-round cipher encrypts 4660 → 49554 and decrypts back to 4660 using a round function F(r,k)=(3r+k) mod 256 that is not invertible, built from ⊕, <<, >>, & (the bitwise operators, doing cryptographic work). Its reversibility is structural: encrypt and decrypt are the same network with reversed keys — a self-undoing shape that runs bit-exact. For any I-13 symmetric cipher this is the cleanest skeleton; the security lives entirely in a strong F (an S-box, dart 191) and enough rounds (avalanche, 194).