浅析RSA算法的安全性

摘要:随着计算机科学技术及网络通信技术的飞速发展和 Internet的快速普及,计算机网络的和无线通信技术的应用已遍及人类社会的各个领域。网络的发展给人们带来了前所未有的便利,同时也给人们提出了新的挑战。如果通过网络以明文方式传送不希望第三方知道的敏感信息,无论是通过无线还是有线传输,所传送的敏感信息很容易被第三方窃听。若把在公共信道上传送的信息以密文的方式传输,使窃听者难以获得有用信息,则可达到安全通信的目的。密码技术是唯一已知的实用方法。

关键词:RSA算法;网络;密码;安全性

中图分类号:TP393文献标识码:A文章编号:1009-3044(2009)27-7660-02

1 RSA 公钥密码算法简介

1978年美国麻省理工学院(MIT)的研究小组成员李维斯特(R.L.Rives)、沙米尔(A.Shamir)和艾德勒曼(L.Adelman)在杂志IEEE上,提出了一种以幂模函数为密码算法的公钥体制,通称RSA公钥密码体制。它是一种比较典型的公开密钥加密算法,也是迄今为止理论上最为成熟和完善的一种公钥密码体制。普遍认为是一个比较理想的公钥体制,到目前为止,仍不失为最有希望的一种公钥密码体制。

1.1 RSA 公钥密码算法的数学基础

同大多数公钥密码体制一样,RSA的安全性主要取决于构造其加密算法的数学函数的求逆的困难性,我们称这样的函数为单向函数。单向函数在密码学中起一个中心作用。它对公钥密码体制的构造是非常重要的。单向函数的研究是公钥密码体制理论中的一个重要课题。但是,虽然很多函数(包括RSA算法的加密函数)被认为或被相信是单向的,但目前还没有一个函数能被证明是单向的。所谓“单向函数”就是极难求得其反函数的函数。单向函数是贯穿整个公钥密码体制的一个核心概念。

RSA的基础是数论的欧拉定理。

欧拉定理:若整数a和n互素,则a?渍(n)1 mod n

其中?准(n)是比n小但与n互素的正整数个数。

推论(Fermat):若p是素数,(a,p)=1,则ap-11 mod p

1.2 RSA加密算法的流程

1) 找到三个数:p, q, d,其中p和q是两个相异的质数,d是与(p-1)(q-1)互质的数。计算出n=pq。

2) 寻找另一个数e,使得ed 1 mod ?准(n)。因为d与?准(n)互质,所以用辗转相除法一定可以找到e。

3) 把{n, e}公开,作为公钥,(n, d)就是私钥;加密时,将待加密信息M看成一个大整数,假设M

1.3 RSA 公钥密码算法的实现

RSA运用两个指数e和d,这里e是公共的而d是私密的。假定P是明文C是密文,发信方运用C=Pe mod n从明文P来创建密文C;收信方运用P=Cd mod n恢复发信方发送的明文。模n是一个非常大的数,是在密钥生成过程中创建的。数对(e,n)称为公钥,是可以对外公布的,(d,n)称为私钥,为解密者所有,不对外公布,此外,公钥和私钥是互逆的,也可以以(d,n)为公钥而(e,n)为私钥。创建公钥和私钥的步骤如下:

1) 随机选取两个不同的大素数p和q,记n=p*q,此处的n即为RSA算法的模。

2) 随机选取e,要求e与(p-1)(q-1)互质,且1

3) 计算满足e × d=1(mod(p-1)(q-1))的d,此处的d即为私钥。公式e × d=1(mod(p-1)(q-1))表示数e和d互为乘法逆,即满足(p-1)(q-1) × z+1=e × d其中z为整数。

4) 加密过程为C=Me mod n,M为明文,C为密文。

5) 解密过程为M=Cd mod n。

2 RSA攻击

2.1 攻击手段

攻击者对 RAS系统攻击有:强行攻击、定时攻击、穷举攻击、统计分析攻击、数学分析攻击。

强行攻击:强行攻击是对所有的密钥都进行尝试。因此(e,)d 的位数越长,算法越安全,但这时密钥生成、加密和解密运算效率也越低。

定时攻击:定时攻击是利用测定RSA解密所进行的模指数运算的时间来估计解密指数d,然后再精确定出d的取值。这种攻击方法可以通过解密运算量与参数d无关来挫败,也可以采用盲化技术来挫败。

穷举攻击:指密码分析者用试遍所有密钥的方法来破译密码,穷举攻击所花费的时间等于尝试次数乘以一次加密(解密)所需的时间。显然可以通过增大密钥量或加大解密(加密)算法的复杂性对抗穷举攻击。

统计分析攻击:指密码分析者通过分析密文和明文的统计规律来破译密码。对抗统计分析攻击的方法是设法使明文的统计特性不带入密文。这样,密文不带有明文的痕迹,从而使统计分析成为不可能。

数学分析攻击:指密码分析者针对加密算法的数学依据通过数学求解和足够复杂的加密算法。为对抗这种数学分析攻击,应选用具有坚实数学基础和足够复杂的加密算法。而这里RSA已经论证很难通过数学分析攻击来找到破绽。

2.2 RSA安全性讨论

RSA算法的体制构造是基于数论的欧拉定理,它的安全性依赖于大数因子分解的困难性。它基于一个非常简单的数论思想,但能抗所有密码攻击。该算法利用了数论领域的一个事实,那就是虽然把两个大质数相乘生成一个合数是件十分容易的事情,但要把一个合数分解为两个质数却十分困难。合数分解问题目前仍然是数学领域尚未解决的一大难题,至今没有任何高效的分解方法。很多专家对这个算法进行了分析和研究。而RSA的安全性是依赖于作为公钥的大数n的位数长度的。目前因子分解速度最快的方法,

假设偷听者乙,获得了甲的公钥N和e以及丙的加密消息c,但无法直接获得甲的密钥d。要获得d,最简单的方法是从c算出n,然后将N分解为p和q,这样她可以计算(p-1)(q-1)并从而由e推算出d。至今为止还没有人找到一个多项式时间的计算方法来分解一个大的整数的因子,但至今为止也还没有人能够证明这种算法不存在。至今为止也没有人能够证明对N进行分解因式是唯一的从c导出n的方法,但今天还没有找到比它更简单的方法。(至少没有公开的方法。)因此今天一般认为只要N足够大,那么黑客就没有办法了。

假如N的长度小于或等于256位,那么用一台个人计算机在几个小时内就可以分解它的因子了。1999年,数百台计算机合作分解了一个512位长的N。今天对N的要求是它至少要1024位长。

所以RSA 面临的较大威胁主要来自于计算能力的持续提高和因子分解算法的不断改进,其中计算能力的提高包括由于计算机网络的发展所导致的联网众多计算机进行分布式计算能力的大力提高和巨型计算机计算能力的提高。

3 总结

随着单机计算能力的提高、Internet网络的迅猛发展、各种快速算法的提出,RSA模数也要因应而变。长的密钥会在很长的一段时间内是安全的。如果想保密很多年,应该选择非常长的密钥。现在RSA 应用中大都采用1024BIT 的模数,因为1024-2048BIT的模数将会在今后很长一段时间里是安全的。

因此,只要合理选择参数,科学应用RSA,应该是安全的、可行的。