23
2008
09

RSA加密算法

该算法于1977年由美国麻省理工学院MIT(Massachusetts Institute of Technology)的Ronal Rivest,Adi Shamir和Len Adleman三位年轻教授提出,并以三人的姓氏Rivest,Shamir和Adlernan命名为RSA算法。该算法利用了数论领域的一个事实,那就是虽然把两个大质数相乘生成一个合数是件十分容易的事情,但要把一个合数分解为两个质数却十分困难。合数分解问题目前仍然是数学领域尚未解决的一大难题,至今没有任何高效的分解方法。与Diffie-Hellman算法相比,RSA算法具有明显的优越性,因为它无须收发双方同时参与加密过程,且非常适合于电子函件系统的加密。

RSA算法可以表述如下:

(1) 密钥配制。假设m是想要传送的报文,现任选两个很大的质数p与q,使得:

(12-1);

选择正整数e,使得e与(p-1)(q-1)互质;这里(p-1)(q-1)表示二者相乘。再利用辗转相除法,求得d,使得:

(12-2) 其中x mod y是整数求余运算,其结果是x整除以y后剩余的余数,如5 mod 3 = 2。

这样得:

(e,n),是用于加密的公共密钥,可以公开出去;以及

(d,n),是用于解密的专用钥匙,必须保密。

(2) 加密过程。使用(e,n)对明文m进行加密,算法为:

(12-3);

这里的c即是m加密后的密文。

(3) 解密过程。使用(d,n)对密文c进行解密,算法为:

(12-4);

求得的m即为对应于密文c的明文。

RSA算法实现起来十分简捷,据说英国的一位程序员只用了3行Perl程序便实现了加密和解密运算。

RSA算法建立在正整数求余运算基础之上,同时还保持了指数运算的性质,这一点我们不难证明。例如:

(12-5);

(12-6)。

RSA公共密钥加密算法的核心是欧拉(Euler)函数ψ。对于正整数n,ψ(n)定义为小于n且与n互质的正整数的个数。例如ψ(6) = 2,这是因为小于6且与6互质的数有1和5共两个数;再如ψ(7) = 6,这是因为互质数有1,2,3,5,6共6个。

欧拉在公元前300多年就发现了ψ函数的一个十分有趣的性质,那就是对于任意小于n且与n互质的正整数m,总有mψ(n) mod n = 1。例如,5ψ(6) mod 6 = 52 mod 6= 25 mod 6 =1。也就是说,在对n求余的运算下,ψ(n)指数具有周期性。

当n很小时,计算ψ(n)并不难,使用穷举法即可求出;但当n很大时,计算ψ(n)就十分困难了,其运算量与判断n是否为质数的情况相当。不过在特殊情况下,利用ψ函数的两个性质,可以极大地减少运算量。

性质1:如果p是质数,则ψ(p) = (p-1)。

性质2:如果p与q均为质数,则ψ(p·q) = ψ(p)·ψ(q) = (p-1)(q-1)。

RSA算法正是注意到这两条性质来设计公共密钥加密系统的,p与q的乘积n可以作为公共密钥公布出来,而n的因子p和q则包含在专用密钥中,可以用来解密。如果解密需要用到ψ(n),收信方由于知道因子p和q,可以方便地算出ψ(n) = (p-1)(q-1)。如果窃听者窃得了n,但由于不知道它的因子p与q,则很难求出ψ(n)。这时,窃听者要么强行算出ψ(n),要么对n进行因数分解求得p与q。然而,我们知道,在大数范围内作合数分解是十分困难的,因此窃密者很难成功。

有了关于ψ函数的认识,我们再来分析RSA算法的工作原理:

(1) 密钥配制。设m是要加密的信息,任选两个大质数p与q,使得 ;选择正整数e,使得e与ψ(n) = (p-1)(q-1)互质。

利用辗转相除法,计算d,使得ed mod ψ(n) = ,即ed = kψ(n) +1,其中k为某一正整数。

公共密钥为(e,n),其中没有包含任何有关n的因子p和q的信息。

专用密钥为(d,n),其中d隐含有因子p和q的信息。

(2) 加密过程。使用公式(12-3)对明文m进行加密,得密文c。

(3) 解密过程。使用(d,n)对密文c进行解密,计算过程为:

cd mod n = (me mod n)d mod n

= med mod n

= m(kψ(n) + 1) mod n

= (mkψ(n) mod n)·(m mod n)

= m

m即为从密文c中恢复出来的明文。

例如,假设我们需要加密的明文代码信息为m = 14,则:

选择e = 3,p = 5,q = 11;

计算出n = p·q = 55,(p-1)(q-1) = 40,d = 27;

可以验证:(e·d) mod (p-1)(q-1) = 81 mod 40 = 1;

加密:c = me mod n = 143 mod 55 = 49;

解密:m = cd mod n = 4927 mod 55 = 14。

关于RSA算法,还有几点需要进一步说明:

(1) 之所以要求e与(p-1)(q-1)互质,是为了保证 ed mod (p-1)(q-1)有解。

(2) 实际操作时,通常先选定e,再找出并确定质数p和q,使得计算出d后它们能满足公式(12-3)。常用的e有3和65537,这两个数都是费马序列中的数。费马序列是以17世纪法国数学家费马命名的序列。

(3) 破密者主要通过将n分解成p·q的办法来解密,不过目前还没有办法证明这是唯一的办法,也可能有更有效的方法,因为因数分解问题毕竟是一个不断发展的领域,自从RSA算法发明以来,人们已经发现了不少有效的因数分解方法,在一定程度上降低了破译RSA算法的难度,但至今还没有出现动摇RSA算法根基的方法。

(4) 在RSA算法中,n的长度是控制该算法可靠性的重要因素。目前129位、甚至155位的RSA加密勉强可解,但目前大多数加密程序均采用231、308甚至616位的RSA算法,因此RSA加密还是相当安全的。

据专家测算,攻破512位密钥RSA算法大约需要8个月时间;而一个768位密钥RSA算法在2004年之前无法攻破。现在,在技术上还无法预测攻破具有2048位密钥的RSA加密算法需要多少时间。美国Lotus公司悬赏1亿美元,奖励能破译其Domino产品中1024位密钥的RSA算法的人。从这个意义上说,遵照SET协议开发的电子商务系统是绝对安全的。

« 上一篇下一篇 »

发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。