高效加密预计算RSA算法实现方法.pdf

《高效加密预计算RSA算法实现方法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、国短文高效加密预计算RSA算法实现方法谢芳清刘佳(仲恺农业技术学院计算机科学与工程学院)摘要：本文提出了一种随机预先计算RSA算法。实验结果表明，相比原始公钥密码算法RSA17次模n乘法运算复杂度，随机预先计算RSA算法计算复杂度只需4次模n乘法运算，揭示了预计算RSA算法的加密时间复杂度小，在很大程度上提高了加密速度，有利于实践应用。关键词：RSA算法：时间复杂度；加密modn：1引言(3)、解密：m=ydmodn，通过上式得到解密结果。1978~MIT(MassachusettsInstituteofTechnology)2．2原始RS

2、A加解密时间复杂度分析三位年青数学家R．L．Rivest，A．Shamir和L．Adleman用在RSA体制使用过程中，通常情况下选择数论构造双钥密码的方法，称为RSA体制【l】。它既可P=2+2用于加密、又可用于数字签名，易懂且易于实现，是，其其中中：ee00：一1。有目前仍然安全并且逐步被广泛应用的一种体制[2。国mmodn=(modn)·(()modn)L·()smodn)·(()‘modn)modn际上一些标准化组织ISO、ITU、及SWIFT等均已接加密算法用l6次模n平方运算和1次模n乘法受RSA体制作为标准，Intemet~用

3、的PGP(PrettyGoodPrivacy)也将RSA作为传送会话密钥和数字签名的标运算。解密算法用一次模n指数幂运算。准算法【4，。在现实应用中，密码体制一方面需要保证3随机预计算RSA安全性，另一方面需要保证运算速度【6，刀。本文提出一3．1预计算RSA算法实现方法种随机预先计算RSA算法，通过参数选择、加密、解预计算RSA算法可通过如下三个步骤实现：密三个步骤，并在解密过程中预先计算，不仅可以保(1)、参数选择：独立地选取两大素数p1和p2(各证算法安全，同时比原始RSA算法加密速度要快的512bf的数)，计算n=pl×p2，其欧拉

4、函数值tp(n)=(pl多。一1)(p2—1)，随机选一整数e，l<(n)，((p(n)，e)：l(因2原始RSA算法原理而在模(P(n)下e有逆元)，d=e一1mod(p(n)，k1=2，k2=3，k3，k4，k5，k6：e=+2．1原始RSA算法实现方法，公钥为n，kl，RSA算法可通过如下三个步骤实现：k2，l【3，k4，k5，k6；私钥为d，(1Ol,p2不再需要，(1)、参数选择：独立地选取两大素数pl和p2(各可以销毁)；512bit的数1，计算n=plXp2，其欧拉函数值tp(n)=(pl(2)、加密：将明文分组，各组长102

5、4比特；明—1)(p2一1)，随机选一整数e，1<(p(n)，(‘p(n)，e)==l(因文集Az=-{m：l，(m，n)=1)；随机选择rl，r2Ⅳ加密得到密文c(c1，c2，c3)；其中：c-=·modn而在模(P(n)下e有逆元)，d=e-1mod(p(n)，公钥为n，，e；私钥为d，(pl,p2不再需要，可以销毁)；C2=2·modn(2)、加密：将明文分组，各组长1024比特；明cl=modn，因此文集Az={m：l，(Il1’n)==l}；加密得到密文c-meC=(q)·(c2)·()一2010年第2期自动化与信息工程4l-基金

6、项目：仲恺农业工程学院校级科研基金项目(G3091814)(3)、解密：当解密者接收到密文c(c1，c2，4结论，可能过公式m=cdmodn得到解密结果。在RSA算法的现实应用中，由于加密算法的效通过分析可知，随机的k3，k4，k5，k6组成了率不高，本文提出了一种预计算RSA算法，把公钥原始密码的公钥e，其它的参量和原始的相同，因此拆成随机的4个分量，通过分析，它不仅不会影响安没有改变原始密码的安全性。全性，同时很大程度上提高了加密速度，有利于实践3．2预计算RSA加解密时间复杂度分析应用。e：2+1_2参考文献加密过程同样选择。，其中[

7、1】Rivest，R．；A．Shamir；L．Adleman．”AMethodforObtainingeieoI本方案可以预先计算Rmodn，；DigitalSignaturesandPublic-KeyCryptosyst-ems”．=modn~c3‘modn，CommunicationsoftheACM21(2)：120-126．因此在线加密只[2]Smart，NigelP．Errorsmatter：BreakingRSA-basedPIN需计算clmR1modnc2=mR2modn，，此加encryptionwimthirtyciph

8、ertextvalidityqueries[C]．Lecture密算法只用4次模n平方运算就可以完成整个加密。NotesinComputerScience(includingsu