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