（计算机应用技术专业论文）基于前缀码的密码分析与设计.pdf

哈尔滨理丁人学t 学硕l j 学位论文 基于前缀码的密码分析与设计 摘要 随着i n t e m e t 的飞速发展，网络上的资源共享越来越强化。随之而来的，网 络安全问题也越来越突出。网络在带给人们诸多便利的同时，也成了许多犯罪 分子攻击的目标。他们以计算机为工具，同时又以计算机为目标，在网上对计 算机数据信息进行恶意的修改、删除，为了保证互联网上信息传输的机密性、 真实性、完整性和通讯的不可否认性，密码学己成为了计算机安全领域的主要 研究方向。因此对多种加密算法的研究具有很高的理论意义和现实价值。 本文主要对非对称加密体制和对称加密体制进行研究，之后分析数字签名 的过程并进行改进，在此基础上实现混合加密系统，完成数据的混合加密。 首先对于非对称加密体制，对r s a 算法作了详细的说明，r s a 算法基于大 数模幂乘运算，其运行效率决定了r s a 非对称密码的性能，文中说明了各种模 幂算法的快速实现方法，并进行比较分析。 其次对于对称加密体制，以d e s ( d a t ae n c r y p t i o ns t a n d a r d ，数据加密标 准) 算法和r i j n d a e l 算法为重点，首先对d e s 和r i j n d a e l 算法的加密原理进行说 明，并通过对算法的分析找出它们的不足之处，女i i d e s 算法，易受选择明文法 攻击，而s q u a r e 攻击法是对r i j n d a e l 算法最有效的攻击法。它们的攻击原理是基 于加密系统的不变性，因此本文提出了基于前缀码的解决方案，因为前缀码具 有很好的译码特性，通过前缀码的引入可以对输入的明文译码，以此来改变算 法子密钥的使用顺序，从而使加密系统不再固定不变，而是随着明文的不同而 不断变化，使算法对攻击具有很好的抵抗性。 最后对数字签名过程进行分析，由于m d 5 算法已经被破解，所以数字签名 存在着被伪造的隐患。因此本文提出了基于前缀码的数字签名改进方案，通过 前缀码的译码特性对m d 5 算法产生的摘要进行译码、变换，然后再通过网络传 输，消除了数字签名可能被伪造的隐患。之后在此基础上完成了将改进后的 r i j n d a e l 算法和r s a 算法相结合混合加密系统，并把改进的数字签名方案应用 到系统中。 关键词前缀码；对称加密体制；数据加密标准；数字签名；混合加密 a n a l y s i sa n dd e s i g no fc i p h e rb a s e do np r e f i xc o d e s a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to f i n t e m e t ，t h es h a r i n go fr e s o u r c e so nt h en e t w o r k a r em o r ea n dm o r es t r e n g t h e n a t t e n d a n t ，t h ep r o b l e mo fn e t w o r k s e c u r i t yh a s b e c o m ep r o m i n e n ti n c r e a s i n g l y n e t w o r kb r i n g sal o to fc o n v e n i e n c et o p e o p l e ； h o w e v e r , i ta l s ob e c a m et h et a r g e t so fm a n y c r i m i n a l s t h e yu s et h ec o m p u t e ra sa t o o l ，a n du s e dt h ec o m p u t e ra st h et a r g e t sa tt h es a m et i m e t h e yd e l e t ea n dm o d i f y t h ei n f o r m a t i o no nc o m p u t e rd a t ao nt h en e t w o r k m a l i c i o u s l y i no r d e rt og u a r a n t e e t h e c o n f i d e n t i a l i t yo fi n f o r m a t i o nt r a n s m i s s i o n ，a u t h e n t i c i t y , i n t e g r i t ya n dn o n r e p u d i a t i o no fc o m m u n i c a t i o n ，c r y p t o g r a p h yh a sb e c o m ea m a j o ra r e ao fc o m p u t e r s e c u r i t yr e s e a r c h t h u saw i d er a n g eo fe n c r y p t i o na l g o r i t h mr e s e a r c hh a sg r e a t t h e o r e t i c a ls i g n i f i c a n c ea n dp r a c t i c a lv a l u e t h ep a p e rr e s e a r c h e st h e n o n s y m m e t r i ce n c r y p t i o ns y s t e ma n ds y m m e t r i c e n c r y p t i o ns y s t e mm a i n l y ，a n di ta n a l y s i s e st h ep r o c e d u r eo fd i g i t a ls i g n a t u r ea n d m a k e si m p r o v e m e n t s ，i nt h ee n di ti m p l e m e n t st h eh y b r i de n c r y p t i o ns y s t e m ，a n d c o m p l e t e st h eh y b r i de n c r y p t i o n f i r s t l y ，f o rt h en o n s y m m e t r i ce n c r y p t i o ns y s t e m ，t h ep a p e ri n t r o d u c e st h er s a a l g o r i t h mf o rc o m p r e h e n s i v ed e t a i l ，a n dt h e na n a l y s i st h ee f f i c i e n c ya n ds e c u r i t vo f r s aa l g o r i t h m r s a a l g o r i t h mb a s e do no fl a r g en u m b e r s ，a n di t s o p e r a t i n g e f f i c i e n c yd e t e r m i n e st h ep e r f o r m a n c eo fr s ap u b l i ck e yc r y p t o g r a p h y ，t h ep a p e r s i n t r o d u c e sav a r i e t yo ff a s ti m p l e m e n t a t i o nm e t h o d so fm o d u l a r e 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 n ，a n dt h e nd o e sc o m p a r a t i v ea n a l y s i s s e c o n d l y ，f o rt h es y m m e t r i ce n c r y p t i o n s y s t e m ，i tt a k e st h ed e s ( d a t a e n c r y p t i o ns t a n d a r d ) a l g o r i t h ma n dr i j n d a e la l g o r i t h ma st h e f o c u s ，f i r s f l y i n t r o d u c e st h ee n c r y p t i o np r i n c i p l eo ft h ed e sa n dr i j n d a e le n c r y p t i o na l g o r i t h m a n df i n dt h e i rd e f i c i e n c i e st h o u g ht h ed e p t ha n a l y s i so f t h ea l g o r i t h m s u c ht h a td e s e n c r y p t i o na l g o r i t h mi sv u l n e r a b l et oc h o s e n - p l a i n t e x ta t t a c km e t h o d ，w h i l et h e s q u a r ea t t a c k si st h em o s te f f e c t i v em e t h o dt or i j n d a e la l g o r i t h m t h e i rp r i n c i p l e so f u 哈尔滨理t 大学t 学硕j j 学位论文 a t t a c k sa r eb a s e do nt h ei n v a r i a n c eo fe n c r y p t i o ns y s t e m s ，s ot h ep a p e rp u t sf o r w a r d t oas o l u t i o nw h i c hi sb a s e do np r e f i xc o d e s ，b e c a u s ep r e f i xc o d e sh a v eav e r yg o o d d e c o d i n gc h a r a c t e r i s t i c s ，t h r o u g ht h e i n t r o d u c t i o no ft h ep r e f i xc o d e s ，i tc o u l d d e c o d e st h ep l a i n t e x tt oc h a n g et h es e q u e n c eo fs u b k e yo ft h ea l g o r i t h m ，a n dm a k e s t h ee n c r y p t i o ns y s t e mb en o ti n v a r i a n c e ，b u tb ev a r i a b l e 谢t lt h ed i f f e r e n tp l a i n t e x t t h i sm e t h o dm a k e st h ea l g o r i t h mh a v eg o o dr e s i s t a n c et os o m ea t t a c k s f i n a l l y ，t h ep a p e ra n a l y s i s e st h ep r o c e d u r eo ft h ed i g i t a ls i g n a t u r e ，m d 5 a l g o r i t h mh a sb e e nc r a c k e d ，s ot h ed i g i t a ls i g n a t u r eh a st h e h i d d e nd a n g e rt ob e f o r g e d i nt h i sp a p e r ，i tp u t sf o r w o r dt oa s o l u t i o no fd i g i t a ls i g n a t u r ew h i c hi sb a s e d o np r e f i xc o d e s ，t h r o u g ht h ed e c o d i n gc h a r a c t e r i s t i c so ft h ep r e f i xc o d e s ，i td e c o d e s a n dt r a n s f o r m e dt h es u m m a r yw h i c hi sg e n e r a t e db yt h em d 5a l g o r i t h m ，a n dt h e n t r a n s m i t t e do v e rt h en e t w o r k ，s oi tc o u l de l i m i n a tt h eh i d d e nd a n g e rt h a tt h ed i g i t a l s i g n a t u r em a yb ef o r g e d a f t e rt h a tt h ep a p e rc o m p l e t e st h eh y b r i de n c r y p t i o ns y s t e m w h i c hi sb a s e do ni m p r o v e dr i j n d a e la l g o r i t h ma n dr s aa l g o r i t h ma n da p p l i e st h e i m p r o v e dd i g i t a ls i g n a t u r ep r o c e d u r et ot h es y s t e mt om a k et h eh y b r i de n c r y p t i o n s y s t e mh a sm o r eh i 曲e re f f i c i e n c ya n ds e c u r i t y k e y w o r d sp r e f i xc o d e s ，s y m m e t r i ce n c r y p t i o ns y s t e m ，d a t ae n c r y p t i o ns t a n d a r d ， d i g i t a ls i g n a t u r e ，h y b r i de n c r y p t i o n i i i 哈尔滨理工大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文基于前缀码的密码分析与设 计，是本人在导师指导下，在哈尔滨理工大学攻读硕士学位期间独立进行研 究工作所取得的成果。据本人所知，论文中除已注明部分外不包含他人已发表 或撰写过的研究成果。对本文研究工作做出贡献的个人和集体，均已在文中以 明确方式注明。本声明的法律结果将完全由本人承担。 作者签名乏岛讳舀飞日期：函习年3 月夕，日 哈尔滨理工大学硕士学位论文使用授权书 基于前缀码的密码分析与设计系本人在哈尔滨理工大学攻读硕士学位 期间在导师指导下完成的硕士学位论文。本论文的研究成果归哈尔滨理工大学 所有，本论文的研究内容不得以其它单位的名义发表。本人完全了解哈尔滨理 工大学关于保存、使用学位论文的规定，同意学校保留并向有关部门提交论文 和电子版本，允许论文被查阅和借阅。本人授权哈尔滨理工大学可以采用影 印、缩印或其他复制手段保存论文，可以公布论文的全部或部分内容。 本学位论文属于 保密口，在年解密后适用授权书。 不保密味 ( 请在以上相应方框内打) 作者签名与格匹嗍跏净歹月堋 刷噬轹谁形醐吵夕年3 b 堋 哈尔滨理t 大学丁学硕l j 学位论文 第1 章绪论 1 1 课题研究的目的和意义 随着计算机i n t e m e t 和通信技术的迅速发展，人们对网络信息的需求在不断 增加，对服务质量的要求也越来越高，大量敏感信息常常通过公共通信设施或 计算机网络进行交换，而其中很重要的一个环节就是如何保证信息传送过程中 的安全。当今社会，许多公共和私人部门的一些机构愈来愈多地应用电子数据 处理，将数据存放到数据库中，如何防止非法泄露、删除、修改等成为必须正 视的问题。在计算机犯罪趋于日益严重的今天，如果不能对数据信息进行有效 的保护，就无法满足现有存储和传输的条件和要求。例如，对于银行的电子资 金传输系统，就算是使用专用的网络，也仅仅能够减少从外部攻击的可能性， 而对于一般的信息传输系统，比如说一个地方的电子政务系统，其被攻击成功 的可能性相对要大得多。由此可见，加强信息安全的研究，寻求解决信息安全 问题的良方，是信息时代提出的迫切任务，本文的研究具有很重的现实价值和 理论意义。 密码学的基本目的是使在不安全信道中通信的两方以一种使他们的对手不 能明白和理解的通信内容的方式进行通信。由于传输中的公共信道和存储的计 算机系统非常脆弱，为了避免信息在传输过程中受到攻击，除了制订必要的法 律外，还需要合适的保护措旌。 密码技术就是一种有效的方法。密码技术自古有之，目前已发展成为一门 结合数学、计算机科学、电子与通信、微电子等技术的交叉学科。密码技术可 以有效地用于信息鉴别、数字签名等，用以防止电子欺骗，对信息系统的安全 起到极其重要的作用。事实证明，这也是最经济可行的方法，它能够在潜在不 安全的环境中保证通信的安全。密码技术的关键是信息的加密和解密，信息的 加密和解密就是在保证信息不被非法截取、复制、删除、更改或插入等操作的 前提下，在通信中对信息进行存储和传输。正因为如此，研究最佳的信息加密 解密方法，确保数据在网络环境中安全传输一直是人们追求的目标，也是本文 研究的主要目的。近几年，有不少专家、学者致力于密码学的研究，其安全理 论和安全产品已有许多，为推动网络通信、电子文档的安全传输作出了较大的 贡献。 哈尔滨理下人学t 学硕f 饽。位论文 1 2 国内外研究现状及分析 密码学是加密解密算法研究的关键。密码学以研究秘密通信为目的，即研 究对传输信息采取何种秘密变换以防止第三者对信息的窃取。近年来，密码学 之所以十分活跃，在理论和方法上都有了巨大的发展，主要原因是它与计算机 科学的蓬勃发展息息相关。目前，世界上的许多国家均非常重视加密算法的研 究。在近代密码学上有两件大事。 一是1 9 7 7 年美国国家标准局正式公布实施了美国的数据加密标准d e s ( d a t ae n c r y p t i o ns t a n d a r d ) ，公开它的加密算法，并批准可用于非保密单位 及商业上的保密通信。 二是1 9 7 6 年由d i f f i e 和h e l l m a n 在“密码学的新方向 一文中提出了非对 称加密体制的思想，在此基础上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 非对称密码系统，可以这么说：“没有非对称密码的研究就没有近代密 码学。 密码体制从原理上可分为单钥密码体制和双钥密码体制两大类。单钥密码 体制又称为对称加密体制，双钥密码体制又称为非对称加密体制或者公钥加密 体制幢1 。 1 2 1 对称加密体制 数据加密标准d e s ( d a t ae n c r y p t i o ns t a n d a r d ) 是迄今为止应用最为广泛 的一种对称加密算法，也是最具代表性的一种分组密码体制1 。d e s 是美国 1 9 7 7 年公布实施的第一个公开绝大部分加密原理和算法细节的分组密码体制。 掌握和了解这一算法的基本原理、设计思想、安全性分析等问题，对于研究分 组密码理论和其实际应用具有重要意义。 d e s 作为分组密码的杰出代表，在密码学发展历史上具有重要的地位。 1 9 7 8 年估计d e s 算法在2 0 1 5 年内安全性不成问题h 1 。但是随着计算技术的飞速 发展，再加上d e s 产生的各密文块之间没有联系，从而造成了黑客可以对其中 的敏感信息进行破坏。另外，它的密钥管理的效率、复杂性及长度的限制，其 安全性在后来受到了各方面的质疑。随后d e s 也改进为3 d e s ，采用三组不同 密钥对每块信息加密3 次( 速度要降低三分之二) ，并将新的密文块与前一密 文块连接一起后再加密，获得了很好的效果。但是由于其速度降低太多，因此 哈尔滨理丁人学t 学硕i j 学位论文 在那些安全性能要求较高、实时性要求又很强、用户终端计算处理能力弱的场 合和无线网络中都受到了局限1 。d e s 经历了2 0 多年世界性的分析和攻击，目 前比较有效的方法是选择明文攻击法以及b i h a r n 和s h a m i r 提出的差分密码分析 法( d i f e r e n t i a lc r y p t a n a l y s i s ) 。近年来分组密码新的算法不断涌现，由中国学 者来学嘉博士与著名密码学家j a m e sm a s s e y 与1 9 9 0 年提出，后经修改于1 9 9 2 年 完成的i d e a ( i n t e r n a t i o n a ld a t ae n c r y p t i o na l g o r i t h m ) 依靠方法论上的新颖， 并且速度快，成为其中的佼佼者。 1 9 9 7 年4 月，美国国家标准和技术研究所( k i s t ) 发起征集a e s ( a d v a n c e de n c r y p t i o ns t a n d a r d ) 算法的活动1 6 1 ，并成立了a e s 工作组。其目的 是为了确定一个非保密的、公开披露的、全球免费使用的加密算法，用于保护 下一世纪政府的敏感信息，也希望能够成为秘密和公开部门的数据加密标准。 a e s 的基本要求是比三重d e s 快，且至少和三重d e s 一样安全，分组长度是 1 2 8 b i t ，密钥长度1 2 8 1 9 2 2 5 6 b i t 。1 9 9 9 年n i s t 从1 5 个候选算法中选出5 个，在 这5 个算法中继续进行评价。并在2 0 0 0 年1 0 月，n i s t 公布了最终评选结果，优 胜者是r i j n d a e l 算法。 对称密码体制不仅可以用于数据加密，也可以用于消息认证。但是对称加 密体制存在着严重的缺陷：在进行安全通信之前，通信的双方必须通过安全信 道商定和传送密钥，而在实际的通讯网络中，通信双方很难确定一条合理的安 全通道；另外一个问题就是密钥的管理。在拥有大量用户的计算机通信网络 中，n 个相互进行保密通信的用户需要从n f n 1 ) 2 个密钥；当n 值太大的时候， 密钥管理的开销极大，密钥只能记录在计算机内存或外存上，这本身就是极不 安全n 1 。另外就是密钥分发问题。对称加密系统中，加密的安全性完全依赖于 对密钥的保护，但是由于通信双方使用的是相同的密钥，人们又不得不相互交 流密钥，所以为了保证安全，人们必须使用一些另外的安全信道来分发密钥， 例如用专门的信使来传送密钥。这种做法的代价是相当大的，甚至可以说是非 常不现实的，尤其在计算机网络环境下，人们使用网络传送加密的文件，却需 要另外的安全信道来分发密钥，显而易见，这需要新的解决方法。 1 2 2 非对称加密体制 对称加密体制的特点是解密密钥与加密密钥相同或者很容易从加密密钥导 出解密密钥，因而，加密密钥的泄露会使系统变得不安全。对称密码系统的一 个严重缺陷是在任何密文传输之前，发送者和接收者必须使用一个安全信道预 哈尔滨理t 人学t 学硕 j 学位论文 先商定和传送密钥。在实际的通讯中，通信双方则很难确定一条合理的安全通 道。为了解决这些问题，w d i f f i e 和m e h e l l m a m 在1 9 7 6 年发表了具有划时代 意义的“密码学的新方向 一文，提出了非对称加密体制思想，为近代密码学 的发展指明了方向，克服了对称加密体制的缺点。它的出现是密码学研究领域 中的一项重大突破，也是现代密码学诞生的标志之一嵋t 9 1 。 在非对称加密体制中，加密密钥不等于解密密钥。加密密钥可对外公开， 使任何用户都可将传送给此用户的信息用公开密钥加密发送，而该用户唯一保 存的私人密钥是保密的，也只有他能将密文复原、解密引。虽然解密密钥理论 上可由加密密钥推算出来，但这种算法设计在实际上是不可能的，或者虽然能 够推算出，但要花费很长的时间而成为不可行的。所以将加密密钥公开也不会 危害密钥的安全。通信双方无须事先交换密钥就可建立起保密通信。非对称加 密体制克服了对称加密体制的缺点，特别适用于计算机网络中的多用户通信， 它大大减少了多用户通信所需的密钥量，节省了系统资源，也便于密钥管理。 目前比较流行的非对称加密算法主要分为两大类1 。一类是基于大整数因 子分解的算法，其典型代表就是r s a j j n 密算法，是1 9 7 7 年r i v e s t ，s h a m i r 和 a d l e m a n 提出的第一个比较完善的非对称加密算法；另一类是基于离散对数问 题的算法，其中有代表性的算法是基于椭圆曲线上离散对数的e c c 算法n 引。 r s a 是被研究得最广泛的非对称加密算法，从提出到现在已近二十年，经 历了各种攻击的考验，逐渐为人们接受。r s a 的安全性依赖于大数的因子分 解，但并没有从理论上证明破译r s a 的难度与大数分解难度等价。即r s a 的重 大缺陷是无法从理论上把握它的保密性能如何，而且密码学界多数人士倾向于 因子分解不是n p c 问题引。r s a 的缺点主要有： 1 产生密钥麻烦，受到素数产生技术的限制，因而难以做到一次一密。 2 分组长度太大，为保证安全性，n 至少也要6 0 0 b i t s 以上，使运算代价很 高，尤其是速度较慢，较对称加密算法慢几个数量级；且随着大数分解技术的 发展，这个长度还在增加，不利于数据格式的标准化。 椭圆曲线加密算法是1 9 8 5 年由n k o b l i z 和v m i l l e r 把椭圆曲线密码理论应用 到非对称加密系统中提出来的，是国内外目前研究的热点。在通信网的身份认 证与密钥分配中更受青睐。目前它己广泛应用于智能卡、电子商务等业务系统 中。e c c 生成私钥和公钥方便，节省内存空问、带宽和处理时间。从现有的攻 击算法可看出，椭圆曲线上的离散对数问题与乘法群上的离散对数问题难度相 当。而加解密速度相对来说较快，具有明显的技术优势1 。因此，在同级安全 条件下，采用基于椭圆曲线的加密和签名方案，运算速度l 匕r s a 快得多，设计 哈尔滨理工大学工学硕十学位论文 更简单，更灵活。一般来说，密钥长度为1 6 0 位的椭圆曲线加密算法，其安全 性相当于1 0 2 4 位的r s a 力h 密算法n 5 1 6 1 。 但是椭圆曲线加密体制目前仍存在一些问题： 1 现有的椭圆曲线加密系统由于研究应用同r s a 等相比还不够成熟。 2 椭圆曲线加密体制中无有效的编码算法，其它算法加解密速度也不理 想，给椭圆曲线应用带来了不便n 利。 1 3 课题来源及本文主要内容 1 3 1 课题来源 本课题来源于国家自然科学基金( 6 0 6 7 3 1 3 1 、6 0 8 7 3 0 1 9 ) ；黑龙江省自然 科学基金( f 2 0 0 6 0 8 ) ；黑龙江省教育厅海外学人重点科研资助项目 ( 1 1 5 2 h q 0 8 ) 。 1 3 2 本文研究的主要内容 本课题研究的目的是通过对d e s 算法和r i j n d a e l 算法的深入分析找出它们 的不足之处，由于前缀码有很好的译码特性，把前缀码引入数据加密的过程 中，提出基于前缀码的d e s 算法和r i j n d a e l 算法的改进方案，使他们能更安全 的进行数据保护。同时针对m d 5 算法被破解，数字签名存在着被伪造的隐患， 提出基于前缀码的数字签名改进方案，最后完成混合加密系统，实现网络上数 据安全且有效的传输。 本文主要研究以下几项内容： 1 详细介绍前缀码的相关理论，通过前缀码可以译码的优点把前缀码引 入数据加密的过程中，结合对称加密算法和非对称加密算法，达到设计更高效 更安全的加密算法的目的。 2 详细说明非对称加密体制中的r s a j j l l 密算法。并对r s a 算法的各种模 幂乘的快速实现进行比较分析。 3 深入分析对称加密体制及其主要的几个加密算法，如d e s 算法， r i j n d a e l 算法等。指出每个算法的优缺点，提出基于前缀码的算法改进方案。 再分别对两种算法的改进方案进行系统的分析验证。 哈尔滨理- t 人学工学硕：学位论文 4 针对m d 5 算法破解，数字签名存在被伪造的隐患，提出了一种基于前 缀码的数字签名改进方案，通过前缀码对m d 5 算法产生的摘要进行变换后再传 输的方法消除这种隐患。 5 最后将改进后的r i j n d a e l 算法和r s a 算法相结合，完成混合加密系统， 并将改进的数字签名过程应用到加密系统中，并通过v i s u a lc + + 6 0 编程实现混 合加密系统，并进行性能分析 1 4 论文结构 第1 章介绍了本课题研究的目的和意义，国内外研究现状，课题来源及论 文主要研究内容。 第2 章首先说明了r s a 加密算法的加密过程，然后阐述了模幂算法算法 的三种快速实现方法并进行比较分析。 第3 章首先对d e s 算法的加密过程及其子密钥生成过程进行了详细的说 明，然后分析了算法的不足之处，包括d e s 的各种改进算法中仍然存在的问 题，之后对前缀码的译码过程进行分析并将前缀码引入d e s 算法中，提出了 基于前缀码的d e s 算法改进方案，最后对改进的算法进行了系统的分析验 证。 第4 章首先说明了r i j n d a e l 算法加密过程，然后阐述了r i j n d a e l 算法的子 密钥生成过程，分析了r i j n d a e l 算法的优缺点并对已有的改进算法进行研究， 指出其中存在的问题，之后给出了对r i j n d a e l 算法最有威胁的攻击方法 ( s q u a r e 攻击法) 的攻击原理及过程，根据s q u a r e 攻击法的原理，通过前一 章提到的前缀码思想来改进r i j n d a e l 算法，最后对改进的算法进行了系统的分 析验证。 第5 章首先说明了数字签名的过程，针对m d 5 算法被破解，数字签名可 能被伪造的问题提出了基于前缀码的数字签名改进方案，之后结合前三章的研 究内容提出了一个完整的基于改进的r i j n d a e l 算法和r s a 算法的混合加密系 统，同时将改进后的数字签名过程应用到系统中，并通过v i s u a lc + + 6 0 编程 实现此混合加密系统，最后从效率、安全性、密钥管理等方面对混合加密系统 进行性能分析。 结论部分对本文进行了总结，并对进一步的研究做出了展望。 哈尔滨理t 人学t 学硕f j 学位论文 2 1 引言 第2 章r s a 算法分析 在上世纪7 0 年代，w h i t e f i e l dd i f f i e 和m a r t i nh e l l m a n 一直致力于密钥分发 的研究，并在1 9 7 6 年发表了他们的研究成果，提出了以单向陷门函数为基础的 公钥密码学，虽然当时他们并不知道单向陷门函数是否存在，但是这一思想的 提出标志着密码学进入了一个崭新的时期，可以说是密码学发展的里程碑引。 在d i f f i e 和h e l l m e n 发表了公钥密码学的思想后，麻省理工学院的三位教授 r i v e s t 、s h a l m i r 和a d l e m a n 对此进行了深入研究，开发出了个能够真正加密 数据的算法。他们1 9 7 8 年发表了这个算法，这就是著名的r s a 算法( 三位发明 者名字的首字母) 。r s a 算法不仅可以用来对数据进行加密还可以进行数字签 名。它是当今使用最广泛的公钥密码算法，也是事实上的工业标准u 引。 2 2r s a 算法的基本过程 r s a 使用了指数表达式。明文以分组为单位加密，其中每个分组是小于某 个数n 的二进制值。也就是说，分组大小必须小于或者等于l o g n 2 ，实践中分组 大小是尼比特，其 0 2 n 2 川。对于某个明文分组m 和密文分组c ：j n 密及解密的 形式如下幢们： c = 艟m o dn m = d m o d ，z = ( a 厂) d m o d ，z = 厂d m o d 胛 发送方和接收方都必须知道玎的值。发送方知道e 的值，而只有接收方知道 d 的值。因此，这是一种公开密钥为( e ，”) ，私有密钥为( z 胛) 的非对称加密 算法。要使这个算法能够满足公开密钥加密的要求，必须符合如下条件眨： 1 有可能找到p ，d ，玎的值，使得m e a = m m o d 玎。 2 要计算膨和相对来说是简单的。 3 在给定e 和甩时，判断出d 是不可行的。 下面归纳r s a 算法： 1 密钥的产生选择两个素数( 口g ) ；计算聆印g ；计算( 刀) = 1 ) ( g 一 1 ) ，选择一个数e ，使g c a ( c , ( n ) ，p ) = 1 且1 勺 西( n ) ；再计算d ，使( d x e ) m o d 西( 疗) = 哈尔滨理t 人学t 学硕 ? 学位论文 1 ；则最后公开密钥( p ，行) ，私有密钥( 4 口g ) 。 2 加密明文m ，加密后密文c = ：肝m o d ”。 3 解密密文c ，解密后明文m = dr o o d 挖。 2 3 三种快速模幂算法 从上面的算法的基本实现可以看出，不论是r s a 的公钥加密运算还是它 的私钥解密运算都是一个模幂运算，下面说明三种快速模幂算法。 2 3 1 m o n t g o m e r y 算法 1 9 8 5 年p l mm o n t g o m e r y 介绍了一种有效计算r = a x bm o d 玎的算法，这种 算法将模，2 的取模运算转变为对2 的幂次的取模运算。由于计算机采用2 进制来 存放数据，故对处理对2 的幂次进行取模的速度是相当快的，因此该算法特别 适合于计算机瞳2 ，2 3 1 。 m o n t g o m e r y 算法描述1 2 制： 假设n 是一个七位的数2 “1 5 n 5 2 ，令r = 2 ，该算法要求黟讹一= l ，即要求n 是一个奇数，给定整数a n r e t u r nu - n ； e l s e r e t u r nu ； 函数m o d m u l 计算- y = a x bm o d 刀。 m o d m u l ( a ，b ，n ) ( n 为奇数) 哈尔滨理1 二人学丁学硕 ：学位论文 使用扩展欧几里德算法计算y ； a t = a 木r m o d n ； b b b 幸r m o d n ； y k m o n p r o ( a ，b ) ； y = m o n p r o ( y ，1 ) ； r e t u r ny ； ) 从上面的算法可以看到，使用扩展欧几里德算法来计算y 是相当耗费时间 的，而且a ，b 的计算也需要执行模n 的操作，因此该算法对于一次模乘操作是 没有意义的，它的时间消耗比直接计算r 的时间都大，但是考虑到在模幂运算 中，要进行多次对同一模进行模乘操作，那么m o n t g o m e r y 算法在实现模幂运算 的时间将比直接计算模幂的时间要少得多，特别是当幂指数越大，该算法所体 现的优越性就越高。 2 3 2 以“权”为基准的流水式运算 作为实现r s a 算法的核心运算，模幂运算似x b ) m o dc 的效率将影响到 r s a 算法处理数据的整体效率。以计算( 6 8 5 9 ) m o d8 9 为例，贝, u a = 6 8 ，b = 5 9 ， c = 8 9 。将a 记作a i a 0 ，b 记作b l b 0 ，则传统的模幂计算方法除了用m o n t g o m e r y 算法外，常采用如表2 1 所示的方法，其计算步骤是先计算a x b 的值，再算出 似b ) c 的下界值，再用彳与b 乘积的值减去商乘以模的值从而得到取模运算的 结果陷5 一引。 表2 1 传统取模运算方法 t a b l e2 1t r a d i t i o n a lc o m p u t i n gm e t h o d so fm o d u l u s 第一步计算乘积( 彳b ) 4 0 1 2 第二步计算商并取整 ( 彳b ) c 4 5 第三步计算余数 ( 爿x b ) r o o dc 7 r s a 的模幂运算要对1 0 2 4 b i t 的模做模幂运算，这种方法显然不能适用。为 此，引入以“权( w e i g h t ) 为基准的流水线结构。段棚b 和模除运算口功 m o dc 均采用以“权”为基准的流水线方式，用现有的乘法器和除法器资源， 哈尔演理丁人学t 学硕 j 学位论文 分步求出各段商，最后求出余数从而实现超长位宽的模幂运算。用以“权 为 基准的流水线结构，将数据按其“权”对齐进行乘累加，计算出相应“权 的 段商，当所有“权”的段商都计算出来后，再减去相应的模、除、减、积，最 终的余数就是模幂运算的结果。 2 3 3 模缩减方法 p a u lb a r r e t 于1 9 8 7 年在应用数字信号处理器进行r s a 力i 密运算时，引入 了模缩减( m o d u l a rr e d c c t i o n ) 算法。其基本思想是将取模运算中的除法求商 运算 z n 转化为用预先计算好的模的倒数 2 2 伽与明文相乘的求商运算，从而 避开了实现除法运算所需要的硬件开销及除法电路带来的速度瓶颈。如公式 ( 2 1 ) 和( 2 2 ) 所示： z m o d - z - f ( z n ) n = z - z 2 。1 1 2 朋u 2 ( 附1 ) n = z - q x n ( 2 1 ) q = z 2 1 1 f 2 加m 2 肿1 j ( 2 2 ) 公式( 2 1 ) 和( 2 - 2 ) 非常便于硬件实现。被2 ( n - i ) 和2 ”除的运算仅需截 取操作数的最低刀1 和行+ l 二进制位即可而 2 2 咖仅仅取决于模，对于给定的模 是一个常数，可以预先计算出来。这样，看似复杂的取模运算便简化为一个 简单的乘法运算和两个截取运算。不难发现，由于取整运算的影响，取模运算 结果可能比模大，因此进一步将结果减掉或2 m 就能得到最终结果曙引。 执行模幂运算俨m o d 常用的方法是二进制指数方法j 2 引，亦称( 平方乘法 算法) ，采用此方法的模幂运算是将指数e 转换为二进制序列，并对此二进制 序列作特殊处理后，根据二进制序列由高及低各位为“l ”或“0 决定中间结 果是作平方运算后对n 取模还是作乘法运算后对n 取模( 统称为“模乘运 算 ) 。对于两个n 位的二进制整数a n 1 ：0 】与b n 1 ：0 】的乘积对，2 位的二迸制整 数u n 1 ：0 】取模的模乘运算辩叫 ”1 ：0 x b n 1 ：0 】m o du n 1 ：0 】，可以引用b a r r e t 模 缩减方法。得出一种高效率的模乘运算方法： 令z = a n - l ：0 】b 【门1 ：0 】，显然z 除以j v 其商的整数部分q = z n ，主要决定于 数摘于模最高位的“权”重的那些位z 【2 甩1 ：，z 】，并且，由于模是n 位二进制 数，所以数z 的不高于模= 最高位的“权”重的那些位z n 1 ：0 1 对商的整数部分 的影响只是多出一个“l ”的问题，即中间结果可能比币确结果多出模n ，但是 由于连续的模乘运算将抵消多出的模，故不必对中间结果进行修正而只需对最 后结果作一次减模的修正。 哈尔滨理下人学t 学硕f j 学位论文 2 4r s a 模幂算法比较分析 为保证r s a 算法有足够的加密强度，电子商务的s e t ( s e c u r ee l e c t r o n i c t r a n s a n c t i o n ) 协议规定c a 使用2 0 4 8 b i t 的r s a 密钥，其他实体使用1 0 2 4 b i t 的 r s a 密钥1 。这样，在使用r s a 对数据进行处理时，就需要进行大量的模幂运 算，模幂运算的效率决定了r s a 算法的数据吞吐率。 由上一节知道快速模幂运算方法主要包括m o n t g o m e r y 算法、以“权”为基 准的流水式除法运算方法以及b a r r e t 的模缩减运算方法，三种算法的分析比较 如下： 1 m o n t g o m e r y 算法硬件开销小，但数据吞吐率较低，较适合于智能卡等 低端应用。 2 以“权”为基准的流水式除法运算方法数据吞吐率高，较适合于高端应 用( 5 0 0 m h z 时钟频率下约4 0 kb s ) ，但由于组合逻辑的除法器硬件代价高， 且关键路径长( 时间复杂度为o ( n 2 ) ) ，从而系统时钟频率很难提高，造成在高 端应用中的速度瓶颈。 3 b a r r e t 的模缩减运算方法将模幂运算转换成三个乘法运算和一个加法运 算，从而避开了除法运算，大大缩短了硬件电路的关键路径，从而可大幅度提 高系统时钟频率。 2 5 本章小结 本章首先说明了r s a