# 【密碼學 VI - Data Encryption Standard】

## 01. DES 簡介與歷史背景

### 01-01. 發展歷程
- **起源**：1973 年，美國國家標準技術研究所 (NIST) 公開徵求國家級對稱加密標準。
- **獲選**：IBM 的 Lucifer 專案經過修改後被選中。
- **標準化時程**：
1. 1975 年 3 月：在聯邦公報 (Federal Register) 上發布為聯邦資訊處理標準 (FIPS) 草案。
2. 1976 年 11 月：正式被批准為聯邦標準。
3. 1977 年 1 月：正式發布為 FIPS PUB 46。
- **後續發展**：
1. 因安全性考量（主要是金鑰長度問題），NIST 後來限制其僅用於非機密應用。
2. 1999 年發布 FIPS 46-3，建議未來應用改用 Triple DES (3DES)。

### 01-02. 演算法概觀
* **類型**：對稱式區塊加密 (Symmetric-key block cipher)。
* **區塊大小**：64 bits (每次加密 64 位元的明文)。
* **金鑰長度**：64 bits (其中 8 bits 為同位檢查碼，**實際有效長度為 56 bits**)。
* **回合數**：16 個 Feistel 回合。

<br>

## 02. DES 整體運作架構

### 02-01. 加密流程圖解
整個加密過程可以簡化為三個階段：Two Permutations and Sixteen Feistel rounds
1. **初始置換 (Initial Permutation, IP)**：打亂明文順序。
2. **16 輪 Feistel 運算**：核心加密過程，混合金鑰與資料。
3. **最終置換 (Final Permutation, FP)**：IP 的逆運算。

<center>
<img src="https://hackmd.io/_uploads/SkY_duix-x.png"
style="
width: 90%;
height: auto;">
<div style="
border-bottom: 3px solid #d9d9d9;
display: inline-block;
color: #999;
padding: 3px;">
</div>
</center>

**設計核心目標：**
- 讓加密 (Cipher) 與解密 (Reverse Cipher) 的演算法結構盡可能相似 。
- 目的：促進並簡化硬體的實作 (Facilitates hardware implementation) 。

**達成方法 (First Approach)：**
- 為了達成結構相似的目標，DES 採取了一種特殊的設計方式：讓最後一輪 (Round 16) 與其他回合不同 。
- 具體差異：在第 16 輪中，只進行混合 (Mixer)，不進行交換 (No Swapper) 。


**替代做法 (Alternative Approach)：**
- **目標**：讓全部 16 個回合 (Round 1 to 16) 的運算結構完全一致 (Make all 16 rounds the same)。
- **作法**：
1. 在第 16 輪 (Round 16) 中加入交換器 (Swapper)（原本的 First Approach 在這一輪是不交換的）。
2. 接著在第 16 輪結束後，額外增加一個交換器 (Extra Swapper)。
- **原理**：
1. 連續兩次交換會互相抵銷 (Two swappers cancel the effect of each other)。
2. 這樣做既能維持正確的輸出結果（等同於最後沒交換），又能讓每一輪的電路或程式碼邏輯完全相同，簡化設計。

### 02-02. 初始與最終置換 (IP & FP)
- **特性**：它們是互為「逆運算」的單純位置交換 (Straight P-boxes)。即 $IP^{-1}(IP(M)) = M$。
- **安全性**：**不具備密碼學上的安全性意義**。
- **設計目的**：主要是為了早期硬體實作的便利性而設計，與混淆資料無關。

<center>
<img src="https://hackmd.io/_uploads/ryvFudjgWx.png"
style="
width: 80%;
height: auto;">
<div style="
border-bottom: 3px solid #d9d9d9;
display: inline-block;
color: #999;
padding: 3px;">
</div>
</center>

**實例計算 (Example 6.1 & 6.2)**：

- **IP 運算**：
1. **輸入 (Hex)**：0x0002 0000 0000 0001 (只有第 15 bit 和第 64 bit 是 1)。 **(由於 0002 會被拆解成 0000 0000 0000 0010，且 0001 會被拆解成 0000 0000 0000 0001)**
2. **根據 IP 表格規則**：輸入的第 15 bit $\rightarrow$ 變為輸出的第 63 bit。輸入的第 64 bit $\rightarrow$ 變為輸出的第 25 bit。
3. **輸出 (Hex)**：0x0000 0080 0000 0002 (只有第 25 bit 和第 63 bit 是 1)。
- **驗證逆運算 (FP)**：
1. 若將上述 IP 的輸出作為 FP 的輸入。
2. 根據 FP 表格規則：輸入的第 25 bit $\rightarrow$ 變回第 64 bit。輸入的第 63 bit $\rightarrow$ 變回第 15 bit。
3. 結果回到原點：0x0002 0000 0000 0001。

<br>

## 03. 核心機制：Feistel 回合與 DES 函數

### 03-01. Feistel Round 結構
每一輪運算將 64 bits 資料切分為左半部 ($L_{i-1}$) 與右半部 ($R_{i-1}$)，每半部各 32 bits。
**公式**：
* $L_i = R_{i-1}$ (左半部直接承接上一輪的右半部)
* $R_i = L_{i-1} \oplus f(R_{i-1}, K_i)$ (右半部是上一輪左半部與函數結果做 XOR)

**Swapper**：在每一輪結束後左右交換（最後一輪通常不交換，以便解密流程對稱）。

### 03-02. DES 函數 ($f$ Function) 詳解
這是 DES 的心臟，將 32-bit 的資料 ($R$) 與 48-bit 的子金鑰 ($K$) 混合。步驟如下：

- **擴展置換 (Expansion P-box)**：
1. 將 32 bits 擴展為 48 bits。
2. 目的：讓資料長度能與金鑰匹配，並產生擴散效果 (Diffusion)

- **白化/混和 (Whitener / XOR)**：
1. 將擴展後的 48 bits 資料與當前回合的 48 bits 子金鑰 ($K_i$) 進行 XOR 運算。
2. 注意：金鑰僅在此步驟參與運算。

- **S-Boxes (Substitution Boxes) —— 最關鍵的步驟**：
1. **功能**：提供「混淆 (Confusion)」與非線性特性。
2. **輸入/輸出**：DES 使用 8 個 S-boxes。每個 S-box 接收 6 bits 輸入，產生 4 bits 輸出。

:::success
**重點筆記**：S-Box 規則 (Example 6.3 & 6.4)

- 輸入 6 bits：取第 1 位與第 6 位組成二進位數，決定「列 (Row 0-3)」；取中間 4 位 (第 2,3,4,5 位) 決定「行 (Column 0-15)」。
- 實例 1 (Example 6.3)：
1. 輸入：100011
2. 列計算：首尾是 1 和 1 $\rightarrow$ 二進位 11 = Row 3。
3. 行計算：中間是 0001 $\rightarrow$ 二進位 0001 = Column 1。
4. 查表 (S-box 1)：Row 3, Col 1 的值為 12。
5. 輸出：12 的二進位為 1100。
- 實例 2 (Example 6.4)：
1. 輸入：000000
2. 列計算：首尾 00 $\rightarrow$ Row 0。
3. 行計算：中間 0000 $\rightarrow$ Column 0。
4. 查表 (S-box 1)：Row 0, Col 0 的值為 14。
5. 輸出：14 的二進位為 1110。
:::

- **直線置換 (Straight P-box)**：將 8 個 S-boxes 產生的 32 bits 結果再次打亂順序。

### Pseudocode

Cipher (plainBlock[64], RoundKeys[16, 48], cipherBlock[64])
{
    permute (64, 64, plainBlock, inBlock, InitialPermutationTable)
    split (64, 32, inBlock, leftBlock, rightBlock)
    for (round = 1 to 16){
        mixer (leftBlock, rightBlock, RoundKeys[round]) 
        if (round!=16) swapper (leftBlock, rightBlock)
    }
    combine (32, 64, leftBlock, rightBlock, outBlock) 
    permute (64, 64, outBlock, cipherBlock, FinalPermutationTable)
    
    mixer (leftBlock[48], rightBlock[48], RoundKey[48]) {
        copy (32, rightBlock, T1)
        function (T1, Roundkey, T2)
        exclusiveOr (32, leftBlock, T2, T3) 
        copy (32, T3, rightBlock)
    }
    swapper (leftBlock[32], rigthBlock[32]) {
        copy (32, leftBlock, T)
        copy (32, rightBlock, leftBlock)
        copy (32, T, rightBlock)
    }
    function (inBlock[32], RoundKey[48], outBlock[32]){
        permute (32, 48, inBlock, T1, ExpansionPermutationTable)
        exclusiveOr (48, T1, RoundKey, T2) substitute (T2, T3, SubstituteTables)
        permute (32, 32, T3, outBlock, StraightPermutationTable)
    }
    substitute (inBlock[32], outBlock[48], SubstitutionTables[8, 4, 161]) {
    for (i = 1 to 8){
        row <- 2 x inBlock[i × 6 + 1] + inBlock [i x 6 + 6] 
        col <- 8 x inBlock[i × 6 + 2] + 4 x inBlock[i × 6 + 3] + 2 x inBlock[i × 6 + 4] + inBlock[i × 6 + 5]
        value = SubstitutionTables [i][row][col]
        outBlock[[i × 4 + 1] <- value / 8; value <- value mod 8
        outBlock[[i × 4 + 2] <- value / 4; value <- value mod 4
        outBlock[[i × 4 + 3] <- value / 2; value <- value mod 2
        outBlock[[i × 4 + 4] <- value
        }
     }
}

<br>

## 04. 金鑰產生流程 (Key Schedule)

### 04-01. 金鑰結構與同位元 (Parity Bit)
- 輸入金鑰：64 bits，由 8 個 Bytes 組成。
- 同位元 (Parity Bit)：
1. 每個 Byte 的第 8 個 bit (即第 8, 16, 24...64 bit) 是同位檢查碼。
2. 功能：最簡單的錯誤偵測碼，用來檢查二進位數值中 1 的個數是奇數還是偶數。
3. 處理：在加密過程中，這 8 個 bits 會被丟棄。有效長度：因此，DES 的實際有效金鑰長度僅為 56 bits。

### 04-02. 子金鑰產生器 (Round-Key Generator)
**利用 56 bits 的 Cipher Key 產生 16 把 48 bits 的 Round Keys。**
- Parity Drop：去除同位元，64 bits $\rightarrow$ 56 bits。
- 切分：左右各 28 bits。
- 循環左移 (Left Shift)：根據回合表決定移 1 位或 2 位。
- 壓縮置換 (Compression P-box)：56 bits $\rightarrow$ 48 bits。

### 04-03. Psuedocode

Key_Generator (key WithParities[64], RoundKeys[16, 48], ShifiTable[16]) {
    permute (64, 56, keyWithParities, cipherKey, ParityDropTable) 
    split (56, 28, cipherKey, lefiKey, rightKey)
    for (round = 1 to 16) {
        shiftLeft (leftKey, ShiftTable[round) shiftLeft (rightKey, ShiftTable[round])
        combine (28, 56, leftKey, rightKey, preRoundKey)
        permute (56. 48. preRoundKev, RoundKeys[round], KevCompressionTable)
   }
}
                                       
shiftLeft (block[28], numOfShifts) {
    for (i = 1 to numOfShifts)
        T <- block[l]
        for (j = 2 to 28) {
            block [j-1] <- block [j]
        }
        block[28] <- T
}

<br>

:::success
**重點筆記**：加密範例 (Encryption)
- 設定數值 (Hex)：
1. Plaintext: 123456ABCD132536
2. Key: AABB09182736CCDD
- 加密過程摘要：

<center>

| 階段 | 左半部 (Left) | 右半部 (Right) | 使用的子金鑰 (Round Key) |
| :--: | :--: | :--: | :--: |
|初始置換後 ($L_0, R_0$) | 14A7D678 | 18CA18AD | - |
| Round 1 | 18CA18AD | 5A78E394 | 194CD072DE8C |
| Round 2 | 5A78E394 | 4A1210F6 | 4568581ABCCE |
|... | ... | ... | ... |
|Round 15 | BD2DD2AB | CF26B472 | 3330C5D9A36D |
Round 16 | 19BA9212 | CF26B472 | 181C5D75C66D |

</center>

- 合併後：19BA9212CF26B472
- 最終密文 (Ciphertext)：C0B7A8D05F3A829C (經過 Final Permutation)


:::

:::success
**重點筆記**：解密範例 (Decryption)
- Bob 收到密文後，使用相同的金鑰進行解密。注意子金鑰的使用順序是相反的。
- 輸入密文: C0B7A8D05F3A829C
- 解密過程摘要：

<center>

| 階段 | 左半部 (Left) | 右半部 (Right) | 使用的子金鑰 (Round Key) |
| :--: | :--: | :--: | :--: |
| 初始置換後 | 19BA9212 | CF26B472 | - |
| Round 1 (對應加密的 R16 Key) | CF26B472 | BD2DD2AB | 181C5D75C66D |
| Round 2 (對應加密的 R15 Key) | BD2DD2AB | 387CCDAA | 3330C5D9A36D |
| ... | ... | ... | ... |
| Round 15 (對應加密的 R2 Key) | 5A78E394 | 18CA18AD | 4568581ABCCE |
| Round 16 (對應加密的 R1 Key) | 14A7D678 | 18CA18AD | 194CD072DE8C |

</center>

- 合併後：14A7D67818CA18AD
- 還原明文 (Plaintext)：123456ABCD132536

:::

<br>

## 05. 解密流程 (Decryption)

### 05-01. 演算法的對稱性
DES 的設計使得加密與解密可以使用**完全相同的硬體與演算法**。
* **唯一差別**：子金鑰的使用順序相反。
1. 加密：$K_1 \rightarrow K_2 \rightarrow \dots \rightarrow K_{16}$
2. 解密：$K_{16} \rightarrow K_{15} \rightarrow \dots \rightarrow K_1$
* 由於第 16 輪沒有交換 (或經過額外交換抵銷)，解密時的初始輸入 ($L_0, R_0$) 剛好會對應到加密結束前的狀態，使得逆運算可以順利進行。
<br>

## 06. DES 的安全特性分析
### 06-01. 設計準則 (Design Criteria)
- S-box：負責提供混淆 (Confusion) 與擴散 (Diffusion)。
- P-box：負責提供擴散 (Diffusion)。
- 回合數：16 輪是為了讓密文成為明文與金鑰的隨機函數。

### 06-02. 崩塌效應 (Avalanche Effect)
* **定義**：明文或金鑰發生微小的改變（例如只變 1 bit），密文應該要有劇烈的變化（例如約一半的 bits 翻轉）。

* 實測數據：
1. Plaintext A: 000...000 $\rightarrow$ Cipher: 4789...
2. Plaintext B: 000...001 (只差最後 1 bit) $\rightarrow$ Cipher: 0A4E...
3. 結果：密文有 29 bits 不同 (約佔 45%)。
4. 觀察：從表格可見，顯著的變化早在第 3 輪就開始發生 (差異從 1 bit 跳升至 20 bits)。

### 06-03. 完整性 (Completeness)
* **定義**：密文的每一個 bit 都應該依賴於明文中的每一個 bit。
* **來源**：主要歸功於 P-box 的擴散與 S-box 的混淆。

<br>

## 07. 已知弱點與特殊金鑰
### 07-01. 組件的弱點
- S-box：存在碰撞，特定的兩個不同輸入可能產生相同的輸出。
- P-box：初始置換 (IP) 與最終置換 (FP) 沒有密碼學上的安全性效益。

### 07-02. 弱金鑰 (Weak Keys)
- 數量：4 個。
- 成因：產生出的 16 把子金鑰都相同。
- 現象：加密兩次會變回明文。
- 公式：$E_k(E_k(P)) = P$
- 實例：使用弱金鑰 0101010101010101 加密明文兩次，結果會回到原明文。

### 07-03. 半弱金鑰 (Semi-weak Keys)
- 數量：6 對 (共 12 個)。
- 成因：只產生兩種不同的子金鑰交替出現。
- 現象：用其中一把 ($k_1$) 加密，可以用另一把 ($k_2$) 再「加密」一次來還原（效果等同解密）。
- 公式：$E_{k2}(E_{k1}(P)) = P$

### 07-04. 可能弱金鑰 (Possible Weak Keys)
- 數量：48 個。
- 定義：產生出 4 組不同的子金鑰（每組 4 個）。
- 機率分析：
1. 特殊金鑰總數 = 4 (弱) + 12 (半弱) + 48 (可能弱) = 64 個。
2. 選中機率 = $64 / 2^{56} \approx 8.8 \times 10^{-16}$。
3. 結論：在隨機選取金鑰的情況下，選中弱金鑰的機率極低，幾乎不可能發生。

### 07-05. 金鑰互補性 (Key Complement)
- 定義：若將金鑰與明文全部反轉 (Bitwise NOT)，密文也會反轉。
- 公式：若 $C = E(K, P)$，則 $\bar{C} = E(\bar{K}, \bar{P})$
- 實例驗證：
1. 原 Key/Plaintext 產生的 Ciphertext: E112BE1DEFC7A367
2. 互補 Key/Plaintext 產生的 Ciphertext: 1EED41E210385C98
3. 兩者互為補數 (XOR 結果為全 1)。
- 安全性影響：這是一個重大特性，因為攻擊者 (Eve) 只需要測試一半的金鑰空間 ($2^{55}$)，另一半可以透過互補性質推導出來。這大幅降低了暴力破解的難度。


<br>

## 08. 對 DES 的攻擊方式

### 08-01. 暴力攻擊 (Brute-Force Attack)
**致命傷**：由於 DES 金鑰長度過短，且具有**金鑰互補性 (Key Complement)** 的弱點，攻擊者只需測試一半的金鑰空間，即 $2^{55}$ 次加密即可破解。

**破解歷史與成本**：
* **1977 年**：Diffie 與 Hellman 提出了一個理論上的 DES 破解機概念，造價約 2000 萬美元，能在一天內找到金鑰，但當時未有公開實作 。
* **2008 年**：德國波鴻魯爾大學 (Ruhr University Bochum) 與英國基爾大學 (Keele University) 的團隊實現了上述概念，打造出 **COPACOBANA RIVYERA** 機器，成功在一天內破解 DES 。
* *比較*：若使用每秒測試一百萬個金鑰的電腦需耗時 2000 年；但若使用平行運算（一百萬個晶片），僅需約 20 小時 。

### 08-02. 密碼分析 (Cryptanalysis)
**差異分析 (Differential Cryptanalysis)**：
- **防禦設計**：DES 的設計者早已知曉此類攻擊方式。
- **抵抗機制**：特意設計的 **S-boxes** 以及選擇 **16 回合**的運算數量，正是為了讓 DES 能夠抵抗差異分析。
- DES 的設計者（IBM 與 NSA）早已知曉此攻擊並強化了 S-Box，因此 DES 對此攻擊有較強的抵抗力。

**線性分析 (Linear Cryptanalysis)**：
- **背景**：由 Kaliski 與 Robshaw 於 **1994 年**提出，比差異分析更新。
- **脆弱性**：DES 對此攻擊較為脆弱，可能是因為 DES 設計者當初並不知道這種攻擊手法。
- **攻擊原理**：
1. 攻擊者試圖尋找 S-box 輸入與輸出位元之間的**線性近似 (Linear approximations)** 關係，並估算這些關係成立的機率。
2. 將這些近似關係跨回合串聯，並透過統計分析來找出最可能的子金鑰位元。
- **抵抗力**：S-boxes 對線性分析的抵抗力不佳。
1. **需求**：理論上需要 **$2^{43}$ 對已知明文 (Known Plaintexts)** 才能破解，但在實務上很難取得如此大量的明文對。

<br>

## 09. 多重 DES (Multiple DES)

為了解決金鑰過短的問題，發展出了多重加密模式。

### 09-01. Double DES (2DES)
**作法**：用兩把金鑰加密兩次，公式為 $C = E_{K2}(E_{K1}(P))$。

**弱點**：**中間相遇攻擊 (Meet-in-the-Middle Attack)**。
* **歷史**：由 Diffie 與 Hellman 於 1977 年提出。
* **原理**：攻擊者從加密端計算 $M = E_{K1}(P)$，並從解密端計算 $M = D_{K2}(C)$，尋找兩者相符的 $M$ 值。
* **計算複雜度**：由於中間值 $M$ 兩端各有 $2^{56}$ 種可能，攻擊者只需執行 $2 \cdot 2^{56} = 2^{57}$ 次測試。
* **結論**：破解難度僅提升至 $2^{57}$，而非預期的 $2^{112}$，安全性提升有限。


### 09-02. Triple DES (3DES)
為了抵抗中間相遇攻擊，採用三層結構。一般結構為 $E-D-E$ (加密-解密-加密)。

* **三種金鑰選取 (Keying Options)**：
1. **Option 1: 3TDEA (Three-Key Triple DES)**
* **設定**：$K_1, K_2, K_3$ 皆獨立。
* **公式**：$C = E_{K3}(D_{K2}(E_{K1}(P)))$。
* **安全性**：提供最高等級安全，有效金鑰長度為 $3 \times 56 = 168$ bits。
* **應用**：商業應用如 PGP (Pretty Good Privacy) 協定即採用此模式。
2. **Option 2: 2TDEA (Two-Key Triple DES)**
* **設定**：$K_1$ 與 $K_2$ 獨立，但令 $K_3 = K_1$。
* **公式**：$C = E_{K1}(D_{K2}(E_{K1}(P)))$。
* **安全性**：
* 理論有效長度為 $2 \times 56 = 112$ bits。
* 比單純的 Double DES 強，可抵抗中間相遇攻擊。
* *注意*：因存在特定已知明文攻擊的可能性，NIST 將其有效安全強度評定為僅 **80 bits**。
3. **Option 3: 1 Key**
* **設定**：$K_1 = K_2 = K_3$。
* **結果**：前兩步 $E_{K1}$ 與 $D_{K1}$ 互相抵銷，結果等同於單一 DES ($56$ bits)。

### 09-03. 總結 (Summary)
* 雖然 3DES 增強了安全性，但仍容易受到某些理論攻擊的影響。
* 隨著針對 DES 的密碼分析方法不斷發展，其整體安全性已逐漸下降。
* **現況**：DES 已不再被 NIST 認可為官方的加密標準。