Chapter 5 現代對稱式金鑰加密法

學習目標 區別傳統對稱式金鑰加密法和現代對稱式金鑰加密法。 介紹現代區塊加密法並討論其特性。 解釋為何要將現代區塊加密法設計成取代加密法。 介紹區塊加密法的組成元件，例如 P-box 和 S-box。 討論乘積加密法並區別兩類乘積加密法︰Feistel加密法和非Feistel 加密法。

學習目標 (續) 討論特別為現代區塊加密法而設計的兩種攻擊︰差異破密分析和線性破密分析。 介紹串流加密法並區別同步串流加密法和非同步串流加密法。 討論在實作串流加密法時，線性回饋位移暫存器與非線性回饋位移暫存器的使用。

5.1 現代區塊加密法 一個對稱式金鑰現代區塊加密法（modern block cipher）是加密一個 n 位元的明文區塊 或解密一個 n 位元的密文區塊。加密演算法或解密演算法使用一把 k 位元的金鑰。

5.1 現代區塊加密法 (續) 本節討論的主題 取代或換位 區塊加密法形成排列群 現代區塊加密法的組成要素 乘積加密法 兩種乘積加密法的類型 區塊加密法的攻擊

圖 5.1 一個現代區塊加密法

範例5.1 如果一個字元使用 8 位元的 ASCII 編碼，而區塊加密法接受 64 位元的區塊，則 100 個字元的訊息必須加入多少填塞位元呢？ 解法：使用 8 位元的 ASCII 對 100 個字元編碼，將產生一個 800 位元的訊息，明文必須可以被 64整除，假設 |M| 和 |Pad| 分別表示訊息的長度和填塞位元的長度，

5.1.1 取代或換位 現代區塊加密法可以設計成取代加密法或換位加密法。 注意 為了抵抗徹底搜尋攻擊，現代區塊加密法必須設計成取代加密法。

範例5.2 假設有一個區塊加密法，其中 n = 64。如果密文中有 10 個位元 1，在下列情況下，Eve 需要做多少次的嘗試錯誤測試，才能從竊聽的密文取得明文？ a. 加密法被設計成取代加密法。 b. 加密法被設計成換位加密法。

範例5.2 (續) 解法： a. 在第一種情況中（取代），Eve 不知道明文中有多少個位元 1，因此 Eve 必須嘗試全部 264 個可能 的 64 位元區塊，以找到其中有意義的一個。 b. 在第二種情況中（換位），Eve 知道在明文中正好有 10 個位元 1，因為換位不會改變密文裡 1 的 數目。Eve 可以只使用那些正好有 10 個位元 1 的 64 位元區塊，來進行徹底搜尋攻擊。

全大小金鑰換位區塊加密法 在一個全大小金鑰換位加密法，我們需要有 n! 個可能的金鑰，因此金鑰應該有  個位元。

範例5.3 顯示一個 3 位元區塊換位加密法的模型和其排列表集合，其中區塊大小是 3 位元。 解法：排列表的集合共有 3! = 6 個元素，如圖 5.2 所示。

全大小金鑰取代區塊加密法 一個全大小金鑰取代加密法不調換位元而是取代位元，但如果能對輸入解碼並對輸出編碼，就能將取代加密法模型化成一種排列。

範例5.4 顯示一個 3 位元區塊取代加密法的模型和其排列表集合。 解法：圖 5.3 顯示其模型和排列表集合。金鑰長度 位元也長很多。

圖5.3 取代區塊加密法模型化成一種排列

全大小金鑰加密法 注意 一個全大小金鑰的 n 位元換位加密法或取代區塊加密法可以被模型化成一種排列，但是它們的金鑰大小是不相同的︰ 對換位加密法而言，金鑰的長度是 位元。 對取代加密法而言，金鑰的長度是 位元。

部分大小金鑰加密法 注意 如果一個部分金鑰加密法是其相對應全大小金鑰加密法的一個子群，那麼這個部分金鑰加密法在組合運算下是一個群。

現代區塊加密法的組成要素 現代區塊加密法通常是有金鑰的取代加密法，其中金鑰只允許從可能的輸入到可能的輸出之部分對應。

P-box P-box（排列 box）類似於傳統的字元換位加密法，不同之處在於 P-box 的換位單元是位元。

圖5.4 三種不同型態的 P-box

範例5.5 圖 5.5 顯示一個 3 × 3 的標準的 P-box 之全部六種的可能對應。

表 5.1 一個標準的 P-box 的排列表範例

範例5.6 為一個標準的 P-box 設計一個 8 × 8 排列表，將輸入字組的兩個中間位元（位元 4 和 5） 移動至輸出字組的兩端兩個位元（位元 1 和8），而其他位元彼此間的相對位置不變。 解法：此標準的 P-box 排列表是 [4 1 2 3 6 7 8 5]，輸入位元 1、2、3、6、7、8 彼此間的相對位置 沒有改變，但是第 1 個輸出來自第 4 個輸入，且第 8 個輸出來自第 5 個輸入。

壓縮的 P-Box 一個壓縮的 P-box（compression P-box）是一個輸入為 n 且輸出為 m 的 P-box。

擴展的 P-Box 一個擴展的 P-box（expansion P-box）是一個輸入為 n 且輸出為 m 的 P-box。

P-Box：可逆性 注意 一個標準的 P-box 是可逆的，但壓縮的 P-box 和擴展的 P-box 是不可逆的。

範例5.7 圖 5.6 以一個一維的表格來顯示如何反轉一個排列表。

圖 5.7 壓縮的 P-box 和擴展的 P-box 是不可逆

S-box S-box（取代 box）可以視為一種小型的取代加密法。 注意 一個 S-box 是一個 m × n 的取代裝置，其中 m 和 n 不一定要相同。

範例5.8 在一個具有 3 個輸入和 2 個輸出的 S-box 中，若輸入和輸出之間的關係是 則此 S-box 是線性的，因為 a1,1 = a1,2 = a1,3 = a2,1 = 1 且 a2,2 = a2,3 = 0。此關係可用以下的矩陣來表示：

範例5.9 其中，乘法和加法是在GF(2)裡的運算。此S-box是非線性的，因為輸入和輸出之間沒有線性關係。

範例5.10 下表定義一個 3×2 S-box 的輸入／輸出關係，其中列表示輸入的最左邊位元，欄表 示輸入的最右邊兩個位元，而列與欄交叉處的值則是兩個位元的輸出值。 依此表格，010 的輸入會產生 01 的輸出，101 的輸入會產生 00 的輸出。

S-box：可逆性 S-box 可以是可逆的或是不可逆的，可逆的 S-box 其輸入位元的數量必須與輸出位 元的數量相同。

範例5.11 圖 5.8 是一個可逆的 S-box 例子，如果左邊 S-box 的輸入是 001，則輸出是 101；而右邊表格的輸入是 101 時，將產生 001的輸出。這顯示了這兩個表格彼此互為反向。

互斥或 在大多數的區塊加密法中，互斥或運算是非常重要的組成元件。我們在第四章曾討論過，在GF(2n) 中的加法和減法運算是透過稱為互斥或（XOR）的單一運算來執行的。 互斥或運算在GF(2n)中的五種特性使得此運算是區塊加密法中非常有趣的組成元件：封閉性、結合性、交換性、存在單位元素、存在反元素。

互斥或：反向 在一個加密法中，如果某個組成元件是代表單元運算（一個輸入和一個輸出），那麼此組成元件的反向是有意義的。例如，一個無金鑰的 P-box 或者一個無金鑰的 S-box 可以是可逆的，因為有一個輸入和一個輸出。一個互斥或運算是一個單元運算，互斥或運算只有在輸入之一是固定的情況下（加密和解密時都一樣），其反向才會有意義。例如，如果輸入之一是金鑰，此金鑰通常在加密和解密時是一樣的，那麼互斥或運算是自我可逆的，如圖 5.9 所示。

圖 5.9 互斥或運算的可逆性

循環位移 一些現代區塊加密法也常使用循環位移運算（circular shift operation）。 圖 5.10　向左或向右循環位移一個 8 位元字組

交換 交換運算（swap operation）是循環位移運算的特殊情況，其中 k = n/2 。 圖 5.11 一個 8 位元字組的交換運算

分割與整合 一些現代區塊加密法中其他兩個常見的運算是分割與整合。 圖 5.12 一個 8 位元字組的分割與整合運算

5.1.4 乘積加密法 乘積加密法（product cipher）的概念是由 Shannon 提出。乘積加密法是一種結合了取 代、排列和前幾節所討論的其他運算之複雜加密法。

擴散與混淆 擴散 混淆 注意 擴散隱藏密文和明文之間的關係。 注意 混淆隱藏密文和金鑰之間的關係。

回合 擴散和混淆可以使用迭代的乘積加密法來達到，其中每一次的迭代是 S-box、P-box 和其他組成元件的結合。

圖5.13 一個兩回合的乘積加密法

圖 5.14 區塊加密法的擴散和混淆

5.1.5 兩種乘積加密法的類型 現代區塊加密法都是乘積加密法，但是可分成兩種： Feistel加密法 非Feistel加密法

在Feistel設計裡的混合器是自我可逆的。 Feistel 設計了一種非常聰明和有趣的加密法，已經使用數十年了。Feistel加密法（Feistel cipher）有三種組成元件︰自我可逆、可逆和不可逆的。 注意 在Feistel設計裡的混合器是自我可逆的。

圖 5.15 Feistel 加密法設計的最初想法

範例5.12 這是一個簡單的範例。明文和密文的長度各是 4 位元，金鑰長度是 3 位元，假設此 函數取金鑰的第一和第三位元，將此二位元解釋成十進位的數字，再將該數字平方，以二進位的 4 位元表示結果。如果原始的明文是 0111，而金鑰是 101，請顯示加密和解密的結果。

範例5.12 (續) 解法：此函數取出第一和第三位元，得到二進位的 11 或十進位的 3，平方的結果是 9，以二進位 表示則是 1001。

圖 5.16 先前 Feistel 設計的改進

圖 5.17 兩回合的 Feistel 加密法最後設計

非 Feistel 加密 非 Feistel 加密法（non-Feistel cipher）只使用可逆的組成元件，明文的某個成分在密文中有相對應的成分。

5.1.6 區塊加密法的攻擊 對傳統加密法的攻擊也能用在現代區塊加密法上，但是第三章討論過現今的區塊加密法能抵抗大多數這類攻擊。

差異破密分析 Eli Biham 和 Adi Shamir 提出差異破密分析（differential cryptanalysis）的想法，這是一種選擇明文攻擊。

範例5.13 假設有一加密法只由一個互斥或運算組成，如圖 5.18 所示，在不知道金鑰的情況之下，Eve 可以容易地找出明文差異與密文差異之間的關係，其中明文差異是指 P1 ⊕ P2，而密文差異 是指 C1 ⊕ C2。以下證明 C1 ⊕ C2 = P1 ⊕ P2 ︰ 圖5.18

範例5.14 我們在範例 5.13 中新增一個 S-box，如圖 5.19 所示。 圖 5.19

範例5.14 (續) 此時Eve能建立一個機率的關係，如表5.4所示。 表5.4

範例5.15 Eve 能從範例 5.14 的結果建立機率的資訊，如表 5.5 所示。 表 5.5

範例5.16 查看表 5.5，Eve 知道如果 P1 ⊕ P2 = 001，則 C1 ⊕ C2 = 11 的機率是 0.50（50%），她嘗 試 C1 = 00 並且得到 P1 = 010（選擇密文攻擊），她也嘗試 C2 = 11 並且得到 P2 = 011（另一次選擇密文 攻擊）。現在，她試著往回做，根據第一對 P1 和 C1， 這兩次的試驗確認 K = 011 或 K = 101。

差異破密分析 (續) 注意 差異破密分析是基於區塊加密法中S-box的不平均差異分布表。 注意 更詳細的差異破密分析在附錄N說明。

線性破密分析 線性破密分析（linear cryptanalysis）是 1993 年由 Mitsuru Matsui 所提出，此分析使用已知明文攻擊。

圖 5.20 具一個線性 S-box 的簡單加密法

線性破密分析 (續) 求解三個未知數，我們得到 這意味著三個已知明文攻擊能找出 k0、k1 和 k2。

線性相近 在一些現代區塊加密法中，可能發生的情況是某些 S-box 不是完全非線性，而是藉由一些線性函數機率式地近似於非線性。 其中，1 ≤ x ≤ m、1 ≤ y ≤ n 且 1 ≤ z ≤ n。