Download presentation
Presentation is loading. Please wait.
1
第三章 對稱式金鑰密碼系統 - 資料加密標準
2
1970 年代 Horst Feistel 為美國 IBM 電腦公司研發出 “Lucifer” 系統。 美國國家標準局 (NBS, 現為 NIST) 在 1973 年徵求構想 書，希望能訂定國際加密標準。 DES 最後在 1997 年 1 月發表於《聯邦公報》稱為 FIPS 46 。 DES 是一種對稱加密演算法其加密方式為區塊加密。 2 3.1 S-DES 概述
3
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
4
總共有七種函數 (Seven functions) ◦ 密鑰產生函數 (Key generation) P10:10 位元的置換 (permutation) (3 5 2 7 4 10 1 9 8 6) Shift: 分為左邊五個位元與右邊五個位元，個別向 左移一位元。 P8: 10 位元對應到 8 位元的函數 ◦ 加密函數 (Encryption) IP: initial permutation(10 位元 ) f K : a complex function SW: 左邊 4 bits 和右邊 4 bits 互換 IP -1 : IP 的反函數。 4 3.1 S-DES 架構圖
5
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 為 (10111101) 且 F(1101, SK) = (1110) 則 f K (10111101) = ((1011) (1110), (1101)) = (01011101) 5 3.1 S-DES 架構圖
6
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 運算 ◦ 例 : 1 1 0 1 1 1 1 0 1 0 1 1 1 2 3 4 0 1 0 1 0 0 1 1 SK 1 0 1 1 1 0 0 0 4 1 2 3 2 3 4 1 1 1 1 0 1 0 1 1 EP(1101) SK = (10111000) Input: 3.1 S-DES 架構圖
7
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
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 架構圖
9
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(01000100)) = P4(1110) =1011 9 3.1 S-DES 架構圖
10
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))))) 10 3.1 S-DES 架構圖
11
11 資料加密標準 (Data Encryption Standard ， DES) 是由 IBM 在 1970 年代初期發展出來的演算法， DES 使用 很廣泛，特別在商業領域。 DES 使用 56 位元金鑰，且使用 7 個 8 位元的位元組 ( 每 個位元組的第 8 個位元是做為同位元檢查 ) 做為金鑰 的內容。 DES 屬於區塊式密碼 (block cipher) ，一次處理 64 位元 明文。 DES 密碼共有 16 個循環，每個循環都使用不同的次 金鑰 (subkey) ，且每一個金鑰都會透過自己的演算法 取得 16 個金鑰。 3.2 資料加密標準 (DES)
12
使用 56 位元的鑰匙對 64 位元的區段加密。 加密與解密使用相同的 56 位元的金鑰。 12 DES 加密法 DES 加密法 64 位元明文 64 位元密文 加密加密 DES 反向加密法 DES 反向加密法 64 位元明文 64 位元密文 解密解密 56 位元金鑰 3.2 資料加密標準 (DES)
13
DES 加密程序由兩個排列 (P-box ，稱為初始排列與最 終排列 ) 以及十六個 Feistel 回合所組成。 每個回合使用一把不同的 48 位元回合金鑰，該回合金 鑰由加密金鑰透過一個預先定義的演算法所產生。 DES 的一般結構 13 3.2 資料加密標準 (DES) - 初始排列與最終排列
14
每一個排列接受一個 64 位元輸入，並根據預先定義來 規則排列。 P-box 的排列為右表，表的每一個元素表示輸入為第 幾位元。 14 3.2 資料加密標準 (DES) - 初始排列與最終排列 初始排列與最終排列 DES 初始排列與最終排列的步驟
15
15 例題 3.1 找出如下十六進制表示的初始排列的輸出結果： 0002 0000 0000 0001 1. 首先將十六進制轉換為二進制： 0000000000000010 0000000000000000 0000000000000000 0000000000000001 123456789……15………………………………………......……………………64 輸入僅有兩的為 1 的位元 ( 第 15 與第 64 個位元 ) 2. 依序填入初始排列表 3. 輸出初始排列的結果： 0000 0080 0000 0002 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 1 0 0 0 0 0 0 01 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 1 00 0 0 0 0 0 1 0 3.2 資料加密標準 (DES) - 初始排列與最終排列
16
16 例題 3.2 找出如下十六進制表示的最終排列的輸出結果： 0000 0080 0000 0002 1. 首先將十六進制轉換為二進制： 0000000000000000 0000000010000000 0000000000000000 0000000000000010 123456789…………………..25………………………......…………………6364 輸入僅有兩的為 1 的位元 ( 第 15 與第 64 個位元 ) 2. 依序填入初始排列表 3. 輸出初始排列的結果： 0002 0000 0000 0001 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 1 00 0 0 0 0 0 1 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 1 3.2 資料加密標準 (DES) - 初始排列與最終排列
17
17 3.2 資料加密標準 (DES) - 回合
18
18 3.2 資料加密標準 (DES) -DES 函數
19
19 3.2 資料加密標準 (DES) -DES 函數：擴展的 P-box
20
擴展排列的 P-box 20 3.2 資料加密標準 (DES) -DES 函數：擴展的 P-box 擴展的 P-box 表 5 6 7 85 6 7 8 49 4 5 6 7 8 94 5 6 7 8 9 目前區段 前一區段下一區段 30
21
漂白器 (XOR) ：擴展排列後， DES 將擴展的右半部與 回合金鑰做 XOR 運算，注意右半部與金鑰長度皆為 48 位元。 S-box ：進行實際的混合 ( 混淆 ) ， DES 使用 8 個 S-box ， 每一個有 6 位元輸入及 4 位元輸出。 21 3.2 資料加密標準 (DES) -DES 函數：漂白器 (XOR) 、 S-box
22
48 位元的輸入分成八個 6 位元的區塊，每一區塊被餵 入一個 S-box ，每一個 S-box 輸出結果為 4 位元的區塊， 這些區塊結合起來為 32 位元。 每一個 S-box 的取代方式為一個 4 列乘 16 行的表格；輸 入的第 1 與 6 位元來決定列的值；第 2~5 位元決定行的 值。 22 3.2 資料加密標準 (DES) -DES 函數： S-box
23
每一個 S-box 有自己的表格，有八個表格來定義這些 S-box 的輸出。輸入值 ( 列數字與行數字 ) 以及輸出值 以十進位來表示，這些值需要轉換成二進制表示。 23 3.2 資料加密標準 (DES) -DES 函數： S-box S-box 1 S-box 2 01
24
24 3.2 資料加密標準 (DES) -DES 函數： S-box S-box 3 S-box 4
25
25 3.2 資料加密標準 (DES) -DES 函數： S-box S-box 5 S-box 6
26
26 3.2 資料加密標準 (DES) -DES 函數： S-box S-box 7 S-box 8 00 13 00
27
27 例題 3.3 若 S-box 1 的輸入為 100010 ，其輸出為何 ? 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
28
標準排列 ( 標準的 P-box) ： DES 最後一個運算是 32 位元 輸入及 32 位元輸出的標準排列，其輸入 / 輸出關係顯 示表如下。 28 3.2 資料加密標準 (DES) -DES 函數：標準的 P-box 標準排列表
29
回合金鑰產生器 (round- key generator) 建立 16 個 48 位元金鑰，這些金鑰 由 56 位元的加密金鑰而 來。 通常加密金鑰為 64 位元， 其中包含額外 8 個位元 為同位元檢查。 這 8 位元在真正金鑰產 生程序前將會被移除。 29 3.2 資料加密標準 (DES) - 金鑰產生
30
金鑰產生的預先程序是壓縮排列，稱之為同位元移除 (parity bit drop) 。 從 64 位元金鑰中移除同位元 ( 第 8 、 16 、 24…64 位元 ) ， 並根據同位元移除表排列剩下的位元。 剩下的 ˙56 位元金鑰為實際的加密金鑰，可用來產生 回合金鑰。 30 3.2 資料加密標準 (DES) - 金鑰產生：同位元移除 同位元移除表
31
在標準排列之後，加密金鑰被分為兩個部分各為 28 位 元。 每一部分左移 ( 循環左移 ) ，位移數量如下表所示。 此兩部分皆左移後再合併成 56 位元。 31 3.2 資料加密標準 (DES) - 金鑰產生：左移位 每一回合的位移數量表
32
在壓縮排列將 56 位元轉換為 48 位元，此 48 位元成為每 一回合的金鑰。 32 3.2 資料加密標準 (DES) - 金鑰產生：壓縮排列 金鑰壓縮排列表
Similar presentations
