现在人们普遍将互联网作为信息传送的平台,但在互联网上进行信息的传送存在许多不安全因素.为了确保重要信息在网上安全传输,目前采用的措施主要有3种:安全信道、加密技术和信息隐藏,其中加密技术是应用最广的一种,虽然目前理论上没有不能被破解的加密算法,但只要加密后的数据在要求的时间内不被破解,数据就是安全的。目前的密码体制分为对称密码体制和非对称密码体制2种,非对称密码体制的密钥的管理和传送很方便,在通过网络传输信息时,公钥密码算法体现出了单密钥加密算法不可替代的优越性,其中公钥密码体制的算法中最著名的代表是RSA算法,RSA算法的安全性问题尚未得到理论上的证明,笔者就其安全性进行了一定的分析.

1 RSA加密算法的描述

RSA算法是一个基于初等数论定理的公钥密码体制加密算法,它的实现过程为:选取2个大素数p与q,然后算出n=pq,φ(n)=n-p-q+1,再选取一个正整数e,使之满足(e,φ(n))=1,1<E<Φ(N);再求出正整数D,使之满足1<D,而密钥是.明文消息m满足0≤m

例 取2个质数p=11,q=13,p和q的乘积为n=p×q=143,算出φ(n)=n-p-q+1=120;再选取一个与φ(n)互质的数,例如e=7,则公开密钥=n,e=143,7.

对于这个e值,用欧几里德扩展算法可以算出其逆:d=103.因为e×d=7×103=721,满足e×d mod z =1;即721 mod 120=1成立.则秘密密钥=n,d=143,103,

设发送方需要发送机密信息(明文)m=85,发送方已经从公开媒体得到了接收方的公开密钥n,e=143,7,于是发送方算出加密后的密文c= me mod n=857 mod 143=123并发送给接收方.

接收方在收到密文c=123后,利用只有他自己知道的秘密密钥计算m= cd mod n =123103 mod 143=85,所以,接收方可以得到发送方发给他的真正信息m=85,实现了解密.

用RSA体制加密时,先将明文数字化再进行加密,在实际应用中m值的长度一般要远大于n的长度,因此实际加密消息m时,首先将它分成比n小的数据分组(采用二进制数,选取小于n的2的最大次幂),再每组单独加密和解密.比如说,选用的p和q为100位的素数,那么n将有200位,每个数据分组应小于200位长,但为保证安全性,每个数据的长度应尽量接近n的长度.

2 RSA算法的加密强度与因子分解强度

目前密码的破译主要有2种方法.方法之一是密钥的穷尽搜索,其破译方法是尝试所有可能的密钥组合.虽然大多数的密钥尝试都是失败的,但最终有一个密钥让破译者得到原文,这个过程称为密钥的穷尽搜索.方法之二是密码分析.由于RSA算法在加密和解密过程都是用指数计算,其计算工作量巨大,用穷尽搜索法进行破译是根本不可能的.因此要对RSA算法加密后的信息进行破译只能采用密码分析法,用密码分析法攻击RSA密码系统,途径之一是直接计算“n的e次方根”,但目前还没有解决这一问题的算法,这个问题是现实不可计算的问题;途径之二[4]是想办法计算出d,欲得到d,可考虑从以下3个方面入手.

(1) 将数n分解因子

密码分析员一旦分解出n的因子p和q,就可以先后求出φ(n)和d,从而攻破RSA公开钥密码系统.由此得出如下结论:破译RSA密码不可能比分解因子的问题更困难.

(2) 不分解n的因子计算φ(n)

显然,如果密码分析员能够求出φ(n),由于e是公开的,就可以通过de≡1 (modφ(n))算出d,从而攻破RSA密码系统.但是,一旦密码分析员知道了φ(n),他就可以很容易地分解出n的因子.究其原因为

φ(n)=n-(p+q)+l,

所以,由n及φ(n)可以计算出(p+q).有了(p+q),就可以通过p-q=(p+q)2-4n求出(p-q),因而最终解出p和q.计算φ(n)的方法并不比分解n的因子容易,换言之,通过计算φ(n)破译RSA密码的方法不会比通过分解n的因子破译RSA密码的方法更容易.

(3) 不分解n的因子或计算φ(n)确定d

如果能够知道d,分解n的因子问题也同样会变得容易起来.因为φ(n)=(ed-1)×k,其中k为任意整数,已知d (e 是公开的)时,可求出φ(n),根据φ(n)=n-(p+q)+l,由于n是已知的(公开的),在求出φ(n)时可求出p+q,设求出的p+q=r,又由于n=p×q,从而可得p×p-p×r+n=0,这是一个一元二次方程,自然可非常简单求出p,同理可求出q,分解n完成.

G. L. Miller在1975年指出,利用φ(n)的任何倍数都可以容易地分解出n的因子.因此,用Miller算法就可以由(ed-1)分解出n的因子,也就是说计算d并不比分解n的因子更容易.密码分析员还可能希望找到某个与d等价的d′,从而攻破RSA密码.但是,所有这样的d′只相差(p-1)和(q-1)的最小公倍数的整数倍,因此,找到一个这样的d′就可以使分解n的因子问题变得容易起来,也即找到这样的d′并不比分解n的因子更容易.

综上所述,破译RSA密码系统和分解因子问题同样困难,尽管目前还不能完全证实它,即在目前状况下,如果参数p,q和e选取恰当的话,RSA的加密强度,就取决于的抗因子分解强度.

3. 大数因子分解的难度

著名数学家费马(1601—1665)和勒让德((1752—1833)都研究过分解因子的算法,现代某些更好的算法是勒让德方法的扩展.其中,R. Schroeppel算法是好算法中的一类,用此法分解因子仍然需要大约eln nlnln n次运算,其中ln表示自然对数,可见分解n 所需的运算次数与密钥的长度有关,随着密钥长度的增加,分解所需的时间会成指数倍增加.对于不同长度的十进制数n,Schroeppel算法分解n的因子时所需的运算次数如表1所示.

若用1台1 s能进行1亿次因子分解的高速计算机来计算,分解十进制长度为200位的n,其所需时间为3 800 000年.由此可见,对于RSA系统,如果用一个长度为200位(十进制)的n,认为它是比较安全的,如果n的长度更长,因子分解越困难,一般来说,每增加10位二进制数,分解的时间就要加长1倍.密码就越难以破译,加密强度就越高.

不过随着计算机运算速度的提高和并行计算的发展,破解的速度也会同步提高,这时可能要求使用更长的密钥.

RSA的安全性依赖于大数的因子分解,这样攻击RSA系统的难度就是大整数因子分解的难度,一般认为这是一个NPC问题,尽管尚未在理论上证明分解因子的问题一定困难,但千百年来经过众多学者的研究,迄今没有找到一种有效算法,绝大多数数论学家倾向于认为不存在大整数因子分解的多项式算法,因此目前这一破译只能依赖于现代的计算机技术,用程序进行尝试分解,从而对大数的因子分解.不过随着计算机运算速度的提高和并行计算的发展,加上因子分解方法的改进,低位数的密钥的破解已成为可能.因子分解需的时间随密钥长度的增加而成指数指增加,只要n的长度达到一定要求,并且参数p,q和e选取恰当的话,RSA系统是相当安全的.

小知识之RSA公钥介绍:

RSA公钥加密算法是1977年由Ron Rivest、Adi Shamirh和LenAdleman在(美国麻省理工学院)开发的。RSA取名来自开发他们三者的名字。RSA是目前最有影响力的公钥加密算法,它能够抵抗到目前为止已知的所有密码攻击,已被ISO推荐为公钥数据加密标准。RSA算法基于一个十分简单的数论事实:将两个大素数相乘十分容易,但那时想要对其乘积进行因式分解却极其困难,因此可以将乘积公开作为加密密钥。