（计算机应用技术专业论文）rsa加密算法的研究与实现.pdf

摘要 公钥密码学由于它在数字签名、认证和密钥管理上的优越性，在 现代保密体系中占据十分重要的地位，应用十分广泛，其中r s a 是目 前公认的在理论和实际应用中最为成熟和完善的一种公钥密码体制。 它不仅可以进行加密，还可以用来进行数字签名和身份验证，是公钥 密码体制的代表。 r s a j i 密体制主要基于数论当中的欧拉定理进行一系列的数学变 换，以实现加解密和身份验证。在变换过程中，r s a 必需经历大数的 模幂乘运算。由于模幂乘运算存在耗时过多的缺陷，导致r s a 的效率 受到一定程度的影响，制约其更进一步发展。 论文以提高r s a 运算中的模幂乘效率为目标，自r s a 的数论基础 展开研究，分析t r s a j i 解密变换、身份验证的基本原理，结合当前 针对r s a 算法的攻击手段以及对策，归纳出提高r s a 算法安全性应该 考虑的几个因素；对基于乘同余特性的s m m 算法、指数2 k 进制化算法 等r s a 当前主要实现算法进行了详细描述，结合各算法在模幂乘环节 的优点，提出了基于现有几种算法的一种新的组合算法，通过实验的 方式对新算法进行了测试，通过比对，得出新算法相比较原有算法在 效率上有一定程度提高的结论。 论文设计了一个基于组合算法的加解密软件，并针对邮件收发提 出了一个基于单位局域网的r s a 应用方案。 关键词r s a ，模幂乘，算法研究，改进实现 a b s t r a c t t h ea d v a n t a g e so ft h ep u b l i ck e yc r y p t o g r a p h ya r ed e m o n s t r a t e db y d i g i t a ls i g n a t u r e ，a u t h e n t i c a t i o na n dk e ym a n a g e m e n t t h ep u b l i ck e y c r y p t o g r a p h yp l a y sa ni m p o r t a n tr o l ei nm o d e mc r y p t o g r a p h ys y s t e ma n d h a sb e e nw i d e l yu s e d a m o n gt h e m ，r s ai st h em o s tm a t u r ea n dp e r f e c t p u b l i ck e yc r y p t o g r a p h ys y s t e mi nt h e o r e t i c a la n dp r a c t i c a la p p l i c a t i o n ， w h i c hi sw i d e l ya c c e p t e da tp r e s e n t i tn o to n l yc a nb ee n c r y p t e db u ta l s o c a nb eu s e df o rd i g i t a l s i g n a t u r ea n di d e n t i t y a u t h e n t i c a t i o na n di t p r e s e n t st h ep u b l i ck e yc r y p t o g r a p h ys y s t e m b a s e do nt h ee u l e rt h e o r e m ，t h er s a 印s y s t e mp e r f o r m sas e r i e so f m a t h e m a t i c a lt r a n s f e i r m a t i o nt or e a l i z e 印a n dd pa n di d e n t i t y a u t h e n t i c a t i o n d u r i n gt h ep e r i o do ft r a n s f o r m i n g ，r s as h o u l dp e r f o r m t h em o d u l a re x p o n e n t i a t i o nm u l t i p l i c a t i o na l g o r i t h mo fl a r g en u m b e r b u t t h em o d u l a r e x p o n e n t i a t i o nm u l t i p l i c a t i o na l g o r i t h m i st o o t i m e - c o n s u m i n ga n dt h ee f f i c i e n c yo fr s ah a sb e e na f f e c t e do nc e r t a i n l e v e la n ds u s t a i n si t sd e v e l o p m e n t t h i st h e s i sa i m sa tr a i s i n ge f f i c i e n c yo fm o d u l a re x p o n e n t i a t i o n m u l t i p l i c a t i o nd u r i n gt h ea l g o r i t h mo fr s aa n ds t a r t s r e s e a r c ho nt h e b a s i so fa r i t h m e t i c a lt h e o r yo fr s a i ta n a l y z e st h ek e y s t o n eo fe pa n dd p t r a n s f o r m a t i o na n di d e n t i t ya u t h e n t i c a t i o no fr s a c o m b i n gw i t hc u r r e n t a t t a c k i n gm e a n sa n dc o u n t e r m e a s u r e sa i m i n g a tr s aa l g o r i t h m ，i t c o n c l u d e ss e v e r a lf a c t o r sw h i c hs h o u l db ec o n s i d e r e dt oe n h a n c et h e s a f e t y t h i s t h e s i sd e s c r i b e ss m ma l g o r i t h ma n db i n a r yi nd e t a i l c o m b i n gw i t ht h ea d v a n t a g e so f v a r i e sa l g o r i t h m ，i tp u t sf o r w a r dan e w a l g o r i t h mb a s i n go nt h ec u r r e n ts e v e r a la l g o r i t h m sa n dt e s t s t h ev a r i e d n e wa l g o r i t h mt h r o u g he x p e r i m e n t t h r o u g hc o m p a r i n g ，i td r a w s a c o n c l u s i o nt h a tt h ee f f i c i e n c yo fn e wa l g o r i t h mi sb e t t e rt h a nt h eo l do n e b a s e do nt h ea s s e m b l e da l g o r i t h m ，t h i st h e s i sd e s i g n sas o f tw a r eo f 印a n dd pa n db r i n g sf o r w a r da nr s aa p p l i c a t i o ns c h e m ea i m i n ga te m a i l r e c e i v i n ga n dd i s p a t c h i n g ，w h i c hi sb a s e du p o nu n i tl a n k e yw o r d s r s a ，m o d u l a re x p o n e n t i a t i o nm u l t i p l i c a t i o n ， a l g o r i t h mr e s e a r c h ，i m p r o v i n gr e a l i z a t i o n 1 1 1 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得中南 大学或其他单位的学位或证书而使用过的材料。与我共同工作的同志对本 研究所作的贡献均己在论文中作了明确的说明。 储签磋邕 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校有权 保留学位论文并根据国家或湖南省有关部门规定送交学位论文，允许学位 论文被查阅和借阅；学校可以公布学位论文的全部或部分内容，可以采用 复印、缩印或其它手段保存学位论文。同时授权中国科学技术信息研究所 将本学位论文收录到中国学位论文全文数据库，并通过网络向社会公 众提供信息服务。 储签珑量新签名避吼年上j q _ l _ e t 硕士学位论文第一章 第一章绪论 随着计算机和电子通讯技术，包括因特网的迅猛发展，金融电子化的步伐大 大加快，这种电子化、数字化的趋势已经波及社会生活的几乎所有的方面。人与 人之间的许多交往活动，包括商业贸易、金融财务和其他经济活动中，不少已以 数字化信息的方式在网上流动着，电子商业、电子银行和电子货币的研究、实施 和标准化正在紧锣密鼓地进行中。许多传统上基于纸面的，常常需要签名盖章的 重要凭证，诸如存单、支票、股票、公函、合同、租约、遗嘱、选票、法律文书 等等，已陆续转化为数字电子媒体的形式出现。这种转化方兴未艾，前景辉煌， 虽然未必会有百分之百的转化，但对社会、经济、商业、金融乃至个人生活各方 面的影响将是深刻的。 1 1 问题的提出 信息从基于纸面转化为基于数字电子媒体的形式后，在生成、传输、保存、 验证和鉴定等多方面出现了新的技术需求、问题和困难。无疑，其中最重要的是 安全问题：怎样才能确保原始信息不被窃取、窃听，不被伪造、篡改，怎样才能 确认信息发送者的真实性，怎样才能保证信息发送者无法抵赖等，同时，我们还 必须考虑到那些机密的、甚至价值连城的重要信息常常需要在公开的网络上传 送。“公开”和“机密”虽有其水火不相容的一面，在需要的场合，它们还是可 以协调共存，相互补充的。“公开密钥密码系统( p u b l i c k e yc r y p t o s y s t e m ， 或称“公开密钥密码体制”) 的巧妙方法比较成功地解决了上述问题，并已在业 界得到了广泛的应用。 从本质上看，网络安全就是网络上的信息安全；从广义上来说，凡是涉及到 网络信息的保密性、完整性、可用性、可靠性和不可抵赖性的相关技术和理论都 是网络安全的研究领域。信息安全的技术主要包括监控、扫描、检测、加密、认 证、防攻击、防病毒以及审计等几个方面，其中加密技术是信息安全的核心技术。 通常保障网络信息安全的方法有两大类：一是以防火墙技术为代表的被动防 卫型，二是建立在数据加密，用户授权确认机制上的开放型网络安全保障技术。 “防火墙 是一种形象的说法，其实它是种由计算机硬件和软件的组合， 使互联网与内部网之间建立起一个安全网关，而保护内部网免受非法用户的侵 入，即一个把互联网与内部网隔开的屏障。使用防火墙是保障网络安全的第一步， 选择一款合适的防火墙，是保护信息安全不可或缺的一道屏障。 数据加密技术，或称为密码技术，是与防火墙配合使用的安全技术，是为提 硕士学位论文 第一章绪论 高信息系统及数据的安全性和保密性，防止数据被外部破析所采用的主要技术手 段之一。按作用不同，数据加密技术主要分为数据传输、数据存储、数据完整性 的鉴别以及密钥管理技术四种。数据传输加密技术目的是对传输中的数据流加 密，常用的方针有线路加密和端端加密两种；数据存储加密技术目的是防 止在存储环节上的数据失密，可分为密文存储和存取控制两种：数据完整性鉴别 技术目的是对介入信息的传送、存取、处理的人的身份和相关数据内容进行验证， 达到保密的要求，一般包括口令、密钥、身份、数据等项的鉴别；密钥的管理技 术包括密钥的产生、分配保存、更换与销毁等各环节上的保密措施。 由于以数据加密和用户认证为基础的开放性安全保证技术对网络服务影响 较小，它的特征是利用现代的数据加密技术来保护网络系统包括用户信息在内的 所有数据流，在网络服务的可用性和信息的完整性方面不需要特殊的网络拓扑结 构支持，其实施代价主要体现在软件的开发和系统运行维护方面。因此，利用这 一途径来解决用户信息的安全问题，就可有效地抵挡病毒、黑客攻击及其它各种 安全威胁。可见，信息安全的基础就是数据加密，而其关键和核心技术就是设计 高强度的加密算法，它由加密和解密两部分组成。所以选择一种抗攻击力强、计 算效率高、密钥长度可变且管理方便的密码算法，用以保护信息的安全是十分必 要的。 r s a 算法是第一个既能用于数据加密也能用于数字签名的算法，它易于理解 和操作。同时r s a 也是被研究得最广泛的公钥算法，从提出到现在已有二十年， 经历了各种攻击的考验，逐渐为人们接受，在各种安全或认证领域，均起着安全 核心的作用，被普遍认为是目前最优秀的公钥方案之一。但由于r s a 算法核心进 行的都是大数计算，使得相同条件下r s a 最快的情况也比d e s 慢上1 0 0 倍，无论是 软件还是硬件实现，速度一直是r s a 的缺陷。因此，对提高r s a 效率的研究是一个 非常有意义的课题。 随着网络的不断扩大，网络安全更加会成为人们的一个焦点，同时也成为是 否能进一步投入到更深更广领域的一个基石。网络的安全是一个动态的概念，世 界上没有绝对安全的网络，只有相对安全的网络。而相对安全环境的取得是可以 通过不断地完善系统程序、增强防御保密技术来实现的。 1 2 密码学概述 密码学的历史极为久远，其起源可以追溯到远古时代，人类有记载的通信密 码始于公元前4 0 0 年1 1 。密码学的一些常用基本概念有【2 - s 】：密码学是研究信息系 统安全保密的科学，它包括两个分支，密码编码学和密码分析学；密码编码学是 对信息进行编码实现信息隐蔽的技术和科学；密码分析学是研究分析破译密码的 2 硕士学位论文第一章绪论 技术和科学；明文是指发送方想要发给接受方的消息；密文是指明文被加密后的 消息；加密是将明文变换为密文的过程；解密是将密文恢复为明文的过程。 密码是实现秘密通讯的主要手段，是隐蔽语言、文字、图像的特种符号。凡 是用特种符号按照通讯双方约定的方法把电文的原形隐蔽起来，不为第三者所识 别的通讯方式称为密码通讯。在计算机通讯中，采用密码技术将信息隐蔽起来， 再将隐蔽后的信息传输出去，使信息在传输过程中即使被窃取或截获，窃取者也 不能了解信息的内容，从而保证信息传输的安全。 近三十年来，密码学已成为一门热门的学科，在理论和方法上都有了巨大的 发展。1 9 4 9 年香农( s h a n n o n ) 发表“保密系统的信息理论 6 1 ；1 9 7 5 年3 月公 开发表d e s 算法( d i g i t a le ps t a n d a r d ，数据加密标准) 1 7 ，1 9 7 7 年美国国家标 准局宣布d e s 可用于非国家保密机关，正式作为商用加密算法的标准；1 9 7 6 年 由d i f f i e 和h e l l m a n 在所谓“密码学的新方向【s l 文中提出了公钥密码体制的 思想，在此基础上1 9 7 8 年由r l r i v e s t ，a s h a m i r 和l a d l e i t l 觚【9 】提出并实现了 r s a 公钥密码系统，该系统己成为事实上的工业标准；随后d e s 也改进为3 d e s ； 19 8 5 年由n k o b l i z 和v m i l l e r 把椭圆曲线密码( e l l i p t i cc u r v e sc r y p t o g r a p h y ，简 称e c c ) 理论应用到公钥密码系统中提出e c c 算法；2 0 0 0 年1 0 月2 日美国国 家标准与技术研究所确定用比利时密码学家j o a nd a e m e n ，v i n c e n tr i j m e n 发明 的r i j n d a e l 算法替代d e s 算法，称为a e s 算法【l o l ；1 9 9 0 年我国学者来学嘉与瑞 士密码学家j a m e sm a s s e y 提出了著名的i d e a 算法。同时还有许多新的加密方 法，如用于电子邮件加密的p e m ( p r i v a c ye n h a n c e dm a i l ) 和p g p ( p r e t t yg o o d p r i v a c y ) ；在网络系统中得到应用的加密算法还有美国国家标准局提出的d s a 算 法( d i g i t a ls i g n a t u r ea l g o r i t h m ) 和标准局建议的可靠不可逆加密标准( s h s s u r e h a s hs t a n d a r d ) 以及数字签名中使用的s h a 1 等算法。值得一提的是，我国密 码学家陶仁骥发明的基于有限自动机的公钥密码算法( 1 9 8 5 年首次提出，1 9 9 5 年被攻破) 以及国内由此开展的研究工作在国际上是非常有研究价值的【3 】。 根据加密密钥和解密密钥是否相同或者本质上等同，可将现有的加密体制分 为两种。一种是单钥加密体制( 也叫对称加密密码体制) ，即从其中一个容易推 出另一个，其典型代表是美国的数据加密标准d e s ( d a t ae ps t a n d a r d ) ；另一种 是公钥密码体制( 也叫非对称加密密码体制) ，其典型代表是r s a 密码体制p j ， 其他比较重要的还有m c e l i e c e 算法【l l 】、m e r k e h e l l m a n 背包算法【1 2 】、椭圆曲线 密码算法【2 】和e 1 g a m a l 算法【1 3 】等。 1 3 国内外研究现状与水平 r s a 公钥密码体制是在1 9 7 8 年由r l r i v e s t ，a s h a m i r 和l a d l e m a n 三人 硕士学位论文 第一章绪论 在文章实现数字签名和公钥密码体制的一种方法中共同提出的，是最具代表 性的公钥密码体制。由于算法完善( 既可用于数据加密，又可用于数字签名) ， 安全性良好( 据传山东大学信息科学与工程学院的季凯和他的破解团队成员刘强 等人宣布己找到可有效破解r s a 的方法，并公布了算法，但未经证实) ，易于实 现和理解，r s a 已成为一种应用极广的公钥密码体制，它的提出真正使得互不 相识的通信双方在一个不安全的信道上进行安全通信最终成为可能。在广泛的应 用中，不仅它的实现技术日趋成熟，而且安全性也逐渐得到事实的证明，因此人 们对r s a 十分重视。但在实现过程中，由于算法中包含有大数的乘方运算，在 计算机上运算时，会耗费大量的时间，严重影响了r s a 的加密效率，制约了它 的应用，因此人们对其从不同方面进行了改进，并形成了以下实现算法： 传统实现算法。由r i v e s t 等人在r s a 体制建立时提出，是把乘方后求模的 计算改为在边乘方边求模的计算，以减小中间结果的数值，尽量避免大数的乘方 计算。该算法在一定程度上改善了r s a 的效率。 s m m 算法。是利用“乘同余对称特性”来减少加密和解密运算中乘法和求 模运算量的一种改进算法。其本质是减小求幂运算中的基数的大小，但并没有考 虑指数的情况，故只是在一定的程度上改进了原算法的效率。 指数2 。进制化算法。是通过缩短指数的长度来减少迭代的次数，从而提高 计算效率。但是，在求幂运算的过程中，基数的大小也是影响运算速度的重要因 素，而该算法只是减小了指数的长度。 r s r 算法。是将r s a 传统算法中的求模运算变成一系列2 的乘幂的余数和 运算，可以在一定程度上提高计算速度，但是由于在实际实现时，r s r 算法要 进行对大整数进行字节、比特的不断转换，不适合与其他算法联合使用。 此外还有蒙哥马利算法、利用中国剩余定理降指法等。 总之，上述各个实现算法分别从不同方面改进了r s a 加密算法，使得加密 速度有了一定的提高。但是，随着计算机软、硬件的不断发展，数据量也在急剧 增大，对加密的速度要求也越来越高，人们需要不断改进加密算法，以提高加密 运算的速度。 1 4 本论文研究内容 本文在对r s a 算法进行基础研究的基础上，选择几种当前实现算法进行分析 并优化组合，提出r s a 改进算法以提高计算效率的基本思路。研究内容为： ( 1 ) 对r s a 算法的数论基础、安全性进行分析研究。 ( 2 ) 对当前r s a 实现算法进行分析比较，得出各算法的优点和不足。 ( 3 ) 结合上述研究，提出新的组合算法。 硕士学位论文第一章绪论 ( 4 ) 基于新的组合算法，设计实现并得出测试结论。 ( 5 ) 提出新算法应用方案。 硕士学位论文 第二章r s a 算法数论基础及其安全性分析 第二章r s a 算法数论基础及其安全性分析 r s a 可视为现今使用最广泛的公钥密码系统及数字签名系统。诸如i s o ( 国际 标准化组织) 、i t u ( 国际电信联盟) 及s w i f t ( 环球同业银行金融电讯协会) 等 国际标准组织均已接受r s a 系统为标准；根据不同的应用需要，人们基于r s a 算法 开发了大量的加密方案与产品，例如，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 作为传送会话密钥和数字签名的标准算法【1 4 1 。本章 将详细阐述r s a 公钥密码系统的数学理论基础、设计思想、实现算法需主要考虑 的问题，并分析其安全性与速度问题。 2 1r s a 算法的数学理论基础 在密码学中需要使用到许多数学理论，例如数论、信息论、复杂度理论等， 它们是设计密码系统及协议不可或缺的工具，其中数论是密码学中( 尤其是公开密 钥密码系统中) 最重要的数学基础，因此有必要对有关数论理论做一介绍。下面介 绍r s a 算法的数学基础知识n h 。 2 1 1 单向和陷门单向函数 r s a 的安全性主要取决于构造其加密算法的数学函数的求逆困难性，这同大多 数公钥密码系统一样( 譬如e i g a m a l 算法就是基于离散对数问题的困难性【2 2 】) ，我 们称这样的函数为单向函数。单向函数不能直接用作密码体制，因为如果用单向 函数对明文进行加密，即使是合法的接收者也不能还原出明文，因为单向函数的 逆运算是困难的。与密码体制关系更为密切的陷门单向函数，即函数及其逆函数 的计算都存在有效的算法，而且可以将计算函数的方法公开。单向和陷门单向函 数的概念是公钥密码学的核心，它对公钥密码系统的构造非常重要，甚至可以说 公钥密码体制的设计就是陷门单向函数的设计。 定义2 1 ：令函数厂是集合a 到集合口的映射，以厂：彳寸b 表示。若对任意 x 。x ：，x i 工z a ，有f ( x - ) f ( x z ) ，则称为1 一l 映射，或可逆函数。 定义2 2 ：一个可逆函数厂，若它满足： 1 对所有x a ，易于计算厂( x ) ； 6 硕士学位论文 第二章r s a 算法数论基础及其安全性分析 2 对“几乎所有 x 彳，由厂( 石) 求x “极为困难，以至于实际上不可能做 到。则称厂为单向函数n 1 ( o n e - w a y f u n c t i o n ) 上述定义中的“极为困难”是对现有计算机能力和算法而言的，m a s s e y 称此 为视在困难性，相应的函数称之为视在单向函数。以此来和本质上的困难性相区 分。目前，还没有人能够从理论上证明单向函数是存在的。 2 1 2 同余及模运算 同余：假定有三个整数a ，b ，n ( n o ) ，当我们称a 在模n 时与b 同余，是指当且 仅当a 与b 的差为n 的整数倍，臣p a - b - - k n ，其中k 为任一整数。若a 与b 在模n 中同余， 我们可写为a 兰b ( m o d 玎) 或n l ( a - b ) 。 剩余类( r e s i d u ec l a s s ) ：很明显地，利用同余概念，所有整数在模n 中被分成 n 个不同的剩余类；为n 所整除的数( 即余数为o ) 为一剩余类，被n 所除余数为1 的 数为另一剩余类，余2 的数又为一剩余类，以此类推。 完全剩余系( c o m p l e t es e to fr e s i d u e s ) ：若将每一剩余类中取一数为代表，形 成一个集合，则此集合称为模n 的完全剩余系，以z i l 表示。很明显地，集合f 0 ，l ， 2 ，n 1 为模n 的一完全剩余系。 从o 到n 1 的整数组成的集合构成了模n 的“完全剩余系”。这意味着，对每一 个整数a ，它的模n 剩余是从o 到n 1 之间的某个整数。 所谓运算am o dn 表示求a 被n 除的余数，成为模运算。 既约剩余系( r e d u c e ds e to fr e s i d u e s ) ：在模n 的完全剩余系中，若将所有与n 互素的剩余类形成一个集合，则称此集合为模n 的既约剩余系，以z n 表示。例如 n = 1 0 时， o ，1 ，2 ，3 ，4 ，5 ，6 ，7 ，8 ，9 ) 为模1 0 的完全剩余系；而 1 ，3 ，7 ，9 ) 为模l o 的 既约剩余系。 2 1 3 欧拉函数、欧拉定理和费尔马定理 欧拉函数( 九) ：是一个定义在正整数上的函数，其值等于序n 0 ，1 ，2 ，3 ，n 1 中与n 互素的数的个数。即矽( ”) 为模n 既约剩余系中所有元素的个数。 由定义知，当p 是素数时，矽( p ) = p 一1 。 定理2 1 欧拉定理：若m ，a 为正整数，有g c d ( a ，m ) = l ( g c d ，g r e a t e s tc o m m o n d i v i s o r ，最大公约数) ，则a 州州兰l ( m o d m ) 。其中妒( 聊) 称为欧拉函数，它是比m 小 但与m 互素的正整数个数。欧拉定理也有一种等价形式：口妒( ”) + 1 兰a ( m o d m ) 。 7 硕士学位论文第二章r s a 算法数论基础及其安全性分析 定理2 2 设p 和q 是两个不同的素数，n = p q ，则( 玎) = ( p 1 ) ( q - 1 ) ，对 任意的x z 。及任意的非负整数k ，有x 州咖1 三x ( m o d n ) 。 定理3 费尔马定理：如果p 是素数，且g c d ( m ，p ) = l ( 可表示为( m ，p ) = 1 ) ， 则脚川兰l ( m o dp ) ，费尔马定理还存在另一种等价形式：如果p 是素数，m 是任意 正整数，则m p 三m ( m o dp ) 。 对于素数p 来说，缈( p ) = p 一1 ，所以费尔马定理实际是欧拉定理的一个推论。 费尔马定理和欧拉定理及其推论在构成了r s a 算法的主要理论基础。 2 1 4 乘法逆元及其求法 乘法逆元的定义：若a b 兰l ( m o d n ) ，则称b 为a 在模n 的乘法逆元，b 可表示为a - 1 。 利用e u c l i d ( 欧几里德) 算法( 辗转相除法) 求乘法逆元：己知a 及n 且( a n ) = 1 ，求a a 三l ( m o d n ) 。 欧几里德算法是古希腊数学家欧几里德给出的求两个自然数的最大公约数的 方法，如果( a ，n ) = 1 ，则b 一定存在。首先介绍利用欧几里德算法求g c d ( a ，n ) 的方 法，再介绍求乘法逆元的方法。 令r o = i l ，r l = f l ，a n ，利用辗转相除法可得 r o = r l g j + r 2 0 _ r 2 r l r l = r 2 9 2 + r 30 r 3 r 2 r j 2 2r j - l g j 1 + r j0 _ _ _ r j r j 1 r m 3 = r m 2 9 m 2 + r b 1 0 r m 1 r m - 2 r m _ 2 = r m 1 9 m 1 + r m 0 r m r m 1 r m 1 2r m g m 则r m 为a 及n 的最大公因子。( 欧几里德算法求g c d 的主要概念在于：若c - - d g + r ， 则( c ，d ) = ( d ，r ) 。因此在上述算法中，( a ，n ) = ( r o ，r 0 = ( r l ，r 2 ) = - - ( r 州，r m ) = ( r m ，o ) - - r m 。 可以通过举例说明利用欧几里德算法求逆元的方法，如：求1 0 0 1 b - l m o d3 8 3 7 ， b 是1 0 0 1 关于模3 8 3 7 的乘法逆元。 因为( 1 0 0 1 ，3 8 3 7 ) = l ，而 3 8 3 7 = 3 1 0 0 1 + 8 3 4 1 0 0 1 = 1 8 3 4 + 16 7 8 3 4 = 4 1 6 7 + 1 6 6 1 6 7 = 1x1 6 6 + 1 硕士学位论文 第二章r s a 算法数论基础及其安全性分析 所以l = 1 6 7 1 6 6 = 1 6 7 - - ( 8 3 4 - - 4 1 6 7 ) = 5 1 6 7 8 3 4 = 5 ( 1 0 0 1 8 3 4 ) 一8 3 4 = 5 1 0 0 1 - - 6 8 3 4 = 5 1 0 0 1 - - 6 ( 3 8 3 7 3 1 0 0 1 ) = 2 3 x1 0 0 1 - - 6 3 8 3 7 因此2 3 1 0 0 1 兰l ( m o d 3 8 3 7 ) ，故1 0 0 1 关于模3 8 3 7 的乘法逆元为2 3 。一般 求乘法逆元以欧几里德算法为佳。 2 2r s a 算法的各环节 r s a 算法是1 9 7 8 年由r l r i v e s t ，a s h a m i r 和l a d l e m a n 提出的一种用数论 构造的、也是迄今为止理论上最为成熟完善的公钥密码体制。r s a 的理论基础是 数论中的欧拉定理【15 1 ，它的的安全性依赖于大数的因子分解，但并没有从理 论上证明破译r s a 的难度与大数分解难度等价。 2 2 1 r s a 公钥加密解密概述 r s a 算法采用下述加密解密变换。 1 密钥的产生 选择两个保密的大素数p 和q 。 计算n = p q ，缈( 忉= ( p 一1 ) ( g 一1 ) ，其中伊( ) 是的欧拉函数值。 选择一个整数e ，满足l e 缈( ) ，且g c d ( 缈( ) ，e ) 三1 。 计算私钥d ( 解密密钥) ，满足e d 兰l ( m o d q ，( p o ) ，d 是e 在模伊( ) 下的乘 法逆元。 以( p ，) 为公钥，( d ，) 为密钥，销毁p ，q ，伊( ) 。 2 加密 加密时首先将明文比特串进行分组，使得每个分组对应得串在数值上小于， 即分组的二进制长度小于l 0 9 2 n 。然后，对每个明文分组m ，作加密运算： c = e k ( m ) = m 。m o d n 3 解密 对密文分组的解密运算为： m = d ( c ) = c 4m o d n 由定理1 和定理2 可以证明解密运算能恢复明文m 9 硕士学位论文 第二章r s a 算法数论基础及其安全性分析 2 2 2r s a 签名算法 并非所有的公开密钥系统，均可同时达到秘密性与数字签名功能。一般而言， 一公开密钥系统若作为密码系统，则无法作为数字签名，反之亦然。只有很少数 的系统可同时作为密码系统和数字签名，如本文讨论的r s a 系统【1 5 】。r s a 签名算 法如下【5 2 2 】： 设n = p q ，且p 和q 是两个大素数，e 和d 满足e d 三l ( m o d q ，( n ) ) 。 公开密钥：n ，e 私有密钥：d 签名过程：发送方使用自己的私钥d 对明文x 进行数字签名变换： y = 石dm o d n ：并将加密后的消息和签名y 发送给接收方； 验证过程：接收方使用发送方的公钥e 对收到的消息y 进行数字签名验证变换 x = y 。m o d n ，并使用发送方的密钥解密恢复消息x ，比较一与x ，如果x = x 则证 实发送方的身份合法。 这样，用户a 若想用r s a 签名方案对消息x 签名，他只需公开他的公钥和 e ，由于签名算法是保密的，因此a 是唯一能产生签名的人，任何要验证用户a 签名的用户只需查到a 的公钥即可验证签名。 对于实现签名和公钥加密的组合，常用方法是：假定通信双方为a 和b 。对 于明文工，a 计算他的签名y = x dr o o d n ，然后利用b 的公开加密函数e 。对信息 对( x ，y ) 加密得到z ，将密文z 传送给曰，当b 收到密文z 后，他首先用他的解密 函数d 占来解密得到( x ，y ) = d 占( z ) = d 占( ( x ，y ) ) ，然后利用a 的验证算法来检查 x t = 石= y 。r o o d n 是否成立。 2 2 3 大数运算处理 r s a 依赖大数运算，目前主流r s a 算法都建立在1 0 2 4 位的大数运算之上。 而大多数的编译器只能支持到6 4 位的整数运算，即我们在运算中所使用的整数必 须小于等于“位，即：0 x 册珩珩也就是1 8 4 4 6 7 4 4 0 7 3 7 0 9 5 5 1 6 1 5 ，这远远达 不到r s a 的需要，于是需要专门建立大数运算库来解决这一问题。最简单的办法 是将大数当作数组进行处理，数组的各元素也就是大数每一位上的数字，通常采 用最容易理解的十进制数字0 - - , 9 。然后对“数字数组”编写加减乘除函数。但是 这样做效率很低，因为二进制为1 0 2 4 位的大数在十进制下也有三百多位，对于任 何一种运算，都需要在两个有数百个元素的数组空间上多次重循环，还需要许多 1 0 硕士学位论文第二章r s a 算法数论基础及其安全性分析 额外的空间存放计算的进退位标志及中间结果。另外，对于某些特殊的运算而言， 采用二进制会使计算过程大大简化，而这种大数表示方法转化成二进制显然非常 麻烦，所以在某些实例中则干脆采用了二进制数组的方法来记录大数，当然这样 效率就更低了。一个有效的改进方法是将大数表示为一个n 进制数组，对于目前 的3 2 位系统而言n 可以取值为2 的3 2 次方，即0 x 1 0 0 0 0 0 0 0 0 ，假如将一个二进 制为1 0 2 4 位的大数转化成0 x 1 0 0 0 0 0 0 0 进制，就变成了3 2 位，而每一位的取值范 围不再是二进制的0 - 一1 或十进制的0 - 9 ，而是o o x m 珩m 我们正好可以用一 个3 2 位的d w o r d ( 如：无符号长整数，u n s i g n e dl o n g ) 类型来表示该值。所 以1 0 2 4 位的大数就变成一个含有3 2 个元素的d w o r d 数组，而针对d w o r d 数组进行各种运算所需的循环规模至多3 2 次而已。 例如大数18 4 4 6 7 4 4 0 7 3 7 0 9 5 516 15 ，等于0 x 脚f 1 2 晰7 其表示方式就相当 于十进制的9 9 ：有两位，只是每位上的元素不是9 而都是0 x t t t t i t f f 。而 1 8 4 4 6 7 4 4 0 7 3 7 0 9 5 5 1 6 1 6 等于0 x 0 0 0 0 0 0 0 10 0 0 0 0 0 0 00 0 0 0 0 0 0 0 ，就相当于十进制的 1 0 0 ：有三位，第一位是l ，其它两位都是0 ，如此等等。在实际应用中，“数字 数组 的排列顺序采用低位在前高位在后的方式，这样，大数a 就可以方便地用 数学表达式来表示其值： x = 彳f ，( ，= 0 x 1 0 0 0 0 0 0 0 0 ，o x f ，) i = o 任何整数运算最终都能分解成数字与数字之间的运算，在o x l 0 0 0 0 0 0 0 0 进制 下其“数字 最大达到o x 腼筒，其数字与数字之间的运算，结果也必然超出了目 前3 2 位系统的字长。在v c + + 中，存在一个i n t 6 4 类型可以处理6 4 位的整数，所 以不用担心这一问题，而在其它编译系统中如果不存在6 4 位整形，就需要采用更 小的进制方式来存储大数，例如1 6 位的w o r d 类型可以用来表示0 x 1 0 0 0 0 进制。 但效率更高的办法还是采用3 2 位的d w o r d 类型。 2 2 4 大素数的产生 根据r s a 算法的加解密变换，需要产生两个保密的大素数作为基础运算。在 2 0 0 0 年前欧几里德证明了素数有无穷多个，这自然的就引出一个问题：既然 素数有无穷个，那么是否有一个计算素数的通项公式? 两千年来，数论学的 一个重要任务，就是寻找一个可以表示全体素数的素数普遍公式。为此，人 类耗费了巨大的心血。希尔伯特认为，如果有了素数统一的素数普遍公式， 那么这些哥德巴赫猜想和孪生素数猜想都可以得到解决。“研究各种各样的素 数分布状况，一直是数论中最重要和最有吸引力的中心问题之一。关于素数分布 硕士学位论文第二章r s a 算法数论基础及其安全性分析 性质的许多著名猜想是通过数值观察计算和初步研究提出的，大多数至今仍未解 决”【23 。因此，欲得到素数，必须另寻出路。 大素数的产生应是现代密码学应用中最重要的步骤。几乎所有的公开密钥系 统均需要用到大的素数，若此素数选用不当，则此公开密钥系统的安全性就岌岌 可危。一般而言，素数的产生通常有两种方法，一为确定性素数产生方法，一为 概率性素数产生方法1 2 4 】，目前后者是当今生成素数的主要方法。所谓概率性素数 产生法，是指一种算法，其输入为一奇数，输出为两种状态y e s 或n o 之一。若 输入一奇数n ，输出为n o ，则表示1 1 为合数，若输出为y e s ，则表示n 为素数的 概率为1 一r ，其中r 为此素数产生法中可控制的任意小数，但不能为0 。此类方法 中较著名的有s o l o v a y - s t r a s s e n 算法、l e h m a n n 算法、m i l l e r - r a b i n 算法等( 文献 2 4 2 6 分别描述了这三种测试算法) 。在实际应用中，一般做法是先生成大的随机 整数，然后通过素性检测来测试其是否为素数。数论学家利用费尔马定理研究出 了多种素数测试方法，目前最快的算法是m i l l e r - r a b i n ( 拉宾米勒) 测试算法( 也 称为伪素数检测【l 】) ，其过程如下：首先选择一个待测的随机数计算，2 7 是能 够整除n 1 的2 的最大幂数。 1 计算m ，使得n = 2 7 m + 1 。 2 选择随机数a n 。 3 若a 村m o d n = l ，则通过随机数a 的测试。 4 让a 取不同的值对进行5 次测试，若全部通过则判定为素数。 若通过一次测试，则为合数( 非素数) 的概率为2 5 ，若通过t 次测 试，则为合数( 非素数) 的概率为1 4 。事实上取t 为5 时，为合数的概率为 1 1 2 8 ，n 为素数的概率已经大于9 9 9 9 f 2 7 j 。 另可参看后文“强素数”有关概念。 2 3r s a 的安全性 密码学所讨论的系统，其安全性是最高的评价准则。再好的密码系统，若安 全性不足则一文不值，同时，密码系统的安全性很难用理论证明( 事实上证明一 个安全系统是安全的很难，但若该系统不安全，证明它是不安全的则很容易) 啪10 r s a 从提出到现在已近二十年，经历了各种攻击的考验，逐渐为人们接 受，普遍认为是目前最优秀的公钥方案之一。但是在特定的条件下，r s a 实现 细节的疏忽会导致对r s a 算法的有效攻击。因此，对r s a 体制实现的各个环节进 行充分考虑，避免安全性缺陷是非常有必要的。 硕士学位论文第二章r s a 算法数论基础及其安全性分析 2 3 1r s a 参数的选择 r s a 遭受攻击的很多情况是因为算法实现的一些细节上的漏洞所导致的，所以 在使用r s a 算法构造密码系统时，为保证安全，在生成大素数的基础上，还必须 认真仔细选择参数，防止漏洞的形成。根据r s a 加解密过程，其主要参数有三个： 模数，加密密钥e ，解密密钥d 乜1 。 1 模数的确定 虽然迄今人们无法证明，破解r s a 系统等于对因子分解，但一般相信r s a 系统的安全性等同于因子分解，即：若能分解因子，即能攻破r s a 系统，若能 攻破r s a 系统，即能分解因子。因此，在使用r s a 系统时，对于模数的选择 非常重要。在r s a 算法中，通过产生的两个大素数p 和q 相乘得到模数，而后