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 (see §1.5.3) is to build a complex encryption function by composing several simple operations which offer complementary, but individually insufficient, protection (note cascade ciphers per Definition 7.29 use independent keys). Basic operations include transpositions, translations (e.g., XOR) and linear transformations, arithmetic operations, modular multiplication, and simple substitutions.
- 7.78 Definition A product cipher combines two or more transformations in a manner intending that the resulting cipher is more secure than the individual components.
- 7.79 Definition A substitution-permutation (SP) network is a product cipher composed of a number of stages each involving substitutions and permutations (Figure 7.7).
Figure 7.7: Substitution-permutation (SP) network.
Many SP networks are iterated ciphers as per Definition 7.80.
- 7.80 Definition 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 к of the input key К from which r subkeys K, (round keys) are derived. For invertibility (allowing unique decryption), for each value K, the round function is a bijection on the round input.
- 7.81 Definition A Feistel cipher is an iterated cipher mapping a 2/-bit plaintext (L0, R0), for t-bit blocks L0 and /?<ь to a ciphertext (/?,.. Lr), through an r-round process where r > 1.
For 1 < i < r, round i maps (L;_i, R,-i) -4 (Li,Ri) as follows: L, = R, b R> = Li-iOf(Ri-i, 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, K, through Kp, for example, the last round is undone by simply repeating it (see Note 7.84). The / function of the Feistel cipher may be a product cipher, though / itself need not be invertible to allow inversion of the Feistel cipher.
Figure 7.9(b) illustrates that successive rounds of a Feistel cipher operate on alternating halves of the ciphertext, while the other remains constant. Note the round function of Definition 7.81 may also be re-written to eliminate Lp. Ri = Яг-2Ф/(-Кг-ь Ki). In this case, the final ciphertext output is (Rr. Rr~i), with input labeled (R (. Ro).