臺灣博碩士論文加值系統

DES和 Triple DES即將因為新標準的提出而過時，本文依照新一代加密演算法之規格提出新的加密法，我們修改DES提出新的演算法使其加密金匙和加密資料區塊長度符合現代標準，這個演算法主要是使用較多的替代盒以達成較長的加密金匙和加密資料區塊，並且將我們的演算法針對差分攻擊法和線性攻擊法做調整使其對於此兩種攻擊法有抵抗力。本文分析所提出之加密法，其安全性有一定的保證。並且我們也發現DES之原始設計對於線性攻擊法有所缺陷，我們提出之演算法則可避免此一問題。
差分攻擊法藉由特定的明文與密文組合來分析加密金匙，一般衡量一加密系統對於差分攻擊法的抵抗強度以估計在許多明文密文組合中能夠找到有用組合的機率來衡量，本文亦提出一個嘗試，使用演化式計算以更快找到所需的明文密文組合。
新一代標準加密法AES由Rijndael獲勝，本文也對於此加密法提出修改，藉由安插隨機位元進入被加密資料區塊以增強其強度。

DES and Triple DES will be out of date due to the new standards. In this thesis, a new encryption algorithm is proposed according to the new requirements of key and block sizes. Based on DES, we modify the algorithm to enhance the sizes. The modification is to use more S-boxes in a round function. We also tune our algorithm to resist differential and linear attacks. Based on our cryptanalyses, the security of the algorithm shows some promises. The weakness of DES toward linear cryptanalysis is also shown in this thesis, which is avoided in our algorithm.
Differential attack makes use of specific plaintext pairs to analyze the key. The strength of an encryption system toward differential relies on a lower expected number of right pairs among huge number of plaintext pairs. In this thesis, we proposed an evolutionary computation model to try to find the right pair effectively.
The new standard AES winner is Rijndael. We also modify Rijndael to improve its security by adding some random bits into the plaintext.

Chapter 1 Introduction 1
Chapter 2 Background 5
2.1 AES 6
2.2 NESSIE 11
2.3 DES 15
2.4 Differential Cryptanalysis of DES 19
2.5 Linear Cryptanalysis of DES 25
Chapter 3 Variants of DES 31
3.1 Properties of a Boolean Function 32
3.2 Coupling Rows and Construction of S-boxes 40
3.3 Proposed Extended DES 48
3.3.1 Algorithm of Our Scheme 49
3.3.2 Permutations in Our Scheme 50
3.3.3 Differential Cryptanalysis of Our Scheme 56
3.3.4 P-box and Linear Cryptanalysis 62
3.4 XDES 64
3.4.1 Algorithm of XDES 65
3.4.2 S-box Design Criteria and Differential Cryptanalysis 67
3.4.3 P-box Design Criteria and Linear Cryptanalysis 75
3.4.4 Weak Keys of XDES 82
3.5 Comparison of DES Variants and Other Ciphers 83
Chapter 4 Employ Genetic Algorithm in Differential Cryptanalysis 90
4.1 Differential Cryptanalysis and Genetic Algorithm 90
4.1.1 Differential Cryptanalysis of Seven Round DES 91
4.1.2 Genetic Algorithms 93
4.2 Evolution Model 94
4.3 Simulation Result 96
Chapter 5 Random Rijndael 100
5.1 Rijndael with Random Bits 100
5.2 Strength of Rijndael 103
Chapter 6 Conclusions 105
Bibliography 107

[1] E. Biham. A Fast New DES Implementation in Software. In Proceedings of the 4th Fast Software Encryption workshop, pages 260-272, 1997.
[2] E. Biham. On Matsui's Linear Cryptanalysis. In Proceedings of EUROCRYPT, pages 341-355, 1994.
[3] E. Biham and N. Keller. Cryptanalysis of Reduced Variants of Rijndael. Submitted paper of the Third AES Candidate Conference, 2000, available at [38].
[4] E. Biham, and A. Shamir. Differential Cryptanalysis of the Data Encryption Standard. New York: Springer-verlag, 1993.
[5] R.Chang. A New Method of Building DES S-boxes. Master Thesis of Department of Computer & Information Science of National Chao-Tung University, 1999.
[6] D. Coppersmith. The Data Encryption Standard (DES) and Its Strength against Attacks. IBM journal of Research and Development, 38(3):243-250, 1994.
[7] J. H. Cheon, S. Chee, and C. Park. S-boxes with Controllable Nonlinearity. In Proceedings of Eurocrypt, pages 286-294, 1999.
[8] J. Daemon, V. Rijnmen. AES proposal. See http://www.esat.kuleuven.ac.be/~rijmen/rijndael/
[9] J. H. Evertse. Linear Structure in Block Ciphers. In Proceedings of Eurocrypt, pages 249-266, 1987.
[10] D. B. Fogel. Evolutionary Computation. IEEE press, 1995.
[11] N. Ferguson, J. Kelsey, S. Lucks, B. Schneier, M. Stay, D. Wagner, and D. Whiting. Improved Cryptanalysis of Rijndael. In Proceedings of the Seventh Fast Software Encryption Workshop, pages 213-230, 2000.
[12] N. Ferguson. Twofish Technical Report #5 Impossible Differentials in Twofish. AES Round 2 public comment, 1999, available at [38].
[13] N. Ferguson. Twofish Technical Report #6 A Twofish Retreat: Related-Key Attacks Against Reduced-Round Twofish. AES Round 2 public comment, 2000, available at [38].
[14] H. Gilbert and M. Minier. A collision attack on 7 rounds of Rijndael. In Proceedings of the Third AES Candidate Conference, pages 230-241, 2000.
[15] H. Gilbert and H. Handschuh and A. Joux and S. Vaudenay. A Statistical Attack on RC6. In Proceedings of the Seventh Fast Software Encryption Workshop, pages 64-74, 2000.
[16] T. M. Hsieh, Y. S. Yeh, Y. C. Hsieh and C. C. Wang. A Homophonic DES. Information processing letters, 66(6):317-320, 1998.
[17] I. Harvey. The Effects of Multiple Algorithms in the Advanced Encryption Standard. In Proceedings of the Seventh Third AES Candidate Conference, pages 269-278, 2000.
[18] D. Johnson. AES and Future Resiliency: More Thoughts And Questions. In Proceedings of the Third AES Candidate Conference, pages 257-268, 2000.
[19] J. Kelsey, T. Kohno and B. Schneier. Amplified Boomerang Attacks Against Reduced-Round MARS and Serpent. In Proceedings of the Seventh Fast Software Encryption Workshop, pages 75-93, 2000.
[20] J. Kelsey and B. Schneier. MARS Attacks! Preliminary Cryptanalysis of Reduced-Round MARS Variants. In Proceedings of the Third AES Candidate Conference, pages 169-185, 2000.
[21] K. Kim, S. Lee, S. Park and D. Lee. Securing DES S-boxes against Three Robust Cryptanalysis. In Proceedings of the Workshop on Selected Areas in Cryptography (SAC '95), pages 145-157, 1995.
[22] K. Kim, S. Lee, S. Park and D. Lee. How to Strengthen DES against Two Robust Attack. In Proceedings of the 1995 Korea-Japan Join Workshop on Information Security and Cryptography, pages 173-182, 1995.
[23] L. Knudsen and W. Meier. Correlations in RC6 with a Reduced Number of Rounds. In Proceedings of the Seventh Fast Software Encryption Workshop, pages 94-108, 2000.
[24] L. R. Knudsen. Iterative Characteristics of DES and S2-DES. In Proceedings of CRYPTO, pages 497-511, 1991.
[25] T. Kohno, J. Kelsey and B. Schneier. Preliminary Cryptanalysis of Reduced-Round Serpent. In Proceedings of the Third AES Candidate Conference, pages 195-214, 2000.
[26] S. Lee, S. H. Sung and K. Kim. An Efficient Method to Find the Linear Expressions for Linear Cryptanalysis. In Proceedings of Japan-Korea Join Workshop on Information Security and Cryptology (JW-ISC’95), pages 183-190, 1995.
[27] S. Lucks. Attacking Seven Rounds of Rijndael Under 192-bit and 256-bit Keys. In Proceedings of the Third AES Candidate Conference, pages 215-229, 2000.
[28] M. Matsui. Linear Cryptanalysis Method for DES Cipher. In Proceedings of EUROCRYPT, pages 386-397, 1993.
[29] W. Meier and O. Staffelbach. Nonlinearity Criteria For Cryptographic Functions. In Proceedings of Eurocrypt, pages 549-562, 1989.
[30] W. Millan, L. Burnett, G. Carter, E. Dawson and A. Clark. Evolutionary Heuristics for Finding Cryptographically Strong S-boxes. In Proceedings of the Second International conference On Information and Communication Security, pages 263-274, 1999.
[31] National Bureau of Standards, NBS FIPS PUB 46. Data Encryption standard. National Bureau of Standards, U.S. Department of Commerce, 1977.
[32] J. Nechvatal, E. Barker, L. Bassham, W. Burr, M. Dworkin, J. Foti, and E. Roback. Report on the Development of the Advanced Encryption Standard (AES). Journal of Research of the National Institute of Standards and Technology, 106(3):511-577, 2001.
[33] F. Sano, M. koike, S. mawamura and M Shiba. Performance Evalution of AES Finalists on the High-End Smart Card. In Proceedings of the Third AES Candidate Conference, pages 82-93, 2000.
[34] B. Schneier, Applied Cryptography Second Edition: protocols, algorithms and source code in C, John Wiley & Sons, 1996.
[35] J. Seberry and X. M. Zhang. Highly Nonlinear 0-1 Balanced Boolean Functions Satisfying Strict Avalanche Criterion. In Proceedings of ASIACRYPT, pages 145-155, 1992.
[36] A. F. Webster and S. E. Tavares. On the Design Of S-boxes. In Proceedings of CRYPTO, pages 523-534, 1985
[37] X. M. Zhang, Y. Zheng and H. Imai. Relating Differential Distribution Tables to Other Properties of Substitution Boxes. Designs Codes and Cryptography, 19(1):45-63, 2000.
[38] http://csrc.nist.gov/encryption/aes/index2.html
[39] https://www.cosic.esat.kuleuven.ac.be/nessie/