公钥密码体制（RSA）算法及安全性探析□宣克祥【摘要】作为现代经典加密技术，无论是数据加密标准（DES）还是高级加密标准（AES），都是一种私钥密码体制，其安全性是由其密钥的私密性来保证的；而RSA则是一种公钥密码体制，不仅加密算法本身可以公开，甚至加密用的密钥也可以公开。
本文对公钥密码体制RSA算法原理、具体实现过程及安全性进行深入探讨和分析。
【关键词】RSA算法；加密标准；信息安全【作者单位】宣克祥，解放军国际关系学院1976年，美国斯坦福大学的威特菲尔德·笛福（Whit-field Diffie）和马丁·赫尔曼（Martin Hellman）在题为《密码学的新方向》的论文中提出了一种崭新的思想，不仅加密算法本身可以公开，甚至加密用的密钥也可以公开，这种密码体制被称作非对称式公钥密码体制。
1978年，美国麻省理工学院的隆·里维斯特（Ronald L．Rivest）、阿迪·沙米尔（Adi Shamir）和雷奥纳德·阿德曼（Leonard M．Adleman）提出了迄今为止理论上最成熟、最成功的RSA公钥密码体制，它变革了已使用几千年的对称密钥技术。
在公开密钥加密技术中，加密密钥与解密密钥是不一样的。
如果要向对方发送消息，可以先用对方的公开密钥加密要发送的消息；对方收到消息后，可用自己的私钥解密。
加密密钥是公开的，谁都可以找到，然而，以其加密的消息却必须用接收者保留的私钥才能解密，因而别人无法阅读该消息。
一、RSA算法简介RSA公钥密码体制的安全性是基于数论中的大整数因子分解：两个大质数p和q相乘得到乘积n，在min（p，q）与（p－1）（q－1）之间选取另一个数d，该数与（p－1）（q－1）互质，即两者之间没有公因子，然后用如下公式计算出e：ed mod（p－1）（q－1）=1假如明文块用M表示，密文块用C表示，那么RSA的加密过程为：Me mod n=CRSA的解密过程即为：C d mod n=M假如选定了两个小的质数11和23，那么n=11ˑ23= 253。
接着，在11与220（10ˑ22）之间选取一个与220互质的数d，假设是19，则由19e mod220=1计算出e=139。
根据RSA公钥密码体制，n（253）和e（139）是公开的，而p （11）、q（23）和d（19）是保密的。
在ASCII码中，对于消息“Hi”，用16位二进制数表示为0100100001011001，将它置换为十进制数为72和105。
甲加密过程为：72139mod253=2105139mod253=101乙得到密文2和101后，用密钥d（19）解密：219mod253=7210119mod253=105由于e和n是公钥，可以公开，所以任何人都可以生成密文；但是d是密钥，与p、q一起都要保密。
要想找出d，必须知道p和q，也就是要将n进行因子分解。
但是，如果n很大，分解是十分困难的，现今所有的算法不可能在有效的时间里实现。
这样，情报的安全性就得到了保障。
二、RSA算法公钥和私钥的生成RSA算法实际上是对质数（prime）特性的一种利用。
所谓质数即这样的一种正整数，除了1和其自身外，不存在其它约数（非质数整数被称为合数）。
任何正整数都可能有多种形式被分解为若干整数的乘积，但只具有一种质因数分解形式。
数学家很早就发现了质数的这种特性，但没有加以应用。
RSA算法所使用的公钥必须能够分解成两个质数之乘积。
在目前条件下，分解一个较小的数字如6185371，数秒之－1与3－2，4－1与4－2。
在不同图组的显示图标中，每个热区域对应的显示图标应不同。
4．总分统计。
（1）擦除前图：添加计算图标，录入函数eraseall并添加显示图标，输入“您的总分为”；（2）录入函数“正确｛x｝，错误｛y｝，总分｛z｝”，完成整个游戏如图4所示。
三、结语利用“开发游戏”为手段进行authorware的教学，不但能够提高学生的学习兴趣，锻炼学生的动手能力，还对全部已学内容进行全面的复习与应用，使得学生记忆深刻，并收到不错的教学效果。
【参考文献】1．冯建平符策群等．中文authorware多媒体制作教程［M］．北京：人民邮电出版社，20062．高新考试编委会．authorware6．5职业考试培训教程［M］．北京：北京希望电子出版社，2004内就可以完成（6185371=1867ˑ3313）；但是，如果这个整数很大，例如有50位的一个数，要把它分解成两个质数相乘的结果，所需要的时间就很长，运算方法也较复杂。
由于数字很大，在设计程序软件时，相关变量最好定义为长整型数据，如_int64类型；否则，当程序运行时，数字会增加很快，当变量取值超过其范围时，就会产生越界错误，出现不正确的结果。
在分析研究RSA 算法的时候，我们一般先选择两个质数p 和q ，从p 和q 计算出互质数d ，这三个数就是私钥；再由私钥推算出公钥n 和e 。
这里以产生质数p 为例，质数q 的产生过程与p 是一样的。
质数p 与质数q 必须不同，如果是相同的数，加密和解密就会产生错误。
//产生质数pvoid CRSADlg ：：OnChoosenum1（）｛//TODO ：Add your control notification handler code here _int64m ，j ，flag ，i ；char cBuffer ［N ］；//取edit3中的数作为初始数p m_edit3．GetWindowText （cstredit3，10）；p =_atoi64（cstredit3）；i =p ；//清空列表框m_listbox1．ResetContent （）；//在从p 至p +50的范围里寻找质数for （；i ＜p +50；i ++）｛flag =1；m =（int ）sqrt （（double ）i ）；for （j =2；j ＜=m ；j ++）｛if （i%j ==0）｛flag =0；break ；｝｝//若i 为质数则写入列表框并显示在edit3中if （flag ==1）｛_i64toa （i ，cBuffer ，10）；m_listbox1．AddString （（LPCTSTR ）cBuffer ）；m_edit3．SetWindowText （（LPCTSTR ）cBuffer ）；UpdateData （FALSE ）；｝｝｝在两个质数p 和q 中取较小的一个，然后计算出（p －1）ˑ（q －1），互质数就是在此之间的一个数，它与（p －1）ˑ（q －1）没有公约数。
//产生互质数dvoid CRSADlg ：：OnChoosenum3（）｛//TODO ：Add your control notification handler code here _int64num3，num4，max ，flag ，temp ，i ；char cBuffer ［N ］；m_edit3．GetWindowText （cstredit3，10）；m_edit4．GetWindowText （cstredit4，10）；num3=_atoi64（cstredit3）；num4=_atoi64（cstredit4）；max =（num3－1）*（num4－1）；if （num3＜num4）temp =num3+1；elsetemp =num4+1；//初始d 从num3和num4两个质数中取较小者加1d =temp ；//清空列表框m_listbox3．ResetContent （）；//在num3或num4加1－－（num3－1）*（num4－1）的范围里//寻找与（num3－1）*（num4－1）互质的数//d 以前50个可能的数为限for （d =temp ；d ＜max ＆＆d ＜temp +50；d ++）｛flag =1；for （i =2；i ＜d ；i ++）｛if （d%i ==0＆＆max%i ==0）｛flag =0；break ；｝｝//若为互质数，则加入列表框并显示于edit5中if （flag ==1）｛_i64toa （d ，cBuffer ，10）；m_listbox3．AddString （LPCTSTR （cBuffer ））；m_edit5．SetWindowText （（LPCTSTR ）cBuffer ）；UpdateData （FALSE ）；｝｝｝在知道了私钥p 、q 、d 之后，我们就可以计算出公钥n 和e 了。
在例子中，p 、q 、d 、n 和e 都设置成了全局变量，其值求出以后，在加密和解密函数中即能使用。
//推算公钥n 和evoid CRSADlg ：：OnChoosenum5（）｛//TODO ：Add your control notification handler code here char eBuf ［N ］；_int64m ；//取编辑框中的字符串m_edit3．GetWindowText （cstredit3，10）；m_edit4．GetWindowText （cstredit4，10）；m_edit5．GetWindowText （cstredit5，10）；//转换为数字p =_atoi64（cstredit3）；q =_atoi64（cstredit4）；d =_atoi64（cstredit5）；//计算出m 和n m =（p －1）*（q －1）；n =p*q ；//计算出efor （e =1；e ＜m ；e ++）｛if （e*d%m ==1）break ；e ++；｝//将n 和e 转换为字符串并显示于edit7和edit8_i64toa （n ，eBuf ，10）；m_edit7．SetWindowText （（LPCTSTR ）eBuf ）；_i64toa （e ，eBuf ，10）；m_edit8．SetWindowText （（LPCTSTR ）eBuf ）；UpdateData （FALSE ）；｝选取并分解公钥是一个时间较长的过程，选取的公钥越大，分解所需要的时间越多。
因此，在这里特意设计了一个选取和分解公钥的过程。
先假设给定一个公钥nn ，由此产生两个数pp 和qq ；若公钥nn 等于pp ˑqq ，那么再测试pp 和qq 是不是质数；若同时都为质数，则nn 可作为我们要寻找的公钥。
测试一个数是否是质数的函数是_int64prime （_int64n ）函数，若n 为质数，该函数的返回值为1，否则为0。
//选取并分解公钥nvoid CRSADlg ：：OnChoosenum4（）｛//TODO ：Add your control notification handler code here char eBuf ［N ］；char cBuffer ［N ］；_int64nn ，pp ，qq ；int flag =0；//先从edit7中的数开始m_edit7．GetWindowText （cstredit7，10）；nn =_atoi64（cstredit7）；//清空列表框m_listbox4．ResetContent （）；flag =0；//每次寻找10个公钥while （flag ＜10）｛//质数pp 先取最小的质数3//并在3－－nn /3的范围里++循环for （pp =3；pp ＜nn /3；pp ++）｛//质数qq 先取nn /pp//并在nn /pp －－3的范围里－－循环for （qq =nn /pp ；qq ＞2；qq －－）｛//若nn 等于两个数的乘积if （nn ==pp*qq ）｛//判断这两个数是否都是质数，若是则//形成nn ==pp*qq 字符串并加入列表框//置n =nn ，并标明已找到1个质数if （prime （pp ）＆＆prime （qq ））｛_i64toa （nn ，eBuf ，10）；strcpy （cBuffer ，eBuf ）；strcat （cBuffer ，"="）；_i64toa （pp ，eBuf ，10）；strcat （cBuffer ，eBuf ）；strcat （cBuffer ，"*"）；_i64toa （qq ，eBuf ，10）；strcat （cBuffer ，eBuf ）；m_listbox4．AddString （（LPCTSTR ）cBuffer ）；n =nn ；UpdateData （FALSE ）；flag ++；｝｝｝｝//不管此轮找到质数与否，nn 均增加1nn ++；｝//将最后找到的质数显示于edit7_i64toa （n ，eBuf ，10）；m_edit7．SetWindowText （（LPCTSTR ）eBuf ）；UpdateData （FALSE ）；｝公钥和私钥的处理应注意以下几点：（一）RSA 算法所使用的公钥一般都很大，其安全性是因公钥很大而分解困难达成的。