第三章 對稱式金鑰密碼系統 - 資料加密標準

 1970 年代 Horst Feistel 為美國 IBM 電腦公司研發出 “Lucifer” 系統。  美國國家標準局 (NBS, 現為 NIST) 在 1973 年徵求構想 書，希望能訂定國際加密標準。  DES 最後在 1997 年 1 月發表於《聯邦公報》稱為 FIPS 46 。  DES 是一種對稱加密演算法其加密方式為區塊加密。 S-DES 概述

3 3.1 S-DES 架構圖  精簡版的 DES(S-DES) 不是一個安全的加密演算法。 10-bit key P10 LS-1 P8 LS-2 P8 K1K1 K2K2 5-bit 8-bit 5-bit

總共有七種函數 (Seven functions) ◦ 密鑰產生函數 (Key generation)  P10:10 位元的置換 (permutation) ( )  Shift: 分為左邊五個位元與右邊五個位元，個別向 左移一位元。  P8: 10 位元對應到 8 位元的函數 ◦ 加密函數 (Encryption)  IP: initial permutation(10 位元 )  f K : a complex function  SW: 左邊 4 bits 和右邊 4 bits 互換  IP -1 : IP 的反函數。 S-DES 架構圖

f K : 8 位元對到 8 位元的函數 ◦ 最複雜的部分 ◦ 結合排列和替換 ◦ f K (L, R)=(L  F(R, SK), R)  SK: 給定密鑰所產生的子鑰 K i (i = 1, 2, …)  L: input 的左邊 4 bits  R: input 的右邊 4 bits  F: 將 R 利用子鑰 SK 加密的 4 位元對到 4 位元的函數 假設 input 為 ( ) 且 F(1101, SK) = (1110) 則 f K ( ) = ((1011)  (1110), (1101)) = ( ) S-DES 架構圖

6 F: 將 R 利用子鑰 SK 加密的 4 位元對到 4 位元的函數. ◦ Input: 4-bit number R=(n 1 n 2 n 3 n 4 ). ◦ 先做一個 expansion/permutation(E/P) 的運算得 8 位 元字串 (n 4 n 1 n 2 n 3 n 2 n 3 n 4 n 1 ) ◦ 然後和 sub-key SK 做 exclusive-or  運算 ◦ 例 : SK EP(1101)  SK = ( )  Input: 3.1 S-DES 架構圖

7 F: 將 R 利用子鑰 SK 加密的 4 位元對到 4 位元的函數. ◦ Input: 4-bit number R= (n 1 n 2 n 3 n 4 ). ◦ 計算 (n 4 n 1 n 2 n 3 n 2 n 3 n 4 n 1 )  SK 得 8 位元字串 (l 1 l 2 l 3 l 4 r 1 r 2 r 3 r 4 ). ◦ 利用 S-box S0 與 S1 得到一 4 位元 (a 1 a 2 b 1 b 2 )  利用左邊 4 bits l 1 l 2 l 3 l 4 與 S-box S0(4  4 矩陣 ) 來產生 2-bit output (a 1 a 2 ).  利用右邊 4 bits r 1 r 2 r 3 r 4 與 S-box S1(4  4 矩陣 ) 來產 生另外 2-bit output (b 1 b 2 ). 3.1 S-DES 架構圖

8 Example: S0(0100)=3 or (11) 2 S1(0010)=1 or (01) 2 S-box 的 4-bit input 中, 第 1 、 4 bits 用來決定要參考矩 陣中的哪一列, 第 2 、 3 bits 則用來決定要參考矩陣中 的哪一行。 由此得出矩陣中的某一項, 然後將其化為二進位表示 式。 3.1 S-DES 架構圖

F: 將 R 利用子鑰 SK 加密的 4 位元對到 4 位元的函數. ◦ Input: 4-bit number R= (n 1 n 2 n 3 n 4 ). ◦ 計算 (n 4 n 1 n 2 n 3 n 2 n 3 n 4 n 1 )  SK 得 8 位元字串 (l 1 l 2 l 3 l 4 r 1 r 2 r 3 r 4 ). ◦ 利用 S-box S0 與 S1 得到一 4 位元 (a 1 a 2 b 1 b 2 ) ◦ 再利用一 4 位元的 permutation P4 將重新排列得到一 4- bit output 。 ◦ 例 :P4(b 1 b 2 b 3 b 4 )=b 2 b 4 b 3 b 1  P4(S-box( )) = P4(1110) = S-DES 架構圖

 S-DES 公視整理，加密鑰匙的產生公式 : K 1 =P8(Shift(P10(key))) K 2 =P8(Shift(Shift(P10(key)))))  密文的加密公式 :  Ciphertext = IP -1 (f k2 (SW(f k1 (IP(plaintext)))))  明文的解密公式 :  Plaintext = IP -1 (f k1 (SW(f k2 (IP(ciphertext))))) S-DES 架構圖

11 資料加密標準 (Data Encryption Standard ， DES) 是由 IBM 在 1970 年代初期發展出來的演算法， DES 使用 很廣泛，特別在商業領域。 DES 使用 56 位元金鑰，且使用 7 個 8 位元的位元組 ( 每 個位元組的第 8 個位元是做為同位元檢查 ) 做為金鑰 的內容。 DES 屬於區塊式密碼 (block cipher) ，一次處理 64 位元 明文。 DES 密碼共有 16 個循環，每個循環都使用不同的次 金鑰 (subkey) ，且每一個金鑰都會透過自己的演算法 取得 16 個金鑰。 3.2 資料加密標準 (DES)

 使用 56 位元的鑰匙對 64 位元的區段加密。  加密與解密使用相同的 56 位元的金鑰。 12 DES 加密法 DES 加密法 64 位元明文 64 位元密文 加密加密 DES 反向加密法 DES 反向加密法 64 位元明文 64 位元密文 解密解密 56 位元金鑰 3.2 資料加密標準 (DES)

 DES 加密程序由兩個排列 (P-box ，稱為初始排列與最 終排列 ) 以及十六個 Feistel 回合所組成。  每個回合使用一把不同的 48 位元回合金鑰，該回合金 鑰由加密金鑰透過一個預先定義的演算法所產生。  DES 的一般結構 資料加密標準 (DES) - 初始排列與最終排列

 每一個排列接受一個 64 位元輸入，並根據預先定義來 規則排列。  P-box 的排列為右表，表的每一個元素表示輸入為第 幾位元。 資料加密標準 (DES) - 初始排列與最終排列 初始排列與最終排列 DES 初始排列與最終排列的步驟

15 例題 3.1 找出如下十六進制表示的初始排列的輸出結果： 首先將十六進制轉換為二進制： ……15………………………………………......……………………64 輸入僅有兩的為 1 的位元 ( 第 15 與第 64 個位元 ) 2. 依序填入初始排列表 3. 輸出初始排列的結果： 資料加密標準 (DES) - 初始排列與最終排列

16 例題 3.2 找出如下十六進制表示的最終排列的輸出結果： 首先將十六進制轉換為二進制： …………………..25………………………......…………………6364 輸入僅有兩的為 1 的位元 ( 第 15 與第 64 個位元 ) 2. 依序填入初始排列表 3. 輸出初始排列的結果： 資料加密標準 (DES) - 初始排列與最終排列

資料加密標準 (DES) - 回合

資料加密標準 (DES) -DES 函數

資料加密標準 (DES) -DES 函數：擴展的 P-box

 擴展排列的 P-box 資料加密標準 (DES) -DES 函數：擴展的 P-box 擴展的 P-box 表 目前區段 前一區段下一區段 30

 漂白器 (XOR) ：擴展排列後， DES 將擴展的右半部與 回合金鑰做 XOR 運算，注意右半部與金鑰長度皆為 48 位元。  S-box ：進行實際的混合 ( 混淆 ) ， DES 使用 8 個 S-box ， 每一個有 6 位元輸入及 4 位元輸出。 資料加密標準 (DES) -DES 函數：漂白器 (XOR) 、 S-box

 48 位元的輸入分成八個 6 位元的區塊，每一區塊被餵 入一個 S-box ，每一個 S-box 輸出結果為 4 位元的區塊， 這些區塊結合起來為 32 位元。  每一個 S-box 的取代方式為一個 4 列乘 16 行的表格；輸 入的第 1 與 6 位元來決定列的值；第 2~5 位元決定行的 值。 資料加密標準 (DES) -DES 函數： S-box

 每一個 S-box 有自己的表格，有八個表格來定義這些 S-box 的輸出。輸入值 ( 列數字與行數字 ) 以及輸出值 以十進位來表示，這些值需要轉換成二進制表示。 資料加密標準 (DES) -DES 函數： S-box S-box 1 S-box 2 01

資料加密標準 (DES) -DES 函數： S-box S-box 3 S-box 4

資料加密標準 (DES) -DES 函數： S-box S-box 5 S-box 6

資料加密標準 (DES) -DES 函數： S-box S-box 7 S-box

27 例題 3.3 若 S-box 1 的輸入為 ，其輸出為何 ? 1. 首先將第 1 位元與第 6 位元寫在一起，以二進位表示為 10 ，以 十進制表示為 3 ，查表 S-box 1 表示列的 2 。 2. 剩下第 2~5 位元 0001 ，以十進制表示為 1 ，查表 S-box 1 表示行 的 1 。 3. 第 2 列與第 1 行交叉處為十進制的 01 ，以二進制 ( 四位元 ) 表示為 0001 。 3.2 資料加密標準 (DES) -DES 函數： S-box S-box 1 01

 標準排列 ( 標準的 P-box) ： DES 最後一個運算是 32 位元 輸入及 32 位元輸出的標準排列，其輸入 / 輸出關係顯 示表如下。 資料加密標準 (DES) -DES 函數：標準的 P-box 標準排列表

 回合金鑰產生器 (round- key generator) 建立 16 個 48 位元金鑰，這些金鑰 由 56 位元的加密金鑰而 來。  通常加密金鑰為 64 位元， 其中包含額外 8 個位元 為同位元檢查。  這 8 位元在真正金鑰產 生程序前將會被移除。 資料加密標準 (DES) - 金鑰產生

 金鑰產生的預先程序是壓縮排列，稱之為同位元移除 (parity bit drop) 。  從 64 位元金鑰中移除同位元 ( 第 8 、 16 、 24…64 位元 ) ， 並根據同位元移除表排列剩下的位元。  剩下的 ˙56 位元金鑰為實際的加密金鑰，可用來產生 回合金鑰。 資料加密標準 (DES) - 金鑰產生：同位元移除 同位元移除表

 在標準排列之後，加密金鑰被分為兩個部分各為 28 位 元。  每一部分左移 ( 循環左移 ) ，位移數量如下表所示。  此兩部分皆左移後再合併成 56 位元。 資料加密標準 (DES) - 金鑰產生：左移位 每一回合的位移數量表

 在壓縮排列將 56 位元轉換為 48 位元，此 48 位元成為每 一回合的金鑰。 資料加密標準 (DES) - 金鑰產生：壓縮排列 金鑰壓縮排列表