浅谈RSA密码算法及应用

韦 相，李志勇，朱永缤

（红河学院计算机科学与技术系，云南蒙自 661100）

浅谈RSA密码算法及应用

韦 相，李志勇，朱永缤

（红河学院计算机科学与技术系，云南蒙自 661100）

RSA算法能同时用于加密和数字签名，并能实现密钥分发功能，也易于理解和操作.它的安全性依赖于大数分解，但是否等同大数分解，还没有理论上的证明.RSA算法普遍被认为是目前最优秀的，使用最广泛的非对称密码体制，它经历了20多年的攻击考验，才被人们接受.

RSA算法；加密；数字签名

1 前言

随着计算机网络和计算机通讯技术的发展，人们对网络信息资源的依赖程度日益加，为了保证数据在存储和传输的过程中不被泄露、窃取、篡改或者伪造，必须对这些数据进行保护，以保证信息安全.而密码技术不仅可以实现数据加密，还可以实现数字签名、身份验证等功能，因此，计算机密码学得到前所未有的重视并迅速普及和发展起来.

密码技术主要用于保证电子数据的保密性，完整性和真实性[1].

保密性是对数据进行加密，使非法用户无法读懂数据信息，而合法用户可以用密钥读取信息.

完整性是对数据完整性的鉴别，以确定数据是否被非法篡改，保证合法用户得到正确、完整的信息.

真实性是数据来源的真实性、数据本身真实性的鉴别，可以保证合法用户不被欺骗.

RSA加密演算法是一种非对称加密演算法.在公钥加密标准和电子商业中RSA被广泛使用.RSA公钥加密算法是1977年由Ron Rivest、Adi Shamirh和Len Adleman在美国（麻省理工学院）开发的.RSA取名来自开发他们三者的名字.

2 密码学基础

密码学有很长的研究历史，但一般人对它依然十分陌生，因为它只在如军事、情报、外交等这些敏感部门小范围内使用.计算机密码学是研究计算机信息加密、解密及其变换的科学，是数学和计算机的交叉学科，也是一门新兴的学科[1].

计算机密码学的普及和发展依赖于计算机网络和计算机通讯技术的发展.

2.1 密码系统

用于加密和解密的系统称为密码系统.假设发送者想发送消息，而且确信窃听者不能阅读发送的消息的方式安全地发送信息.发送者要加密信息，再发送；接收者要解密信息才能阅读.这就是密码系统实现加密传输的过程.

2.2 密码体制

主要有两种安全性基于密钥的算法：对称算法和公开密钥算法（非对称算法）[2].

（1）对称密码体制

因为加密密钥和解密密钥相同，或者加密密钥能够从解密密钥中推算出来，所以对称算法又叫传统密码算法.

对称算法在多数情况下，加解密的密钥是相同的.对称算法的密钥分发过程就是，双方在通信之前，协商一个密钥.方法是一方生成密钥并通过安全信道传送给另一方.

（2）非对称密码体制

之所以公开密钥算法又叫非对称算法，那是因为加密密钥和解密密钥是不同的，而且不能通过加密密钥算出解密密钥，或者至少在可以计算的时间内不能计算出来.

加密密钥叫做公开密钥（简称公钥），解密密钥叫做私人密钥（简称私钥）.之所以叫做公开密钥算法，因为算法的安全性依赖于解密密码的保密性，不依赖于加密密钥，加密密钥能够公开，使人们能用公钥加密信息，但只有用相应的私钥才能解密信息.

3 公钥加密算法——RSA算法

一个密码系统的安全性只在于密钥的保密性，而不在算法的保密性.通信双方采用对称加密技术进行通信时，必须先约定一个密钥，这种约定密钥的过程称为“分发密钥”.这就产生了一个重要的密钥管理问题，如何告诉对方这个密钥，如果在网路上传输，无论如何也不能保证这个的密钥不被一直肆机的敌人截获.对称加密系统最大的问题是密钥的分发和管理非常复杂、代价高昂.对称加密算法另一个缺点是不能实现数字签名.

非对称式加密就是加密和解密所使用的不是同一个密钥，称为“公钥”和“私钥”两个密钥，当然它们必需配对使用以实现加密解密文件.这里的“公钥”是指可以对外公开的，泄露出去也不怕，而“私钥”则不能，只能由持有人一个人知道.它的优势就在这里，因为对称加密算法如果是在网络上传输加密信息就很难把密钥告诉对方，不管用什么方法都有可能被别窃听到.而非对称式的加密算法有两个密钥，且其中的“公钥”是可以公开的，也就不怕别人知道，收件人解密时只要用自己的私钥即可以，这样就很好地避免了密钥的传输安全性问题[3].

3.1 RSA的算法描述

RSA 算法利用了陷门单向函数，其算法描述如下[1]：

(1) 寻找两个大素数：p和q.为了提高安全性，两个素数的长度要求一样.并计算出其乘积N(N=p*q).

(2) 随后计算出N 的欧拉函数φ(N)=(p-1)(q-1)，φ(N)定义为不超过N并与N互素的数的个数.

(3) 从[0，φ(N)-1]中随机选取加密密钥e，使得e和φ(N)互为素数.

(4) 计算出满足公式e×d = 1modφ(N)中的d，d为解密密钥.

(5) 若用整数X表示明文，整数Y表示密文(X，Y均小于N)，则加解密运算为：

加密：Y=X^e mod N

解密：X=Y^d mod N

其中的d和N也互素、e和N是公开密钥、d和N是秘密密钥.两个素数p和q应舍弃，但不能泄密.

3.2 RSA算法的安全性

RSA算法的可靠性基于分解极大的整数是很困难的.假如有人找到一种很快的分解因子的算法的话，那么用RSA加密的信息的可靠性就肯定会极度下降.但找到这样的算法的可能性是非常小的.今天只有短的RSA钥匙才可能被强力方式解破.到2004年为止，世界上还没有任何可靠的攻击RSA算法的方式.只要其钥匙的长度足够长，用RSA加密的信息实际上是不能被解破的.

3.3 RSA 加密算法的缺点

（1）安全性：RSA的安全性依赖于大数分解的困难性，但是否等同大数分解，因子分解不否是NPC问题，还没有理论上的证明.

（2）速度太慢：使用RSA算法加解密，需要进行大量的计算，运算代价很高，因而速度较慢，和DES算法相比，它要慢几个数量级；且随着大数分解技术的发展，为了保证安全，密钥的长度还要增加，计算量会更大，更不利于数据格式的标准化.为了解决速度问题,人们结合对称,公钥密码算法来使用,实现优势互补:对称钥密码加密速度快,适合用来加密较长的文件,而RSA算法，安全性高，但速度慢，主要用来给文件密钥加密,还解决了对称算法的密钥分发问题.

（3）产生密钥很麻烦：受到素数产生技术的限制，产生素数的效率比较低，很难做到一次一密[4].

3.4 RSA算法的应用

RSA 作为公钥密码体制，其有着较广泛的应用，不仅可以用于保密通信，而且可以实现数字签名和分发密钥.

（1）使用RSA 算法对数据进行加密时，发送方用接收方的公钥对欲发送的信息进行加密，接收方收到密文后用自己对应的私钥进行解密.

（2）用公钥加密，私钥解密，这就实现了信息的保密性.因为公钥无须保密，可以公开传播，而私钥保密就行，因而RSA算法比较方便实现密钥分发.反过来，若使用某人的私钥加密消息，用其公钥正确解密，因为私钥是保密的，只有一个人知道，就可肯定该消息是某人签名的.这样，用私钥加密，用公钥解密，就可以实现数字签名.

任何公钥密码体制，当用私钥签名时，接收方可认证签名人的身份; 当用接收方的公钥加密时，只有接收方能够解密.

这就是说，公钥密码体制即可用作数字签名，也可用作加密.

（3）由于用于加密的公钥是公开的，密钥的分发和管理就很简单，比如对于具有n个用户的网络，仅需要2n个密钥.公钥可在通信双方之间公开传递，或在公用储备库中发布，但相关的私钥必须是保密的，只有使用私钥才能解密用公钥加密的数据，而使用私钥加密的数据只能用公钥来解密.

4 RSA 算法的现状和发展前景

经历了20多年的应用检验，RSA已成为最流行的一种加密标准，许多硬件，软件产品的内核中都有RSA的软件和类库,方便人们的使用.在Apple的协作软件PowerTalk上还增加了签名拖放功能,用户只要把需要加密的数据拖到相应的图标上,就完成了电子形式的数字签名[5].在网络上，RSA 加密方法被引入到几乎所有Internet 安全协议.在它的Digital ID 下可以生成、管理应用于其它厂商的数字签名的公开密钥验证.在硬件上，RSA 技术也被广泛的使用在如安全电话、以太网卡和智能卡中[6].

[1] 石志国等.计算机网络安全教程[M].北京：清华大学出版社，2007.

[2] 张殿明等.计算机网络安全[M].清华大学出版社，2010.

[3] 贾义，赵楠.信息安全和RSA [J] .教育理论与实践，2009.

[4] 数据加密技术[DB/OL].互联网数据中心,2011.http://zy.zhku.edu.cn/info/kcln/10/3.htm.

[5] 陈晓峰,王育民.公钥密码体制研究与进展[J] .通信学报，2004，（8）.

[6] 张仕斌 ,万武南 ,张金全.应用密码学[M].西安：西安电子科技大学出版社，2009.

RSA Calculations and Application

WEI Xiang, LI Zhi-yong, ZHU Yong-bin
(Department of Computer Science, Honghe University, Mengzi 661100, China)

RSA algorithm is easy to understand and operating which can be using in data encryption, digital signature and Key Distribution.Its safety depends on the factor decomposition, but didn't prove theoretically the difficulty of deciphering the RSA with tarsus decomposition difficulty equivalent.RSA is the most widely studied of public-key algorithm, from nearly 20 years, experienced all sorts of attack of the test, for people to accept which is the best, the most widely used asymmetric cryptosystem.

RSA algorithm;encrypt;digital signature

TP3

A

1008-9128（2011）04-0031-03

2011-05-30

红河学院一类课程建设项目( wlkc0903)

韦相(1980-),男,讲师，硕士.研究方向：数据挖掘及图象处理.

[责任编辑 张灿邦]