跳到主要內容

臺灣博碩士論文加值系統

(107.21.85.250) 您好!臺灣時間:2022/01/18 10:14
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:鄧俊泓
研究生(外文):Chun-Hung Teng
論文名稱:線性攻擊法之研究與模擬
論文名稱(外文):The Study and Simulation of Linear Cryptanalysis
指導教授:賴溪松賴溪松引用關係
指導教授(外文):Chi-Sung Laih
學位類別:碩士
校院名稱:國立成功大學
系所名稱:電機工程學系碩博士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:中文
論文頁數:116
中文關鍵詞:密碼學線性攻擊法塊狀密碼器
外文關鍵詞:Linear CryptanalysisBlock CipherCryptography
相關次數:
  • 被引用被引用:1
  • 點閱點閱:425
  • 評分評分:
  • 下載下載:64
  • 收藏至我的研究室書目清單書目收藏:0
過去二十幾年來,DES(Data Encryption Standard)資料加密標準一直在資訊安全上扮演著重要的角色,被廣泛應用於商業、軍事、秘密通訊及身分認證等各方面。雖然在不久的將來AES(Advanced Encryption Standad)也就是新一代的加密標準將完全取代DES的地位,但是這主要是因為DES的金鑰長度太短,在計算機日新月異的今天可能即將不敷使用,而不是在演算法上有明顯的漏洞。
曾經有不少專家學者針對DES做了一些安全性分析,也提出了一些十分有名的攻擊法,例如在西元1990年由Biham與Shamir所提出的差分攻擊法(Differential Cryptanalysis)與在西元1993年由Matsui所提出的線性攻擊法(Linear Cryptanalysis)。但是這些攻擊法都需要獲得十分大量的明文密文對來分析部分的子金鑰位元,雖然很多專家學者都致力於降低這些攻擊法所需要的明文密文對數上,但是很可惜的只有在西元2000年由Knudsen與Robshaw所提出的線性攻擊法的選擇明文變形—選擇明文線性攻擊法(Chosen-Plaintext Linear Attack)有一些進展,因此到目前為止破解DES最有效的方式還是暴力搜尋所有可能的金鑰。
在本論文中我們將深入研究與學習以線性攻擊法及其變形—選擇明文線性攻擊法破解DES金鑰的詳細過程,並以PC cluster平行計算的方式完成這兩種攻擊法攻擊完整16回合DES的模擬程式。我們也修改了Matsui所提出的找尋線性關係式的演算法,提出了一個能夠找尋適合於選擇明文線性攻擊法的線性關係式之演算法,並藉著這個演算法找出6~13回合適合於選擇明文線性攻擊法的最佳線性關係式。
目錄

第一章 簡介 1
1.1 研究動機 1
1.2 論文組織 2
1.3 本論文之主要成果 2
第二章 塊狀密碼器之概述 4
2.1 塊狀密碼器之構成要素 5
2.2 塊狀密碼器設計的安全準則 6
2.2.1 一般性的安全準則 6
2.2.2 其他安全準則 7
2.3 DES演算法 7
第三章 差分攻擊法 15
3.1 差分攻擊法簡介 15
3.1.1 DES之相關特性 15
3.1.2 特徵 18
3.1.3 訊號雜訊比(The Signal to Noise Ratio)的概念 20
3.2 用差分攻擊法攻擊較少回合的DES 22
3.2.1 用差分攻擊法攻擊4-round DES 22
3.2.2 用差分攻擊法攻擊6-round DES 24
3.2.3 用差分攻擊法攻擊8-round DES 29
第四章 線性攻擊法及其相關模擬程式之實現 35
4.1 線性攻擊法簡介 35
4.1.1 線性關係式 35
4.1.2 線性關係式的串聯 39
4.1.3 用統計方法大幅提昇猜對金鑰位元的機率 42
4.1.4 用線性攻擊法攻擊8-round DES 45
4.2 差分線性攻擊法 49
4.3 找出差分特徵和線性關係式的方法 52
4.3.1 差分攻擊法和線性攻擊法之間的對偶性(Duality) 52
4.3.2 找尋差分特徵和線性關係式的演算法 55
4.4 用線性攻擊法攻擊完整16回合DES及其模擬程式之實現 57
4.4.1 用線性攻擊法攻擊完整16回合DES 58
4.4.2 以PC Cluster平行計算的方式完成線性攻擊法攻擊16-round DES
的模擬實驗 62
4.5 用選擇明文線性攻擊法攻擊完整16回合DES及其模擬程式
之實現 64
4.5.1 線性攻擊法的選擇明文變形—選擇明文線性攻擊法 64
4.5.1.1 線性攻擊法的第一個選擇明文變形 65
4.5.1.2 線性攻擊法的第二個選擇明文變形 67
4.5.1.3 線性攻擊法的第三個選擇明文變形 70
4.5.2 以PC Cluster平行計算的方式完成選擇明文線性攻擊法攻擊
16-round DES的模擬試驗 73
4.6 找尋適合於選擇明文線性攻擊法的線性關係式之演算法 75
4.6.1 演算法的基本架構 75
4.6.2 我們所提出的演算法 77
第五章 結論與未來工作 81
參考文獻 82
附錄A DES中S-BOX的差分分布表 84
附錄B DES中S-BOX的線性關係式之機率分布表 100
附錄C 適合於選擇明文線性攻擊法的最佳線性關係式 116


表目錄

表2.1 在DES加/解密演算法中的一些排列表 11
表2.2 DES之替換盒(S-Boxes)函數 12
表2.3 在DES的子金匙產生過程中的一些排列表 14
表3.1 DES的S1的差分分布表(部份) 16
表3.2 當S1的輸入差分為0X34、輸出差分為0XD,且SE=0X01,SE*=0X35時所有
可能的子金鑰 18
表3.3 SEe及SKe與已知、未知金鑰位元之間的關係表 28
表 3.4 E’的可能值與f’的可能值之間的關係 32
表3.5 SEg及SKg與已知、未知金鑰位元之間的關係表 34
表4.1 DES中S5的線性關係式機率分布表 (部份) 37
表 4.2 Algorithm 4.1在幾種N值下的成功機率 44
表 4.3 F8(CR, K8)[17]經過P-1 permutation後可得知是相對應於S1的輸出 48
表 4.4 Algorithm 4.2在幾種N值下的成功機率 49
表4.5 線性攻擊法第一個選擇明文變形的成功率實驗結果 65
表4.6 線性攻擊法第二個選擇明文變形的成功率實驗結果 67
表4.7 原作者所作線性攻擊法第三個選擇明文變形的成功率實驗結果 71
表4.8 本論文所作線性攻擊法第三個選擇明文變形的成功率實驗結果 71
表A.1 DES中S1的差分分布表 84
表A.2 DES中S2的差分分布表 86
表A.3 DES中S3的差分分布表 88
表A.4 DES中S4的差分分布表 90
表A.5 DES中S5的差分分布表 92
表A.6 DES中S6的差分分布表 94
表A.7 DES中S7的差分分布表 96
表A.8 DES中S8的差分分布表 98
表B.1 DES中S1的線性關係式之機率分布表 100
表B.2 DES中S2的線性關係式之機率分布表 102
表B.3 DES中S3的線性關係式之機率分布表 104
表B.4 DES中S4的線性關係式之機率分布表 106
表B.5 DES中S5的線性關係式之機率分布表 108
表B.6 DES中S6的線性關係式之機率分布表 110
表B.7 DES中S7的線性關係式之機率分布表 112
表B.8 DES中S8的線性關係式之機率分布表 114
表C.1 適合於選擇明文線性攻擊法的各回合最佳線性關係式 116

圖目錄

圖2.1 塊狀密碼器加密端結構圖……………………………. 4
圖2.2 塊狀密碼器解密端結構圖……………………………. 5
圖2.3 DES加密演算法流程圖………………………………… 9
圖2.4 f ( R , K )函數之計算過程………………………… 10
圖2.5 DES的子金匙產生過程……………………………... 13
圖3.1 DES中的F函數………………………………………... 17
圖3.2 一個一回合特徵的例子,特徵機率p=1……………… 19
圖3.3 一個一回合特徵的例子,特徵機率p=14/64………. 19
圖3.4 一個三回合特徵的例子,特徵機率p=(14/64)2……. 20
圖3.5 正確的子金鑰與不正確的子金鑰…………………… 21
圖3.6 4回合DES……………………………………………… 22
圖3.7 破解4-round DES所使用的第一個特徵……………….23
圖3.8 破解4-round DES所使用的第二個特徵……………….24
圖3.9 6回合DES……………………………………………… 24
圖3.10 破解6-round DES所使用的第一個特徵……………….25
圖3.11 破解6-round DES所使用的第二個特徵……………….25
圖3.12 The clique method概念圖…………………………….27
圖3.13 8回合DES……………………………………………… 29
圖3.14 破解8-round DES所使用的特徵……………………….30
圖4.1 如何算出NSi(a, b)的示意圖……………………... 36
圖4.2 由S box線性關係式推得回合函數的線性關係式示意圖….38
圖4.3 3-round DES線性關係式串聯圖……………………… 39
圖4.4 5-round DES線性關係式串聯圖……………………..40
圖4.5 在已知N=n的條件下,隨機變數T/N的機率密度函數(在p > 的情況下)….. 45
圖4.6 用線性攻擊法攻擊8-round DES示意圖……………….46
圖4.7 在p’> 的情況下,假設 ,
產生N對明文密文對,T=X1+X2+…+XN的機率密度函數,其中Xi= ……... 48
圖4.8 以差分線性攻擊法攻擊8回合DES示意圖………….. 51
圖4.9 DES架構圖及其內部中間值符號表示法,Yi=Fi(Xi, Ki)………………… 53
圖4.10 DES差分特徵串聯圖, …………………………….. 54
圖4.11 DES線性關係式串聯圖, ………………………... 55
圖4.12 用線性攻擊法攻擊16-round DES示意圖…………... 60
圖4.13 線性攻擊法的第一個選擇明文變形示意圖………… 66
圖4.14 線性攻擊法的第二個選擇明文變形示意圖………… 69
圖4.15 線性攻擊法的第三個選擇明文變形示意圖………… 72
圖4.16 一個由於一次求解的金鑰位元數太大而不能應用於攻擊16-round DES的例子…………………………… 76
參考文獻

[1]E. Biham and A. Shamir, Differential Cryptanalysis of the Data Encryption Standard. Springer Verlag, 1993.
[2]E. Biham, “On Matsui’s Linear Cryptanalysis,” Advances in Cryptology: EUROCRYPT’94, LNCS 950, pp.349-361, 1994.
[3]E. Biham and A. Biryukov, “How to strengthen DES using existing hardware,” Advances in Cryptology: ASIACRYPT’94, LNCS 917, pp.398-412.
[4]E. Biham, “A Fast New DES Implementation in Software,” FSE 97, LNCS 1267, pp.260-272.
[5]F. Brickell, J. H. Moore, and M. R. Purtill, “Structure in the S-Boxes of the DES,” Advances in Cryptology: CRYPTO’86, LNCS 263, pp.3-7, 1986.
[6]W. Diffie and M. E. Hellman, “New Directions in Cryptography,” IEEE Transactions on Information Theory, Vol.IT-22, No.6, pp.644-654, Nov. 1976.
[7]L. Goubin and J. Patarin, “DES and Differential Power Analysis—The Duplication Method,” CHES 99, LNCS 1717, pp.158-172.
[8]B. S. Kaliski and M. J. B. Robshaw, “Linear cryptanalysis using multiple approximations,” Advances in Cryptology: CRYPTO’94, LNCS 839, pp. 26-39, Springer Verlag, 1994.
[9]L. R. Knudsen and M. P. J. Robshaw, “Non-linear approximations in linear cryptanalysis,” Advances in Cryptology: EUROCRYPT’96, LNCS 1070, pp.224-236, Springer Verlag, 1996.
[10]L. R. Knudsen and J. E. Mathiassen, “A Chosen-Plaintext Linear Attack on DES,” FSE 2000, LNCS 1978, pp. 262-272. Springer Verlag, 2001.
[11]P. Kocher, J. Jaffe, and B. Jun, “Differential Power Analysis,” Advances in Cryptology: CRYPTO’99, LNCS 1666, pp.388-397.
[12]X. Lai, “On the Design and Security of Block Ciphers”, Hartung-Gorre Verlag Konstanz, 1992.
[13]S. K. Langford and M. E. Hellman, “Differential-Linear Cryptanalysis,” Advances in Cryptology: CRYPTO’94, LNCS 839, pp. 17-25. Springer Verlag, 1994.
[14]M. Matsui, “Linear cryptanalysis method for DES cipher,” Advances in Cryptology: EUROCRYPT’93, LNCS 765, pp. 386-397. Springer Verlag, 1993.
[15]M. Matsui, “On Correlation Between the Order of S-boxes and the Strength of DES,” Advances in Cryptology: EUROCRYPT’94, LNCS 950, pp. 366-375. Springer Verlag.
[16]M. Matsui, “The first experimental cryptanalysis of the Data Encryption Standard,” Advances in Cryptology: CRYPTO’94, LNCS 839, pp. 1-11. Springer Verlag, 1994.
[17]W. Meier and O. Staffelbach, “Nonlinearity Criteria for Cryptographic Functions,” Advances in Cryptology: EUROCRYPT’89, LNCS 434, pp.549-562, 1989.
[18]H. Miyano, “A Method to Estimate the Number of Ciphertext Pairs for Differential Cryptanalysis,” Advances in Cryptology: ASIACRYPT’91, LNCS 739, pp.51-58, 1991.
[19]K. Nyberg, “Perfect Nonlinear S-Boxes,” Advances in Cryptology: EUROCRYPT’91, LNCS 547, pp.378-386, 1991.
[20]K. Nyberg, “Differentially uniform mappings for cryptography,” Advances in Cryptology, EUROCRYPT’93, LNCS 765, pp.55-64.
[21]K. Nyberg, “Linear Approximations of Block Ciphers,” Advances in Cryptology: EUROCRYPT’ 94, LNCS 950, pp.439-444, 1994.
[22]National Bureau of Standards, Data Encryption Standard, U.S. Department of Commerce, FIPS pub. 46, Jan. 1997.
[23]National Bureau of Standards, DES Modes of Operation, U.S. Department of Commerce, FIPS pub. 81, Dec. 1980.
[24]K. Ohta, S. Moriai, and K. Aoki, “Improving the Searching Algorithm for the Best Linear Expression,” Advances in Cryptology: CRYPTO’95, LNCS 963, pp.157-170.
[25]B. Preneel, “Analysis and Design of Cryptographic Hash Function,” Doct. Dissertation KULeuven, 1993.
[26]O. S. Rothaus, On ”bent” functions. J. Combinational Theory, Ser. A, 20, pp.300-305, 1976.
[27]B. Schneier, “Applied Cryptography”, Second Edition.
[28]A. Shamir, “On the Security of DES,” Advances in Cryptology: CRYPTO’85, LNCS 218, pp.280-281, 1986.
[29]C. E. Shannon, “Communication theory of secrecy systems,” Bell System Technical Journal, vol. 28, pp.656-675, 1949.
[30]T. Shimoyama and T. Kaneko, “Quadratic relation of s-box and its application to the linear attack of full round DES,” Advances in Cryptology: CRYPTO’98, LNCS 1462, pp.200-211. Springer Verlag, 1998.
[31]S. Vaudenay, “An experiment on DES – statistical cryptanalysis,” Procedings of the 3rd ACM Conferences on Computer Security, New Delhi, India, pp. 139-147. ACM Press, 1995.
[32]賴溪松、韓亮、張真誠,”近代密碼學及其應用”,松崗出版社,2000年。
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
1. 8.尹章華,論故意與過失之法理結構,軍法專刊,第三十六卷第六期,民國七十九
2. 9.吳俊毅,竊盜罪不法所有意圖之探討,刑事法雜誌,第四十三卷第二期,民國八
3. 10.余信達,犯罪結構與階層理論之省思--一階層理論之論證(上),軍法專刊,第四
4. 11.余信達,犯罪結構與階層理論之省思--一階層理論之論證(下),軍法專刊,第四
5. 14.周冶平,「人的違法觀」說,刑事法雜誌,第九卷第一期,民國五十四年二月,
6. 15.林山田,評一九九九年的刑法修正,月旦法學雜誌,第五十一期,民國八十八年
7. 16.林東茂,一個知識論上的刑法學思考─刑法體系的思想根源試探,刑事法雜誌,
8. 20.林東茂,加重竊盜--實務相關見解評析,月旦法學雜誌,第七十一期,民國九十
9. 23.法治斌,保障言論自由的遲來正義--評司法院大法官釋字第五零九號,月旦法學
10. 28.柯耀程,刑法「法律競合」問題思辯--法學方法的思考(上),東海大學法學研究,
11. 37.柯耀程,圖利罪修正與法律適用問題分析(上),月旦法學雜誌,第八十期,民
12. 38.柯耀程,圖利罪修正與法律適用問題分析(下),月旦法學雜誌,第八十一期,
13. 43.洪福增,犯罪論之體系,刑事法雜誌,第十九卷第五期,民國六十四年十月,第
14. 44.高金桂,刑法上規範性構成要件要素之探討,警政學報,第二十六期,民國八十
15. 48.陳志龍,曲解內亂罪竟五十年,律師通訊,第一四一期,民國八十年六月,第十