RSA公钥密码体制中安全大素数的生成.pdfVIP

第 18 卷 　第 9 期 计 算 机 技 术 与 发 展 Vol . 18 　No . 9 2008 年 9 月 　　　　　　　　　 　　　　　　　　 Sep . 　2008 COM PU TER TECHNOL O GY AND D EV EL OPM EN T RSA 公钥密码体制中安全大素数的生成 张 　宏 ,刘晓霞 ,张若岩 (西北大学 信息科学与技术学院 ,陕西 西安 7 10 127) 摘 　要 :RSA 算法是基于数论的公钥密码体制 ,是公钥密码体制中最优秀的加密算法 。由于 RSA 算法中大素数的生成对 RSA 加密算法的安全性有直接的影响 ,其寻找大素数的实现难度大 ,运算时间长 。文中在研究了密钥生成的一般算法的 基础上 , 即确定性素数产生和概率性素数产生方法 ,给出了利用 Mont gomery 算法优化的 Miller - Rabin 算法和 Pocklington 定理算法实现 ,构造了大素数的生成算法 , 以提高 RSA 算法的安全性和运行速度 。 关键词 :RSA ;Miller - Rabin 算法 ;Mont gomery 算法 ;Pocklington 定理 ( ) 中图分类号 : TP309 . 7 　　　　　　文献标识码 :A 　　　　　　　文章编号 : 1673 - 629X 2008 09 - 0 13 1 - 03 Generation of Great Prime Number in RSA Publ ic Key Cryptosystem ZHAN G Hong , L IU Xiaoxia , ZHAN G Ruoyan (Dept . of Computer Science and Technology , Nort hwest University , Xi ’an 7 10 127 ,China) Abstract :The RSA algorit hm based on t he numeric t heory is t he best encryption algorit hm in public key cryptosystems. It is much com plicated and difficult in generating a great p rime number , because t he great p rime number directly affect s t he safet y of t he RSA encryption algorit hm . Works at t he common generating algorit hms , t hat is , certain generating algorit hms and p robabilistic generating algorit hms , and demonst rates a p rogramming algorit hm based on Miller - Rabin algorit hm imp roved by Mont gomery algorit hm and Pocklington t heo rem . This p rogramming algorit hm const ruct s a great p rime numb