DES 加密算法原理與 VC++ 實現（上）：核心流程、置換表與 f 函數深度解析

前言

DES (Data Encryption Standard) 為 1977 年美國 NBS 發布的對稱加密標準，雖已被 AES 取代，但其結構設計（Feistel 網路、S 盒非線性、置換擴散）仍是現代密碼學教學與輕量級加密的經典範本。本文系統解析 DES 加密核心流程、各置換表定義、f 函數內部結構，並提供 VC++ 6.0 關鍵實作代碼。

整體加密流程：Feistel 網路 16 輪

明文 (64位) → IP 置換 → (L₀, R₀) → 16 輪迭代 → (R₁₆, L₁₆) → IP⁻¹ 置換 → 密文 (64位)

每輪迭代：
Lᵢ = Rᵢ₋₁
Rᵢ = Lᵢ₋₁ ⊕ f(Rᵢ₋₁, Kᵢ)

f 函數：32位 → E擴展(48位) → ⊕Kᵢ(48位) → S盒(32位) → P置換(32位)

關鍵置換表完整定義

1. IP 初始置換表 (64→64)

58 50 42 34 26 18 10  2
60 52 44 36 28 20 12  4
62 54 46 38 30 22 14  6
64 56 48 40 32 24 16  8
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

2. IP⁻¹ 逆置換表 (64→64)

40  8 48 16 56 24 64 32
39  7 47 15 55 23 63 31
38  6 46 14 54 22 62 30
37  5 45 13 53 21 61 29
36  4 44 12 52 20 60 28
35  3 43 11 51 19 59 27
34  2 42 10 50 18 58 26
33  1 41  9 49 17 57 25

3. E 擴展置換表 (32→48)

32  1  2  3  4  5
 4  5  6  7  8  9
 8  9 10 11 12 13
12 13 14 15 16 17
16 17 18 19 20 21
20 21 22 23 24 25
24 25 26 27 28 29
28 29 30 31 32  1

4. P 置換表 (32→32)

16  7 20 21
29 12 28 17
 1 15 23 26
 5 18 31 10
 2  8 24 14
32 27  3  9
19 13 30  6
22 11  4 25

f 函數深度解析

輸入: Rᵢ₋₁ (32位), Kᵢ (48位)
1. E擴展: Rᵢ₋₁ → 48位
2. 異或: 48位 ⊕ Kᵢ → 48位
3. 分組: 48位 ÷ 8 = 8組 × 6位
4. S盒查表: 每組 6位 → 4位 (行: b₁b₆, 列: b₂b₃b₄b₅)
5. 合併: 8×4位 = 32位
6. P置換: 32位置換 → 輸出 f(Rᵢ₋₁, Kᵢ) (32位)

S 盒結構 (8 個 4×16 查表)

每個 S 盒：4 行 (0-3) × 16 列 (0-15)，值域 0-15 (4 位)。

輸入 6 位 b₁b₂b₃b₄b₅b₆：

• 行號 = b₁×2 + b₆ (二進制，取首尾位)
• 列號 = b₂×8 + b₃×4 + b₄×2 + b₅ (中間四位)
• 輸出 = S[row][col] 轉 4 位二進制

VC++ 6.0 關鍵實作代碼

1. IP 置換

for (i = 1; i <= 64; i++)
    m1[i] = m[ip[i-1]];  // ip[] 為 IP 表 (0-based 索引)

2. 第 8 輪迭代範例 (其餘輪次同理)

// E 擴展: 32位 -> 48位
for (i = 1; i <= 48; i++)
    RE1[i] = R7[E[i-1]];

// 異或子金鑰 K8
for (i = 1; i <= 48; i++) {
    RE1[i] = RE1[i] + K8[i];  // 模 2 加法
    if (RE1[i] == 2) RE1[i] = 0;
}

// 分組進 8 個 S 盒
for (i = 1; i < 7; i++) {
    s11[i] = RE1[i];
    s21[i] = RE1[i+6];
    s31[i] = RE1[i+12];
    s41[i] = RE1[i+18];
    s51[i] = RE1[i+24];
    s61[i] = RE1[i+30];
    s71[i] = RE1[i+36];
    s81[i] = RE1[i+42];
}

// S 盒查表 (s1~s8 為 4×16 整數陣列)
s[1] = s1[s11[6] + s11[1]*2][s11[5] + s11[4]*2 + s11[3]*4 + s11[2]*8];
s[2] = s2[s21[6] + s21[1]*2][s21[5] + s21[4]*2 + s21[3]*4 + s21[2]*8];
s[3] = s3[s31[6] + s31[1]*2][s31[5] + s31[4]*2 + s31[3]*4 + s31[2]*8];
s[4] = s4[s41[6] + s41[1]*2][s41[5] + s41[4]*2 + s41[3]*4 + s41[2]*8];
s[5] = s5[s51[6] + s51[1]*2][s51[5] + s51[4]*2 + s51[3]*4 + s51[2]*8];
s[6] = s6[s61[6] + s61[1]*2][s61[5] + s61[4]*2 + s61[3]*4 + s61[2]*8];
s[7] = s7[s71[6] + s71[1]*2][s71[5] + s71[4]*2 + s71[3]*4 + s71[2]*8];
s[8] = s8[s81[6] + s81[1]*2][s81[5] + s81[4]*2 + s81[3]*4 + s81[2]*8];

// 8 個 4位值合併為 32位
for (i = 0; i < 8; i++) {
    for (j = 1; j < 5; j++) {
        temp[j] = s[i+1] % 2;
        s[i+1] = s[i+1] / 2;
    }
    for (j = 1; j < 5; j++)
        f[4*i + j] = temp[5-j];  // 高位在前
}

// P 置換
for (i = 1; i < 33; i++)
    frk[i] = f[P[i-1]];

// Feistel 交換與異或
for (i = 1; i < 33; i++)
    L8[i] = R7[i];
for (i = 1; i < 33; i++) {
    R8[i] = L7[i] + frk[i];
    if (R8[i] == 2) R8[i] = 0;
}

3. 最終 IP⁻¹ 置換

// 合併 R16 || L16 (注意順序！)
for (i = 1; i <= 32; i++) final[i] = R16[i];
for (i = 1; i <= 32; i++) final[i+32] = L16[i];

// IP⁻¹ 置換
for (i = 1; i <= 64; i++)
    cipher[i] = final[ip_inv[i-1]];

實作關鍵提醒

1. 索引基準：標準表多為 1-based，C/C++ 陣列 0-based，轉換時 table[i-1]。
2. 位元順序：DES 規定大端序（MSB first），陣列索引 1 對應最高位。
3. 模 2 加法：用 ^ (XOR) 或 (a+b)%2，避免邏輯 ||。
4. S 盒輸出組裝：查表得 0-15 整數，需轉 4 位二進制並按高位在前順序填入。
5. 合併順序：IP⁻¹ 前必須 R₁₆ 在前、L₁₆ 在後，否則解密失敗。

總結

DES 核心在於：初始置換打亂 → 16 輪 Feistel 迭代 (擴展→異或→S盒非線性→P置換擴散) → 逆置換還原。理解各置換表與 S 盒的設計意圖（混淆與擴散），是掌握現代分組密碼體制的基石。下篇將詳細解析子金鑰生成與解密流程。