2022年RSA公钥密码算法的攻击与防范 .pdf

《2022年RSA公钥密码算法的攻击与防范 .pdf》由会员分享，可在线阅读，更多相关《2022年RSA公钥密码算法的攻击与防范 .pdf（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、RSA算法的攻击与防范摘要：作为对典型的公钥密码算法，RSA算法在信息安全领域得到了广泛的应用，但是其安全性却一直是学者们议论的话题。本文首先介绍RSA公钥加密算法的工作原理，对 RSA算法的缺陷以及对其所可能遭受的攻击进行分析，最后讨论了针对RSA 算法攻击的防范措施。关键词：公钥密码算法RSA算法缺陷攻击防范Abstract:As the typical public-key algorithms,RSA algorithms has been widely applied in the field of information security,but its security has

2、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;Pre

3、vention 一、引言计算机和互联网络的飞速发展使世界范围内信息的传递变得越来越方便，同时，也带来了保障信息安全的新问题。而密码学理论和技术的研究与应用，为保证信道中信息的安全传输奠定了基础。现代密码体制主要分为私钥密码体制和公钥密码体制，其中私钥体制又称单钥体制或对称密码体制，其加密密钥和解密密钥相同，密钥严格保密；公钥体制又称双钥体制或非对称密码体制，其所用的加、解密钥不同，加密密钥公开，解密密钥不公开，适用于开放的使用环境。1976 年 Diffie 和 Hellman 发表了密码学的新方向一文，首次提出了公开密钥的密码学，即公钥密码学，打破了长期使用单密钥体制的束缚。目前比较流行的公

4、钥密码算法主要有两种：一类是基于大素数因子分解问题的，其中最典型的代表就是RSA公钥密码算法；1977 年 R.L.River，A.Shamir 和 L.Adleman3 人共同提出了RSA算法，并很快成为了一种典型的公钥体制密码算法。另一类是基于离散对数问题的，如 ELGamal公钥密码算法和椭圆曲线公钥密码算法等。二、RSA算法简介RSA公钥加密算法是1978 年由美国麻省理工学院（MIT）的 Rivest、Shamirh 和 Adleman共同提出的，它是目前最有影响力的公钥加密算法。RSA算法基于一个非常简单的数学难题：将两个大素数相乘十分容易，但想要对其乘积进行因式分解却非常困难，用

5、很简单的形式实现了非常可靠的密码算法。RSA的安全性依赖于大数的因子分解，而大整数因子分解问题是数学上的著名难题，至今没有有效的方法予以解决，因此能够确保RSA算法的安全性。RSA 算法是目前最优秀的公钥方案之一，除加密功能外，公钥系统还用于身份验证（Authentication）或数字签名（Digital Signature），因此它为公用网络上信息的加密和鉴别提供了一种基本的方法。大多数使用公名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 4 页 -钥密码进行加密和数字签名的产品和标准使用的都是RSA算法。它通常是先生成一对RSAl 密钥，其中之一是保密密钥，由用户保存；另一

6、个为公开密钥，可对外公开，甚至可在网络服务器中注册，人们用公钥加密文档发送给个人，个人就能够用私钥解密接受。三、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算法加密和解密变换首先将明文分块并数字化，每个数字

7、化的明文的长度不大于 2n，然后对每个明文块m（0mn）一次进行加解密变换：1.加密变换：使用公钥e 和明文 m，获得密文cme（modn）2.解密变换：使用私钥d 和密文 c，获得明文mcd（modn）四、RSA算法的缺陷RSA密码算法作为公钥密码体制的代表被广泛地应用于现代信息安全的各个领域，它的安全性的理论基础是大素数的因子分解问题，此问题至今没有很好的算法，但是它本身却存在着一些缺陷，综合来说，RSA算法的不足或者缺陷主要包括：（一）RSA算法所要求的n，p，q 都要求为很大的整数或素数，实现时采用的是重复平方求模和相乘后求模的迭代方法来实现，此方法在进行数据加密时耗费时间过长。（二）

8、RSA算法中所用的p，q 如果太接近的话，密码分析者可以通过计算，然后在附近搜索 p，q 来分解 n。（三）对于一个明文消息m（0mn),如果将其加密成m 自身，称m 为 RSA的不动点，也 成m为 未隐匿的消息。对RSA 算法 来讲其不动点的个数为（1+gcd(e-1)，(p+1)*(1+gcd(e-1)，(q-1)。由于 e-1，p-1，q-1 都是偶数，所以RSA不动点的个数至少为9个。（四）同态性。由RSA算法知对于一切x1，x2Zn，有 Ek（x1，x2）Ek(x1)Ek(modn)是 RSA算法的一个缺陷，因为攻击者知道C1,C2的明文，就可以知道C1C2(modn)对应明文m1m

9、2（modn）。基于以上的缺陷，攻击者想来对RSA 算法进行攻击的一系列攻击方法，其中最常用的攻击方法有因子分解攻击、选择密文攻击、同模攻击、小指数/指数攻击、迭代循环攻击、定时攻击等。五、常见的RSA攻击方法（一）因子分解攻击易知，若n=pq 被因子分解，则可以得到p(n)=(p-1)*(q-1)的值，从而利用edl(mod(（n）)解出 d。较早出现的因子分解攻击方法是试除法，即通过尝试小于n 的所有素数，来找到因子。这种办法理论上是有效的，但对于大数n，由于要花费更多时间使其变得不可能完成。由于因子分解的时间复杂性并未降到多项式时间，所以仍是一个计算上的难题。但是随着计算速度的提高，分解

10、的速度会越来越快，2002 年人们成功分解了RSA-158。（二）选择密文攻击名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 4 页 -选择密文攻击是通过骗取掌握私钥者的签名实现攻击。假设攻击者截获了密文y，想得到明文 x，可以采用如下方法：选择一个随机数r，rn，然后使用收件人的公钥加密r，假设得到的中间结果为t，显然t=re(modn)；然后着将中间结果t 与截获的密文相乘，假设得到 O，O=t*Y(modn)，想办法骗取收件人用私钥d 对 O 进行签名，假设签名后的结果为u，u=O(modn)，得到 u 后，攻击者计算值f=r-1(modn)，结合 u 就可以计算出明文X。

11、（三）共模攻击共模攻击是由于在RSA体制的实现过程中，不同用户使用相同的模n、不同的指数值e和 d 所引起的。由于出现这种情况可能导致下列三个主要问题，所以会使得系统变得不再安全。1.若相同的明文分送给两个不同的使用者，且此二使用者的公开密钥为互素，则此系统并不安全。2.拥有一对的加/解密密钥就能因子分解n。3.拥有一对加/解密密钥，能在不必分解n 的情况下，求出另一对加解密密钥。（四）小指数攻击从计算速度角度考虑，公钥指数 e 越小加密速度越快。可是，当明文也很小时就会出现问题。比如我们取e=3，明文 x 小于 N 的三次方，密文y=xe(modN)=x3(modN)=x3，这样直接对密文y

12、 开三次方就会得到明文x。（五）定时攻击定时攻击主要针对RSA核心运算是非常耗时间的模乘，只要能精确监视RSA的解密过程，获得解密时间，就可以估算出私有密钥d。模指数运算是通过一位一位来计算的，每次迭代执行一次模乘，并且如果当前位是l，则还需要进行一次模乘对于有些密码，后一次模乘执行速度会极慢，攻击者就可以在观测数据解密时，根据执行时间判断当前位是1 还是0。六、RSA算法的防范针对 RSA 算法的固有缺陷和对RSA算法的常见攻击方法，我们可以采取以下几种措施对其进行防范：（一）为了保证安全性，在选取p、q 时使用较大的素数，因式分解理论的研究现状表明：使用 RSA密钥至少需要1024 比特，

13、才能有效的保证攻击者无法在短时间破解得到因子。（二）通过设计新的素数生成方案，保证为每一用户生成不同的大素数，从而消除用户共模，避免系统遭受共模攻击。（三）公钥e 不可选得过小，使攻击者很难通过开方得到密文。（四）通过常数取幂时间，随即延时，在加密前对数据做盲化处理盲化等方法对定时攻击进行防范。七、结束语RSA算法是第一个能同时用于加密和数字签名的算法，也是被研究得最为广泛的公钥算法，从 1978 年提出到现在的三十多年里经历了各种攻击的考验，被认为是目前最优秀的公钥方案之一。但是，假RSA的安全性还需要不断的研究和改进，这就使得我们在应用时既要注意使用安全和环境安全，发挥RSA 自身的优势，

14、同时也要重视多种密码体制并用，不断研究和发现新的密码体制，来满足人们的通信安全保密需求。参考文献：1卢开澄.计算机密码学（第2 版）M.北京:清华大学出版社,1998 2洪帆,崔国华,付小青.信息安全概论 M.武汉:华中科技大学出版社,2005 3赵胜,孙永道.RSA公开密钥加密算法解析J.硅谷,2008(11):5657.名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 4 页 -4Carisle Adams,Steve Lloyd.公开密钥基础设施概念?标准和设施 M.北京:人民邮电出版社,2001 5陈彦学.信息安全理论实务M.北京:中国铁道出版社,2001 6(美)Bruce Schneierm.网络信息安全的真相M.北京:机械工业出版社,2001 7杨先伟.分析 RSA的攻击与陷门 J.烟台职业学院学报,2007,3:8487 8谢朝海.RSA密码攻击进展 J.信息网络安全,2007,1 9邹惠,余梅生,王建东.有效解决RSA 共模攻击的素数生成方案J.计算机工程与应用,2004,27:88-89 10 董青,吴楠.整数质因子分解算法新进展与传统密码学面临的挑战J.计算机科学,2008,8:71-91 名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 4 页 -