過去二十幾年來，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回合適合於選擇明文線性攻擊法的最佳線性關係式。

none

參考文獻

[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年。