A majority of serious modern encryption algorithms use a structure called Feistel networks. This structure allows each round of an algorithm to introduce new key material, provides additional plain text diffusion, and assures that the overall algorithm remains reversible across multiple rounds (in fact, across as many rounds as you want). It is actually quite a remarkable accomplishment for such a simple structure.

In a Feistel network algorithm, the round input text of each round (including the original plain text) is divided into two equal pieces. Each round swaps the left and right half of the current block around, while introducing keyed XOR substitution in just one of the directions. That is, the output of the "ith" round of a Feistel network is determined from the output of the i-1 round by:

		    L{i} = R{i-1}
		    R{i} = L{i-1} XOR f(R{i-1},K{i})
		    

The right side output moves to the left side with no transformation at this stage. The left side, however, moves back to the right after an XOR with some function f. All that constrains f is that its domain is the pair of the last right side output and some key material (the ith sub-key, derived from the key in some manner). The design of f is where the real work of the cipher goes on. For example, in the case of DES, f includes all the S-box transformations and a few other operations.

Why is a Feistel network reversible? Clearly, R{i-1} can be obtained from L{i} with no work at all. How do we get L{i-1}? That, too, is straightforward -- by the nature of XOR:

		    L{i-1} = L{i-1} XOR f(R{i-1},K{i}) XOR f(R{i-1},K{i})
		    

Or, simplifying:

		    L{i-1} = R{i} XOR f(L{i},K{i})
		    

As long as we can still construct the ith sub-key (which we should have no problem with if we have the key), we have accomplished the reverse algorithm of a Feistel network.