RSA算法的攻击与防范

摘要:作为对典型的公钥密码算法,RSA算法在信息安全领域得到了广泛的应用,但是其安全性却一直是学者们议论的话题。本文首先介绍RSA公钥加密算法的工作原理,对RSA算法的缺陷以及对其所可能遭受的攻击进行分析,最后讨论了针对RSA算法攻击的防范措施。

关键词:公钥密码算法;RSA算法;缺陷;攻击;防范

中图分类号:TN918.1文献标识码:A文章编号:1007-9599 (2010) 06-0000-02

Attacking&Prevention of RSA Algorithms

Li Shixiao

(Zhongyuan University of Technology,Zhengzhou450007,China)

Abstract:As the typical public-key algorithms,RSA algorithms has been widely applied in the field of information security,but its security has been among the scholars.This paper first introduces the theory of the RSA public-key encryption algorithm,and then,analysis the defects of the possible attacking,finally,discusses the attacking preventive measures for RSA algorithms.

Keywords:Public-key algorithms;RSA algorithms;Defects;Attacking;

Prevention

一、引言

计算机和互联网络的飞速发展使世界范围内信息的传递变得越来越方便,同时,也带来了保障信息安全的新问题。而密码学理论和技术的研究与应用,为保证信道中信息的安全传输奠定了基础。

现代密码体制主要分为私钥密码体制和公钥密码体制,其中私钥体制又称单钥体制或对称密码体制,其加密密钥和解密密钥相同,密钥严格保密;公钥体制又称双钥体制或非对称密码体制,其所用的加、解密钥不同,加密密钥公开,解密密钥不公开,适用于开放的使用环境。1976年Diffie和Hellman发表了《密码学的新方向》一文,首次提出了公开密钥的密码学,即公钥密码学,打破了长期使用单密钥体制的束缚。

目前比较流行的公钥密码算法主要有两种:一类是基于大素数因子分解问题的,其中最典型的代表就是RSA公钥密码算法; 1977年R.L.River,A.Shamir和L.Adleman3人共同提出了RSA算法,并很快成为了一种典型的公钥体制密码算法。另一类是基于离散对数问题的,如ELGamal公钥密码算法和椭圆曲线公钥密码算法等。

二、RSA算法简介

RSA公钥加密算法是1978年由美国麻省理工学院(MIT)的Rivest、Shamirh和Adleman共同提出的,它是目前最有影响力的公钥加密算法。RSA算法基于一个非常简单的数学难题:将两个大素数相乘十分容易,但想要对其乘积进行因式分解却非常困难,用很简单的形式实现了非常可靠的密码算法。RSA的安全性依赖于大数的因子分解,而大整数因子分解问题是数学上的著名难题,至今没有有效的方法予以解决,因此能够确保RSA算法的安全性。

RSA算法是目前最优秀的公钥方案之一,除加密功能外,公钥系统还用于身份验证(Authentication)或数字签名(Digital Signature),因此它为公用网络上信息的加密和鉴别提供了一种基本的方法。大多数使用公钥密码进行加密和数字签名的产品和标准使用的都是RSA算法。它通常是先生成一对RSA 密钥,其中之一是保密密钥,由用户保存;另一个为公开密钥,可对外公开,甚至可在网络服务器中注册,人们用公钥加密文档发送给个人,个人就能够用私钥解密接受。

三、RSA的算法描述

(一)RSA算法密钥的产生

1.选两个大的素数p,q(保密);

2.计算n=p*q(公开),欧拉函数Ф(n)=(p-1)*(q-1);

3.随机选取e作为公钥(加密密钥),满足gcd(e,Φ(n))=1(公开);

4.计算私钥d(解密密钥),满足edl(mod(Φ(n))),即ed-1(mod(Φ(n));

5.销毁p,q及Φ(n);

6.得到所需的公开密钥和保密密钥。

公开密钥:EK={e,n};保密密钥:DK={d,n};

(二)RSA算法加密和解密变换

首先将明文分块并数字化,每个数字化的明文的长度不大于[S2n],然后对每个明文块m(0≤m≤n)一次进行加解密变换:

1.加密变换:使用公钥e和明文m,获得密文cme(modn)

2.解密变换:使用私钥d和密文c,获得明文mcd(modn)

四、RSA算法的缺陷

RSA密码算法作为公钥密码体制的代表被广泛地应用于现代信息安全的各个领域,它的安全性的理论基础是大素数的因子分解问题,此问题至今没有很好的算法,但是它本身却存在着一些缺陷,综合来说,RSA算法的不足或者缺陷主要包括:

(一)RSA算法所要求的n,p,q都要求为很大的整数或素数,实现时采用的是重复平方求模和相乘后求模的迭代方法来实现,此方法在进行数据加密时耗费时间过长。

(二)RSA算法中所用的p,q如果太接近的话,密码分析者可以通过计算 ,然后在 附近搜索p,q来分解n。

(三)对于一个明文消息m(0≤m

(四)同态性。由RSA算法知对于一切x1,x2∈Zn,有Ek(x1,x2)Ek(x1)Ek(modn)是RSA算法的一个缺陷,因为攻击者知道C1,C2的明文,就可以知道C1C2(modn)对应明文m1m2(modn)。

基于以上的缺陷,攻击者想来对RSA算法进行攻击的一系列攻击方法,其中最常用的攻击方法有因子分解攻击、选择密文攻击、同模攻击、小指数/指数攻击、迭代循环攻击、定时攻击等。

五、常见的RSA攻击方法

(一)因子分解攻击

易知,若n=pq被因子分解,则可以得到p(n)=(p-1)*(q-1)的值,从而利用edl(mod(Φ(n)))解出d。较早出现的因子分解攻击方法是试除法,即通过尝试小于n的所有素数,来找到因子。这种办法理论上是有效的,但对于大数n,由于要花费更多时间使其变得不可能完成。

由于因子分解的时间复杂性并未降到多项式时间,所以仍是一个计算上的难题。但是随着计算速度的提高,分解的速度会越来越快,2002年人们成功分解了RSA-158。

(二)选择密文攻击

选择密文攻击是通过骗取掌握私钥者的签名实现攻击。假设攻击者截获了密文y,想得到明文x,可以采用如下方法:选择一个随机数r,r

(三)共模攻击

共模攻击是由于在RSA体制的实现过程中,不同用户使用相同的模n、不同的指数值e和d所引起的。由于出现这种情况可能导致下列三个主要问题,所以会使得系统变得不再安全。

1.若相同的明文分送给两个不同的使用者,且此二使用者的公开密钥为互素,则此系统并不安全。

2.拥有一对的加/解密密钥就能因子分解n。

3.拥有一对加/解密密钥,能在不必分解n的情况下,求出另一对加解密密钥。

(四)小指数攻击

从计算速度角度考虑,公钥指数e越小加密速度越快。可是,当明文也很小时就会出现问题。比如我们取e=3,明文x小于N 的三次方,密文y=xe(modN)=x3(modN)=x3,这样直接对密文y开三次方就会得到明文x。

(五)定时攻击

定时攻击主要针对RSA核心运算是非常耗时间的模乘,只要能精确监视RSA的解密过程,获得解密时间,就可以估算出私有密钥d。模指数运算是通过一位一位来计算的,每次迭代执行一次模乘,并且如果当前位是l,则还需要进行一次模乘.对于有些密码,后一次模乘执行速度会极慢,攻击者就可以在观测数据解密时,根据执行时间判断当前位是1还是0。

六、RSA算法的防范

针对RSA算法的固有缺陷和对RSA算法的常见攻击方法,我们可以采取以下几种措施对其进行防范:

(一)为了保证安全性,在选取p、q时使用较大的素数,因式分解理论的研究现状表明:使用RSA密钥至少需要1024比特,才能有效的保证攻击者无法在短时间破解得到因子。

(二)通过设计新的素数生成方案,保证为每一用户生成不同的大素数,从而消除用户共模,避免系统遭受共模攻击。

(三)公钥e不可选得过小,使攻击者很难通过开方得到密文。

(四)通过常数取幂时间,随即延时,在加密前对数据做盲化处理盲化等方法对定时攻击进行防范。

七、结束语

RSA算法是第一个能同时用于加密和数字签名的算法,也是被研究得最为广泛的公钥算法,从1978年提出到现在的三十多年里经历了各种攻击的考验,被认为是目前最优秀的公钥方案之一。但是, RSA的安全性还需要不断的研究和改进,这就使得我们在应用时既要注意使用安全和环境安全,发挥RSA自身的优势,同时也要重视多种密码体制并用,不断研究和发现新的密码体制,来满足人们的通信安全保密需求。

参考文献:

[1]卢开澄.计算机密码学(第2版)[M].北京:清华大学出版社,1998

[2]洪帆,崔国华,付小青.信息安全概论[M].武汉:华中科技大学出版社,2005

[3]赵胜,孙永道.RSA公开密钥加密算法解析[J].硅谷,2008(11):56―57.

[4]Car]isle Adams,Steve Lloyd.公开密钥基础设施――概念､标准和设施[M].北京:人民邮电出版社,2001

[5]陈彦学.信息安全理论实务[M].北京:中国铁道出版社,2001

[6](美)Bruce Schneierm.网络信息安全的真相[M].北京:机械工业出版社,2001

[7]杨先伟.分析RSA的攻击与陷门[J].烟台职业学院学报,2007,3:84―87

[8]谢朝海.RSA密码攻击进展[J].信息网络安全,2007,1

[9]邹惠,余梅生,王建东.有效解决RSA共模攻击的素数生成方案[J].计算机工程与应用,2004,27:88-89

[10]董青,吴楠.整数质因子分解算法新进展与传统密码学面临的挑战[J].计算机科学,2008,8:71-91

作者简介:李世晓(1981-),男,汉族,河南巩义人,助理电气工程师,在读硕士研究生,主要研究方向:网络安全,主机取证。

基金项目:河南省科技攻关计划项目(092102310038)