Better to know some
... than all
The Data Encryption Standard (DES) is the most well-known symmetric-key block cipher. Recognized world-wide, it set a precedent in the mid 1970s as the first commercial-grade modern algorithm with openly and fully specified implementation details. It is defined by the American standard FIPS 46-2.
Product ciphers and Feistel ciphers
The design of DES is related to two general concepts: product ciphers and Feistel ciphers. Each involves iterating a common sequence or round of operations.
The basic idea of a product cipher is to build a complex encryption function by composing several simple operations which offer complementary, but individually insufficient, protection. Basic operations include transpositions, translations (e.g., XOR) and linear transformations, arithmetic operations, modular multiplication, and simple substitutions.
A product cipher combines two or more transformations in a manner intending that the resulting cipher is more secure than the individual components.
A substitution-permutation (SP) network is a product cipher composed of a number of stages each involving substitutions and permutations.
An iterated block cipher is a block cipher involving the sequential repetition of an internal function called a round function. Parameters include the number of rounds r, the block bitsize n, and the bitsize k of the input key K from which r subkeys Ki (round keys) are derived. For invertibility (allowing unique decryption), for each value Ki the round function is a bijection on the round input.
A Feistel cipher is an iterated cipher mapping a 2t-bit plaintext (L0,R0), for t-bit blocks L0 and R0, to a ciphertext (Rr, Lr), through an r-round process where r >= 1. For 1 <= i <= r, round i maps (Li-1,Ri-1) Ki---> (Li,Ri) as follows: Li = Ri-1, Ri =Li-1f(Ri-1,Ki), where each subkey Ki is derived from the cipher key K.
Typically in a Feistel cipher, r >= 3 and often is even. The Feistel structure specifically orders the ciphertext output as (Rr, Lr) rather than (Lr,Rr); the blocks are exchanged from their usual order after the last round. Decryption is thereby achieved using the same r-round process but with subkeys used in reverse order, Kr through K1; for example, the last round is undone by simply repeating it. The f function of the Feistel cipher may be a product cipher, though f itself need not be invertible to allow inversion of the Feistel cipher.
The successive rounds of a Feistel cipher operate on alternating halves of the ciphertext, while the other remains constant. Note the round function of Definition may also be re-written to eliminate Li: Ri = Ri-2f(Ri-1,Ki). In this case, the final ciphertext output is (Rr,Rr-1), with input labeled (R-1,R0).