密碼學 Chapter 3 基於電腦的對稱性金鑰密碼學演算法

Presentation on theme: "密碼學 Chapter 3 基於電腦的對稱性金鑰密碼學演算法"— Presentation transcript:

1 密碼學 Chapter 3 基於電腦的對稱性金鑰密碼學演算法
Computer-based Symmetric Key Cryptographic Algorithms(Part 2)

2 國際資料加密演算法 國際資料加密演算法(International Data Encryption Algorithm, IDEA)
被認為是一個強勁的密碼學演算法 發表於1990年 並沒有如DES受到廣泛的歡迎 IDEA是有專利的 商業始用需要得到授權 歷史不如DES悠久 應用範例 電子郵件隱私技術 良好隱私(Pretty Good Privacy, PGP)

3 IDEA的發展 1990 1991 1992 建議加密標準 (Proposed Encryption Standard, PES)
Xuejia Lai和James Massey在瑞士聯邦技術組織發展 1991 改善建議加密標準 (Improved Proposed Encryption Standard, IPES) 由密碼分析者找出一些虛弱的區域，並加以改善的演算法 1992 國際資料加密演算法 (International Data Encryption Algorithm, IDEA) 沒有主要的改變，只是單純地改名

4 IDEA基本原理 IDEA是一種區塊密碼 使用64位元明文區塊 金鑰長度128位元 IDEA在加密中同時使用擴散和混淆

5 IDEA的概略步驟

6 變數定義 明文區塊(64 位元) 密文區塊(64位元) 回合結束產生區塊 金鑰(128位元) P1, P2, P3, P4(各16位元)
C1, C2, C3, C4(各16位元) 回合結束產生區塊 R1, R2, R3, R4(各16位元) 金鑰(128位元) 子金鑰 K1, K2, K3, … , K51, K52(各16位元)

7 回合內的特殊運算 模數 (Mod) 加* 乘* 求餘數 兩數相加取模數216 Mod 216 = Mod 65536
兩數相乘取模數216+1 Mod = Mod 65537

8 IDEA回合的細節 P1和K1相乘* P2和K2相加* P3和K3相加* P4和K4相乘* 步驟1和步驟3的結果做XOR
步驟6和步驟7的結果相加* 步驟8的結果和K6相乘* 步驟7和步驟9的結果相加* 步驟1和步驟9的結果做XOR 步驟3和步驟9的結果做XOR 步驟2和步驟10的結果做XOR 步驟4和步驟10的結果做XOR

9 一個IDEA回合

10 一個回合內的金鑰產生 原始金鑰依序每16位元產生一把子金鑰 當原始金鑰依序產生完畢，則將原始金鑰向左位移25位元產生新的原始金鑰
再從新的原始金鑰依序產生子金鑰 直到產生52把子金鑰

11 輸出轉換 於第8回合結束後進行 使用4把子金鑰 產生密文區塊(64位元) 由C1, C2, C3, C4結合而來

12 輸出轉換細節 R1和K1相乘* R2和K2相加* R3和K3相加* R4和K4相乘*

13 輸出轉換過程

14 IDEA解密 IDEA解密的過程如同加密的過程 解密的子金鑰實際上是加密子金鑰的相反

15 IDEA的強度 IDEA的金鑰長度為128位元，是DES金鑰的兩倍大 IDEA金鑰的安全性 2128種可能
個人電腦運算需要超過5.4*1024年

16 RC5 為對稱性金鑰區塊加密演算法 主要特徵為十分快速 只使用電腦的基本運算 允許變動的回合數與金鑰大小來增加彈性
加法、XOR、位移…等 允許變動的回合數與金鑰大小來增加彈性 執行時需要較少的記憶體，因此也可運用於智慧卡等記憶體容量少的裝置 已被加入RSA資料安全協會的產品中

17 RC5基本原理 明文區塊大小、回和數、金鑰中8位元組數目都是可以調整的

18 RC5基本原理 RC5-w/r/b RC5-32/16/16 建議最小安全版本 w＝位元中字組的大小(一次加密2字組區塊) r ＝回合數
區塊大小64位元 16回合數 金鑰長度為128位元 建議最小安全版本 RC5-32/12/16

19 RC5操作步驟 輸入明文被分割成兩個部份，區塊A與區塊B S[0]與S[1]分別被加入A與B中，並個別產生C與D 回合運算 位元位置XOR
循環式左移 在C與D中加入下一個子金鑰，並求加法後的餘數

20 RC5操作步驟

21 一次性初始運算

22 回合運算 C和D做XOR E做循環式左移 E和下一個子金鑰相加 D和F做XOR 循環式左移G G和下一個子金鑰相加 其餘工作 i值遞增
是否所有回合完成 回合未完成則F與H重新命名為C與D並回到步驟1

23 回合運算 步驟 1 步驟 2

24 回合運算 步驟 3 步驟 4

25 回合運算 步驟 5 步驟 6 S[2i+1]

26 回合運算 步驟 7

27 RC5加密數學表示式 加密 <<< 表示左循環 >>> 表示右循環 解密

28 子金鑰的製造 RC5子金鑰的產生需要兩個步驟 子金鑰S[0],S[1],…被產生 子金鑰與原始金鑰L相對應的部份L[0],L[1],…混和

29 子金鑰產生 產生子金鑰序列S = S[0],S[1],… 使用兩個常數P, Q S[0] = P
下個金鑰(S[1],S[2],…)則是前一金鑰與Q相加取模數232 (模數由區塊大小決定) 需產生2(r + 1) + 1，r為回合數

30 子金鑰產生

31 子金鑰混和 子金鑰S[0],S[1],…與原始金鑰的子部份L[0],L[1],…,L[c]混合

32 Blowfish 布魯斯‧施奈爾於1993年開發 屬於對稱金鑰區塊加密演算法 區塊長度為64位元 金鑰為1至448位元的可變長度
處理數度比DES快 無須授權即可使用 廣泛用於檔案加密軟體與 SSH 上

33 Blowfish設計目標 快速 緊密 簡單 安全 在32位元的微處理器上，加密速率為每位元組26個時脈週期 可在少於5kb的記憶體中執行
只使用基本運算如：加法、XOR、查表 安全 具有最大448位元的可變金鑰長度，兼顧彈性與安全性

34 Blowfish運算 使用一個可變長度的金鑰來加密64位元區塊 包含兩個部份 金鑰擴增 資料加密
可轉換金鑰長度到448位元和子金鑰的總長度為4168位元 資料加密 對一個簡單的函數疊代16次 每一回合包含金鑰相依排列、金鑰相依替代和資料相依替代

35 Blowfish流程

36 高等加密標準 Advanced Encryption Standard, AES
為比利時密碼學家 Joan Daemen 和 Vincent Rijmen 所設計 結合兩位作者名字以 Rijndael 命名 區塊大小為128位元 金鑰大小為128位元 (後來有192、256位元版本)

37 AES發展歷史 1990年 1998年6月 1999年8月 2000年10月 美國政府想要提出一個新的標準化密碼學演算法，取代DES
Rijndael於被提交到NIST 1999年8月 為競爭中剩下的5個演算法之一 2000年10月 Rijndael被公佈成為AES的最後選擇

38 AES發展歷史 2001年11月 2002年5月 2006年 發佈於 FIPS PUB 197 成為有效標準
已經成為對稱金鑰加密中最流行的演算法之一

39 AES的特徵 對稱性和平行架構 符合現代處理器 適合智慧卡 這給予演算法實現諸多的彈性，也能嚴密地對抗密碼分析攻擊
演算法能在現代處理器中執行 Pentium, RISC, 平行 適合智慧卡 演算法能在智慧卡中執行

40 Rijndael的運作 明文區塊與金鑰區塊可以被排列成各種未定的大小 可含有多種回合 每回合的步驟 16、24或32位元組
10、12或14個回合 每回合的步驟 位元組替代 位移列 混合行 金鑰加法

41 初始明文／金鑰區塊

42 Rijndael步驟

43 位元組替代

44 位移行

45 金鑰加法

46 差分密碼分析和線性密碼分析 差分密碼分析 線性密碼分析攻擊 由Eli Biham和Adi Shamir提出
專注於成對的密文，其明文有著特殊的差異 線性密碼分析攻擊 Mitsuru Matsui發明 基於線性近似值

47 章節總結 密碼學演算法有兩個主要的觀點 兩個主要的演算法型態 鏈結模式使區塊密碼更安全 四個鏈結模式是 型態 模式 串流密碼 區塊密碼
電子碼冊(ECB) 密文區塊鏈結(CBC) 密碼回饋(CFB) 輸出回饋(OFB)

48 章節總結 資料加密標準(DES)是一個非常受歡迎的對稱性金鑰演算法。 DES 的變化，亦即雙重 DES 和三重 DES 很受歡迎。
其他受歡迎的對稱性金鑰演算法是：IDEA、RC5、Blowfish。 美國政府已經證明一個演算法，稱為 Rijndael，就像高等加密標準(AES)一樣。 差分密碼分析專注於明文中具有特殊差異的密文對。 線性密碼分析攻擊是基於線性近似的基礎上。

49 The End