Data Encryption Standard (DES)

1. DES at a Glance (FIPS 46, 1977)

IBM Lucifer → NBS standard: 64-bit blocks, 56-bit key (64 bits with 8 parity), 16 Feistel rounds. Structure:

P(64) → IP → (L0 32 | R0 32)
16×: Li = R(i-1) ; Ri = L(i-1) ⊕ F(R(i-1), Ki)   [Ki = 48-bit subkey]
→ swap → FP (= IP⁻¹) → C(64)

IP/FP are keyless bookends (no security, historical hardware convenience). All strength sits in $F$ + key schedule.

2. Round Function F (E → XOR → S → P)

$F(R, K)$ : $R$ is 32 bits, $K$ 48 bits:

R(32) → Expansion E → 48 bits → XOR K(48)
→ 8 S-boxes (6→4 each) → 32 bits → Permutation P → F output

E-box $[32,1,2,3,4,5,4,5,6,7,8,9,\dots]$ : 32 → 48 by duplicating 16 edge bits — feeds diffusion (each input bit hits two S-boxes).
S-boxes $S_1 \dots S_8$ : 6 bits in (row = outer $b_1b_6$ , col = inner $b_2b_3b_4b_5$ ), 4 bits out — the ONLY nonlinear part (confusion core). Example: $S_1(011011)$ : row $01 = 1$ , col $1101 = 13$ → $5 = 0101$ .
P-box straight permutation of 32 bits — diffusion across S-boxes next round.

3. Key Schedule (56 → 16 × 48)

64-bit key (every 8th bit parity, discarded) → PC-1 → 56 bits → split $(C_0, D_0)$ 28+28 → per round $i$ : left-rotate by 1 (rounds 1,2,9,16) or 2 (others) → PC-2 selects 48 → $K_i$ . Total rotations $4 \times 1 + 12 \times 2 = 28$ = full cycle, so $(C_{16}, D_{16}) = (C_0, D_0)$ . Decrypt: apply $K_{16} \dots K_1$ .

Numerical check habit: given $C_0, D_0$ and round-1 shift 1, $K_1$ = PC-2 of once-rotated halves — exams test shift counts (which rounds shift 1?) more than full PC tables.

4. DES in One Worked Bite + Decryption

Round-0 example: $L_0 = 01234567_{hex}$ -style halves; $F$ output XOR flips $\approx$ half of $R_1$ bits (avalanche visible by round 3). Decryption proof: Feistel invertibility (Topic 2): with $(L_{16}, R_{16})$ , run same rounds with $K_{16} \to K_1$ : $R_{15} = L_{16}$ , $L_{15} = R_{16} \oplus F(L_{16}, K_{16})$ — unwinds exactly. IP/FP cancel ( $FP = IP^{-1}$ ).

5. DES Properties and Legacy

Complement property: $C = DES_K(P) \Rightarrow \bar{C} = DES_{\bar{K}}(\bar{P})$ — saves 1 bit in brute force (chosen-plaintext distinguisher).
Weak keys (4: all-0/all-1 halves → all subkeys equal; $E_K(E_K(P)) = P$ ), semi-weak pairs (6 pairs: $E_{K2}(E_{K1}(P)) = P$ ) — avoid in key generation.
56-bit key fell 1998 (EFF Deep Crack, 56 h); 64-bit block falls to Sweet32 birthdays — DES survives only as Triple-DES (Module 4 Topic 4).

Exam Points

Block diagram with IP → 16 Feistel → FP + $F$ internals (E/S/P sizes 32→48→32) — 5-mark diagram.
S-box $6 \to 4$ indexing (outer = row, inner = col) with $S_1(011011) = 0101$ trace.
Key schedule: PC-1 → shifts (1,2,9,16 shift 1) → PC-2; total 28 rotations.
Complement + weak keys statements; decrypt = reversed subkeys.

Data Encryption Standard (DES)