Chapter 15 — The Data Encryption Standard#
“For 20 years, the DES was the most widely used encryption algorithm in the world.” — Bruce Schneier, Applied Cryptography, 1996
In this chapter we implement the complete Data Encryption Standard (DES) from scratch, study its Feistel structure, and analyze its security properties including weak keys and the avalanche effect.
15.1 Historical Context#
In 1972, the U.S. National Bureau of Standards (NBS, now NIST) issued a public call for a standard encryption algorithm. IBM submitted a modified version of its Lucifer cipher, designed by Horst Feistel and refined by a team including Don Coppersmith. After review by the NSA — which controversially reduced the key length from 128 to 56 bits and modified the S-boxes — the algorithm was published as FIPS 46 in January 1977.
DES became the dominant symmetric cipher for over two decades. Its eventual demise came not from cryptanalytic weakness but from its 56-bit key length:
Year |
Event |
|---|---|
1977 |
DES published as FIPS 46 |
1993 |
Matsui’s linear cryptanalysis (2⁴³ known plaintexts) |
1997 |
RSA DES Challenge: broken in 96 days by distributed computing |
1998 |
EFF Deep Crack: broken in 56 hours ($250,000 hardware) |
1999 |
Deep Crack + distributed.net: broken in 22 hours |
2001 |
AES selected as replacement |
Tip
Although DES is now obsolete, its Feistel structure influenced nearly every subsequent block cipher. Understanding DES is essential for understanding the attacks (linear and differential cryptanalysis) that shaped modern cipher design.
15.2 The Feistel Structure#
Definition 15.1 — Feistel Network
A Feistel network of \(r\) rounds splits the input block into two halves \((L_0, R_0)\) and applies:
where \(F\) is the round function and \(K_i\) is the \(i\)-th round key.
Theorem 15.1 — Feistel Invertibility
A Feistel cipher is always invertible regardless of whether \(F\) is invertible. Decryption uses the same structure with round keys in reverse order.
Proof
Given \((L_i, R_i)\), we recover \((L_{i-1}, R_{i-1})\) by:
This uses only \(F\) in the forward direction, never \(F^{-1}\). \(\square\)
Definition 15.2 — DES Round Function
The DES round function \(F(R, K)\) consists of:
Expansion \(E\): 32 bits → 48 bits
Key mixing: XOR with 48-bit round key
S-box substitution: eight 6→4-bit S-boxes
Permutation \(P\): 32-bit straight permutation
where \(B_1 \| B_2 \| \cdots \| B_8 = E(R) \oplus K\).
15.3 Implementation#
We implement the complete DES algorithm using only NumPy. All standard tables (IP, IP⁻¹, E, P, S-boxes, PC-1, PC-2) are included.
import numpy as np
# ============================================================
# DES Standard Tables
# ============================================================
# Initial Permutation (IP)
IP_TABLE = np.array([
57, 49, 41, 33, 25, 17, 9, 1,
59, 51, 43, 35, 27, 19, 11, 3,
61, 53, 45, 37, 29, 21, 13, 5,
63, 55, 47, 39, 31, 23, 15, 7,
56, 48, 40, 32, 24, 16, 8, 0,
58, 50, 42, 34, 26, 18, 10, 2,
60, 52, 44, 36, 28, 20, 12, 4,
62, 54, 46, 38, 30, 22, 14, 6,
], dtype=int)
# Inverse Initial Permutation (IP^-1)
IP_INV_TABLE = np.zeros(64, dtype=int)
IP_INV_TABLE[IP_TABLE] = np.arange(64)
# Expansion permutation (E): 32 -> 48 bits
E_TABLE = np.array([
31, 0, 1, 2, 3, 4,
3, 4, 5, 6, 7, 8,
7, 8, 9, 10, 11, 12,
11, 12, 13, 14, 15, 16,
15, 16, 17, 18, 19, 20,
19, 20, 21, 22, 23, 24,
23, 24, 25, 26, 27, 28,
27, 28, 29, 30, 31, 0,
], dtype=int)
# P-box permutation (after S-boxes)
P_TABLE = np.array([
15, 6, 19, 20, 28, 11, 27, 16,
0, 14, 22, 25, 4, 17, 30, 9,
1, 7, 23, 13, 31, 26, 2, 8,
18, 12, 29, 5, 21, 10, 3, 24,
], dtype=int)
# 8 DES S-boxes (each: 4 rows × 16 columns)
SBOXES = np.array([
# S1
[[14,4,13,1,2,15,11,8,3,10,6,12,5,9,0,7],
[0,15,7,4,14,2,13,1,10,6,12,11,9,5,3,8],
[4,1,14,8,13,6,2,11,15,12,9,7,3,10,5,0],
[15,12,8,2,4,9,1,7,5,11,3,14,10,0,6,13]],
# S2
[[15,1,8,14,6,11,3,4,9,7,2,13,12,0,5,10],
[3,13,4,7,15,2,8,14,12,0,1,10,6,9,11,5],
[0,14,7,11,10,4,13,1,5,8,12,6,9,3,2,15],
[13,8,10,1,3,15,4,2,11,6,7,12,0,5,14,9]],
# S3
[[10,0,9,14,6,3,15,5,1,13,12,7,11,4,2,8],
[13,7,0,9,3,4,6,10,2,8,5,14,12,11,15,1],
[13,6,4,9,8,15,3,0,11,1,2,12,5,10,14,7],
[1,10,13,0,6,9,8,7,4,15,14,3,11,5,2,12]],
# S4
[[7,13,14,3,0,6,9,10,1,2,8,5,11,12,4,15],
[13,8,11,5,6,15,0,3,4,7,2,12,1,10,14,9],
[10,6,9,0,12,11,7,13,15,1,3,14,5,2,8,4],
[3,15,0,6,10,1,13,8,9,4,5,11,12,7,2,14]],
# S5
[[2,12,4,1,7,10,11,6,8,5,3,15,13,0,14,9],
[14,11,2,12,4,7,13,1,5,0,15,10,3,9,8,6],
[4,2,1,11,10,13,7,8,15,9,12,5,6,3,0,14],
[11,8,12,7,1,14,2,13,6,15,0,9,10,4,5,3]],
# S6
[[12,1,10,15,9,2,6,8,0,13,3,4,14,7,5,11],
[10,15,4,2,7,12,9,5,6,1,13,14,0,11,3,8],
[9,14,15,5,2,8,12,3,7,0,4,10,1,13,11,6],
[4,3,2,12,9,5,15,10,11,14,1,7,6,0,8,13]],
# S7
[[4,11,2,14,15,0,8,13,3,12,9,7,5,10,6,1],
[13,0,11,7,4,9,1,10,14,3,5,12,2,15,8,6],
[1,4,11,13,12,3,7,14,10,15,6,8,0,5,9,2],
[6,11,13,8,1,4,10,7,9,5,0,15,14,2,3,12]],
# S8
[[13,2,8,4,6,15,11,1,10,9,3,14,5,0,12,7],
[1,15,13,8,10,3,7,4,12,5,6,11,0,14,9,2],
[7,11,4,1,9,12,14,2,0,6,10,13,15,3,5,8],
[2,1,14,7,4,10,8,13,15,12,9,0,3,5,6,11]],
], dtype=int)
# Key schedule: Permuted Choice 1 (PC-1): 64 -> 56 bits
PC1_TABLE = np.array([
56, 48, 40, 32, 24, 16, 8,
0, 57, 49, 41, 33, 25, 17,
9, 1, 58, 50, 42, 34, 26,
18, 10, 2, 59, 51, 43, 35,
62, 54, 46, 38, 30, 22, 14,
6, 61, 53, 45, 37, 29, 21,
13, 5, 60, 52, 44, 36, 28,
20, 12, 4, 27, 19, 11, 3,
], dtype=int)
# Permuted Choice 2 (PC-2): 56 -> 48 bits
PC2_TABLE = np.array([
13, 16, 10, 23, 0, 4,
2, 27, 14, 5, 20, 9,
22, 18, 11, 3, 25, 7,
15, 6, 26, 19, 12, 1,
40, 51, 30, 36, 46, 54,
29, 39, 50, 44, 32, 47,
43, 48, 38, 55, 33, 52,
45, 41, 49, 35, 28, 31,
], dtype=int)
# Left rotation schedule per round
ROTATION_SCHEDULE = np.array([1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1], dtype=int)
print('DES tables loaded.')
print(f'S-boxes shape: {SBOXES.shape}')
DES tables loaded.
S-boxes shape: (8, 4, 16)
import numpy as np
class DES:
"""Complete DES implementation using NumPy bit arrays."""
def __init__(self, key_64bit):
"""
Initialize DES with a 64-bit key (including 8 parity bits).
key_64bit: numpy array of 64 bits
"""
self.key = np.array(key_64bit, dtype=int)
assert len(self.key) == 64
self.round_keys = self._key_schedule()
def _permute(self, data, table):
"""Apply a permutation table to data."""
return data[table]
def _left_rotate(self, data, n):
"""Left circular shift by n positions."""
return np.roll(data, -n)
def _key_schedule(self):
"""Generate 16 round keys (each 48 bits)."""
# Apply PC-1: 64 -> 56 bits
key56 = self._permute(self.key, PC1_TABLE)
C = key56[:28].copy()
D = key56[28:].copy()
round_keys = []
for i in range(16):
C = self._left_rotate(C, ROTATION_SCHEDULE[i])
D = self._left_rotate(D, ROTATION_SCHEDULE[i])
CD = np.concatenate([C, D])
round_key = self._permute(CD, PC2_TABLE)
round_keys.append(round_key)
return round_keys
def _sbox_lookup(self, six_bits, sbox_idx):
"""Look up a 6-bit input in the specified S-box, return 4 bits."""
# Row = outer bits (bit0, bit5), Column = inner bits (bit1-4)
row = six_bits[0] * 2 + six_bits[5]
col = six_bits[1] * 8 + six_bits[2] * 4 + six_bits[3] * 2 + six_bits[4]
val = SBOXES[sbox_idx, row, col]
# Convert to 4 bits
return np.array([(val >> 3) & 1, (val >> 2) & 1, (val >> 1) & 1, val & 1], dtype=int)
def _feistel(self, R, round_key):
"""DES Feistel function F(R, K)."""
# Expansion: 32 -> 48 bits
expanded = self._permute(R, E_TABLE)
# XOR with round key
xored = expanded ^ round_key
# S-box substitution: 48 -> 32 bits
sbox_out = np.zeros(32, dtype=int)
for i in range(8):
chunk = xored[6*i : 6*i+6]
sbox_out[4*i : 4*i+4] = self._sbox_lookup(chunk, i)
# P-box permutation
return self._permute(sbox_out, P_TABLE)
def encrypt_block(self, plaintext_64bit):
"""Encrypt a single 64-bit block."""
data = np.array(plaintext_64bit, dtype=int)
# Initial permutation
data = self._permute(data, IP_TABLE)
L, R = data[:32].copy(), data[32:].copy()
# 16 Feistel rounds
for i in range(16):
new_L = R.copy()
new_R = L ^ self._feistel(R, self.round_keys[i])
L, R = new_L, new_R
# Final swap and inverse IP
combined = np.concatenate([R, L]) # Note: R, L (not L, R)
return self._permute(combined, IP_INV_TABLE)
def decrypt_block(self, ciphertext_64bit):
"""Decrypt a single 64-bit block (reverse round key order)."""
data = np.array(ciphertext_64bit, dtype=int)
data = self._permute(data, IP_TABLE)
L, R = data[:32].copy(), data[32:].copy()
# 16 rounds with keys in reverse order
for i in range(15, -1, -1):
new_L = R.copy()
new_R = L ^ self._feistel(R, self.round_keys[i])
L, R = new_L, new_R
combined = np.concatenate([R, L])
return self._permute(combined, IP_INV_TABLE)
def encrypt_block_rounds(self, plaintext_64bit):
"""Encrypt and return intermediate state after each round."""
data = np.array(plaintext_64bit, dtype=int)
data = self._permute(data, IP_TABLE)
L, R = data[:32].copy(), data[32:].copy()
states = [np.concatenate([L, R]).copy()]
for i in range(16):
new_L = R.copy()
new_R = L ^ self._feistel(R, self.round_keys[i])
L, R = new_L, new_R
states.append(np.concatenate([L, R]).copy())
return states
def generate_des_key(key_56bit):
"""Generate a 64-bit DES key from 56 key bits (add parity bits)."""
key_56 = np.array(key_56bit, dtype=int)
key_64 = np.zeros(64, dtype=int)
for i in range(8):
key_64[8*i : 8*i+7] = key_56[7*i : 7*i+7]
key_64[8*i+7] = (1 + np.sum(key_56[7*i : 7*i+7])) % 2 # odd parity
return key_64
# --- Demo ---
rng = np.random.default_rng(42)
key56 = rng.integers(0, 2, size=56)
key64 = generate_des_key(key56)
plaintext = rng.integers(0, 2, size=64)
des = DES(key64)
ciphertext = des.encrypt_block(plaintext)
decrypted = des.decrypt_block(ciphertext)
print(f'Plaintext: {"".join(map(str, plaintext[:16]))}...')
print(f'Ciphertext: {"".join(map(str, ciphertext[:16]))}...')
print(f'Decrypted: {"".join(map(str, decrypted[:16]))}...')
print(f'Match: {np.array_equal(plaintext, decrypted)}')
Plaintext: 1011110100100010...
Ciphertext: 1100010010010100...
Decrypted: 1011110100100010...
Match: True
import numpy as np
# Correctness test: encrypt/decrypt 100 random blocks
rng = np.random.default_rng(123)
n_tests = 100
all_match = True
for _ in range(n_tests):
key = generate_des_key(rng.integers(0, 2, size=56))
pt = rng.integers(0, 2, size=64)
des_test = DES(key)
ct = des_test.encrypt_block(pt)
dt = des_test.decrypt_block(ct)
if not np.array_equal(pt, dt):
all_match = False
break
print(f'Tested {n_tests} random encrypt/decrypt cycles: {"ALL PASSED" if all_match else "FAILED"}')
Tested 100 random encrypt/decrypt cycles: ALL PASSED
15.4 Key Space and Security#
Key Space
DES uses a 56-bit effective key, giving \(2^{56} \approx 7.2 \times 10^{16}\) possible keys. By modern standards this is far too small — an exhaustive search is feasible with specialized hardware or distributed computing.
Danger
DES should never be used for new applications. Triple-DES (3DES) provides 112-bit effective security but is also being phased out in favor of AES.
15.5 Experiments#
Experiment 1: Avalanche Effect#
A single bit flip in the plaintext should affect approximately half the ciphertext bits. We measure the avalanche across all 16 rounds.
Show code cell source
import numpy as np
import matplotlib.pyplot as plt
rng = np.random.default_rng(42)
key = generate_des_key(rng.integers(0, 2, size=56))
des_av = DES(key)
# Average over multiple random plaintexts and bit positions
n_trials = 200
n_rounds = 17 # 0 (initial) + 16 rounds
avg_diff = np.zeros(n_rounds)
for _ in range(n_trials):
pt = rng.integers(0, 2, size=64)
bit_pos = rng.integers(0, 64)
pt_flipped = pt.copy()
pt_flipped[bit_pos] ^= 1
states1 = des_av.encrypt_block_rounds(pt)
states2 = des_av.encrypt_block_rounds(pt_flipped)
for r in range(n_rounds):
diff_bits = np.sum(states1[r] != states2[r])
avg_diff[r] += diff_bits / n_trials
fig, ax = plt.subplots(figsize=(10, 5))
rounds = np.arange(n_rounds)
ax.plot(rounds, avg_diff, 'o-', color='#e74c3c', linewidth=2, markersize=6)
ax.axhline(y=32, color='green', linestyle='--', alpha=0.5, label='Ideal (32 bits = 50%)')
ax.set_xlabel('Round')
ax.set_ylabel('Average Differing Bits (out of 64)')
ax.set_title('DES Avalanche Effect: 1-Bit Plaintext Change')
ax.set_xticks(rounds)
ax.legend()
ax.grid(True, alpha=0.3)
ax.set_ylim(0, 40)
plt.tight_layout()
plt.savefig('des_avalanche.png', dpi=150, bbox_inches='tight')
plt.show()
print(f'After round 1: {float(avg_diff[1]):.1f} bits differ')
print(f'After round 5: {float(avg_diff[5]):.1f} bits differ')
print(f'After round 16: {float(avg_diff[16]):.1f} bits differ')
After round 1: 3.0 bits differ
After round 5: 32.0 bits differ
After round 16: 32.0 bits differ
Observation
Full diffusion is achieved by approximately round 5–6. By round 16, a single bit change in the plaintext produces an average of ~32 differing ciphertext bits — exactly the ideal 50% threshold.
Experiment 2: Weak Keys#
DES has 4 weak keys where all 16 round keys are identical. Encrypting twice with a weak key returns the original plaintext.
Show code cell source
import numpy as np
import matplotlib.pyplot as plt
def bits_from_hex(hex_str):
"""Convert hex string to bit array."""
bits = []
for h in hex_str:
val = int(h, 16)
bits.extend([(val >> 3) & 1, (val >> 2) & 1, (val >> 1) & 1, val & 1])
return np.array(bits, dtype=int)
def hex_from_bits(bits):
"""Convert bit array to hex string."""
result = []
for i in range(0, len(bits), 4):
val = bits[i]*8 + bits[i+1]*4 + bits[i+2]*2 + bits[i+3]
result.append(f'{val:X}')
return ''.join(result)
# The 4 DES weak keys (in hex, including parity bits)
weak_keys_hex = [
'0101010101010101', # All zeros (with parity)
'FEFEFEFEFEFEFEFE', # All ones (with parity)
'E0E0E0E0F1F1F1F1', # C-half zeros, D-half ones
'1F1F1F1F0E0E0E0E', # C-half ones, D-half zeros
]
rng = np.random.default_rng(42)
pt = rng.integers(0, 2, size=64)
print('DES Weak Keys: E(E(P, K_weak), K_weak) = P')
print('=' * 60)
for hex_key in weak_keys_hex:
key_bits = bits_from_hex(hex_key)
des_w = DES(key_bits)
# Check all round keys are identical
rk = des_w.round_keys
all_same = all(np.array_equal(rk[0], rk[i]) for i in range(1, 16))
# Double encryption should equal plaintext
ct = des_w.encrypt_block(pt)
double_ct = des_w.encrypt_block(ct)
is_involution = np.array_equal(pt, double_ct)
print(f'Key: {hex_key}')
print(f' All round keys identical: {all_same}')
print(f' E(E(P,K),K) = P: {is_involution}')
print()
# Visualize round key uniqueness for weak vs normal key
normal_key = generate_des_key(rng.integers(0, 2, size=56))
des_n = DES(normal_key)
weak_key = bits_from_hex('0101010101010101')
des_wk = DES(weak_key)
fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(12, 5))
# Normal key: show hamming distances between consecutive round keys
normal_dists = [np.sum(des_n.round_keys[i] != des_n.round_keys[i+1]) for i in range(15)]
weak_dists = [np.sum(des_wk.round_keys[i] != des_wk.round_keys[i+1]) for i in range(15)]
ax1.bar(range(15), normal_dists, color='#3498db', alpha=0.8)
ax1.set_xlabel('Round Pair (i, i+1)')
ax1.set_ylabel('Hamming Distance')
ax1.set_title('Normal Key: Round Key Differences')
ax1.set_ylim(0, 30)
ax2.bar(range(15), weak_dists, color='#e74c3c', alpha=0.8)
ax2.set_xlabel('Round Pair (i, i+1)')
ax2.set_ylabel('Hamming Distance')
ax2.set_title('Weak Key: Round Key Differences (All Zero!)')
ax2.set_ylim(0, 30)
plt.tight_layout()
plt.savefig('des_weak_keys.png', dpi=150, bbox_inches='tight')
plt.show()
DES Weak Keys: E(E(P, K_weak), K_weak) = P
============================================================
Key: 0101010101010101
All round keys identical: True
E(E(P,K),K) = P: True
Key: FEFEFEFEFEFEFEFE
All round keys identical: True
E(E(P,K),K) = P: True
Key: E0E0E0E0F1F1F1F1
All round keys identical: True
E(E(P,K),K) = P: True
Key: 1F1F1F1F0E0E0E0E
All round keys identical: True
E(E(P,K),K) = P: True
Experiment 3: Complementation Property#
DES satisfies \(E_K(P) = \overline{E_{\overline{K}}(\overline{P})}\), which halves the effective search space for brute force.
import numpy as np
rng = np.random.default_rng(42)
n_tests = 50
all_pass = True
for _ in range(n_tests):
key = generate_des_key(rng.integers(0, 2, size=56))
pt = rng.integers(0, 2, size=64)
key_comp = 1 - key # Complement the key
pt_comp = 1 - pt # Complement the plaintext
des1 = DES(key)
des2 = DES(key_comp)
ct1 = des1.encrypt_block(pt)
ct2 = des2.encrypt_block(pt_comp)
ct2_comp = 1 - ct2 # Complement of ct2
if not np.array_equal(ct1, ct2_comp):
all_pass = False
break
print(f'Complementation property E_K(P) = complement(E_{{comp(K)}}(comp(P)))')
print(f'Tested {n_tests} random cases: {"ALL PASSED" if all_pass else "FAILED"}')
print()
print('Implication: brute force search needs only 2^55 encryptions (not 2^56)')
print('because for each key K tried, we get the result for complement(K) for free.')
Complementation property E_K(P) = complement(E_{comp(K)}(comp(P)))
Tested 50 random cases: ALL PASSED
Implication: brute force search needs only 2^55 encryptions (not 2^56)
because for each key K tried, we get the result for complement(K) for free.
Experiment 4: Diffusion Heatmap Across Rounds#
We visualize which output bits are affected by flipping each input bit, across different numbers of rounds.
Show code cell source
import numpy as np
import matplotlib.pyplot as plt
rng = np.random.default_rng(42)
key = generate_des_key(rng.integers(0, 2, size=56))
des_hm = DES(key)
# For selected rounds, build a 64×64 diffusion matrix
rounds_to_show = [1, 3, 5, 16]
n_samples = 100
fig, axes = plt.subplots(1, 4, figsize=(16, 4))
for ax, r in zip(axes, rounds_to_show):
diff_matrix = np.zeros((64, 64))
for _ in range(n_samples):
pt = rng.integers(0, 2, size=64)
states_orig = des_hm.encrypt_block_rounds(pt)
for bit in range(64):
pt_flip = pt.copy()
pt_flip[bit] ^= 1
states_flip = des_hm.encrypt_block_rounds(pt_flip)
diff = (states_orig[r] != states_flip[r]).astype(float)
diff_matrix[bit] += diff / n_samples
im = ax.imshow(diff_matrix, cmap='YlOrRd', aspect='equal', vmin=0, vmax=1)
ax.set_title(f'Round {r}')
ax.set_xlabel('Output bit')
if r == rounds_to_show[0]:
ax.set_ylabel('Flipped input bit')
plt.colorbar(im, ax=axes[-1], label='P(bit differs)', shrink=0.8)
fig.suptitle('DES Diffusion: Input Bit → Output Bit Influence', fontsize=13, y=1.02)
plt.tight_layout()
plt.savefig('des_diffusion_heatmap.png', dpi=150, bbox_inches='tight')
plt.show()
Observation
After round 1, the Feistel structure ensures only half the bits are affected (the right half influences the left half via \(F\)). By round 5, the heatmap shows near-uniform influence — every input bit affects every output bit with probability close to 0.5. This is the diffusion property that Shannon identified as essential for security.
15.6 Exercises#
Exercise 15.1 (Warm-up) Verify the Feistel invertibility theorem by implementing a generic 4-round Feistel cipher with a random round function \(F\) and confirming that decryption recovers the plaintext.
Hint
Define \(F(R, K) = \) random permutation of bits. Implement the Feistel encryption and decryption as described in the theorem, using opposite key order.
Exercise 15.2 (Applied) DES has 4 weak keys and 6 pairs of semi-weak keys (12 keys total). A semi-weak pair \((K_1, K_2)\) satisfies \(E_{K_1}(E_{K_2}(P)) = P\). Find all semi-weak key pairs by searching for keys whose round key schedules are reverses of each other.
Hint
Semi-weak keys have the property that their C and D halves consist of repeating patterns (e.g., alternating 01). Enumerate keys where C and D are each one of: all-0, all-1, alternating-01, alternating-10.
Exercise 15.3 (Analysis) Show that 2DES (double DES) with two independent 56-bit keys provides only \(2^{57}\) effective security, not \(2^{112}\), due to a meet-in-the-middle attack.
Hint
Given \((P, C)\): encrypt \(P\) with all \(2^{56}\) keys \(K_1\), decrypt \(C\) with all \(2^{56}\) keys \(K_2\), and look for matches in the middle. This requires \(O(2^{56})\) time and \(O(2^{56})\) storage.
Exercise 15.4 (Theory) Prove the complementation property: \(E_K(P) = \overline{E_{\bar{K}}(\bar{P})}\).
Hint
Show by induction that after each round, if we complement both halves and the round key, the XOR structure of the Feistel function preserves the complementation through the expansion and S-box stages.
Exercise 15.5 (Challenge) Implement a reduced DES with only 6 rounds. Generate 100 random plaintext-ciphertext pairs and verify that the avalanche is incomplete (some bit correlations remain). What is the minimum number of rounds for full avalanche?
Hint
Modify encrypt_block_rounds to stop after \(r\) rounds. Measure the
standard deviation of the diffusion matrix — it should be close to 0
for full avalanche and positive for incomplete diffusion.
15.7 Summary#
Concept |
Key Point |
|---|---|
Structure |
16-round Feistel network on 64-bit blocks |
Key length |
56 bits effective (plus 8 parity bits) |
Round function |
Expansion → XOR → 8 S-boxes → P-permutation |
Feistel property |
Always invertible, regardless of round function |
Weak keys |
4 keys where all round keys are identical |
Complementation |
\(E_K(P) = \overline{E_{\bar{K}}(\bar{P})}\) halves search space |
Avalanche |
Full diffusion by round 5–6 |
Tip
DES is now the standard target for both linear and differential cryptanalysis. In Chapters 16–18, we will use linear cryptanalysis (Matsui 1993) to attack an SPN cipher modeled on DES. In Chapters 19–21, differential cryptanalysis (Biham & Shamir 1991) will provide an even more powerful attack.
References#
Feistel, H. (1973). Cryptography and Computer Privacy. Scientific American, 228(5), 15–23.
National Bureau of Standards (1977). Data Encryption Standard. FIPS Publication 46.
Biham, E. and Shamir, A. (1991). Differential Cryptanalysis of DES-like Cryptosystems. Journal of Cryptology, 4(1), 3–72. [9]
Matsui, M. (1994). Linear Cryptanalysis Method for DES Cipher. EUROCRYPT ‘93, LNCS 765, 386–397. [10]
Heys, H. M. (2002). A Tutorial on Linear and Differential Cryptanalysis. Cryptologia, 26(3), 189–221. [11]