【作者】 王萍；

【导师】 魏贵民； 张树贵； 范安东；

【作者基本信息】 成都理工大学 ， 计算数学， 2010， 硕士

【摘要】 随着信息产业的迅速发展,人们对信息和信息技术的需要不断增加,信息安全也显得越来越重要。基于对网络传输数据安全性的考虑,保障网络信息安全的加密产品具有广泛的应用前景,密码技术则是保障信息安全的一个重要手段。密码学是信息安全技术的核心,现代密码体制分为公钥体制和私钥体制两大类:私钥体制又称单钥体制,其加密密钥和解密密钥相同;公钥体制又称为双钥体制,其加、解密密钥不同,可以公开加密密钥,而仅需保密解密密钥,从而具有数字签名、鉴别等新功能,被广泛应用于金融、商业等社会生活各领域。RSA是目前公认的在理论和实际应用中最为成熟和完善的一种公钥密码体制,不仅可以进行加密,还可以用来进行数字签名和身份验证,是公钥密码体制的代表。其安全性基于大整数分解的难度,根据其算法原理,我们所选取的大整数必须是符合安全要求的大素数。因此,测素成为保证RSA安全性的一个关键问题。本论文主要围绕大素数的生成进行了一些研究,论文大体结构如下:第一章简要介绍了密码体制和各种加密算法(对称密码算法和公钥密码算法)及公钥密码算法的优缺点及其应用。第二章主要介绍RSA公钥密码体制相关知识并分析其安全性,主要依据的数学理论基础是欧拉定理、Fermat定理、单向函数、伽罗瓦(Galois)域,同时描述了RSA算法和RSA数字签名算法。第三章进一步讨论了RSA算法中各个参数的选取原则,并对RSA算法中所需大素数的生成方法做了分析,介绍了目前大素数生成法是通过概率型和确定型素数测试来筛选符合要求的大素数。第四章主要是根据相关的数学理论,提出改进的大素数生成方法。先是对100以内的小素数筛选法做了改进,由普通试除法改进为根据同余理论得出的小素数分块试除法,再由梅森素数的测试联想到用准梅森素数p = 2 k ?a来进行素性测试,先是给出准梅森素数的定义,然后通过控制参数k和a,用两个循环来实现对大素数的筛选。最后,本文结合Miller-Rabin素数检测法和椭圆曲线素数检测法的原理对Miller-Rabin素数检测法以及ECPP测素法做局部的改进和优化。通过具体的例子结合C语言程序实现了改进的流程,得到了较好的效果。从而,在一定程度上提高了大素数生成的速度。总的说来,本文围绕怎样提高大素数的生成速度,从各个环节进行了改进,包括从理论上和程序实现上都做了一些努力。由于目前为止对于准梅森素数的研究还不够深入,所以对于文中提出的准梅森素数测试法筛选素数还可以进一步得研究改进,这也为将来的研究指明了一个方向。更多还原

【Abstract】 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.更多还原