RSA中大素数的快速生成算法研究
|
摘要
随着信息产业的迅速发展,人们对信息和信息技术的需要不断增加,信息安全也显得越来越重要。基于对网络传输数据安全性的考虑,保障网络信息安全的加密产品具有广泛的应用前景,密码技术则是保障信息安全的一个重要手段。
密码学是信息安全技术的核心,现代密码体制分为公钥体制和私钥体制两大类:私钥体制又称单钥体制,其加密密钥和解密密钥相同;公钥体制又称为双钥体制,其加、解密密钥不同,可以公开加密密钥,而仅需保密解密密钥,从而具有数字签名、鉴别等新功能,被广泛应用于金融、商业等社会生活各领域。
RSA是目前公认的在理论和实际应用中最为成熟和完善的一种公钥密码体制,不仅可以进行加密,还可以用来进行数字签名和身份验证,是公钥密码体制的代表。其安全性基于大整数分解的难度,根据其算法原理,我们所选取的大整数必须是符合安全要求的大素数。因此,测素成为保证RSA安全性的一个关键问题。
本论文主要围绕大素数的生成进行了一些研究,论文大体结构如下:
第一章简要介绍了密码体制和各种加密算法(对称密码算法和公钥密码算法)及公钥密码算法的优缺点及其应用。
第二章主要介绍RSA公钥密码体制相关知识并分析其安全性,主要依据的数学理论基础是欧拉定理、Fermat定理、单向函数、伽罗瓦(Galois)域,同时描述了RSA算法和RSA数字签名算法。
第三章进一步讨论了RSA算法中各个参数的选取原则,并对RSA算法中所需大素数的生成方法做了分析,介绍了目前大素数生成法是通过概率型和确定型素数测试来筛选符合要求的大素数。
第四章主要是根据相关的数学理论,提出改进的大素数生成方法。先是对100以内的小素数筛选法做了改进,由普通试除法改进为根据同余理论得出的小素数分块试除法,再由梅森素数的测试联想到用准梅森素数p = 2 k ?a来进行素性测试,先是给出准梅森素数的定义,然后通过控制参数k和a,用两个循环来实现对大素数的筛选。最后,本文结合Miller-Rabin素数检测法和椭圆曲线素数检测法的原理对Miller-Rabin素数检测法以及ECPP测素法做局部的改进和优化。通过具体的例子结合C语言程序实现了改进的流程,得到了较好的效果。从而,在一定程度上提高了大素数生成的速度。
总的说来,本文围绕怎样提高大素数的生成速度,从各个环节进行了改进,包括从理论上和程序实现上都做了一些努力。由于目前为止对于准梅森素数的研究还不够深入,所以对于文中提出的准梅森素数测试法筛选素数还可以进一步得研究改进,这也为将来的研究指明了一个方向。
With the rapid development of IT technology,people depend on it increasingly,as a result,information security is getting more and more important.Meanwhile,produets that ensure network information show a great prospect due to the importance of transmitting data by network safely,and as an important means of information security,cryptography must be lifted.
Cryptography is the core of the information security. Modern cryptograph is divided into the public key system and the private key system.The private key system is also called the single key system,in which the eneryption proeess is the same as the decryption process.The public key system is also called the double key system,where the encryption process is different with the decryction process. Since the public key system can publish its public key and keep its private key secret,it has many new application such as the digital signature and authentication,which is widely used in every field of the society.
Among the various public key cryptosystem,RSA algorithm is the best choice in both theory and application,and it is open used in digital signature and identification system. Its security is based on the difficulty of large integer factorization. According to the algorithm theory, we selected a large integer must be a safety requirements of large prime numbers. Therefore, the primality testing is a key issue of ensuring the security of RSA.
In this thesis, I do some research on how to generate large prime numbers. The structure of the thesis is roughly as follows:
The first chapter of this thesis briefly introduces cryptography and various encryption algorithms(symmetrical crypto-algorithm and public key crypto-algorithm).and the public key crypto-algorithm’s good and bad points and the application.
The second chapter introduces the RSA public key cryptography-related knowledge and to analyze its security.The RSA public key crypto-algorithm’s 1mathematical theory foundation is the Euler's theorem, the Fermat theorem, the unidirectional function, Galois the (Galois) territory.
The third chapter discussed the principle of each parameter selection in the RSA algorithm, and how to gernerate the large prime number in the RSA algorithm. This chapter introduced the big prime number generator method is the deterministic prime number test screens through the probability conforms to the request big prime number.
The fourth chapter is mainly according to the related mathematical theory, proposes the improvement big prime number production method. This chapter first has made the improvement to 100 within small prime number screening law. By tries the division improvement for the small prime number piecemeal which obtains according to the congruence theory to try the division ordinary. Associates again from the plum woods prime number's test carries on the natural disposition test with the accurate plum woods prime number. It is first gives the accurate plum woods prime number the definition, then through controlled variable k and a, realizes with two circulations to big prime number screening. Finally, this article unifies the Miller-Rabin prime number examination law and the elliptic curve prime number examination method principle to the Miller-Rabin prime number examination law as well as ECPP measured that the element method makes the partial improvement and the optimization. Unified the C language procedure through the concrete example to realize the improvement flow, obtained the good effect. Thus, raised the big prime number production speed to a certain extent.
Generally speaking, how does this article regarding enhance the big prime number the production speed, has made the improvement from each link. Because present up to is not very also thorough regarding the accurate plum woods prime number's research, therefore proposed regarding the article in the accurate plum woods prime number test method screening prime number might also further research improvement, this also indicate a direction for future research.
密码学是信息安全技术的核心,现代密码体制分为公钥体制和私钥体制两大类:私钥体制又称单钥体制,其加密密钥和解密密钥相同;公钥体制又称为双钥体制,其加、解密密钥不同,可以公开加密密钥,而仅需保密解密密钥,从而具有数字签名、鉴别等新功能,被广泛应用于金融、商业等社会生活各领域。
RSA是目前公认的在理论和实际应用中最为成熟和完善的一种公钥密码体制,不仅可以进行加密,还可以用来进行数字签名和身份验证,是公钥密码体制的代表。其安全性基于大整数分解的难度,根据其算法原理,我们所选取的大整数必须是符合安全要求的大素数。因此,测素成为保证RSA安全性的一个关键问题。
本论文主要围绕大素数的生成进行了一些研究,论文大体结构如下:
第一章简要介绍了密码体制和各种加密算法(对称密码算法和公钥密码算法)及公钥密码算法的优缺点及其应用。
第二章主要介绍RSA公钥密码体制相关知识并分析其安全性,主要依据的数学理论基础是欧拉定理、Fermat定理、单向函数、伽罗瓦(Galois)域,同时描述了RSA算法和RSA数字签名算法。
第三章进一步讨论了RSA算法中各个参数的选取原则,并对RSA算法中所需大素数的生成方法做了分析,介绍了目前大素数生成法是通过概率型和确定型素数测试来筛选符合要求的大素数。
第四章主要是根据相关的数学理论,提出改进的大素数生成方法。先是对100以内的小素数筛选法做了改进,由普通试除法改进为根据同余理论得出的小素数分块试除法,再由梅森素数的测试联想到用准梅森素数p = 2 k ?a来进行素性测试,先是给出准梅森素数的定义,然后通过控制参数k和a,用两个循环来实现对大素数的筛选。最后,本文结合Miller-Rabin素数检测法和椭圆曲线素数检测法的原理对Miller-Rabin素数检测法以及ECPP测素法做局部的改进和优化。通过具体的例子结合C语言程序实现了改进的流程,得到了较好的效果。从而,在一定程度上提高了大素数生成的速度。
总的说来,本文围绕怎样提高大素数的生成速度,从各个环节进行了改进,包括从理论上和程序实现上都做了一些努力。由于目前为止对于准梅森素数的研究还不够深入,所以对于文中提出的准梅森素数测试法筛选素数还可以进一步得研究改进,这也为将来的研究指明了一个方向。
With the rapid development of IT technology,people depend on it increasingly,as a result,information security is getting more and more important.Meanwhile,produets that ensure network information show a great prospect due to the importance of transmitting data by network safely,and as an important means of information security,cryptography must be lifted.
Cryptography is the core of the information security. Modern cryptograph is divided into the public key system and the private key system.The private key system is also called the single key system,in which the eneryption proeess is the same as the decryption process.The public key system is also called the double key system,where the encryption process is different with the decryction process. Since the public key system can publish its public key and keep its private key secret,it has many new application such as the digital signature and authentication,which is widely used in every field of the society.
Among the various public key cryptosystem,RSA algorithm is the best choice in both theory and application,and it is open used in digital signature and identification system. Its security is based on the difficulty of large integer factorization. According to the algorithm theory, we selected a large integer must be a safety requirements of large prime numbers. Therefore, the primality testing is a key issue of ensuring the security of RSA.
In this thesis, I do some research on how to generate large prime numbers. The structure of the thesis is roughly as follows:
The first chapter of this thesis briefly introduces cryptography and various encryption algorithms(symmetrical crypto-algorithm and public key crypto-algorithm).and the public key crypto-algorithm’s good and bad points and the application.
The second chapter introduces the RSA public key cryptography-related knowledge and to analyze its security.The RSA public key crypto-algorithm’s 1mathematical theory foundation is the Euler's theorem, the Fermat theorem, the unidirectional function, Galois the (Galois) territory.
The third chapter discussed the principle of each parameter selection in the RSA algorithm, and how to gernerate the large prime number in the RSA algorithm. This chapter introduced the big prime number generator method is the deterministic prime number test screens through the probability conforms to the request big prime number.
The fourth chapter is mainly according to the related mathematical theory, proposes the improvement big prime number production method. This chapter first has made the improvement to 100 within small prime number screening law. By tries the division improvement for the small prime number piecemeal which obtains according to the congruence theory to try the division ordinary. Associates again from the plum woods prime number's test carries on the natural disposition test with the accurate plum woods prime number. It is first gives the accurate plum woods prime number the definition, then through controlled variable k and a, realizes with two circulations to big prime number screening. Finally, this article unifies the Miller-Rabin prime number examination law and the elliptic curve prime number examination method principle to the Miller-Rabin prime number examination law as well as ECPP measured that the element method makes the partial improvement and the optimization. Unified the C language procedure through the concrete example to realize the improvement flow, obtained the good effect. Thus, raised the big prime number production speed to a certain extent.
Generally speaking, how does this article regarding enhance the big prime number the production speed, has made the improvement from each link. Because present up to is not very also thorough regarding the accurate plum woods prime number's research, therefore proposed regarding the article in the accurate plum woods prime number test method screening prime number might also further research improvement, this also indicate a direction for future research.
引文
[1]王育民,刘健伟.通信网的安全一理论与技术.西安洒安电子科技大学,1999.
[2]秦志光.密码算法的现状和发展研究.计算机应用,2004(2):1-4。
[3] [美]Andrew Nhas,William Duane,Celia joseph,等著;张玉清,陈建奇,杨波,等译.公钥基础设施(PKI):实现和管理电子安全.北京:清华大学出版社,2002.12。
[4] [美]Wiliim Stallings著;杨明,胥光辉,齐望东,等译.密码编码学与网络安全:原理与实践(第二版).北京:电子工业出版社,2001.4。
[5] W.Diffie and M.HeUmna.New directions in Cryptography[J].IEEE Transactions in Information Theory, 1976,22(6):644-654。
[6]刘永亮,姚鸿勋,高文.AKS算法对现代密码学的影响.计算机工程与应用,2003(11):l-3,54。
[7] R.L. Rivest,A.Shamir and L.M.Adleman. A method for obtaining digital signatures and public-key cryptosystems[J]. Communications of the ACM, 1978,21(2):120-126。
[8]王静,王樱.RSA算法简述及其在电子投票中的应用.宁波职业技术学院学报,2005(2):72-73。
[9]章磊,卢建朱,凌捷,李家兰.一种新的基于多素数RSA认证加密方案.计算机应用研究,2005(5):105-107。
[10]徐建兵,曲俊华.公开密钥加密体系和数字签名技术的研究.现代电力,2004(l):80-84。
[11]王兆星.政务信息处理中安全域控制机制研究.情报科学,1999(2):135-155。
[12]傅汝霖,谢海慧.公钥密码在网络信息加密中的应用.计算机应用,1998(11):42-43。
[13] B.Kaliski and M.Robshaw.The Secure Use of RAS.CryptoBytes,Autumn 1995。
[14]杨维忠,李彤,郝林.RsA加密体制的安全隐患.云南大学学报(自然科学版),2004(3):212-215。
[15].邹惠,余梅生,王建东.有效解决RSA共模攻击的素数生成方案.计算机工程与应用,27153(2004):88-89,153。
[16]李产麟,郭宝安.破译RSA能力的零知识证明的改进方案.计算机应用,2002(9):99-100。
[17]陈晓峰,王育民.公钥密码体制研究与进展.通信学报,2004,8(25):109-118。
[18]姚茂群.网络攻击的分析与防范措施.计算机应用研究,1998,16(22):34-35。
[19]刘彦,刑琦.计算机网络信息安全.信息技术,2004,5(28):94-96。
[20]任志毅.网络信息安全问题的研究.铁路计算机应用,2003.9。
[21]耿海飞苏锦海.大素数的快速生成研究与实现.电脑与信息技术第13卷第2期2005.4.
[22]卢开澄.计算机密码学(第2版) [M ].北京:清华大学出版社, 1998.
[23] G.Miller.Riemann’s Hypothesis and Tests for Primality. J.Comp.Syst.Sci.13(1976):300-317。
[24]S.Wgaon.Mathematica is in Action.New York:W.H.Freeman,pp.15-17,1991。
[26]裴定一祝跃飞算法数论[M].北京:科学出版社,2002:130-144。
[27]章照止.现代密码学基础[M].北京:北京邮电大学出版社.2004:154-158。
[28]潘成彪潘成洞简明数论[M].北京:北京大学出版社,2005:123-128。
[29] Joseph H.Silverman数论概论[M].北京:机械工业出版社,2008:136-145。
[30] P.里本伯姆著孙淑玲冯克勤译博大精深的素数[M].北京:科学出版社,2007:111-130。
[31] P.K盖伊数论中未解决的问题[M].北京:科学出版社,2003:38-44。
[32]王英. RSA算法中大素数的快速生成方法[J].湖南科技学院学报.第26卷. 2005.5:14-16。
[33]刘明华,余启港.RSA公钥密码算法中大素数的生成及素性检测[J].中南民族大学学报(自然科学版)第23卷第4期.2004.12:94-96。
[34]游新娥. RSA算法中安全大素数生成方法研究与改进[J].北京电子科技学院学报.第15卷第2期.2007.6:14-16。
[35]刘莉.关于Mersenne数的椭圆曲线测试的注记[J].安徽师范大学学报(自然科学版)第30卷1期。
[36]陈燕王瑞.基于椭圆曲线的一种素性检测方法[J].计算机应用与软件第25卷第9期。
[37]刘如玉周锦君.椭圆曲线在整数分解中的应用[J].信息工程学院学报第18卷第2期。
[38] Kennetj H.Rosen.Elementary Numbei Theory and Its Applications(Fourth Edition)[M].北京:机械工业出版社.2004.2:146-157。
[39] Song Y.Yan.Number Theory for Computing(2th Edition)[M].世界图书出版公司.书号:7-5062-7190-7.2002:139-159。
[2]秦志光.密码算法的现状和发展研究.计算机应用,2004(2):1-4。
[3] [美]Andrew Nhas,William Duane,Celia joseph,等著;张玉清,陈建奇,杨波,等译.公钥基础设施(PKI):实现和管理电子安全.北京:清华大学出版社,2002.12。
[4] [美]Wiliim Stallings著;杨明,胥光辉,齐望东,等译.密码编码学与网络安全:原理与实践(第二版).北京:电子工业出版社,2001.4。
[5] W.Diffie and M.HeUmna.New directions in Cryptography[J].IEEE Transactions in Information Theory, 1976,22(6):644-654。
[6]刘永亮,姚鸿勋,高文.AKS算法对现代密码学的影响.计算机工程与应用,2003(11):l-3,54。
[7] R.L. Rivest,A.Shamir and L.M.Adleman. A method for obtaining digital signatures and public-key cryptosystems[J]. Communications of the ACM, 1978,21(2):120-126。
[8]王静,王樱.RSA算法简述及其在电子投票中的应用.宁波职业技术学院学报,2005(2):72-73。
[9]章磊,卢建朱,凌捷,李家兰.一种新的基于多素数RSA认证加密方案.计算机应用研究,2005(5):105-107。
[10]徐建兵,曲俊华.公开密钥加密体系和数字签名技术的研究.现代电力,2004(l):80-84。
[11]王兆星.政务信息处理中安全域控制机制研究.情报科学,1999(2):135-155。
[12]傅汝霖,谢海慧.公钥密码在网络信息加密中的应用.计算机应用,1998(11):42-43。
[13] B.Kaliski and M.Robshaw.The Secure Use of RAS.CryptoBytes,Autumn 1995。
[14]杨维忠,李彤,郝林.RsA加密体制的安全隐患.云南大学学报(自然科学版),2004(3):212-215。
[15].邹惠,余梅生,王建东.有效解决RSA共模攻击的素数生成方案.计算机工程与应用,27153(2004):88-89,153。
[16]李产麟,郭宝安.破译RSA能力的零知识证明的改进方案.计算机应用,2002(9):99-100。
[17]陈晓峰,王育民.公钥密码体制研究与进展.通信学报,2004,8(25):109-118。
[18]姚茂群.网络攻击的分析与防范措施.计算机应用研究,1998,16(22):34-35。
[19]刘彦,刑琦.计算机网络信息安全.信息技术,2004,5(28):94-96。
[20]任志毅.网络信息安全问题的研究.铁路计算机应用,2003.9。
[21]耿海飞苏锦海.大素数的快速生成研究与实现.电脑与信息技术第13卷第2期2005.4.
[22]卢开澄.计算机密码学(第2版) [M ].北京:清华大学出版社, 1998.
[23] G.Miller.Riemann’s Hypothesis and Tests for Primality. J.Comp.Syst.Sci.13(1976):300-317。
[24]S.Wgaon.Mathematica is in Action.New York:W.H.Freeman,pp.15-17,1991。
[26]裴定一祝跃飞算法数论[M].北京:科学出版社,2002:130-144。
[27]章照止.现代密码学基础[M].北京:北京邮电大学出版社.2004:154-158。
[28]潘成彪潘成洞简明数论[M].北京:北京大学出版社,2005:123-128。
[29] Joseph H.Silverman数论概论[M].北京:机械工业出版社,2008:136-145。
[30] P.里本伯姆著孙淑玲冯克勤译博大精深的素数[M].北京:科学出版社,2007:111-130。
[31] P.K盖伊数论中未解决的问题[M].北京:科学出版社,2003:38-44。
[32]王英. RSA算法中大素数的快速生成方法[J].湖南科技学院学报.第26卷. 2005.5:14-16。
[33]刘明华,余启港.RSA公钥密码算法中大素数的生成及素性检测[J].中南民族大学学报(自然科学版)第23卷第4期.2004.12:94-96。
[34]游新娥. RSA算法中安全大素数生成方法研究与改进[J].北京电子科技学院学报.第15卷第2期.2007.6:14-16。
[35]刘莉.关于Mersenne数的椭圆曲线测试的注记[J].安徽师范大学学报(自然科学版)第30卷1期。
[36]陈燕王瑞.基于椭圆曲线的一种素性检测方法[J].计算机应用与软件第25卷第9期。
[37]刘如玉周锦君.椭圆曲线在整数分解中的应用[J].信息工程学院学报第18卷第2期。
[38] Kennetj H.Rosen.Elementary Numbei Theory and Its Applications(Fourth Edition)[M].北京:机械工业出版社.2004.2:146-157。
[39] Song Y.Yan.Number Theory for Computing(2th Edition)[M].世界图书出版公司.书号:7-5062-7190-7.2002:139-159。