公钥密码体制RSA算法_王红珍
中图分类号：TP301文献标识码：A文章编号：1009－2552（2011）08－0034－03
公钥密码体制RSA算法
王红珍1，2，张根耀1，2，李竹林1，2
（1．延安大学计算机学院，延安716000；2．延安大学软件研究与开发中心，延安716000）
摘要：介绍了RSA密码算法原理及在生成注册码方面的应用，并对RSA算法的安全性、缺点进行了简单的分析。
关键词：RSA算法；安全性；加密；解密
RSA algorithm of public key cryptography
WANG Hong-zhen1，2，ZHANG Gen-yao1，2，LI Zhu-lin1，2
（1．Computer Science School，Yan’an University，Yan’an716000，China；
2．Software Research and Development Center，Yan’an716000，China）
Abstract：This paper introduces the principle of RSA cryptography algorithm and the applications for production registration code，and analyzes the security of RSA algorithm，presents the its shortcomings．Key words：RSA algorithm；security；encryption；decryption
0引言
RSA算法是第一个既能用于数据加密也能用于数字签名的算法，是公钥密码体制中最优秀的加密算法。RSA算法的名字以发明者Ron Rivest，Ad-iShamir和Leonard Adleman的名字命名。RSA算法是建立在大数分解和素数检测的理论基础上的，由于RSA的安全性依赖于大数分解，要想对其破解，需要分解一个大数，即从一个公钥中通过因数分解可以得到私钥，但由于其工作量巨大，按目前计算机的处理能力是不可能实现的。这一方面说明RSA 系统具有良好的保密性能，另一方面也对学习和理解这种算法造成一定阻碍。目前，RSA公钥密码体制因其较高的安全性而被广泛采用，在世界许多地方已经成为事实上的标准。
1RSA密码算法原理
首先，选取两个大素数：p和q，为了获得最大程度的安全性，两数的长度一样。计算乘积：n=pq 然后，随机选取加密密钥e，使e和（p－1）（q－1）互素。如果选择合适的e值，RSA的速度将快得多，常用的e值是3，17和65537（216+1）。接着找出d，使得：
ed≡1mod（p－1）（q－1）
则，d=e－1mod（（p－1）（q－1））
d和n也互素。e和n是公用密钥，d是私用密钥。两个素数p和q不再需要，它们可被舍弃，但绝不可泄露。
加密消息m时，将其看成是一个大整数，把它分成比n小的数据分组。按下面公式加密：
ci=mie（mod n）
解密消息时，取每一个加密后的分组ci并计算：mi=cid（mod n）
归纳RSA加解密如表1所示。
表1RSA加解密
公钥
n：两素数p和q的乘积（p和q必须保密）
e：与（p－1）（q－1）互素
私钥d：e－1mod（（p－1）（q－1））
加密c=me mod n
解密m=ed mod n
2利用RSA加密算法实现注册码的生成
利用RSA加密算法设计，根据开发商给顾客编
收稿日期：2011－02－22
基金项目：延安大学专项科研基金（YD2007－21）
作者简介：王红珍（1973－），女，实验师，硕士，研究方向为软件体系结构及应用。
—
43
—
定的顾客号来生成注册码，下面给出主要函数：（1）生成器代码
/*GenRegCode－注册算法主函数*/
BOOL GenRegCode（HWND hWnd）
｛
int len；
big n，d，c，m；
miracl*mip=mirsys（100，0）；
TCHAR szName［MAXINPUTLEN］=｛0｝；
TCHAR szSerial［MAXINPUTLEN］=｛0｝；
TCHAR szBuffer［MAXINPUTLEN］=｛0｝；
len=GetDlgItemText（hWnd，IDC_TXT0，szName，sizeof（szName）/sizeof（TCHAR）+1）；//取顾客号
if（strlen（szName）==0）
｛
SetDlgItemText（hWnd，IDC_TXT1，"请输入字符"）；
return FALSE；
｝
//MIRACL大数运算库运算
//=================== ==================
//p=0xC75CB54BEDFA30AB
//q=0xA554665CC62120D3
//n=0x80C07AFC9D25404D6555B9ACF35
67CF1
//d=0x651A40B9739117EF505DBC33EB8F 442D
//e=0x10001
//128bit RSA
mip－＞IOBASE=16；//16进制模式
c=mirvar（0）；//MIRACL的大数类型
n=mirvar（0）；
d=mirvar（0）；
m=mirvar（0）；
bytes_to_big（len，szName，c）；//将顾客号转换成大数
cinstr（n，"80C07AFC9D25404D6555B9AC F3567CF1"）；//初始化模数n
cinstr（d，"651A40B9739117EF505DBC33E B8F442D"）；//初始化私钥d
powmod（c，d，n，m）；//计算m=（c^d）mod n
cotstr（m，szSerial）；//将m的16进制串表示写入szSerial中，即为注册码
mirkill（c）；
mirkill（n）；
mirkill（d）；
mirkill（m）；
mirexit（）；
SetDlgItemText（hWnd，IDC_TXT1，szSeri-al）；//显示正确的序列号
return TRUE；
｝
（2）注册机代码
/*GenRegCode－RSA算法计算主函数*/
BOOL GenRegCode（HWND hWnd）
｛
int i；
big n，e，c，m；//定义MIRACL的大数类型
miracl*mip=mirsys（100，0）；
TCHAR szName［MAXINPUTLEN］=｛0｝；
TCHAR szSerial［MAXINPUTLEN］=｛0｝；
TCHAR szBuffer［MAXINPUTLEN］=｛0｝；
//初始化0很重要，否则big_to_bytes（0，C，＆szBuffer，0）函数得到结果可能不正确
GetDlgItemText（hWnd，IDC_TXT0，szName，si-zeof（szName）/sizeof（TCHAR）+1）；//取顾客号if（strlen（szName）==0）
｛
return FALSE；
｝
GetDlgItemText（hWnd，IDC_TXT1，szSerial，sizeof（szName）/sizeof（TCHAR）+1）；//取序列号for（i=0；szSerial［i］！=0；i++）//检查输入的序列号是否为16进制数，为cinstr（M，szSerial）使用做准备
｛
if（isxdigit（szSerial［i］）==0）
return FALSE；
｝
//MIRACL大数运算库运算
//=================== ==============
//p=C75CB54BEDFA30AB
//q=A554665CC62120D3
//n=80C07AFC9D25404D6555B9ACF3567CF1
//d=651A40B9739117EF505DBC33EB8F442D
//e=10001
—
53
—
//128bit
mip－＞IOBASE=16；//设定16进制模式
n=mirvar（0）；//初始化变量
e=mirvar（0）；
m=mirvar（0）；//m放明文：注册码
c=mirvar（0）；//c放密文
cinstr（m，szSerial）；//将输入的序列号转换成大数，这里szSerialcinstr（n，"80C07AFC9D25404D655 5B9ACF3567CF1"）；//初始化模数n
cinstr（e，"10001"）；//初始化公钥e
if（compare（m，n）==－1）//m＜n，才能对消息m加密
｛
powmod（m，e，n，c）；//计算明文c=m^e mod n
big_to_bytes（0，c，＆szBuffer，0）；//将c从大数转换成字节数组
mirkill（n）；
mirkill（e）；
mirkill（m）；
mirkill（c）；
mirexit（）；
if（lstrcmp（szName，szBuffer）！=0）//比较姓名与序列号加密后数据的是否相等？
｛
return FALSE；
｝
else
｛
return TRUE；
｝
｝
else
｛
return FALSE；
｝
｝
3RSA加密算法的安全性
RSA的安全性一直未能得到理论上的证明。它经历了各种攻击，至今未被完全攻破。RSA的安全性依赖于大数分解，但是否等同于大数分解一直未能得到理论上的证明，因为没有证明破解RSA就一定需要作大数分解。假设存在一种无须分解大数的算法，那它肯定可以修改成为大数分解算法。目前，RSA的一些变种算法已被证明等价于大数分解。不管怎样，分解n是最显然的攻击方法。一般，n的长度应足够大，比如十进制数200位以上。
但是随着大素数分解技术的发展、计算机能力的提高、计算机造价的降低及并行技术的发展，将会对RSA的安全性造成很大威胁。
4RSA加密体制的缺点
（1）RSA的速度较慢。分组长度太大，为保证安全性，n一般取足够大，不但运算代价很高，而且速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加；而且随着安全级别的提高，密钥的长度在急剧增加，不利于数据格式的标准化；速度一直是RSA的缺陷。
（2）产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。
5解决办法
（1）可以采用新的公钥密码体制，如椭圆曲线公钥密码体制。
（2）可以进一步提高RSA算法的加解密效率，已达到能够在用户可以接受的时间内提供给用户更长的密钥以保证用户信息的安全。
参考文献：
［1］段钢．加密与解密［M］．电子工业出版社，2008．
［2］［美］Paul garrett．密码学导引［M］．吴世忠，等译．机械工业出版社，2003．
责任编辑：
櫀櫀櫀櫀櫀櫀櫀櫀櫀櫀櫀櫀櫀櫀櫀櫀櫀櫀櫀櫀櫀櫀櫀櫀櫀櫀櫀櫀櫀櫀櫀櫀櫀櫀櫀櫀櫀櫀櫀櫀櫀櫀櫀櫀櫀櫀
张禹
（上接第33页）
4结束语
本文对传统中值滤波算法进行了分析，提出了一种改进的中值滤波算法，实验表明该算法在椒盐噪声的抑制和复杂图像细节保护方面具有很好的鲁棒性和适应性，达到了较为理想的滤波效果。
参考文献：
［1］Rafel C Gonzalez，Richard E Woods．Digitial Image Processing ［M］．Second Edition，Beijing：Publishing House of Electronics
Industry，2002．
［2］张明谦，李雷．改进的中值滤波算法［J］．兵工自动化，2007．26（5），77－80．
［3］张旭明，徐滨士，等．去除脉冲噪声的自适应开关中值滤波［J］．光电工程，2006，33（6），1246－1250．
［4］史佳晨，钱建平．一种改进的中值滤波算法的研究［J］．电气电子教学学报，2010，32（2），43－45．
［5］王敏，程京，等．一种改进的自适应中值滤波算法［J］．微计算机信息，2010，26（4），109－110．
责任编辑：肖滨
—
63
—