RSA公钥算法新探析及改进

《RSA公钥算法新探析及改进》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、RSA公钥算法新探析及改进【摘要】众所周知，RSA是唯一一个能够同时实现数据加密、数字签名、祕钥交换的算法。其过程可简述为选取两个大的质数乘积n=p*q(非公开)，然后选择一个和？准(n)互质的整数e(其中1«〈?准(n)),求其关于欧拉函数?准(n)=(p-1)(q-l)=?准(p)*?准©)的逆元d,进而得到公钥对与私钥对(e,n)和(d,n)o假如n是三个或更多素数的乘积会怎样？该算法是否依然成立？本文旨在探讨n取更多素数乘积时所得到的结论以及根据这些结论所能对RSA作出的改进。【关键词】RSA,改进，公钥算法TheDiscussionabouttheImprovementofRSA

2、AlgorithmWuYa-ning(TheComputerScienceAcademyofNanjingUniversityofScienceandTechnologyJiangsuNanjing210094)【Abstract】Asweallknow,RSAistheonlyAlgorithmthatcanbeusedinDataEncryption,DigitalSignatureandKeyDistributioncollectively.TheprocessofRSAcanbebrieflysummarizedinto3stages.First,selectanintegernt

3、hatistheresuItof2primenumbers?product(n二p*q,private).Then,selectanintegerethatisrelativelyprimeto?准(n)(l〈e

4、rs・IstheAlgorithmstillwork?Inthisessay,IamattempttodiscusssomeconclusionsundertheconditionthatnistheresuItoftheproductofmoreintegersandsuggestsomepossibleimprovementsbasedonthoseconclusions.【Keywords】RSA；Improvement；Public-KeyCryptosystem1n取多个质数乘积时的结论及证明1.1n取三个质数乘积时的结论假设n=p*q*r,我们试着推导欧拉函数?准(n)。根据？

5、准(n)的定义，我们要求小于n并且和n互质的正整数的个数。考虑到在小于n且和n不互质的所有数中，有的是P的倍数，有的是q的倍数，有的是r■的倍数，有的既是P又是q的倍数，有的既是q又是r的倍数，还有的既是r又是P的倍数。为了表示方便，我们用S(x)表示小于n的且是X的倍数的正整数的个数。?准(n)=pqr-l-(S(p)+S(q)+S(r)-S(pq)-S(qr)-S(rp)+0)=pqr-l~((pq-1)+(qr~l)+(rp-1)-(p-1)-(q-1)-(r~l)+0)=pqr-pq-qr-pr+p+q+r-1=(p-1)(q-1)(r-1)=?准(p)*?准(q)*?准(r)可以

6、看出计算结果十分巧，正好是p、q、r欧拉函数的乘积。事实上这绝非巧合。这说明用当n二p*q时的证明方法也同样适用于上述情况(证明见下面1.1.2)。换言之，此时RSA算法依然成立。1.2n取三个质数乘积时RSA的正确性证明算法变为：(1)选定p、q、r三个质数(非公开)(2)计算n=p*q*r(公开)(3)选择e使得gcd(?准(n),e)=l；l