一种公开密钥ＲＳＡ算法的实现

石莹莹　李　涛

（安徽理工大学计算机科学与工程学院，安徽淮南232001）

摘要： 主要针对公开密钥RSA算法在面向对象编程方法Visual C++ 6.0下的实现，系统地给 出了类的定义、核心函数的实现流程和使用的主要计算机算法。使算法实现较传统的实现 方法代码更容易重用、数据有更好的封装性和安全性、实现流程更清晰。通过算法的选取 和优化，获得了较传统实现方法更好的系统性能。

关键词：公钥；私钥；RSA；面向对象编程方法

中图分类号：TP301.6文献标识码：A[WT]文章编号：16721098(2008)02007003

The Realization of RSA Algorithm for Public Encryption Key

SHI Yingying,LI Tao

(School of Computer Science and Engineering,Anhui University of Science and Tec hnology,Huainan Anhui 232001,China) Abstract: In the paper the realization of RSA algorithm for public encryption ke y based onVisual C++ 6.0 was presented. Class definition, flow charts of kerne l functions and the computer algorithm were given. Realization of RSA in OOP mak es the code easier to be reused, dataencapsulation better and safer, and flowcharts clearer than the previous realization methods. By optimized algorithm bet ter system performance than the previous realization methods was obtained.

Key words:public encryption key; private key; RSA; object oriented programming

随着计算机的普及和网络的飞速发展，数据的安全性问题显得日益重要，数据的破坏和泄密 会造成重大损失。数据加密算法可以很好地保护数据。加密算法可以分为两大类，对称加密 算法和公开密钥算法。公开密钥算法主要被用来解决网上密钥的交换问题和身份认证、数字 签名。

公开密钥算法的概念是密码学发展史上具有里程碑意义的一件大事［1］，与传统对 称密码体制（即加、解密密码相同）相同，公钥系统使用两个密钥：加密密码可以 公开，称为公钥；解密密钥保密为私钥。产生公钥体制的内在动力有两个：第一传统对称体 制下密码的分配问题；第二信息的数字签证问题，即如何为数字化的消息或文件提供一种类 似于为书面文件手写签证的方法。

RSA算法已经经受了多年深入的密码分析，虽然密码分析者目前既不能证明其安 全性 但也不能否定其安全性，这恰恰说明该算法有很高的实用可信度。本文主要讨论RSA算 法在面向对象编程方法下的具体计算机算法实现。

1RSA算法的基本原理简介

在公钥系统观点之后，文献［2］提出了第一个比较完善的公钥密码算法，这就是著名的RSA 算法。RSA算法描述

(1)选取两个大素数,玴q；

(2)计算,玭=pq,φ(n)=(p-1)(q-1)；

(3)随机选择玠∶1＜d＜φ(n),((d,φ(n))=1；

(4)计算玡∶ed≡1(mod φ(n))；

(5)加密运算对任意明文玬∈zn=｛0,1,…,n-1｝，加密后的密文为c，这里c= m琫玬od n；

(6)解密对密文玞∈zn，明文m=c琩玬od n。

在上面六个步骤中，玭，e公开，n称为模数，e称为加密指数即公钥；p，q，φ(n)，d保密 ，φ(n)为Euler函数，玠称为解密指数，即私钥。解密的正确性证明［3］93略 。

2RSA算法的安全性分析

公钥体制的安全性是指计算上的安全性。RSA算法的安全性建立在大数的因数分解是困难的 这一现实之上，窃听者要解密密文玞，除了穷举攻击外，只能是像合法用户一样拥有d，而 求d应先求φ(n)，而求φ(n)应先求p和q，而求p和q就要分解n，因此破解RSA算法相当于 做大数的因数分解。

3RSA算法的实现细节

结合上面1中的六个步骤，下面讨论RSA的实现过程中应考虑的细节问题。

3.1大素数和的选择

(1) 玴和q多大合适从安全性角度考虑，选择多大的素数，取决于因数分解的能力。目 前已经能够分解130位的十进制数，所以用户应当选择玴,q数为100位的十进制数，这样 玭将达到200位，从而使现有的分解攻击失效。

(2) 大素数的生成目前生成大素数的方法都是概率型的合数检测算法，其原理是 ：对生成的随机数进行合数测试，若该数通过测试，说明其为合数，否则该数可能为素数， 当进行多次测试后，该数均未通过测试，那么这个数为素数的概率将非常大。

既然是概率算法，就有可能有把一个合数当作一个素数用于RSA系统，此时所关心的问题 是：解密可否进行及系统的安全性会否降低［4］。因此，应该首选不受影响系统的 素数生成算法，如可选用SolovayStrassen算法、MillerRabin算法。

(3) ｜p-q｜要适当大因为[SX(](p+q)2[]4[SX)]-n=[SX(](p-q)2[]4[SX)] ，如果｜p-q｜较小，则[SX(](p-q)2[]4[SX)]也较小，因此[SX(](p+q)2[]4[SX)] 稍大于n，也即[SX(]p+q[]2[SX)]稍大于[KF(]n[KF)]，可得如下分解nУ牟街瑁孩 顺 序检查大于[KF(]n[KF)]的每一个整数x，使得x2-n为某一整数y的完全平方，即 x2-n=y2В虎 由x2-n=y2可得n的分解形式n=(x+y)(x-y)，б话愣言，玴和q的二进制表示应当相差几个比特。

(4) 玴-1和q-1都应当有大的素因子这一选择要求是针对RSA的模数玭的Pollard玴 -1因子分解攻击和循环加密攻击。一般的解决方法是：先生成大素数玴1，q1,然后 令p=2p1+1，q=2q1+1，这样生成的p，q均为素数且p-1和q-1都有大的素因子。

(5) (p-1,q-1)应较小假若(p-1,q-1)较大，从而p-1和q-1的最小公倍数，记做u，将会较小；另外满足：ed≡ 1(mod φ(n))的d一定满足ed≡1(mod u)，所以在u较小的情况下可以穷举方法找到d 。

3.2玠,e的选择

玠不能太小，以免穷举攻击。研究结果表明：一般e＜n,d＜[KF(S]4[]n[KF)]时，d是较 容易确定的，这也是实现RSA系统时应先选择玠的原因，选择完d后，可以用扩展的欧几里 德算法计算出e，其依据是［5］：若(d,φ(n))=1，则存在整数s,t使得sd+tφ(n)=1 成立。d,e的选择要在安全性和系统性的有效性之间做出折中。

3.3模指数运算

在加、解密过程中要考虑形如：玿瑀(mod 玭)的模指数运算，为提高运算速度和 节约存储空间，一般采用如下快速算法［3］124

(1) 玜←x,b←r,c←1；

(2) 如果玝=0则输出c，结束；

(3) 若玝(mod2)≠0，则转(5)；

(4) 玝←[SX(]b[]2[SX)],a←(a•a)(mod 玭)转(3)；

⑤ 玝←[SX(]b[]1[SX)],c←(c•a)(mod 玭)转(2)。

3.4不同用户应当使用不同的模数

这样要求的原因是存在着对RSA的如下攻击方法：设两个用户共用一个模数玭，公钥分别为 e1,e2，且(e1,e2)=1，用RSA为他们加密同一消息玬，则密文分别为c1=m琫1(mod n),c2=m琫2(玬od n)；窃听者截获密文c1,c2后，可 以 如下恢复出m：① 用扩展的欧几里德算法求出，满足玶e1+se2=1的两个整数r,s（不妨设r＜0 以及c在(mod n)下的逆元c-11；② 计算(c-11)-rc 瑂2(mod n)就可得到明文m。

当用户的私钥玠泄露后，不仅要更换d，而且要更换模数n。这是因为：如果某人获得了 一个求玠的算法A，则可构造一个以A为子程序的算法［6］ 来分解n，因此在泄露私钥d后仅仅简单的更换d而保留原来的n是不安全的。

4主要成员函数实现流程及其算法

求最大公约数可以使用欧几里德算法，它是幸存到现在的最古老的非凡算法，至今还是可用 的。下面给出算法的Visual C++语言描述：

int god(int 玿,int 珁){

int 玤;

判断取相反数;

if(玿+y==0)

ERROR;

玤=y;

while(玿>0){

取模;}return 玤;}

这个算法可以推广成返回由玬个数组成的god数组。

求模逆元问题等价于寻找一个玿使得： (A•x)玬od n=1，x就是A模n 的逆元。可用来求模逆 元的算法很多，使用扩展的欧几里德算法求模逆元。下面给出算法的Visual C++语言描述：

main(int arg 玞,char **arg 玽){

int 玜,b,god;

if(arg 玞<3){ヅ卸鲜涑;

}int 玼=atoi(atg 玽［1］);int 玽=atoi(arg 玽［2］);

判断输出;}ExtBinEuclid(&玼,&玽,&玜,&玝,&玤od);

cout<<玜<<"*"<<玼<<"+(-"<<玝<<")*<<玽<<"="<<玤od<

if(玤od==1)

输出结果;

return 0;

}ゴ怂惴ㄍü迭代运算来实现的，对于大的整数，其运行可能较慢。Knuth指出这个算法完成 的除法的平均数目是［7］0.843×log2 n+1.47。

5总结

面向对象的概念早在上个世纪60年代就已经被提出了，发展至今已经相当成熟。面向对象编 程方法提出了类的封装概念、代码重用的继承性和对象一致操作的多态性。这些特性使在实 现RSA算法时，可以更好地对敏感数据进行封装、代码得到重用、获得更清晰的程序流程。 从而使算法实现更加安全、更短的开发周期、更好的系统可展性。多态性可以对算法对象进 行一致性操作，使代码更规范、一致。

一个密码系统的设计不仅要有好的算法，实现过程中的细节同样不可忽视。此外，在具体的 应用时还应当考虑到协议的设计细节，因为敌手除了攻击算法外，还可能攻击协议。密码学 是一个不断发展的学科，多年来加密算法设计者和密码分析家在不停地努力，促进密码科学 的进步。一个好的密码学算法可以经得起多年的密码分析，但如果没有一个好的实现方法， 其安全性也是无从谈起的。好的实现方法可以使用户得到近似密码算法理论上的安全性和更 高效的性能。

参考文献：

［1］周玉洁，冯登国.公开密钥算法及其快速实现［M］.北京：国防工业出版社 ，2002：78.

［2］R L RIVEST,A SHAMIR,L ADLEMAN.A Mehod for Obtaining DigitalSignatures and Publickey Cryptosystem［J］.CommACM,1978,21(2):120126.

［3］陈鲁生, 沈世镒. 现代密码学［M］.北京:科学出版社,2002：5772.

［4］ARTO SALOMAA.公钥密码学［M］. 吴世忠，译.北京: 国防工业出版社,1998：7096.

［5］闵嗣鹤, 严士健. 初等数论［M］.第2版.北京:高等教育出版社,1988 ：3642.

［6］冯登国, 林东岱, 吴文玲. 密码学导引［M］.北京:科学出版社,1999：23 55.

［7］BRUCE SCHNEIER(美),应用密码学［M］.吴世忠，译.北京:机械工业出 版社,2006：102118.

(责任编辑：李丽)