The DES encryption algorithm.

Block Ciphers and DES

1. Two Kinds of Symmetric Encryption

---

2. Basic Idea of Block Ciphers

• Definition: an invertible transformation that maps n bits of plaintext to n bits of ciphertext $$C = E_K(M), \quad M = D_K(C)$$
• Core goal: emulate an ideal random substitution (security)
• Implementation: approximate the ideal substitution with multiple rounds of substitution + permutation (S/P).

---

3. Shannon’s Two Principles

---

4. The Feistel Structure (Core of Modern Block Ciphers)

DES, Blowfish and SM4 are all based on it.

Encryption:

$$L_i = R_{i-1}, \quad R_i = L_{i-1} \oplus F(R_{i-1}, K_i)$$

Decryption:

$$R_{i-1} = L_i, \quad L_{i-1} = R_i \oplus F(L_i, K_i)$$

✅ Conclusion:
Decryption = the encryption structure + subkeys used in reverse order

Advantages:

• The structure is invertible;
• Security is scalable (stack more rounds).

---

5. Simplified DES (S-DES)

• Teaching model: 8-bit plaintext + 10-bit key, 2 Feistel rounds;
• Structure: IP → fK₁ → SW → fK₂ → IP⁻¹;
• Illustrates the core idea of “round function + key schedule + left/right swap”.

---

6. DES (Data Encryption Standard)

---

Key Elements of DES

1. S-box:

   • The only nonlinear part;
   • 6-bit input → 4-bit output;
   • The row is determined by bits 1 and 6, the column by the middle 4 bits.

2. Key schedule:

   • Master key → PC-1 → two 28-bit halves (C, D);
   • Each round: circular left shift → PC-2 compression → 48-bit subkey Ki.

3. Symmetry of encryption and decryption:

   • Encryption: K₁→K₂→…→K₁₆
   • Decryption: K₁₆→K₁₅→…→K₁

---

7. Security of DES

DES is still the cornerstone for understanding the structure of modern block ciphers.

---

8. Block Cipher Design Criteria (Key Points to Remember)

• Confusion + diffusion (Shannon’s principles)
• Enough rounds (increase nonlinearity)
• Avalanche effect (SAC): 1 input bit changes → about half of the output bits change
• Bit independence criterion (BIC): changes in output bits are mutually independent
• Complex key schedule: prevents related-key attacks

---

9. Typical Application Scenarios

• Anonymous routing (onion routing): layer-by-layer encryption guarantees path anonymity
• Revocable encryption (copyright protection): revoking a single user’s key does not affect the others

Feistel structure + S-box nonlinearity + multi-round confusion and diffusion = the soul of modern block ciphers.

Block Ciphers in the Post-DES Era

1. From DES to Stronger Block Ciphers

Background

• The DES key is only 56 bits; brute-force attacks are already feasible.
• Two lines of development:
  1️⃣ Iterate DES multiple times (e.g. double DES, triple DES);
  2️⃣ Design brand-new block ciphers (IDEA, AES, SM4).

---

2. Double DES (2DES)

Structure

$$C = E_{K_2}(E_{K_1}(P))$$

Key length: 112 bits (in theory).

Attack: Meet-in-the-Middle (MITM)

1. For every (K1) compute (E{K_1}(P)) and store it in a table.
2. For every (K2) compute (D{K_2}(C)) and compare against the table.
3. A match yields a candidate key pair.

Complexity

• Time: about (2^{57}) DES operations;
• Space: about (2^{56}) entries;
• Only two (P, C) pairs are needed for verification.

✅ Result: the security of double DES ≈ single DES.

---

3. Triple DES (3DES)

Structure (EDE mode, DES-compatible)

$$C = E_{K_1}[D_{K_2}[E_{K_1}(P)]]$$

Decryption is analogous:

$$P = D_{K_1}[E_{K_2}[D_{K_1}(C)]]$$

• Two-key or three-key versions are available:

  • 2-key 3DES: (K_1=K_3), key length 112 bits.
  • 3-key 3DES: three independent keys, length 168 bits.

Security

• Resistance to differential and linear cryptanalysis ≫ DES.
• Brute force requires on the order of (2^{112}) operations.
• No practical attack exists today.

Pros and Cons

✅ Pros:

• Compatible with DES, security improved more than a hundredfold.
  ❌ Cons:
• Slow (3 DES operations).
• Block size is still 64 bits.
  → Gradually replaced by AES.

---

4. IDEA (International Data Encryption Algorithm)

Basic Features

Confusion and Diffusion Mechanism

Based on three operations:

• XOR (⊕)
• Addition modulo (2^{16}) (⊞)
• Multiplication modulo (2^{16}+1) (⊙)

→ Diverse algebraic structures, enhanced nonlinearity.

Advantages

• Resists differential cryptanalysis;
• Efficient in both software and hardware;
• Software speed about twice that of DES;
• Used in PGP (Pretty Good Privacy).

---

5. AES (Advanced Encryption Standard)

History and Selection

• NIST launched the competition in 1997 and selected the Rijndael algorithm in 2001.
• Goal: faster than 3DES and at least as secure.

Basic Parameters

---

The Four Core Steps of the Round Function (Each Round)

1️⃣ SubBytes: nonlinear S-box transformation (confusion).
2️⃣ ShiftRows: cyclic row shifts (diffusion).
3️⃣ MixColumns: polynomial arithmetic in GF(2⁸) (diffusion).
4️⃣ AddRoundKey: XOR with the subkey (key control).

The first and last rounds are slightly adjusted (the last round has no MixColumns).

Key Expansion

• Each 128-bit round key is generated via word rotation and the S-box;
• Supports flexible key lengths (Nk = 4/6/8).

Advantages of AES

✅ Fast (software/hardware)
✅ Resists differential, linear and power attacks
✅ Low memory footprint, suitable for embedded systems
✅ Open, patent-free, cross-platform
❌ Theoretically still vulnerable to side-channel attacks (defensive design required)

AES has become the mainstream symmetric encryption standard worldwide.

---

6. SM4 (China’s Commercial Block Cipher Standard)

Basic Features

Algorithm Characteristics

• Encryption and decryption share the same structure (round keys in reverse order).
• Uses a mix of S-boxes + linear shifts + XOR.
• 32-round key expansion using the constants FK and CK.
• Security comparable to AES.

Applications

• WAPI wireless LAN
• Government, financial and commercial encryption standard systems (the SM series)

---

7. Summary Comparison

---

8. Key Points to Remember

1. Double DES is vulnerable to the meet-in-the-middle attack; security ≈ DES.
2. Triple DES (EDE) is a transitional scheme; the two-key version is the most common.
3. IDEA uses mixed arithmetic (⊕, ⊞, ⊙) and is strongly resistant to differential cryptanalysis.
4. AES = SPN structure (SubBytes, ShiftRows, MixColumns, AddRoundKey).
5. SM4 = China’s national commercial block cipher, 128-bit blocks, 32-round unbalanced Feistel.
6. AES and SM4 have both replaced 3DES as the current mainstream standards.

---

Translated from the Chinese original.