RSA算法的攻击与防范

计算机光盘软件与应用　工程技术　Ｃｏｍｐｕｔｅｒ　ＣＤ　Ｓｏｆｔｗａｒｅ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ　２０１０年第６期　ＲＳＡ算法的攻击与防范　李世晓　（中原３－学院，郑州４５０００７）　摘要：作为对典型的公钥密码算法，ＲＳＡ算法在信息安全领域得到了广泛的应用，但是其安全性却一直是学者们议　论的话题。本文首先介绍ＲＳＡ公钥加密算法的工作原理，对ＲＳＡ算法的缺陷以及对其所可能遭受的攻击进行分析，最后　讨论了针对ＲＳＡ算法攻击的防范措施。　关键词：公钥密码算法；ＲＳＡ算法；缺陷；攻击；防范　中图分类号：ＴＮ９１８．１　文献标识码：Ａ　文章编号：　Ａｔｔａｃｋｉｎｇ＆Ｐｒｅｖｅｎｔｉｏｎ　ｏｆ　ＲＳＡ　Ａｌｇｏｒｉｔｈｍｓ　Ｌｌ　Ｓｈｉｘｉａｏ　（Ｚｈｏｎｇｙｕａｎ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｔｅｃｈｎｏｌｏｇｙ，Ｚｈｅｎｇｚｈｏｕ　４５０００７，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ａｓ　ｔｈｅ　ｔｙｐｉｃａｌ　ｐｕｂｆｉｃ—ｋｅｙ　ａｌｇｏｒｉｔｈｍｓ，ＲＳＡ　ａｌｇｏｒｉｔｈｍｓ　ｈａｓ　ｂｅｅｎ　ｗｉｄｅｌｙ　ａｐｐｌｉｅｄ　ｉｎ　ｔｈｅ　ｆｉｅｌｄ　ｏｆ　ｉｎｆｏｒｍａｔｉｏｎ　ｓｅｃｕｒｉｔｙ，ｂｕｔ　ｉｔｓ　ｓｅｃｕｒｉｙ　ｔｈａｓ　ｂｅｅｎ　ａｍｏｎｇ　ｔｈｅ　ｓｃｈｏｌａｒｓ．Ｔｈｉｓ　ｐａｐｅｒ　ｆｉｒｓｔ　ｉｎｔｒｏｄｕｃｅｓ　ｔｈｅ　ｈｅｏｒｙ　ｔｏｆ　ｔｈｅ　ＲＳＡ　ｐｕｂｌｉｃ—ｋｅｙ　ｅｎｃｒｙｐｔｉｏｎ　ａｌｇｏｒｉｔｈｍ，ａｎｄ　ｔｈｅｎ，ａｎａｌｙｓｉｓ　ｔｈｅ　ｄｅｆｅｃｔｓ　ｏｆ　ｔｈｅ　ｐｏｓｓｉｂｌｅ　ａｔｔａｃｋｉｎｇ，ｉｎａｌｆｌｙ，ｄｉｓｃｕｓｓｅｓ　ｈｅ　ａｔｔｔａｃｋｉｎｇ　ｐｒｅｖｅｎｔｉｖｅ　ｍｅａｓｕｒｅｓ　ｆｏｒ　ＲＳＡ　ａｌｇｏｒｉｔｈｍｓ．　Ｋｅｙｗｏｒｄｓ：Ｐｕｂｌｉｃ－ｋｅｙ　ａｌｇｏｒｉｔｈｍｓ；ＲＳＡ　ａｌｇｏｒｉｔｈｍｓ；Ｄｅｆｅｃｔｓ；Ａｔｔａｃｋｉｎｇ；Ｐｒｅｖｅｎｔｉｏｎ　引言　计算机和互联网络的飞速发展使世界范围内信息的传递变　得越来越方便，同时，也带来了保障信息安全的新问题。而密码　学理论和技术的研究与应用，为保证信道中信息的安全传输奠定　了基础。　现代密码体制主要分为私钥密码体制和公钥密码体制，其中　私钥体制又称单钥体制或对称密码体制，其加密密钥和解密密钥　相同，密钥严格保密：公钥体制又称双钥体制或非对称密码体制，　其所用的加、解密钥不同，加密密钥公开，解密密钥不公开，适　用于开放的使用环境。１９７６年Ｄｉｆｆｉｅ和Ｈｅｌｌｍａｎ发表了《密码　学的新方向》一文，首次提｝±｛了公开密钥的密码学，即公钥密码　学，打破了长期使用单密钥体制的束缚。　目前比较流行的公钥密码算法主要有两种：一类是基于大素　数因子分解问题的，其中最典型的代表就是ＲＳＡ公钥密码算法；　１９７７年Ｒ．Ｌ．Ｒｉｖｅｒ，Ａ．Ｓｈａｍｉｒ和Ｌ．Ａｄｌｅｍａｎ３人其同提出了ＲＳＡ　算法，并很快成为了一种典型的公钥体制密码算法。另一类是基　于离散对数问题的，如ＥＬＧａｍａｌ公钥密码算法和椭圆曲线公钥密　码算法等。　二、ＲＳＡ算法简介　ＲＳＡ公钥加密算法是１９７８年由美国麻省理工学院（ＭＩＴ）的　Ｒｉｖｅｓｔ、Ｓｈａｍｉｒｈ和Ａｄｌｅｍａｎ共同提出的，它是目前最有影响力　的公钥加密算法。ＲＳＡ算法基于一个非常简单的数学难题：将两　个大素数相乘十分容易，但想要对其乘积进行因式分解却非常困　难，用很简单的形式实现了非常可靠的密码算法。ＲＳＡ的安全性　依赖于大数的因子分解，而大整数因子分解问题是数学上的著名　难题，至今没有有效的方法予以解决，因此能够确保ＲＳＡ算法的　安全性。　ＲＳＡ算法是目前最优秀的公钥方案之一，除加密功能外，公　钥系统还用于身份验证（Ａｕｔｈｅｎｔｉｃａｔｉｏｎ）或数字签名（Ｄｉｇｉｔａｌ　Ｓｉｇｎａｔｕｒｅ），因此它为公用网络上信息的加密和鉴别提供了一种　基本的方法。大多数使用公钥密码进行加密和数字签名的产品和　标准使用的都是ＲＳＡ算法。它通常是先生成一对ＲＳＡ密钥，其中　之一是保密密钥，由用户保存；另一个为公开密钥，可对外公开，　甚至可在网络服务器中注册，人们用公钥加密文档发送给个人，　个人就能够用私钥解密接受。　三、ＲｓＡ的算法描述　（～）ＲＳＡ算法密钥的产生　１．选两个大的素数Ｐ，ｑ（保密）：　２．计算ｎ＝ｐ＊ｑ（公开），欧拉函数　（ｎ）＝（ｐ一１），：（ｑ－１）：ｌ　３．随机选取ｅ作为公钥（加密密钥），满足ｇｃｄ（ｅ，　（ｎ））＝１（公　开）：　４．计算私钥ｄ（解密密钥），满足ｅｄ　ｌ（ｍｏｄ（中（ｎ））），即　一、５．销毁ｐ，ｑ及中（ｎ）：　６．得到所需的公开密钥和保密密钥。　公开密钥：ＥＫ＝｛ｅ，ｎ）：　保密密钥：ＤＫ＝（ｄ，ｎ）；　（二）ＲＳＡ算法加密和解密变换　首先将明文分块并数字化，每个数字化的明文的长度不大于　［　２ｎ］，然后对每个明文块ｍ（Ｏ≤ｍ≤ｎ）一次进行加解密变换：　１．加密变换：使用公钥ｅ和明文ｍ，获得密文ｃ－＝ｍｅ（－ｍｏｄｎ）　２．解密变换：使用私钥ｄ和密文Ｃ，获得明文ｍ　ｃｄ（ｍｏｄｎ）　四、ＲＳＡ算法的缺陷　ＲＳＡ密码算法作为公钥密码体制的代表被广泛地应用于现代　信息安全的各个领域，它的安全性的理论基础是大素数的因子分　解问题，此问题至今没有很好的算法，但是它本身却存在着一些　缺陷，综合来说，ＲＳＡ算法的不足或者缺陷主要包括：　（一）ＲＳＡ算法所要求的ｎ，Ｐ，ｑ都要求为很大的整数或素数，　实现时采用的是重复平方求模和相乘后求模的迭代方法来实现，　此方法在进行数据加密时耗费时间过长。　（二）ＲＳＡ算法中所用的Ｐ，ｑ如果太接近的话，密码分析者　可以通过计算　，然后在　附近搜索Ｐ，ｑ来分解ｎ。　（三）对于一个明文消息ｍ（Ｏ≤ｍ＜ｎ），如果将其加密成ｍ自　身，称ｍ为ＲＳＡ的不动点，也成ｍ为未隐匿的消息。对ＲＳＡ算法来讲　其不动点的个数为（１＋ｇｃｄ（（ｅ—１），（ｐ＋１）））　（１＋ｇｃｄ（（ｅ—１），　（ｑ－１））。由于ｅ—ｌ，ｐ－１，ｑ－１都是偶数，所以ＲＳＡ不动点的个数至　少为９个。　（四）同态性。由ＲＳＡ算法知对于一切Ｘ１，ｘ２∈Ｚｎ，有Ｅｋ（ｘｌ，　ｘ２）－＝Ｅｋ（－ｘ１）Ｅｋ（ｍｏｄｎ）是ＲＳＡ算法的一个缺陷，因为攻击者知道　Ｃｌ，Ｃ２的明文，就可以知道ＣＩＣ２（ｍｏｄｎ）对应明文ｍｌｍ２（ｍｏｄｎ）。　基于以上的缺陷，攻击者想来对ＲＳＡ算法进行攻击的一系列　攻击方法，其中最常用的攻击方法有因子分解攻击、选择密文攻　击、同模攻击、小指数／指数攻击、迭代循环攻击、定时攻击等。　五、常见的ＲＳＡ攻击方法　（一）因子分解攻击　易知，若ｎ＝ｐｑ被因子分解，则可以得到ｐ（ｎ）＝（ｐ－１）￥（ｑ－１）的　值，从而利用ｅｄ　ｌ（ｍｏｄ（　（ｎ）））解出ｄ。较早出现的因子分解　攻击方法是试除法，即通过尝试小于ｎ的所有素数，来找到因子。　这种办法理论上是有效的，但对于大数ｎ，由于要花费更多时间　使其变得不可能完成。　由于因子分解的时间复杂性并未降到多项式时间，所以仍是　个计算上的难题。但是随着计算速度的提高，分解的速度会越　来越快，２００２年人们成功分解了ＲＳＡ－１５８。　一（二）选择密文攻击　ｅｉｄ—ｌ（ｍｏｄ（中（ｎ））：　选择密文攻击是通过骗取掌握私钥者的签名实现攻击。假设　攻击者截获了密文ｙ，想得到明文Ｘ，可以采用如下方法：选择一　个随机数ｒ，ｒ＜ｎ，然后使用收件人的公钥加密ｒ，假设得到的中　计算机光盘软件与应用　２０１０年第６期　Ｃｏｍｐｕｔｅｒ　ＣＤ　Ｓｏｆｔｗａｒｅ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ　文。　工程技术　间结果为ｔ，显然ｔ＝ｒ　（ｍｏｄｎ）；然后着将中间结果ｔ与截获的密文　相乘，假设得Ｎｏ，０＝ｔ＊Ｙ（ｍｏｄｎ），想办法骗取收件人用私钥ｄ对０　进行签名，假设签名后的结果为ｕ，ｕ＝０（ｍｏｄｎ），得Ｎｕ后，攻击　者计算值ｆ＝ｒ一　（ｍｏｄｎ），结合ｕ就可以计算出明文ｘ。　（三）共模攻击　共模攻击是由于在ＲＳＡ体制的实现过程中，不同用户使用相　同的模ｎ、不同的指数值ｅ和ｄ所引起的。由于出现这种情况可能　导致下列三个主要问题，所以会使得系统变得不再安全。　１．若相同的明文分送给两个不同的使用者，且此二使用者的　公开密钥为互素，则此系统并不安全。　２．拥有一对的加／解密密钥就能因子分解ｎ。　３．拥有一对Ｎ／解密密钥，能在不必分解ｎ的情况下，求出另　一（四）通过常数取幂时间，随即延时，在加密前对数据做盲　化处理盲化等方法对定时攻击进行防范。　七、结束语　ＲＳＡ算法是第一个能同时用于加密和数字签名的算法，也是　被研究得最为广泛的公钥算法，从１９７８年提出到现在的三十多年　里经历了各种攻击的考验，被认为是目前最优秀的公钥方案之　但是，ＲＳＡ的安全性还需要不断的研究和改进，这就使得我　们在应用时既要注意使用安全和环境安全，发挥ＲＳＡ自身的优势，　同时也要重视多种密码体制并用，不断研究和发现新的密码体　制，来满足人们的通信安全保密需求。　一。参考文献：　对加解密密钥。　（四）小指数攻击　【ｌｉｔ开澄．ｆ计算机密码学（第２版）ｆＭ】．北京：清华大学出版社，１９９８　［２］洪帆，崔国华，付小青．信息安全概论【Ｍ】．武汉：华中科技大学出　版社．２００５　从计算速度角度考虑，公钥指数ｅ越ｄ，２ｎ密速度越快。可是，　当明文也很小时就会出现问题。比如我们取ｅ＝３，明文ｘｄ，于Ｎ的　三次方，密文ｙ＝Ｘ　（ｍｏｄＮ）＝ｘ　（ｍｏｄＮ）＝ｘ。，这样直接对密文ｙ开三次　方就会得到明文Ｘ。　（五）定时攻击　定时攻击主要针对ＲＳＡ核心运算是非常耗时间的模乘，只要　能精确监视ＲＳＡ的解密过程，获得解密时间，就可以估算出私有　密钥ｄ。模指数运算是通过一位一位来计算的，每次迭代执行一　次模乘，并且如果当前位是ｌ，则还需要进行一次模乘．对于有　些密码，后一次模乘执行速度会极慢，攻击者就可以在观测数据　解密时，根据执行时间判断当前位是１还是０。　六、ＲＳＡ算法的防范　针对ＲＳＡ算法的固有缺陷和对ＲＳＡ算法的常见攻击方法，我们　可以采取以下几种措施对其进行防范：　（一）为了保证安全性，在选取Ｐ、ｑ时使用较大的素数，因　式分解理论的研究现状表明：使用ＲＳＡ密钥至少需要１０２４比特，　才能有效的保证攻击者无法在短时间破解得到因子。　（二）通过设计新的素数生成方案，保证为每一用户生成不　同的大素数，从而消除用户共模，避免系统遭受共模攻击。　（－－）公钥ｅ不可选得过小，使攻击者很难通过开方得到密　【３】赵胜，孙永道．ＲＳＡ公开密钥加密算法解析　硅谷，２００８（１１）：５６　７　『４］ｃａｒ］ｉｓｌｅ　Ａｄａｍｓ，Ｓｔｅｖｅ　Ｌｌｏｙｄ．公开密钥基础设施——概念口标准　和设施ｆＭ１．北京：人民邮电出版社，２００１　【５】陈彦学．信息安全理论实务【Ｍ１．北京：中国铁道出版社，２００１　［６］（美）Ｂｒａｃｅ　Ｓｃｈｎｅｉｅｒｍ－网络信息安全的真相［Ｍ】．北京：机械工业出　版社．２００１　ｆ７】杨先伟．分析ＲＳＡ的攻击与陷门田．烟台职业学院学　报，２００７，３：８４—８７　［８】谢朝海．ＲＳＡ密码攻击进展卟信息网络安全，２００７，１　［９】邹惠，余梅生，王建东有效解决ＲＳＡ共模攻击的素数生成方案　Ｄ】计算机工程与应用，２００４，２７：８８—８９　［１Ｏ】董青，吴楠．整数质因子分解算法新进展与传统密码学面临的　挑战Ｕ１．计算机科学，２００８，８：７１—９１　作者简介　李世晓（１９８１一），男，汉族，河南巩义人，助理电气工程师，在　读硕士研究生，主要研究方向：网络安全，主机取证。　基金项目：河南省科技攻关计划项目（０ｇ２ｌＯ２３１００３８）　（上接第４５页）　（一）ｏｕｔ．ｔｒ文件　ＮＳ２生成的ｏｕｔ．ｔｒ仿真过程记录文件．完整记录了封包在模　拟网络中的传输过程。ｏｕｔ．ｔｒ的部分记录如下：　＋ａｗｋ程序中针对ｏｕｔ．ｔｒ仿真过程记录文件的配置部分如下。　ａｃｔｉｏｎ＝￥ｌ：　ｔｉｍｅ＝￥２：　ｆｒｏｍ＝Ｓ３：　ｔｏ＝￥４：　ｔｙｐｅ＝Ｓ５：　ｐｋｔｓｉｚｅ＝￥６：　ｆｌｏｗ　ｉｄ＝￥８：　ｓｒｃ＝￥９：　　‘　’０．１　ｌ　２　ｃｂｒ　１００００．１　ｌ　２　ｃｂｒ　１０００一一一一一一…一２　１．Ｏ　３．１　一　２　１．Ｏ　３．１　一２　１．Ｏ　３．１　一２　１．０　３．１　一２　１．Ｏ　３．１　＋—Ｏ．１Ｏ８　ｌ　２　ｃｂｒ　１０００一０．１Ｏ８　ｌ　２　ｃｂｒ　１０００一Ｒ　０．１１４　ｌ　２　ｃｂｒ　１０００…ｏｕｔ．ｔｒ文件格式如图２所示。　Ｅｖｅｎｔ　Ｔｉｍｅ　Ｆｒｏｍ　Ｔｏ　Ｐｈ　Ｐｌ（ｔ　Ｆｌａｇｓ　ｉｄ　Ｓｒｃ　Ｄｓｔ　Ｓｅｑ　Ｐｌ（ｔ　ｎｏｄｅ　ｎｏｄｅ　ｔｙｐｅ　ｓｉｚｅ　ａｄｄｒ　ａｄｄｒ　ｎｕｒｎ　ｉｄ　图２　ｄｓｔ＝￥１０：　ｓｅｑ—ｎｏ＝￥１１：　ｐａｃｋｅｔ＿ｉｄ＝￥１２：　四、结语　字段１表示封包事件发生的原因：字段２表示事件发生的时　间；字段３和４表示事件发生的地点；字段５表示封包的类型；　字段６是封包的大小；字段７是封包的标记标注；字段８表示封　包所属的数据流：字段９和１０表示封包的来源和目的端；字段　ｌ１表示封包序号；字段ｌ２表示封包的ｉｄ。　（二）ａｗｋ语言　对于ｏｕｔ．ｔｒ的分析通常是使用ａｗｋ语言，执行ａｗｋ时，它　会反复进行下列４个步骤。　自动从指定的数据文件中提取一笔数据。　自动更新相关的内建变量的值。　逐次执行程序中所有的“Ｐａｔｔｅｒｎ｛Ａｃｔｉｏｎ｝”指令。　当执行完程序中所有“Ｐａｔｔｅｒｎ｛Ａｃｔｉｏｎ｝”时，若数据文件　中还有未读取的数据，则反复执行步骤（１）至步骤（４）。　通常要分析网络性能指标包括有端点到端点的延迟，抖动　率，封包遗失率，吞吐量等。　本文提出使用网络模拟的方法对ＴＣＮ实时协议在异构网络上　运行这一问题进行研究，介绍了使用ＮＳ２仿真软件对ＴＣＮ实时协　议进行仿真研究的一般流程以及数据分析的方法。使用网络模拟　的方法可以自由灵活的配置出模拟网络环境，为工作人员在列车　上配置通信设备和协议功能时提供试验数据以供参考。　参考文献：　【１］Ｔｈｅ　Ｎｅｔｗｏｒｋ　Ｓｉｍｕｌａｔｏｒ—ｎｓ一２［ＥＢ／ＯＬ］．　［２］ＩＥＣ　６１３７５１—１９９９．Ｐａｒｔ　１：Ｔｒａｉｎ　Ｃｏｍｍｕｎｉｃａｔｉｏｎ　Ｎｅｔｗｏｒｋ　１９９９　【３】李常贤，谢步明．ＴＣＮ通信技术的自主研发Ⅱ】．机车电传　动，２００６．２　作者简介　欧阳敬原（１９８６一），男，江西人，华东交通大学在读硕士，研究　方向：电力电子及电力传动