How DES Permutes and Substitutes 64-Bit Blocks

The Data Encryption Standard (DES) encrypts data in 64-bit blocks using a symmetric 16-round Feistel network based on alternating stages of permutation and substitution. Permutations rearrange the positions of binary bits to provide diffusion, while substitutions replace bit patterns with new values via non-linear tables to provide confusion. This process ensures that a change in a single bit of plaintext or key propagates unpredictably across the entire 64-bit ciphertext block.

1. Initial Permutation (IP)

The 64-bit input block, represented as a binary sequence from bit 1 to bit 64, first enters the Initial Permutation (IP). The IP is a fixed transposition that rearranges the bits according to a predefined matrix: * All even-indexed bits are shifted to the left half of the block. * All odd-indexed bits are shifted to the right half of the block.

The resulting 64-bit block is split into two 32-bit halves: the Left block (\(L_0\)) and the Right block (\(R_0\)).

2. The Round Structure and Expansion Permutation (E-Box)

DES executes 16 identical rounds. In each round \(i\) (from 1 to 16), the 32-bit right half (\(R_{i-1}\)) undergoes the Feistel function (\(f\)), while the left half (\(L_{i-1}\)) is XORed with the output of \(f\): \[L_i = R_{i-1}\] \[R_i = L_{i-1} \oplus f(R_{i-1}, K_i)\]

Inside the Feistel function, the 32-bit half is first expanded to 48 bits using the Expansion Permutation (E-box). The E-box rearranges the 32 bits and duplicates 16 specific bits, creating 8 groups of 6 bits. This ensures each bit influences two separate substitutions in the next stage.

3. Key Mixing and S-Box Substitution

The expanded 48-bit block is combined with a 48-bit round subkey (\(K_i\)) using bitwise XOR (\(\oplus\)). The 48-bit result is then reduced back to 32 bits through the substitution process using eight distinct Substitution Boxes (\(S_1\) to \(S_8\)): * The 48-bit stream is split into eight 6-bit chunks (\(B_1, B_2, \dots, B_8\)). * Each chunk \(B_j\) is processed by its corresponding box \(S_j\). * In each 6-bit chunk (\(b_1 b_2 b_3 b_4 b_5 b_6\)), the first and last bits (\(b_1 b_6\)) form a 2-bit binary number (0–3) to select the matrix row. * The middle four bits (\(b_2 b_3 b_4 b_5\)) form a 4-bit binary number (0–15) to select the matrix column. * The intersection of the row and column in the S-box yields a unique 4-bit output.

Combining the 4-bit outputs from all eight S-boxes produces a 32-bit block. This substitution stage is the only non-linear component of DES, making the cipher resistant to linear cryptanalysis.

4. Permutation Function (P-Box)

The 32-bit output from the S-boxes is passed through a straight 32-bit permutation known as the P-box. The P-box does not add, remove, or substitute bits; it rearranges the 32 bits according to a fixed mapping. This step ensures that the 4-bit output of each S-box is distributed across multiple S-boxes in the subsequent round, accelerating the avalanche effect.

5. Inverse Initial Permutation (\(IP^{-1}\))

After completing 16 rounds, the final left and right 32-bit halves are swapped and concatenated into a single 64-bit block (\(R_{16}L_{16}\)). This 64-bit block passes through the Inverse Initial Permutation (\(IP^{-1}\)), also known as the Final Permutation.

The \(IP^{-1}\) matrix is the exact mathematical inverse of the Initial Permutation matrix. It restores the transposed bits into the standard format, producing the final 64-bit encrypted ciphertext block.