剩余类环（？）/n（？）上的一致全向置换的存在性与MD5碰撞攻击方法分析
|
摘要
置换是一类在密码算法中使用相当广泛的密码学函数,构造具有良好密码学性质的置换是设计好的密码算法的重要需求之一。
MD5是国际上通用的两大Hash函数之一,它被广泛应用于数字签名方案、检测数据的完整性、群签名、电子货币、抛币协议、密钥交换协议等方面,因此MD5的安全性至关重要。
本文共分两章:
第一章,介绍了密码学中的两类完全映射:正形置换和全向置换。本文在全向置换研究结果的基础上,给出l-全向置换的概念,讨论了l-全向置换的存在性、函数性质、计数等,在此基础上,进一步给出一致全向置换的概念,提出并讨论了一致全向置换的存在性问题。
第二章,介绍了Hash函数的概念、性质,描述了MD5算法及针对Hash函数的主要攻击方法。本文详细地描述了王小云对MD5的模差分攻击方法,并对该种攻击方法能够成功实施的理论原因进行了初步分析。
Permutation is a kind of special cryptographic function, which is widely used in cryptographic algorithm. Constructing a permutation that has a good cryptographical property is one of the important requirements in designing a good cryptographic algorithm.
MD5 is one of the two international hash functions, which is widely deployed in digital signatures, data integrity, group signature, e-cash and many other cryptographic protocols. So its security is vital to these applications.
There are two chapters in this paper. In the first chapter, we further give the definition of l -omni-direction permutation on the residue-class ring Z/nZ based on the study of omni direction permutation and discuss the l-omni-direction permutation's functional properties. Furthermore, the definition of the uniform omni-direction permutation is presented and a question about its existence is raised.
In the second chapter, the conception, properties and main attacks of hash function are introduced, and the MD5 algorithm is also introduced. Then we present the modular differential attack on MD5 in detail, and preliminarily analyze the theoretical reason why this method can attack successfully.
MD5是国际上通用的两大Hash函数之一,它被广泛应用于数字签名方案、检测数据的完整性、群签名、电子货币、抛币协议、密钥交换协议等方面,因此MD5的安全性至关重要。
本文共分两章:
第一章,介绍了密码学中的两类完全映射:正形置换和全向置换。本文在全向置换研究结果的基础上,给出l-全向置换的概念,讨论了l-全向置换的存在性、函数性质、计数等,在此基础上,进一步给出一致全向置换的概念,提出并讨论了一致全向置换的存在性问题。
第二章,介绍了Hash函数的概念、性质,描述了MD5算法及针对Hash函数的主要攻击方法。本文详细地描述了王小云对MD5的模差分攻击方法,并对该种攻击方法能够成功实施的理论原因进行了初步分析。
Permutation is a kind of special cryptographic function, which is widely used in cryptographic algorithm. Constructing a permutation that has a good cryptographical property is one of the important requirements in designing a good cryptographic algorithm.
MD5 is one of the two international hash functions, which is widely deployed in digital signatures, data integrity, group signature, e-cash and many other cryptographic protocols. So its security is vital to these applications.
There are two chapters in this paper. In the first chapter, we further give the definition of l -omni-direction permutation on the residue-class ring Z/nZ based on the study of omni direction permutation and discuss the l-omni-direction permutation's functional properties. Furthermore, the definition of the uniform omni-direction permutation is presented and a question about its existence is raised.
In the second chapter, the conception, properties and main attacks of hash function are introduced, and the MD5 algorithm is also introduced. Then we present the modular differential attack on MD5 in detail, and preliminarily analyze the theoretical reason why this method can attack successfully.
引文
1 L.J.Paige.Complete Mappings of Finite Groups.Pacific J.Math.I(1951):111-116.
2 Lu Shuwang,Liu Zhenhua,The Research of 2~m-degree Orthomorphic Permutations(1),1994.中国科学院DCS中心内部资料。
3 L Mittenthal,Block Substitutions Using OrthomorphicMappings,Advances in Applied Mathematics,1995,16:59-71.
4 吕述望、徐结绿、徐汉良,Z_n上的全向置换.通信学报,2001.22(11):1-5
5 刘振华、舒畅,正形置换的研究和应用,第五届通信保密现状研讨会论文集,西昌,1995,成都:电子部三十所国防科技保密通信重点实验室,四川省电子学会,1995,39-43.
6 LiuZhenhua,Shu Chang,A Method for Constructing Orthomorphic Permutations of Degree 2~m,Symposium on Theoretial Problems of Cryptology,SKLOIS,June 1995,214-231.
7 冯登国、刘振华,关于正形置换的构造,通信保密1996(2).
8 K Zeng and Q Zhai,A New Principle for B1ockcipher Design:The Invariant Subset Issue,ChinaCrype' 98,1998.
9 Q Zhai and K Zeng,On Transformations with Halving Effect on Certain Subvarieties of the Space Vm(F2),ChinaCrypt' 96,Zhengzhou,1996.
10 张宝东,正形置换与分组密码设计,中国科技大学研究生院博士后研究工作报告.1999.
11 L Mittenthal,Orthomophism Groups of Binary Numbers,Personal Communications,1996.
12 闵嗣鹤、严士健.初等数论,高等教育出版社,2000.
13 Rivest R L.The MD5 message digest algorithm.Request for Comments(RFC 1320).1992
14 B.den.Boer,A.Bosselaers.Collisions for the compression function of M D5,Advances in Cryptology,Eurocrypt' 93 Proceedings,Springer-Verlag,1994.
15 H.Dobbertin.Cryptanalysis of MD5 compress,presented at the rump session of Eurocrypt' 96.
16 Xiaoyun Wang,Hongbo Yu,How to Break MD5 and Other Hash Functions,EUROCRYPT2005,LNCS 3494,pp19-35,Spring-Verlag,2005.
17 bibitems Rivest R L.The MD4 message digest algorithm.Advances in Cryptology.Crypto' 90,1991.LNCS 537:303-311.
18 冯登国、裴定一.密码学导引,科学出版社,1999。
19 A.Lenstra and X.Wang and B.de Weger.Colliding X.509 Certificates.lACR Eprint archive.Report 2005/067.http://eprint.iacr.org.
2 Lu Shuwang,Liu Zhenhua,The Research of 2~m-degree Orthomorphic Permutations(1),1994.中国科学院DCS中心内部资料。
3 L Mittenthal,Block Substitutions Using OrthomorphicMappings,Advances in Applied Mathematics,1995,16:59-71.
4 吕述望、徐结绿、徐汉良,Z_n上的全向置换.通信学报,2001.22(11):1-5
5 刘振华、舒畅,正形置换的研究和应用,第五届通信保密现状研讨会论文集,西昌,1995,成都:电子部三十所国防科技保密通信重点实验室,四川省电子学会,1995,39-43.
6 LiuZhenhua,Shu Chang,A Method for Constructing Orthomorphic Permutations of Degree 2~m,Symposium on Theoretial Problems of Cryptology,SKLOIS,June 1995,214-231.
7 冯登国、刘振华,关于正形置换的构造,通信保密1996(2).
8 K Zeng and Q Zhai,A New Principle for B1ockcipher Design:The Invariant Subset Issue,ChinaCrype' 98,1998.
9 Q Zhai and K Zeng,On Transformations with Halving Effect on Certain Subvarieties of the Space Vm(F2),ChinaCrypt' 96,Zhengzhou,1996.
10 张宝东,正形置换与分组密码设计,中国科技大学研究生院博士后研究工作报告.1999.
11 L Mittenthal,Orthomophism Groups of Binary Numbers,Personal Communications,1996.
12 闵嗣鹤、严士健.初等数论,高等教育出版社,2000.
13 Rivest R L.The MD5 message digest algorithm.Request for Comments(RFC 1320).1992
14 B.den.Boer,A.Bosselaers.Collisions for the compression function of M D5,Advances in Cryptology,Eurocrypt' 93 Proceedings,Springer-Verlag,1994.
15 H.Dobbertin.Cryptanalysis of MD5 compress,presented at the rump session of Eurocrypt' 96.
16 Xiaoyun Wang,Hongbo Yu,How to Break MD5 and Other Hash Functions,EUROCRYPT2005,LNCS 3494,pp19-35,Spring-Verlag,2005.
17 bibitems Rivest R L.The MD4 message digest algorithm.Advances in Cryptology.Crypto' 90,1991.LNCS 537:303-311.
18 冯登国、裴定一.密码学导引,科学出版社,1999。
19 A.Lenstra and X.Wang and B.de Weger.Colliding X.509 Certificates.lACR Eprint archive.Report 2005/067.http://eprint.iacr.org.