Chapter 6 資料加密標準

學習目標 回顧 DES 的發展歷史。 定義 DES 的基本結構。 描述 DES 建構元件的詳細情形。 描述回合金鑰產生程序。 分析 DES 。

6.1 簡介 資料加密標準（ Data Encryption Standard, DES ）是一個對稱式金鑰區塊 加密法，由美 國國家標準技術局 （ National Institute of Standards and Technology, NIST ）發表。 本節討論主題 歷史 概述

6.1.1 歷史 在 1973 年， NIST 發布一個國家對稱式 金鑰系統的需求提案。一個由 IBM 所修改 的 Lucifer 計畫被接受成為 DES 。 DES 於 1975 年 3 月發表在《聯邦公報》 （ Federal Register ）上 而成為聯邦資訊 處理標準（ Federal Information Processing Standard, FIPS ）的草案。

6.1.1 概述 DES 是一個區塊加密法，如圖 6.1 所示。 圖 6.1

6.2 DES 結構 加密程序由兩個排列（ P-box ，稱為初 始排列與最終排列）以及十六個 Feistel 回合所組成。 本節討論的主題 初始排列與最終排列 回合 加密法與反向加密法 範例

圖 6.2 DES 的一般結構

圖 6.3 DES 初始排列與最終排列 的步驟

表 6.1 初始排列與最終排列表

範例 6.1 找出初始排列的輸出結果，假設輸入以十六進位表示如下： 解法：輸入僅有兩個為 1 的位元（第 15 個位元及第 64 個 位元），因此輸出必定也只有兩個位元為 1 （標準排列的性 質）。使用表 6.1 ，我們可以找到這兩個位元的相對輸出。 輸入的第 15 個位元將變為 輸出的第 63 個位元；輸入的第 64 個位元將變為輸出的第 25 個位元。亦即輸出只有兩個 1 ， 分別在 第 25 個位元及第 63 個位元。以十六進位表示如下：

範例 6.2 假設輸入如下，請找出最終排列之輸出，以證明 初始與最終排列互為反向。 解法：只有第 25 個位元及第 63 個位元為 1 ，其 餘為 0 。在最終排列中，輸入的第 25 個位元將變 為輸出的第 64 個位元，而輸入的第 63 個位元將 變為輸出的第 15 個位元。因此結果為

初始排列與最終排列 初始排列與最終排列皆為標準的 P-box 且互 為反向。它們在 DES 中均與密碼學無太大 關係。 注意

6.2.1 回合 DES 使用十六個回合。每一個回合是一 個 Feistel 加密法，如圖 6.4 所示。 圖 6.4

DES 函數 DES 的核心為 DES 函數。 DES 函數在最右邊 的 32 位元（ R I−1 ）上運用一個 48 位元的金 鑰， 以產生一個 32 位元的輸出。 圖 6.5

擴展的 P-box 因為 R I−1 是一個 32 位元輸入且 K I 是一個 48 位元金鑰，一開始需要先 將 R I−1 擴展到 48 位 元。 圖 6.6

擴展的 P-box ( 續 ) 雖然輸入與輸出的關係可用數學方式來定義， 但 DES 採用表 6.2 來定義這個 P-box 。 表 6.2

漂白器（ XOR ） 在擴展排列之後， DES 將擴展的右半部 分與回合金鑰做 XOR 運算。注意右半部 與金鑰長度均為 48 位元，而且回合金鑰 僅使用在這個運算上。

S-box S-box 進行實際的混合（混淆）。 DES 使用 8 個 S-box ，每一個 S-box 有 6 位 元 的輸入及 4 位元輸出，見圖 6.7 。 圖 6.7

圖 6.8 S-box 的規則

S-box ( 續 ) 表 6.3 顯示 S-box 1 的排列，剩下的 S- box 請參看課本。 表 6.3

範例 6.3 若 S-box 1 的輸入為 ，其輸出為何？ 解法：若將第 1 位元及第 6 位元寫在一起， 以二進位表示為 11 ，以十進位表示為 3 。 剩下的位元 為 0001 ，以十進位表示為 1 。 我們查表 6.3 （ S-box 1 ）的第 3 列與第 1 行，結果為 12 （十進位），以 二進位表示 為 1100 。因此若輸入為 ，則輸出 為 1100 。

範例 6.4 若 S-box 1 的輸入為 ，其輸出為何？ 解法：若將第 1 位元及第 6 位元寫在一起， 以二進位表示為 00 ，以十進位表示為 0 。 剩下的位元 為 0000 ，以十進位表示為 0 。 我們查表 6.3 （ S-box 1 ）的第 0 列與第 0 行，結果為 13 （十進位），以 二進位表示 為 1101 。因此若輸入為 ，則輸出 為 1101 。

表 6.11 標準排列表

6.2.3 加密法與反向加密法 使用混合器與交換器可以建立加密法與 反向加密法（即解密），均有十六個回 合。整個想法是讓加密法與反向加密法 的演算法變得十分類似。

第一種方式 為達到上述目的，第一種方式即是讓最 後一個回合（第十六回合）與其他回合 不同；其僅有一個混合器而無交換器。 在第一種方式中，最後一個回合沒有交 換器。 注意

圖 6.9 DES 加密法與反向加密法 的第一種方式

演算法 6.1 DES 加密法的虛擬碼

演算法 6.1 DES 加密法的虛擬碼 ( 續 )

另一種方式 我們可以在 第十六回合中包含交換器， 然後在其後加入一個額外的交換器（兩 個交換器的效果相互抵 銷）。

金鑰產生 回合金鑰產生器（ round-key generator ） 建立 16 個 48 位元金鑰，這些金鑰從 56 位元的 加密金鑰而來。

圖 6.10 金鑰產生

表 6.12 同位元移除表

表 6.13 每一個回合的位移數量

表 6.14 金鑰壓縮表

演算法 6.2 回合金鑰產生演算法

演算法 6.2 回合金鑰產生演算法 ( 續 )

範例 6.5 我們選擇一個隨機的明文區塊以及一個 隨機的金鑰，並決定將產生什麼樣的密 文區塊（全部均以十六進位表示）：

表 6.15 範例 6.5 的資料追蹤

表 6.15 範例 6.5 的資料追蹤（續）

範例 6.6 讓我們來看在目的地的 Bob 如何使用相 同的金鑰解開 Alice 傳送的密文。表 6.16 顯示某些有趣的地方。 表 6.16