RSA公钥密码体制中的素性检测问题（精）

《RSA公钥密码体制中的素性检测问题（精）》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、RSA公钥密码体制中的素性检测问题赵文科(犬水师范学院数学与统计学院甘肃天水741000)摘要：RSA公钥密码体制的安全性是基于具有两个素因子的大数分解难题，生成两个安全大素数是保密系统安全的保证，目前要确定生成一个安全大素数是很难的，通常采用的方法是，生成随机数，再对其作素性检测•木文首先介绍了几种主要的素性检测算法,在分析其优缺点的基础上提出了一种生成安全大索数的新方法，分析表明，新方法更适合于实际应用.关键词：大素数，素性检测，RSA公钥密码ThePrimalityTestingProblemoftheRSAPublicKeyCryptosystemZ

2、haoWenke(SchoolofMathematicsandstatisticsTianshuiNormalUniversity,TianshuiGansu741000)Abstract：ThesafetyoftheRSApublickeycryptographysystemisbasedonthetwoelementfactordecompositionoflargeproblem,generatingtwosafetybigprimeisthesafetyguaranteeofsecretsystem.Atpresent.itisverydifficu

3、ltyingeneratingasafetybigprime,Theactualmethodisthatgeneratingrandomnumbersandthendetectingprimalityingeneral.Thepaperintroducesseveralmainprimalitytestingalgorithmandputsforwardanewmethodofgeneratingsafetybigprime,basedontheanalysisoftheiradvantagesanddisadvantages.Theanalysissho

4、wsthatthenewmethodismoresuitableforthepracticalapplication.Keywords：bigprime‘primalitytestRSApublic-keycryptosystem1引言密码学是一门研究加密与解密技术的科学，也是一门既古老又年轻的学科，其研究可以追溯到儿千年以前战争岀现的时候.古典的密码技术主要应用于政治、军事以及外交等领域,随着全球信息基础设施和各个国家信息基础的逐渐形成，计算机网络已经成为信息化社会发展的重耍保证，大量的皱感信息常通过公共通信设施或计算机网络进行交换，或以数字的形式存放在计

5、算机系统里•现代密码技术作为实现网络信息安全的核心技术，是保护数据安全的最重要工具之一,其社会价值和商用价值已经得到了充分的肯定.公钥密码山是产生于20世纪70年代的一类新的密码体制.A和B要进行保密通信,A使用B的公钥将明文加密后得到的密文发送给B,B使用自己的私钥将密文解成明文的过程即为一次基于公钥密码技术的保密通信，在这个过程屮，通信信道是可以公开的.计算机网络的高速发展，为公钥密码的发展提供了很好的环境，公钥密码学诞生30余年来，在众多的公钥密码体制中，基于rsa[2]算法的公钥密码体制是唯一被广泛接受并技术实现的公钥密码体制，目前已成为公钥密码的国

6、际标准⑶.RSA公钥密码体制具有密钥管理方便、破译难度大等优点,其公钥和私钥是一对足够大的素数.RSA公钥密码体制的算法可以描述为：(1)生成一对安全大素数(保密)(2)计算二“xq(公开)，依据Euler定理⑷得到曲)=(〃-询-1)(保密)(3)随机生成正整数e,满足gcd(匕0(司)=1/是公开的加密密钥(4)计算d,满足dxe三(mod加?)),〃是解密密钥对明文C和密文P,加密算法和解密算法分别为：加密算法:对明文C,密文为P=Cc(modn)解密算法:对密文P,明文为C=^(mod/i)RSA算法的数学基础是数论中的Euler定理，其安全性国极大

7、地依赖于模数斤的素因了分解难度，如果〃被成功分解为p和q的乘积，那么就能计算出=怖-1),也就是说任何人都可以根据公钥w计算出私钥d,这就要求n十q必须要足够大，使得斤在有效时间内不可分解•所以只有选择合适的安全大素数因子〃和q,才能保证密码系统的安全，因此RSA公钥密码的发展离不开对素数的研究.而素数研究的一个基本问题就是如何快速有效地判别一个整数是否是素数，即素性检测问题.因此，木文将主要讨论RSA公钥密码体制中的索性检测问题，在研究几主要的索性检测算法优缺点的基础上，提出一种新的素数生成方法，即以Miller-Rabin算法为基础算法，在将待测数送入检

8、测程序之前先对其作预处理生成伪素数，通过Miller