（计算机科学与技术专业论文）rsa算法研究与实现.pdf

r s a 算法研究与实现 舢删删 y 17 5 7 6 ”鞘 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均己在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处， 本人签名：舡一 本人承担一切相关责任。 日期：翘坦! 至j 一 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 本人签名： 导师签名： 日期： 丝f 叟! 墨。! 一 日期： 趁f 芝。2 。 ：一。 - y l r _ r s ：算法研究j 实现 _ 一_ _ 一 r s a 算法研究与实现 r s a 算法研究与实现 摘要 随着网络技术在全球范围的迅速普及，i n t e m e t 已逐渐渗透到人 们的日常生活中，成为信息交流的重要手段。所有这一切在给我们带 来极大便利的同时，也向我们提出了新的挑战，并对网络安全提出了 更高的要求。因此有效保护网络信息传输的安全变得越来越重要。 本文研究的对象是r s a 算法。r s a 算法是一种公开密钥算法， 其加密密钥和算法本身都是公开的，解密密钥则归用户私人所有。从 r s a 的出现的那天起就因为安全强度高、使用方便而受到关注，并 得到广泛的应用。但是，近年来由于分解大整数的能力日益增强，为 保证r s a 算法的安全性，我们就不得不产生更大的大素数。但该算 法所采用的幂模计算会耗费太多的时间，一直是制约其广泛应用的瓶 颈。本文提出了一种有效算法，即在原算法的基础上，对有关实现环 节进行了一些改进，从而提高了产生大素数和r s a 算法的速度。 本文首先对r s a 算法原理进行了深入细致的研究，为改善算法 打下良好的理论基础；其次，分析了r s a 算法的安全性，讨论了针 对r s a 的各种攻击方法，以及如何选取参数以抵御这些攻击；再次， 本文研究了r s a 的各个相关子算法，在研究常用生成大素数算法的 基础上，提出了产生大素数的新算法并进行了性能分析；最后，对新 算法进行代码实现且通过一系列的测试表明，其速度确实有提高。 本论文所介绍的算法虽然对r s a 算法进行了某些局部的改进， 但还有许多不够完善的地方，有待进一步提高。 关键i 百- - tr s am o n t g o m e r y 乘模幂模大整数运算 r s a 算法研究与实现 i 己e s e a r c ha n di m p l e m e n t a t l 0 no fr s a a l g o r i t h m a bs t r a c t a l o n gw i t ht h ef a s tp o p u l a r i z a t i o no f n e t w o r ki nt h es e v e n s e a s ， i n t e r n e tg r a d u a l l yp e n e t r a t e si n t op e o p l e sd a i l yl i f e ，a n di tt u r n si n t ot h e i m p o r t a n tm e t h o d o fi n f o r m a t i o ne x c h a n g e a l lo ft h e s eb r i n gt h e e n o r m o u sc o n v e n i e n c et ot h ep e o p l e ，b u ti ta l s o p r o p o s e st h en e w c h a l l e n g e ，a n ds e t sah i g h e rr e q u e s tt ot h en e t w o r ks e c u r i t y t h e r e f o r e e f f e c t i v e l yp r o t e c t st h es e c u r i t ya b o u tt h ei n f o r m a t i o nw h i c ht r a n s m i ti n t h en e t w o r kh a sb e e nb e c a m em o r ea n dm o r ei m p o r t a n t t h i sa r t i c l es t u d i e st h eo b je c to fr s aa l g o r i t h m ，i tb e l o n g st ot h e a l g o r i t h mo fp u b l i ck e y i nt h i sa l g o r i t h mb o t he n c r y p t i o nk e ya n d a l g o r i t h mc a nb ep u b l i s h e d ，a n dt h ek e yo fd e c i p h e ri sp o s s e s s e db yt h e i n d i v i d u a lu s e r f r o mt h ed a yt h a tb o m e dt h er s aa l g o r i t h mb e c a u s ei t h a dt h ec a p a b i l i t yo fh i g h l ys e c u r i t ya n db eo p e r a t e de a s i l yt h a tr e c e i v e d t h es u p e r f l u i t ya t t e n t i o na n di tw a su s e dw i d e s p r e a d a tp r e s e n t ，r s a a l g o r i t h mi si n v o l v e di nm a n yc r y p t o g r a p h i cs y s t e m s b u ti nr e c e n ty e a r s ， a sar e s u l to ft h ea b i l i t yo fa n a l y z e st h eg r e a ti n t e g e rt ob es t r e n g t h e n e d d a yb yd a y , w eh a v et oi n c r e a s et h el e n g t ho fp r i m et og u a r a n t e et h er s a a l g o r i t h m ss e c u r i t y h o w e v e rt h et i m e c o n s u m i n gm o d u l a re x p o n e n t i a t i o n c o m p u t a t i o nw h i c hh a sa l w a y sb e e nt h eb o t t l e n e c k o fr s a ， r e s t r i c t si t sw i d e r a p p l i c a t i o n t h i sp a p e rp r e s e n t sa no p t i m i z e da l g o r i t h m ， w h i c he n h a n c e st h eo r i g i n a la l g o r i t h ma n di m p r o v e st h ee f f i c i e n c yo ft h e p r o c e s s i n go fm a k i n gb i gp r i m e ，r s aa l g o r i t h m a tf i r s to ft h i sa r t i c l eh a st h o r o u g hc a r e f u l l yr e s e a r c h e dt h ep r i n c i p l e o fr s a a l g o r i t h m ，t h a tb u i l d st h ef a v o r a b l er a t i o n a l ef o rt h ei m p r o v e m e n t o ft h e a l g o r i t h m ；n e x th a sa n a l y z e dt h er s aa l g o r i t h m ss e c u r i t y , d i s c u s s e dm a n ym e t h o d sa t t a c kt or s a ，a sw e l la sh o wc h o o s e st h er i g h t p a r a m e t e rt o r e s i s tt h e s ea t t a c k s ；o n c em o r e ，t h i sp a p e rs t u d i e st h e i i i 0 t p r i m ea n da n a l y z e st h ep e r f o r m a n c eo ft h en e wa l g o r i t h m ；a tl a s t ， i m p l e m e n tt h en e wa l g o r i t h ma n dt h r o u g has e r i e st e s td a t as h o wt h a ti t s s p e e dh a sb e e ne n h a n c e dt r u l y a l t h o u g ht h i sp a p e rm a k e ss o m ei m p r o v e m e n tt ot h er s a a l g o r i t h m ， t h e r ea r es t i l ls o m e a s p e c t st ob ei m p r o v e dl a t e r k e y w o r d ：r s a m o n t g o m e r y sm o d u l a rm u l t i p l i c a t i o nm o d u l a r e x p o n e n t i a t i o na l g o r i t h m m u l t i p l e p r e c i s i o ni n t e g e ra r i t h m e t i c 一 ， 0 i - r r s a 算法研究j 实现 目录 第一章绪论1 1 1 课题背景1 1 2 课题目的与意义1 1 3 课题主要工作3 1 4 论文章节安排4 第二章r s a 算法的数学知识5 2 1 素数与合数5 2 2 最大公约数5 2 3 模运算6 2 3 1 模运算的概念与性质6 2 3 2 模运算的运算规则6 2 4 模逆元7 2 5 费马定理和欧拉定理。7 2 6 单向函数8 第三章r s a 算法简介9 3 1r s a 算诌安9 3 2r s a 算法实例1 0 3 3r s a 算法的合理性分析1 0 3 4r s a 算法安全性分析1 l 3 4 1 分解模数攻击一l l 3 4 2 共模攻击1 2 3 4 3 小指数攻击1 3 3 4 4 选择密文攻击1 3 3 5r s a 参数的选择1 4 3 5 1p 和q 的选择1 4 3 5 2 公钥e 的选择15 3 5 3 私钥d 的选择16 3 5 4 模数n 的选择1 6 3 6r s a 算法的优缺点1 6 第四章r s a 实现分析：1 8 4 1 素数产生1 8 4 1 1 确定性素数判别方法。1 8 4 1 2 概率性素数判别方法1 9 4 1 3 常用产生素数的方法2 2 4 1 4 改进产生素数的方法。2 3 4 1 5 素数产生算法分析2 4 4 1 6 强素数的必要性2 5 4 2 密钥生成2 5 4 3 乘法算法2 6 4 3 1 传统乘法2 6 o r s a 算法研究与实现 4 3 2k a r a t s u b a 乘法2 7 4 3 3c o m b a 乘法2 8 4 4 乘模算法3 0 4 4 1b l a k l e y 乘模法3 0 4 4 2s m m 乘模法3l 4 4 3m o n t g o m e r y 乘模法3 2 4 4 3 1m o n t g o m e r y 模约减算法3 2 4 4 3 2c i o s 算法3 5 4 4 3 - 3f i p s 算法。3 6 4 4 3 4m o n t g o m e r y 平方模算法3 7 4 5 幂模算法4 0 4 5 1 二进制算法4 0 4 5 2b 进制算法4 l 4 5 3 滑动窗口法4 3 五章r s a 算法的改进实现4 5 5 1 大整数表示4 5 5 2 大数运算4 6 5 2 1 大数的比较4 6 5 2 2 大数的赋值4 7 5 2 3 大数的加减法。4 8 5 2 4 大数的乘除法和模运算5 0 5 2 5 大数的最大公约数5 2 5 2 6 大数的模逆元5 3 5 2 7 大数的幂模5 4 5 3 生成密钥函数5 6 5 4 加解密函数5 8 第六章测试与展望6 0 6 1 性能测试6 0 6 1 1 测试环境与工具6 0 6 1 2 测试结果6 0 6 2 未来展望6 2 参考文献6 3 致谢；：6 5 硕士期间发表的学术论文目录6 6 v i 一 、一， r s a 算法研究与实现 1 1 课题背景 第一章绪论 随着全球信息高速公路建设的兴起和通信网络的数字化、智能化、宽带化的 不断加快，特别是i n t e m e t 的高速发展，使人们的交流方式和以前大不一样，给 我们的生活带来了很大的方便。一方面，透过网络，我们可以传输文字、语音、 影像。甚至网络购物、付款、电子邮件、电子政务、电子自动转账支付系统等很 多日常事务，我们都可以在网络上完成。另一方面，越进步的技术的应用也越存 在潜在的危险，一旦这些信息被拦截，不但是个人信息泄露了，甚至可能还会涉 及到社会和国家的安全问题。信息化技术引起社会和经济的深刻变革，也为网络 信息安全开拓了新的空间。 世界主要工业化国家中每年因利用计算机犯罪所造成的经济损失是令人吃 惊的。据美国f b i 的调查报告，美国每年因利用计算机犯罪所造成的经济损失就 高达1 7 0 0 多亿美元，远远超过普通经济犯罪所造成的经济损失。据美国的一项 调查报告，有4 0 的被调查者承认在他们的机构中曾发生过利用计算机犯罪的事 件，在我国利用计算机犯罪的案例也在迅速上升【l l 。因此，在高科技的应用给我 们生活带来巨大方便的同时，也对信息的安全存储、安全处理和安全传输提出了 更高的要求。 伴随着电子商务、电子政务、金融电子化进程的不断深入，各种信息面临诸 多安全威胁，必须采取有效措施确保信息安全。信息安全问题已经被我国政府提 高到了国家发展战略的层次上了，并且也已经得到社会各个方面的广泛关注。解 决网络安全等信息安全问题成了当务之急，加密技术便是为了解决这个问题而出 现的一个技术，也是解决这个问题的有效手段。 1 2 课题目的与意义 密码学，一般理解就是保护信息的机密性，但这仅仅是密码学研究的一个方 面而已。对信息发送人的身份认证以及信息的完整性的检查是研究的另一个方 面。根据加密密钥和解密密钥是否相同或者本质上等同，即从其中一个容易推出 r s a 算 却升究与实现 另一个，可将现有的密码体制分为对称密码体制和非对称密码体制两种【2 】。如果 由其中一个很容易推出另个，或者加密密钥和解密密钥相同，则称为对称密码 体制( 也叫私钥密码体制，或者叫单密钥密码体制) ；如果在计算上不能容易的由 加密密钥推出解密密钥，则称非对称密码体制( 也叫公钥密码体制) 。 对称密码体制使用的加密算法比较简便、高效、密钥简短，所以加密速度都 比较快。但是在一个公开的环境、加密算法公开的情况下，信息的保密性依赖于 密钥。由于在对称密码体制中的加密密钥和解密密钥完全相同，使得在对称密码 体制中存在密钥的分发和管理问题。假设一个网络中n 个用户要安全通信，由于 加密密钥和解密密钥相同，为了保证任意两个人的通信都是安全的，则需要 n ( n - 1 ) 2 个密钥。由于当前的网络通信信道的不安全，给密钥的分发和管理带来 很大的不便【3 j 。 为了解决对称密码中存在的问题，d i f f i e 和h e l l m a n 于1 9 7 6 在他们的论文密 码学的新方向中f 4 】首次提出了公钥密码的观点，它使密码学发生了一场大的变 革。公钥密码不存在对称密码中的密钥的分发和管理问题，对于具有n 个用户的 网络，仅仅需要n 对密钥。公钥密码除了能用于数据加密外，还可以用于数字签 名。公钥密钥具有以下功能： ( 1 ) 保密性( c o n f i d e n t i a l i t y ) ：保证非授权人员不能非法获取信息，通过数据 加密来实现。 ( 2 ) 鉴别性( a u t h e n t i c a t i o n ) - 锞证发送发是属于所声称的实体，通过数字签 名来实现。 ( 3 ) 完整性( i n t e g r i t y ) ：保证信息的内容没有被非法篡改，非法者不可能用假 的消息代替合法的消息，通过数字签名实现。 ( 4 ) 不可抵赖性( n o n r e p u d i a t i o n ) ：发送者不可能事后否认发送过的消息，消 息的接收者可以向中立的第三方实体证实消息确实是由发送者发送的，通过数字 签名实现。 由于公钥密码在密钥分发，数据的完整性及数字签名等面的突出优点，它已 经成为了当今网络安全中最重要的解决方案。 在众多的公钥密码算法中，其中最典型的代表是r s a 算法。r s a 算法是1 9 7 8 年由r i v e s t 、s h a m i r 和a d l e m a n 在m i t 提出的【5 1 ，且被公认为是目前理论和实 际应用中最为成熟的和完善的公钥密码体制。 r s a 算法研制的最初理念与目标是努力是互联网安全可靠，旨在解决对称 密码的密钥分发的难题。实际应用结果不仅很好的解决了这个问题，而且还可以 利用r s a 来进行数字签名来保证信息的否定与抵赖，同时还利用数字签名较容 易发现攻击者对信息的非法篡改以保证信息的完整性。因此，r s a 算法特别适 r s a 算法研允j j 实现 合于现代保密通信的需要。到目前为止，r s a 算法已经在互联网的许多方面得 到了广泛的应用，包括在安全接口层( s s l ) 标斛刨( 该标准是网络浏览器建立安全 的互联网连接时用到的) 方面的应用和i n t e r n e t 所采用的电子邮件安全协议 p g p ( p r e t t yg o o dp r i v a c y ) 将r s a 作为传送会话密钥和数字签名的标准算法。此 外，r s a 算法还可以应用于智能i c 卡等产品。 r s a 的安全性是依赖于大整数的因子分解的困难性，为了满足信息安全强 度的需求，密钥的位数都比较多( 5 1 2 位甚至更高) ，导致幂模运算的运算量极大， 成为提高r s a 算法加解密速度的瓶颈。目前r s a 算法主要存在的问题： ( 1 ) 产生密钥非常麻烦，受制于当前素数产生技术的限制，因而难以做到一 次一密。 ( 2 ) 安全性，r s a 的安全性依赖于大数的因子分解，但并没有从理论上证明破 译r s a 的难度与大数分解难度等价，而且密码学界多数人士倾向于因子分解不 是n p c 问题。目前，人们已能分解1 4 0 多个十进制位的大素数，这就要求使用 更长的密钥。 ( 3 ) 速度太慢，由于r s a 的分组长度太大，为保证安全性，1 1 至少也要5 1 2 位以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且 随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。 为了做到一次一密，人们一直在寻找快速生成大素数的方法；为了提高r s a 算法的加解密速度，人们也一直在寻找、研究各种快速的幂模算法。r s a 算法应 用非常广泛，而且目前国际上流行的其他几种公钥密码体制也需要大素数和幂模 运算，因此，研究r s a 算法具有十分重要的意义。 1 3 课题主要工作 本课题需要解决的问题主要是在现有计算机的计算能力下能比较快速的生 成大素数以及加解密运算。 本课题具体的研究内容如下： 1 、学习了r s a 算法的基本原理。r s a 算法理论研究，包括r s a 算法的原 理及组成，对实现r s a 算法的各个主要子算法( 包括大素数的产生、素性测试、 密钥对生成等) 分别做了比较详细的研究，为算法的改善打下了理论基础。 2 、对r s a 算法的安全性进行了分析。讨论了针对r s a 算法的各种攻击方 法，以及怎么选择参数来避免这些攻击，保证r s a 算法的安全。 3 、深入研究了大素数的产生以及判别方法。将证明素数无穷性所用到的思 路和常用的产生大素数的方法结合起来，得到了快速的、高质量的产生大素数的 改进方法。 r s a 算法研究j 实现 4 、对m o n t g o m e r y 模约减理论进行了比较深入的分析，以及研究了各种利 m o n t g o m e r y 模约减算法及其改进算法实现乘模运算的各种算法。 4 论文章节安排 本论文章节安排如下： 第一章绪论介绍了课题背景和课题目的、意义等。 第二章r s a 算法的数学知识介绍了本课题需要用到或涉及到的一些数学 基本概念、性质、定理。 第三章r s a 算法简介简单介绍了r s a 算法原理，同时证明了r s a 算法的 正确性，以及r s a 在实际应用中存在的各种攻击方法与怎么选择 r s a 算法的参数来保证安全性。 第四章r s a 实现分析主要介绍了r s a 算法需要用到的各个子算法需要用 到的各种算法，以及对素数的产生方法进行了改进。 第五章r s a 算法的改进实现叙述了大整数运算的实现，素数的检测和生 成的算法以及r s a 算法的实现。 第六章测试和展望对实现的素数生成算法及加解密进行测试和对比，总结 本论文的不足之处以及需要继续进行的工作。 参考文献 致谢 硕士期间发表的论文列表 r s a 算法研究。j 实现 2 1 素数与合数 第二章r s a 算法的数学知识 对于某个p l ，它除了能表示为它自己和1 的乘积外，不能表示为任何其它 两个整数的乘积，则称p 为素数。素数具有许多特殊的性质，在数论中举足轻重。 以下为一小素数序列： 2 ，3 ，5 ，7 ，l l ，1 3 ，1 7 ，1 9 ，2 3 ，2 9 ，3 1 ，3 7 ，4 l ，4 3 ， 不是素数且大于l 的整数是合数。整数1 被称为基数，它既不是素数也不是 合数。类似地，0 和所有负整数既不是素数也不是合数。 例如：1 5 能表示成1 5 1 且能表示成5 * 3 ，所以1 5 是合数；1 3 只能表示成 1 3 1 ，所以1 3 是素数。 欧几里得和欧拉已经用反证法非常漂亮的证明了“素数有无穷多个 。 证明：( 反证法) 假设只有有限个素数，不妨设1 1 个。令r n 等于这1 1 个素数的 乘积加l ，则r n 除以这1 1 个素数中的任意一个都余1 ，所以m 也是素数。假设是 错误的。证毕。 若不计素数的排列顺序，任意大于1 的整数a 都能被因数分解为如下的素数 乘积的唯一形式，我们称为标准分解式： a = p p p p 式( 2 1 ) 其中p ，为素数，e l 为正整数。 例如：l1 0 1l = 7 x1 1 2 1 3 另外，如果p 表示所有素数的集合，则任一正整数都可以唯一的表示为如下 形式： 口= 兀p 其中口。o 式( 2 2 ) p 上式右边是所有素数p 的乘积，对于任一正整数a ，大多数的分量口，都是0 。 2 2 最大公约数 如果p 能整除a ，同时也能整除b ，则称p 是a 和b 的公约数。例如，1 2 和 1 8 的公约数有l ，2 ，3 ，6 。注意，l 是任意两个整数的公约数。两个数之间公 r s a 算法研究o j 实现 约数可能有很多个，但是所有这些公约数之间最大的那个就是这两个数的最大公 约数。 一般把两个不同时为0 的整数a 和b 的最大公约数记为g c d ( a ，b ) 。例如， g c d ( 1 2 ，18 ) = 6 ，g c d ( 9 ，7 ) = l ，g e d ( 3 2 ，2 4 ) = 8 。其中我们规定g c d ( o ，o ) = o 。g c d 具有 以下基本性质： g c d ( a ，b ) = g c d ( b ，a ) 式( 2 3 ) g c d ( a ，b ) = g c d ( 一a ，b )式( 2 - 4 ) g c d ( a ，k a ) = l a i 式( 2 5 ) g c d ( a ，b ) = g c d ( b ，a - b )式( 2 6 ) g c d ( a , o ) = l a l式( 2 - 7 ) g c d ( k a ，k b ) = l k l g c d ( a , b )式( 2 8 ) 2 3 模运算 2 3 1 模运算的概念与性质 已知一个整数n ，所有的整数都可以划分为能被n 整除的整数和不能被n 整 除的整数。对于不能被n 整除的整数，同时又可以根据它们除运算所得余数的不 同进行划分。同余类的划分就是基于余数的划分。 对于任意的整数a 和任意的正整数n ，存在唯一的整数q 和r ，满足0 = r n ， 并且a _ q n + r 。可以把这个式子转化为模运算的形式即为f am o dn 。 例如a = 2 0 ，n = 7 ，因为2 0 = - 7 * 2 + 6 ，所以q = 2 ，r = 6 。 转化为模运算后为：2 0m o d7 = 6 。 模运算有如下性质： ( 1 ) 若q l ( a b ) ，则a = 1 5 ( m o dq ) ( 2 ) ( am o d0 3 = 0m o dq ) 意味a - br o o dq ( 3 ) 对称性，a - b m o d q 等价于b - a m o dq ( 4 ) 传递性，若a 兰bm o dq 且b 三cm o dq ，则a - cm o dq 2 3 2 模运算的运算规则 根据模运算的定义，可以很容易的知道模运算的规则和四则运算有很多相似 r s a 算法研究0 实现 的规律： 结合率： 交换率： 分配率： 2 4 模逆元 ( a + b ) m o dn = ( am o dn + bm o dn ) m o d n ( a * b ) m o dn = ( ( am o dn ) 木( bm o dn ) ) m o dn a b m o dn ：( ar o o dn ) b m o dn ( ( a + b ) + c ) r o o dn = ( a + ( b + c ) ) m o dn ( ( a 幸b ) 宰c ) m o di l = ( a ( b c ) ) m o dn ( a + b ) m o dn = ( b + a ) m o dn ( a b ) m o d1 1 = ( b a ) m o dn 式( 2 9 ) 式( 2 1 0 ) 式( 2 - 1 1 ) 式( 2 1 2 ) 式( 2 1 3 ) 式( 2 1 4 ) 式( 2 - 1 5 ) ( ( a + b ) 事c ) m o d1 1 = ( ( a c ) + ( b c ) ) m o dn 式( 2 - 1 6 ) 在模运算领域，求解一个数a 的模1 1 逆元，可以转化为求解方程a x - = l ( m o dn ) 中x 的解的问题。 这个方程等价于寻找一组整数x 和y ，使得：a x = b n + ! 。 如果方程有解，则称x 是a 的模n 逆元，记为a 1 。如果a 和1 1 互素，则方 程必有唯一解。 例如，7 的模9 逆元是4 ，因为7 4 = 9 3 + 1 。2 的模4 却没有逆元。 2 5 费马定理和欧拉定理 费马定理和欧拉定理是数论中的非常重要的定理，在公钥密码学中有非常重 要的作用。r s a 算法的设计就是建立在欧拉定理的基础上的。 费马定理：如果p 是素数，且a 是不能被p 整除的正整数，那么： a p - 1 = 1 ( r o o dp )式( 2 1 7 ) 欧拉根据费马定理发现了更一般的性质，即欧拉定理。 在介绍欧拉定理前，先介绍欧拉函数的概念。 欧拉函数：如果( r ，n ) = l ，则将n 的同余类r m o dn 称为是模n 的既约同余类， 模n 的所有既约同余类的个数记作q ( n ) ，通常称为欧拉函数。通俗的讲，就是小 r s a 算法研究j 实现 于n 且与n 互素的正整数的个数就是欧拉函数。 欧拉函数具有的性质： ( 1 ) 如果n 为素数，则小于所有的n 的正整数都与n 互素，那么 q ( n ) - - n 一1式( 2 18 ) ( 2 ) 如果g c d ( p ，q ) = l ，那么 9 ( p 幸q ) = p ( p ) 幸叩( q )式( 2 19 ) ( 3 ) 如果整数1 1 因数分解为刀= p p p p ，其中p 。，p ：，p 。为互不相同 的素数，h e 。l ，那么 缈( 玎) ：厅( 1 一上) ( 1 一j 【- ) ( 1 一j l _ )式( 2 2 0 ) p 、p 2 p k 欧拉定理：对于任何互质的正整数a 和1 1 ，那么： n ) = l ( m o dn )式( 2 - 2 1 ) r s a 算法的设计就是来源于欧拉定理。欧拉定理在证明r s a 算法的合理性 时非常有用的。这将在合理性分析的章节中作详细介绍。 2 6 单向函数 同大多数公钥密码体制一样，r s a 的安全性取决于构造其加密算法的数学 函数的求逆困难性，我们称满足求逆困难性的数学函数为单向函数。单向函数在 密码学中起一个重要作用。它对公钥密码体制的构造是非常重要的。单向函数的 研究是公钥密码体制的一个重要课题，虽然很多很多函数被认为是或者被相信是 单向函数，但是目前还没有一个函数被证明是单向的。下面介绍一下单向函数的 概念： 定义：一个可逆函数f ：a b ，若它满足： ( 1 ) 对所有x e a ，易于计算f i x ) 。 ( 2 ) 对“几乎所有x a ”由f i x ) 求x “极为困难”，以至于实际上不可能做到， 则称f 为一单i - 句( o n e w a y ) 函数。 定义中的“极为困难”是对现有的计算资源和算法而言。m a s s e y 称此为视 在困难性( a p p a r e n td i f f i c u l t y ) ，相应函数称之为视在单向函数。以此来和本 质_ l ( e s s e n t i a l l y ) 的困难性相区分。 著名的r s a 算法是在1 9 7 8 年由r i v e s t ，s h a m i r 和a d l e m a n 三个人共同提出 的。r s a 是最具代表性的公钥密码算法，可能也是最知名和最古老的公钥密码 算法。由于算法完善( 既可以用于数据加密，又可用于数字签名) ，安全性良好， 易于理解和实现，r s a 已经成为了一种应用极为广泛的公钥密码算法。在广泛 的应用中，不仅它的实现技术日趋成熟，而且安全性也得到了认可。根据不同的 需求，人们基于r s a 算法开发了大量的加密方案与产品。 r s a 算法可以分为产生密钥的过程和加解密的过程： r s a 算法产生密钥的过程 ( 1 ) 系统产生两个大素数p ，q ( 保密k ( 2 ) 计算n = p q ( 公开) ，欧拉函数i p ( n ) ：( p 1 ) ( q - 1 ) ( 保密) ： ( 3 ) 随机选择满足g c d ( c 似n ) 产l 的e 作为公钥，加密密钥就是( e ，n ) ； ( 4 ) 计算满足e d = l ( m o d p ( n ) ) 的d 作为私钥，解密密钥即为( d 芦) 。 r s a 加解密过程 首先将明文分组并数字化，每个数字化分组明文的长度不大于l o gn 。然后 对每个明文分组m 依次进行加解密运算： ( 1 ) 加密运算：使用公钥e 和要加密的明文m 进行c = m e ( m o dn ) 运算即得密 文； ( 2 ) 解密运算：使用私钥d 和要解密的密文c 进行m = c d ( m o dn ) 运算即得明 文。 图3 - 1 能非常清晰的表示r s a 的实现过程。 r s a 算法研究与实现 3 2r s a 算法实例 图3 - 1r s a 算法实现过程 为了便于理解和掌握r s a 算法的基本算法思想，下面给出一个r s a 算法的 简单实例。 取p = 4 7 、q = 7 1 ，则n 印q = 3 3 3 7 ，i p ( n ) = ( p 1 ) ( q i ) = 3 2 2 0 ，随机选择加密密钥 c ，e 与t p ( n ) 互素，若取e = 7 9 ，则d = 7 9 _ ( m o dn ) = 1 0 1 9 。 假设要加密的明文是m = 6 8 8 2 3 2 6 8 7 9 6 6 6 6 8 3 ，首先，根据n 的大小将m 进行 分组，这里我们可以把明文m 分成六个组，即： m1 = 6 8 8m 2 = 2 3 2m 3 = 6 8 7m 4 = 9 6 6m 5 = 6 6 8m 6 = 0 0 3 接着分别对各个分组进行加密运算，第一个分组加密为： c 1 = 6 8 8 7 9 ( m o d3 3 3 7 ) = 1 5 7 0 类似的，对其余各个分组分别进行加密运算，得到如下密文： e = 1 5 7 02 7 5 62 0 9 12 2 7 62 4 2 31 5 8 解密时用私钥1 0 1 9 分别对明文进行解密运算，即： m l = 1 5 7 0 1 0 1 9 ( m o d3 3 3 7 ) = 6 8 8 对其余的密文用同样的计算方法就可以把密文恢复出来，即得到明文。 3 3r s a 算法的合理性分析 要证明r s a 加解密的合理性，即就是要证明对于明文m ，模数n ，加密密 r s a 算法研究与实现 钥e ，解密密钥d 有m 甜= n l ( m o dm 证明：如果( m ，n ) = l ，则根据欧拉定理有m 吼n ) = l ( m o dn ) 。根据算法中e ，d 的取法可知e * d = l + y * t p ( n ) ，则m 甜= m l + y * q 【n ) = m ( m o dn ) ； 如果( m ，n ) = p ，则( m ，q ) = l ，那么根据费马小定理有m q 一= l ( m o dq ) ，则 m ( p 1 q 1 ) = l ( m o dq ) ，即有m e d = m ( m o dq ) ，可得q l m ( m 。d l - 1 ) ，前面( m ，n ) = p 可得p l m ， 两式用整除的性质可得p q im ( m e d - l 1 ) ，所以有m 。d = m ( m o dn ) 。 如果( m ，n ) = q ，则( m ，p ) = l ，那么根据费马小定理有m p l = l ( m o dp ) ，则 m ( p - i x q 一1 ) = l ( m o dp ) ，即有m e d - - m ( m o dp ) ，可得p l m ( m 。d - i - 1 ) ，前面( m ，n 产q 可得q l m ， 两式用整除的性质可得p q im ( m e 1 1 ) ，所以有m 。d = m ( m o dn ) 。 3 4r s a 算法安全性分析 理论上，r s a 的安全性取决于大模数的因子分解的困难性。从严格的技术角 度上来说这是不正确的，在数学上至今还没有证明分解模数就是攻击r s a 的最佳 方法，也未能证明分解大整数就是n p 问题。事实的情况是，大整数因子分解问 题过去几百年来一直是令数学家头疼而又未能有效解决的世界性难题。人们设想 了一些非因子分解的途径来攻击r s a 算法，但这些方法都不比分解模数来得容 易。因此，严格地说，r s a 的安全性基于求解其单向函数的逆的困难性。r s a 单 向函数求逆的安全性没有真正的因子分解模数的安全性高，而且目前人们也无法 证明这两者是等价的。许多研究人员都试图改进r s a 算法使它的安全性等价于因 子分解模数。 r s a 算法从提出到现在已有3 0 多年的时间了，广泛的应用证明r s a 算法的 安全性是非常可靠的。但在许多情况下，如果密钥的设置和使用不当，会带来安 全问题。但是通过精心考虑r s a 体制实现的细节是可以避免这些安全缺陷的。 还没有发现针对r s a 的破坏性攻击。但是预言了以下几种基于弱明文、弱参 数选择或不当执行的攻击。 3 4 1 分解模数攻击 分解模