（信号与信息处理专业论文）基于des、rsa和ecc的混合加密算法研究.pdf

摘要随着计算机技术的发展和网络的普及，网上信息交换日趋频繁和重要，从而需要使用安全的数据加密算法来确保信息交换的安全性。因此，分析和研究现有加密算法，并从中选择比较适合的加密算法用于实际的信息交换是非常重要的。在研究对称加密算法、非对称加密算法和椭圆曲线加密算法的基础上，本文对混合加密算法进行了较深入的研究，主要工作和成果如下：1 对对称加密算法d e s 、非对称加密算法r s a 和椭圆曲线加密算法e c c 等加密算法的实现技术和安全性能进行了研究。2 采用复合公钥加密算法和对称加密相结合的方法，设计了基于d e s ，r s a和e c c 的混合加密算法，并对混合加密算法中的d e s 和l i s a 的模幂运算进行了有益的改进。3 基于上述混合加密算法，给出了一个数据加密传输的方案，进行了实际性能测试和结果分析比较。制关键词：对称加密算法、非对称加密算法、椭圆曲线加密算法、混合加密体r e s e a r c ho fm i x e de n c r y p t i o na r i t h m e t i cb a s e do l ld e s ，r s aa n de c ca b s t r a c tw i t ht h ed e v e l o p m e n to f c o m p u t e rt e c h n o l o g ya n dt h ep o p u l a r i z a t i o no f n e t w o r k ,t h ee x c h a n g eo fn e t w o r ki n f o r m a t i o nb e c o m e sm o r ef r e q u e n ta n di m p o r t a n t ，s ow en e e dt ou s es e c u r ed a t ae n c r y p t i o na r i t h m e t i c st oe 1 1 s t l l - et h es e c u r i t yo fn e t w o r ki n f o r m a t i o n t h e r e f o r e , i ti sv e r yi m p o r t a n tt oa n a l y z ea n ds t u d ys o m ee n c r y p t i o na r i t h m e t i c sa n ds e l e c ta p p r o p r i a t eo d e st oa p p t yi nt h ep r a c t i c a le x c h a n g eo fn e t w o r ki n f o r m a t i o n t h ed i s s e r t a t i o nd e e p l yr e s e a r c h e st h eh y b r i de n c r y p t i o na r i t h m e t i cb a s e do 血s y m m e t r i c a lc r y p t o g r a ma r i t h m e t i c u n s y m m e t r i c a lc r y p t o g r a ma r i t h m e t i ca n de l l i p t i c a lc u r v ec r y p t o g r a ma r i t h m e t i c t h em a i nw o r ka n da c h i e v e m e n t sa r es h o w na sf o l l o w s ：1 d e e p l yr e s e a r c ht h er e a l i z a t i o nt e c h n o l o g i e sa n ds e c u r i t yp e r f o r m a n c ea b o u ts y m m e l r i c a lc r y p t o g r a ma r i t h m e t i c ，u n s y m m e t r i c a lc r y p t o g r a ma r i t h m e t i ca n de l l i p t i c a lc u cc r y p t o g r a ma r i t h m e t i c 2 d e s i g nah y b r i de n c r y p t i o na r i t h m e t i cb a s e do nd e s ，r s aa n de c cm e t h o d s ，i to p t i m i z e sa n da s s e m b l e st h e s ec r y p t o g r a ma r i t h m e t i c s ，a n da m e l i o r a t e sd e sd a t ae n c r y p t i o na r i t h m e t i ca n dr s ad a t ae i l c r y p t i o i la r i t h m e t i c 3 b a s e do i lt h ea b o v eh y b r i de n c r y p t i n ga r i t h m e t i c ，p r o p o s ead a t ae n c r y p t i o i lt r a n s p o r ts c h e m e ，d os o m ep r a c t i c a lp e r f o r m a n c et e s t s ，t h e na n a l y z ea n dc o m p a r et h e i rr e s u l t s k e y w o r 凼：s y m m e t r i c a lc r y p t o g r a ma r i t h m e t i c , t m s y m m e t d c a lc r y p t o g r a ma r i t h m e t i c ，e l l i p t i cc ；u i w ec r y p t o g r a ma r i t h m e t i c ，h y b r i de n c r y p f i o ns y s t e m西北大学学位论文知识产权声明书本人完全了解学校有关保护知识产权的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属于西北大学。学校有权保留并向国家有关部门或机构送交论文的复印件和电子版。本人允许论文被查阅和借阅。学校可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同时，本人保证，毕业后结合学位论文研究课题再撰写的文章一律注明作者单位为西北大学。保密论文待解密后适用本声明。学位论文作者签名：导教师签名：泐7 r 年b西北大学学位论文独创性声明本人声明：所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，本论文不包含其他人已经发表或撰写过的研究成果，也不包含为获得西北大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论文作者签名：j 宝艾? 令加0 7 年6 月7 f 日西北大学颈士学位论文第一章绪论在当前的社会里，随着计算机与通信技术的发展，越来越多的敏感信息通过公共信道和计算机网络进行交换。信息已经不仅仅适用于学术研究，而且涉及到军事、政府、电子商务等一系列应用领域。总而言之，信息已经和人们的日常生活密不可分。随着信息量的增大和复杂度的增加，其安全性和高效性越来越受到人们的关注。因此，研究信息安全中的关键技术加密解密技术，尤其是研究加密解密算法，具有重要的意义。本章介绍课题的背景及意义、研究现状，以及简介本文的主要工作。1 1 背景及意义随着计算机系统和i n t e r a c t 的迅速发展，人们对网络信息的需求在不断增加，对服务质量的要求也越来越高，而其中很重要的一个环节就是信息安全。伴随着计算机网络技术迅速发展的同时，许多公共和私人部门的一些机构愈来愈多她应用电子数据处理，将数据存放到数据库中，防止非法泄露、删除、修改等成为必须正视的问题。在计算机犯罪趋于日益严重的今天，如果不能对数据信息进行有效的保护，就无法满足现有存储和传输的条件和要求。例如，对于银行的电子资金传输系统，就算是使用专用的网络，也仅仅能够减少从外部攻击的可能性；而对于一般的信息传输系统，比如说一个地方的电子政务系统。其被攻击成功的可能性相对要大得多。由此可见，加强信息安全的研究，寻求解决信息安全问题的良方，是信息时代提出的迫切任务。由于传输中的公共信道和存储的计算机系统非常脆弱，为了避免信息在传输过程中受到攻击，除了制订必要的法律外，还需要合适的保护措施，密码技术就是一种有效的方法。密码技术可以有效地用于信息鉴别、数字签名等，用以防止电子欺骗，对信息系统的安全起到极其重要的作用。事实证明，这也是最经济可行的方法，它能够在潜在不安全的环境中保证通信的安全。密码技术的关键是信息的加密和解密，信息的加密和解密就是在保证信息不被非法截取、复制、删除、更改或插入等操作的前提下，在通信中对信息进行存储和传输。正因为如此，研究最佳的信息加密解密方法_直是人们追求的目标。西北大学硕士学位论文1 2 研究现状密码学是加密解密算法研究的关键。密码学以研究秘密通信为目的，即研究对传输信息采取何种秘密变换以防止第三者对信息的窃取。近年来，密码学之所以十分活跃，在理论和方法上都有了巨大的发展，主要原因是它与计算机科学的蓬勃发展息息相关。目前，世界上的许多国家均非常重视加密算法的研究。在近代密码学上有两件大事 1 1 ：一是1 9 7 7 年美国国家标准局正式公布实旅了美国的数据加密标准d e s ( d i g i t a le n e 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 t , s h a m i r 和a d l e m a n 提出并实现了r s a 公钥密码系统，这在密码史上是一个里程碑，可以这么说：“没有公钥密码的研究就没有近代密码学。”d e s 2 1 作为分组密码的杰出代表，在密码学发展历史上具有重要的地位。1 9 7 8 年估计d e s 算法在1 0 1 5 年内安全性不成问题。但是随着计算技术的飞速发展，再加上d e s 产生的各密文块之间没有联系，从而造成了黑客可以对其中的敏感信息进行破坏。另外，它的密钥管理的效率、复杂性及长度的限制，其安全性在后来受到了各方面的质疑。随后d e s 也改进为3 d e s ，采用三组不同密钥对每块信息加密3 次( 速度要降低三分之二) ，并将新的密文块与前一密文块连接一起后再加密，获得了很好的效果。但是由于其速度降低太多，因此在那些安全性能要求较高、实时性要求又很强、用户终端计算处理能力弱的场合和无线网络中都受到了局限。近年来分组密码新的算法【1 】不断涌现，由中国学者来学嘉博士与著名密码学家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 n a l g o r i t h m ) 依靠方法论上的新颖，并且速度快，成为其中的佼佼者。2 0 0 0 年1 0 月美国国家标准与技术研究所确定用比利时密码学家j o a nd a e m e n ，v m c e mg i j m a n 发明的购n d a e l 算法替代d e s 算法，称为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 ) 算法f 2 l 。与此同时，人们还设计了许多新的加密方法1 3 】，例如用于电子邮件加密的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 dp r i v a c y ) 就是这一类加密2西北大学硕士学位论文技术。这类技术应用的优点在于实现相对较为简单，不需要对信息所经过的网络的安全性能提出特殊要求。p g p 使用了r s a ，i d e a 等加密算法，它比d e s 的加密性好，而且计算机功能也不需要那么强。这是一种可以为普通电子邮件用户提供加密、解密方案的安全系统。在p g p 系统中，使用i d e a 的分组长度为1 2 8 b i t ，r s a 用于数字签名、密钥管理，它不但可以对邮件保密以防止非授权者阅读，还能对邮件加以数字签名从而使收信人确信邮件发出者的身份。在网络系统中得到应用的加密算法还有美国国家标准局提出的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 a - 1 以及下面提到e c c 等算法。目前比较流行的公钥密码算法【1 胴主要分为两大类。一类是基于大整数因子分解的算法，其典型代表就是r s a 加密算法；另一类是基于离散对数问题的算法，其有代表性的算法有e i g a m a l 算法，以及基于椭圆曲线上离散对数的e c c 算法。椭圆曲线加密算法是1 9 8 5 年由n k o b l i z 和v m i l l e r 把椭圆曲线密i l j ( e l l i p t i c c u r v ec r y p t o g r a p h y ，简称e c c ) 理论 4 1 应用到公钥密码系统中提出来的，是国内外目前研究的热点。密钥长度为1 6 0 位的椭圆曲线加密算法，其安全性相当于1 0 2 4 位的r s a 加密算法，在通信网的身份认证与密钥分配中更受青睐。目前它已经广泛应用于智能卡、电子商务等业务系统中。e c c 生成私钥公钥方便，节省内存空间、带宽和处理时间。e c c 在1 9 9 8 年被确定为i s o i e c 数字签名标准i s 0 1 4 8 8 8 3 。1 9 9 9 年2 月e c d s a ( 椭圆曲线数字签名算法) 被a n s i 确定为数字签名标准a n s 9 6 2 - 1 9 9 8 ，e c d h ( 椭圆曲线d i 伍e - h e l l m a n 体制版本) 被确定为a n s i x 9 6 3 。2 0 0 0 年2 月被确定为i e e e 标准i e e e l 3 6 3 2 0 0 0 ，同期，n i s t 确定其为联邦数字签名标准f i p s l 8 6 - 2 。2 0 0 0 年1 月欧盟启动了新欧洲数据加密、数字签名、数据完整性计划n e s s i e ，2 0 0 2 年底提出了一套包括强壮的分组密码，流密码，哈稀函数，消息认证码( m a c ) ，数字签名和公钥加密标准的各类算法。其中标准的、高级安全水平的分组密码算法有s a f e r - h - 1 2 8 ，c a m e l l i a ，r c 6 等。由c y l t n k 公司提交的s a i 吧l h 算法是无线蓝牙协议的“挑战响应”实体认证方案。我国网络技术与信息安全2 0 0 5 年资助项目领域有一项就是e c c 安全性( 椭圆曲线离散对数问题e c d l p ) 研究。西北大学硕士学位论文1 3 论文的主要内容和组织本文的工作主要是在密码加密算法理论的基础上，研究基于对称加密算法和非对称加密算法的混合加密算法，具体组织如下：第一章：绪论，主要介绍课题的背景及意义、研究现状。第二章：主要论述了密码学的基础，介绍了数论、群论、有限域理论等数学方面的知识和密码体制的分类情况。第三章i 对d e s 、r s a 、e c c 三种经典加密算法进行了研究。第四章：在第二、三章的理论分析的基础上，对第三章中三种加密算法的优缺点进行了分析，研究了两种公钥加密算法相结合的复合算法，对d e s 和大数的模幂运算迸行了有益的改进，设计了基于多种加密算法相融合的混合加密算法。第五章：总结和展望，对全文进行总结并指出不足之处和今后的研究方向。4西北大学硕士学位论文第二章密码学基础在本章中，我们首先介绍了密码学的数学基础，以及密码学的基本概念和密码体制，这是本文后续章节的基础。2 1 数学准备近代密码学越来越多地用到数学，所涉及的数学不仅仅是数论和有限域理论，而且遍及许多其他数学分支，如概率统计、信息论1 5 、数论【6 】、有限域理论、复杂性理论、编码理论，甚至于代数几何等都在近代密码学中扮演了重要角色，不过应该强调的是数学在这里仅仅是一种工具，一种不可或缺的工具。2 1 1 数论1 数的e l l 进制表示人们习惯于十进制的表示方法，比如1 2 3 ，实际上是1 2 3 = l x l 0 2 + 2 x 1 0 + 3但是在计算机里使用l o 进制数表示法非常不方便。事实上，使用任何进制表示一个数都是可以的，只不过在计算机中适宜于2 迸制表示法，目前这种进制已为人们所熟知。2 因数分解我们把只能被1 和自身除尽的数称为素数，不是l 且非素数的数称为合数。下述中a ，b ，c 均表示正整数。a 除尽b 表示为a i b ，如果aj b ，_ r a l c ，就说a 是b 和c 的公因子。若a 是b 和c 的公因子，且b 和c 的每一个公因子均除尽a ，则称a 是b 和c 的最大公因子，用( 6 ，c ) 或g e d b ，c 表示，即a = ( 6 ，c ) 或n = g e d b ，c 例如5 = 0 0 ，1 5 ) 。若a l c ，则称c 是a 的倍数，若a i c ，bj c ，则称c 是a 和b 的公倍数；如果口和b西北大学硕士学位论文的公倍数c 除尽a 和b 的任一个公倍数，则称c 是a 和b 的最小公倍数，表示为c = k ，6 】或c = l c m a ，b 例如，3 0 = 【5 ，1 0 ，1 5 。3 模算术运算已知一个整数拧，所有整数都可以划分为是n 的倍数的整数与不是雄的倍数的整数。对于不是疗的倍数的那些整数，我们又可以根据它们除以r l 所得的余数来进行分类，数论的大部分理论都是基于上述划分的。对任意整数挖和任意整数a ，存在唯一整数g 和r ，满足0 r s 聆，并r a = q n + r ，值g = 栉j 称为除法的商，l x j 表示小于或等于r 的最大整数。，= 口m o d 一称为除法的余数，因此对于任意整数均可以表示为口= ，厅j n + ( a m o d n ) 或者a m o d n = a 一，疗j 雄例如，a = 1 7 ，n = 7 ，1 7 = 2 x 7 + 3 ，因此q - - - 2 ，r = 3 ，记作1 7 r o o d 7 = 3 。如果( a m o d n ) = ( b m o d n ) ，则称整数a 和b 模疗同余，记作a i b r o o d n ，换言之也就是a b i k n 。下面给出了模运算的性质：自反性，即口i a m o d n对称性，即若口i b m o d n ，则6 i a m o d n传递性，即若a = - b m o d n ，b ；c m o d n ，则a i c m o d n除了具有上述性质外，模运算还满足( 1 ) 交换律q + b ) m o d nip + a ) m o d n0 x b ) m o d n p x a ) m o d n( 2 ) 结合律( ( a + b ) + c ) m o d n ；q + p + c ) ) m o d n( ( 口x b ) x c ) m o d n i ( 6 c ) ) m o d n( 3 ) 分配律x p + c ) ) m o d n = ( ( a x b ) + ( a x c ) ) m o d n4 欧拉定理和费尔玛定理( 1 ) 欧拉定理若a 和m 互素，则一帕- l m o d m此处的( 功是指比所小但与历互素的正整数的个数，称为m 的欧拉函数。它的另一种6西北大学硕士学位论文等价形式是口i 口“”hr o o d m( 2 ) 费尔玛定理若聊是素数，( 口，m ) = l ，则口”- 1 ；l m o d m其等价形式是a ”；a m o d m这两个定理及其推论在证明r s a 算法的有效性时是非常有用的，给定两个素数p和g ，以及整数所和厅= p q ，其中0 ，l n ，则口，d m m ( e - 1 x g 一1 ) m m o d n5 素数的判定因子分解问题是困难问题。如果p 为2 0 0 位十进制数，那么对p 进行素数的因子完全分解大概要花费几十亿年。所以，密码体制都是建立在大数的因式分解的基础上。正因为如此，如何判定一个数是否是素数，在密码学中是至关重要的。判断一个整数是不是素数的过程叫素性检测。目前仍然没有一个简单有效的办法来确定个大数是否是素数。理论上常用的方法有：( 1 ) w i l s o n 定理：若( p 1 ) ! ；一l m o d p ，则p 为素数：( 2 ) 穷举检测：若万不为整数，且p 不能被任何小于石的正整数整除，则p 为素数；但是这些理论上的方法在p 很大时，计算量太大，不适合密码学中使用。现在常用的素性检测的方法是数学家s o l o v a y 和s t r a s s e n 提出的概率算裂。即在某个区间上能经受住某个概率检测的整数，就认为它是素数。2 1 2 群论定义给定一集合g = 口，b ， 和该集合上的运算+ ，满足下列四个条件的代数系统 称为群 7 1 ：( 1 ) 封闭性：若口b g ，则存在c g ，使口b = c ；( 2 ) 结合律成立：a , b ，c g ，恒有0 + 6 ) + c = 口+ ( 6 + c ) ；( 3 ) 存在单位元素e ：即存在e g ，对于v a g ，恒有a + f = p a = a ；( 4 ) 存在逆元素：对于v a g ，恒有b g 使口b = b * a = g7西北大学硕士学位论文元素b 称为a 的逆元素，用a _ 1 表示，即b = a 一。若对a ，b e g ，有口+ b = 矗。口，则称 为阿贝尔( a b e l ) 群。为方便起见，我们记a + 6 = a b 。群的性质：( 1 ) 群的单位元p 是唯一的；( 2 ) a ，b ，c g ，若a b = a c ，则b = c ；若曲= 西，则a = c ：( 3 ) g 的每一个元素的逆元是唯一的：( 4 ) 群 的元素a ，若( 口y = a + + 口) = e诎使上式成立的最小正整数刀称为元素a 的阶，并且有限群g 的每一个元素的阶也是有限的。2 1 3 有限域理论定义f 是至少含有两个元素的集合，对f 定义了两种运算“+ ”和“一，并且满足以下三个条件的代数系统 称为域【刀。( 1 ) f 的元素关于运算“+ ”构成阿贝尔群，设其单位元为0 。( 2 ) f 、 o ) 关于运算“+ ”构成阿贝尔群。( 3 ) 对于a ，b ，c f ，分配律成立。即0 + 6 ) + c = a c + b + cc + ( 4 + 6 ) = c + a + c + bf 、 o ) 表示集合f 除去元素 o 后的元素。如果域f 的元素为有限个，则称之为有限域或者伽罗瓦( g a l o i s ) 域。常用的有限域是素数域e 和特征为2 的有限域。这里介绍其中的一种。素数域b 的定义为：设p 是一个素数，整数集合 0 ，l ，2 , - - - p l 构成一个有限域，记为r 其运算如下：( 1 ) 昂的加法运算：设x ，y 是耳中的元素，则加法结果为( x + y ) m o d p 。加法单位元即为零元素：o ；域元素工的加法逆元为：( - x ) r o o d p 西北大学硕士学位论文( 2 ) 耳的乘法运算：设x ，y 是届中的元素，则乘法结果为( x y ) m o d p 。乘法单位元：l ；非0 元素x 的乘法逆元为y ，其中y 满足x y = l ( m o d 乃。2 2 密码学基本概念什么是密码【2 】【5 】，简单地说它就是一组含有参数后的变换e 。已知信息聊，通过变换匠得到密文c ，即c = e ( 坍)这个过程称之为加密，参数t 称之为密钥。加密算法e 确定以后，随不同的密钥后生成不同的密文c 。下面给出一个传统的保密通信原理图，如图2 1 所示。埘发送( 秘密信遒)图2 1 传统保密通信原理图在上图中，明文m ( m e s s a g e ) 是指发送方想要发送给接受方的消息，从明文m 到密文c ( c i p h e rt e x t ) 的过程称之为加密( e n e r y p t i o n ) ，从密文c 到明文m 的过程称之为解密( d e c r y p t i o n ) 。解密算法d 是加密算法e 的逆运算，解密算法也是含有参数七的变换。传统保密通信加密使用的密钥和解密使用的密钥是相同的，因此，也可以称为对称加密。由上述原理我们可以很容易看到，密钥k 的重要性和加密算法e 的重要性。密钥后由通信双方通过秘密方式私下约定产生，而且只能由通信双方掌握密钥k 。对于加密算法e ，要求计算e 沏) 不困难，而且若第三方不掌握密钥k ，即使截取了密文，也不能把密文c 恢复到明文m ，也就是说反过来由密文f 求明文聊极为困难。密码学【1 1 1 2 ( c r y p t o l o g y ) 是研究信息系统安全保密的科学。包括两个分支，即密码编码学和密码分析学。密码编码学( c r y p t o g r a p h y ) 是对信息进行编码实现信息隐蔽的技术和科学。密码分析学( c r y p t a n a l y s i s ) 是研究分析破译密码的技术与科学。这些基本的概念将伴随本文的始终。9西北大学硕士学位论文2 3 密码体制2 3 1 密码体制的概念一个密码体制嘲s 可定义为s = ( 膨，c ，k ，e ，d ) ，其中m 是明文空间( 亦称信息空间) ，c 是密文空间，k 是密钥空间，是加密映射族，d 是解密映射族。用m 表示明文，c 表示密文。加密变换巨( 聊) ，解密变换以( c ) 。对于v m m ，跣( & ( 彬) = 掰成立，则称该密码体制具有保密性；齐 i q f - v m e m ，暑( 协) ) = 拼成立，并且解密的密钥只能被唯一的数据传输实体接收，则称该密码体制具有认证性。当我们强调一个密码体制的保密功能时，称该密码体制为加密体制：强调一个密码体制的认证功能时，称该密码体制为签名体制；强调一个密码体制的密钥交换功能时，称该密码体制为密钥交换体制。2 3 2 密码体制的分类密码体制从原理上可分为单钥密码体制和双钥密码体制两大类。单钥密码体制又称为对称密码体制，双钥密码体制又称为非对称密码体制或者公钥密码体制【8 1 。对称密码体制，在加密与解密时都是使用同一把密钥进行加密解密。因此，信息的发送者和信息的接收者在进行信息的传输与处理时，必须共同持有该密码。对称密码体制通常使用的加密算法比较简便高效，密钥简短，数学运算量小，加密与解密速度极快。d e s 算法是目前最为典型的对称密钥密码系统算法，除此之外，比较有代表性的算法还有3 d e s ，g o s t 。下面给出对称加密的原理图，如图2 2 所示。密文c m明文m图2 2 对称加密原理图在押用户网络环境下，着所有用户都需要加密服务，则其中某个用户与另外的万一1个用户沟通，就需要n 一1 个信息，即疗一1 对密钥：对整个网络而言，若在两者间分配1 0西北大学硕士学位论文一对密钥，则需刀一1 ) 2 对密钥。如此多的密钥，是难以有效管理的。另外，对称密码体制的密钥不能与密文一起传送，而必须在另外一个保密的安全信道里传送。由于系统的安全性依赖于密钥的安全性，泄漏密钥就意味着任何人都能对加密信息进行解密。所以，在公开的计算机网络上安全地传送和保管密钥是一个严峻的问题。自1 9 7 6 年d i f f i e 和h e l l r n a n 发表了具有开创性的论文以来，公钥密码学获得了很大的发展。公钥密码体制是把加密密钥和解密密钥分离，前者一般通过公共数据库或在传输中对外公开，根据不同的算法可用于加密信息或验证数字签名；后者则必须秘密保存，根据不同的算法可用于解密信息或进行数字签名。其加密密钥与解密密钥是一组相对的密钥，每一组密钥对包含两把相互对应的密钥，一把为可以公开的加密密钥( 简称为“公钥”) ，另一把为必须保密的解密密钥( 简称“私钥”) ，而且自公钥很难推导出私钥。用公钥加密的信息只能用私钥解密，反之亦然。由于公钥算法不需要联机密钥服务器，密钥分配协议简单，所以便于密钥的管理，但是它的速度很慢。除加密功能外，公钥系统还可以用于信息发送者的身份验证( a u t h e n t i c a t i o n ) 或数字签名( d i g i t a ls i g n a t u r e ) 。r s a 算法是目前较著名的非对称密钥密码系统算法。下面给出了对称加密的原理图，如图2 3 所示。啊育m 广密文e m 广 啊文m叫加密模块卜刊帮密横蜓卜一+公开售造节愀方l 啷锄| 揪收方卜一该密码体制的特点是数学运算量大，加密速度相对于对称密码慢，对选择密文攻击脆弱。另外，公钥密码体制所需要的密钥数量少，在n 用户网络环境下，如果每个用户都要求加密服务，某用户与其他用户之间只需l 对密码，而对称密码体制则需用一一l 对；对整个网络而言，公钥加密方式也只需要一对密码，远远少于对称密码体制的n ( n z ) 2 对公钥密码体制主要分为：( 1 ) 基于整数因式分解的公钥密码技术，如r s a ，r w ；( 2 ) 基于离散对数的公钥密码技术，如d s a ，d h ，m q h ，e 1 g a m a l ；西北大学硕士学位论文( 3 ) 基于椭圆曲线的公钥密码技术。公钥密码体系使用的加密技术的安全强度都是基于一些数学难题，这些难题被专家们认为在短期内不可能得到解决。一些问题( 如因式分解问题) 至今已有数千年的历史了。对称密码和公钥密码都有自身的局限性，而彼此恰好可以由另一种密码体制来弥补。比如对称密码加密效率高，但加密密钥和解密密钥相同，不利于在网上传输；而公钥密码虽然加密效率低，但由于其加密密钥和解密密钥的不同，互不存在推导性而不需要在网上传输解密密钥 9 1 1 1 0 3 。因此，可以结合对称密码和公钥密码进行信息加密，即利用对称密码体制的高效性，使用对称加密方法对大量传输信息进行加密：利用公钥密码体制的保密性好的特点，对对称加密方法中使用的密钥进行加密，来达到保密通信的目的。如何取长补短，建立起有效的系统，正是混合密码体制【l l 】研究的核心。混合密码体制的出现对于i n t e m e t 上电子商务及电子政务的开展都具有非常重要的意义。在由m m 等公司联合推出的用于电子商务的协议标准s e t ( s e c u r e e l e c t r o n i ct r a n s a c t i o n ) 中以及多国联合开发的p g p ( p r e t t yg o o dp r i v a c y ) 中，均采用了混合密码体制，包含单钥密码、双钥密码、单向杂凑算法和随机数生成算法等。由此可见，混合密码体制将成为密码学发展的一个重要方向，其应用前景非常广泛。西北大学硕士学位论文第三章经典加密算法的研究经典的加密算法大致分为两大类，即分组密码算法和公钥密码算法【l l f 4 】。分组密码算法即对固定长度的一组明文进行加密的一种加密算法。其中比较突出的具有代表性的算法有d e s 加密算法，i d e a 密码算法，a e s 加密算法，r c 5 加密算法，r c 6 加密算法，t w o f i s h 密码算法等等。公钥密码算法是相对于分组密码算法而言，不像分组密码那样，在通信之前就要约定共同的私钥，这在密钥的分发和管理方恧造成了很多浪费和不便。而公钥密码算法使得通信双方均拥有自己的公钥和私钥，通信过程中用户a 欲与用户b 保密通信，可用自己的私钥及b 的公钥来获取通信密钥，保密通信依然按照传统密码进行。本章我们将选取分组密码中的d e s 算法，公钥密码中的r s a 算法和椭圆曲线密码算法作为典型来进行研究。3 1d e s 加密算法3 1 1d e s 的发展历史1 9 7 3 年美国商业部所属的美国国家标准局( n b s ) 先后两次向公众发出了征求加密算法的公告。加密算法要达到的目的【1 2 】( 通常称为d e s 密码算法要求) 主要为以下4 点：( 1 ) 提供高质量的数据保护，防止数据未经授权的泄露和未被察觉的修改；( 2 ) 具有相当高的复杂性，使得破译的开销超过可能获得的利益，同时又要便于理解和掌握；( 3 ) d e s 密码体制的安全性应该不依赖于算法的保密，其安全性仅以加密密钥的保密为基础；( 4 ) 实现经济，运行有效，并且适用于多种完全不同的应用。1 9 7 3 年首次公布d e s 算法描述，并进行公开讨论。1 9 7 7 美国国家标准局( n i s t ) 公布由i b m 公司研制的一种加密算法，批准它作为非密部门使用的数据加密标准，简称d e s 。d e s 是d a t ae n c r y p t i o ns t a n d a r d 的缩写1 3西北大学硕士学位论文原先规定d e s 的使用期为1 0 年，由于d e s 没有受到严重威胁，再加上新的数据加密标准研制尚未完成，d e s 超期服役到2 0 0 0 年。2 0 多年来，它直活跃在国际保密通信的舞台上，扮演着十分重要的角色。3 1 2d e s 算法描述及实现流程d e s 算法的分组长度为6 4b i t ，密钥k 也是“b i t ，但只有5 6b i t 有效，其他8 位是奇偶校验位。算法主要包括，初始置换、1 6 轮迭代的乘积变换、逆初始置换以及1 6个子密钥产生。6 4 位一组的明文从算法的一端输入，6 4 位的密文从另一端输出。我们假定加密信息为m = 玛m u ，密钥k = 与岛，事实上，在加密过程中，密钥中的毛，k ，k ，岛，k z ，k 是不起作用的。d e s 的加密过程可表示为d e s ( m ) = i p 。1z i 6 写5 五五j p ( ，z )其中三p 为初始置换，上p 。为其逆置换。其置换矩阵如图3 1 和图3 2 所示。l o21 241 461 689ll l31 351 574 81 65 6 2 4 6 4 3 24 71 55 52 36 33 l4 61 45 4 2 2 6 2 3 04 51 35 3 2 16 12 94 41 25 2 2 0 6 02 84 3l i5 l1 95 9 2 74 2i o5 01 8 5 82 64 194 91 75 7 2 5图3 1 p 矩阵图3 2i p 逆矩阵初始信息m ( 明文) 经过初始置换妒之后，明文分为两个部分磊和民，各3 2 比特，随后执行1 6 轮的迭代密码，其中迭代算法如下：= 置一，置= 厶一。o ，( 冠一。，毛)o 为按位作不进位加法运算，即1 0 0 ：0 0 1 = 1 ，0 0 0 = 1 0 l = 0。此处置是6 4 比特的密钥产生的子密钥，置是4 8 位。下面我们给出d e s 加密算法迭代过程的流程图，见图3 3 。8765432l加矜勰竹靳剪弘驺矿博趁拼侉甜筋拍勰如砣药”孔弘弘强加驺卯鲫舵辑拍诣叭躬盯盯轮弭斯孵班站舔懿酡甜卯盼甜酷旷西北大学硕士学位论文lz plil上i上0ilrl工i = rll8 = 厶。厂( r ，毛)厶= 8足= 厶 f ( p h ，岛)l 二，= 二一。厂一1k = 兄i 足，= 上l 。o 厂( 墨。，气，)扣划qi 墨。= ，o ( r ，k ) ilk = 足，illi p - 1i图3 3d e s 加密迭代流程图其实，d e s 加密算法的关键在于，( 置，毛) 的功能，它将3 2 比特输入转化为3 2 比特输出，见图3 6 。e ( 图3 4 ) 的作用时将3 2 比特的输入膨胀为4 8 比特。而置换p3 2l23451 672 02 14567892 91 22 81 7891 0l l1 21 311 52 32 6e1 21 31 41 51 61 7尸51 83 11 01 61 71 81 92 02 1282 41 42 02 l 挖2 32 4 2 53 22 7392 42 52 6 2 7 2 8 2 91 91 33 062 82 93 03 13 2 3 32 21 14 2 5图3 4矩阵e图3 5矩阵p西北大学硕士学位论文( 图3 5 ) 的作用是把3 2 比特的输入改变次序输出。图3 6 中s l 至s 的作用是把4 8墨一3 2 比特)3 2 e 特图3 6八稚。，t ) 功能图比特的输入转化为3 2 比特的输出，下面给出s 表中的s 表，如表3 - 1 所示。表3 - 1s 表0l234567891 01 11 21 31 41 501 441 3l21 51 1831 061 25907墨l01 5741 421 3ll o61 21 195382411 481 3621 11 5 1 29731 05031 51 28249l751 131 41 0061 3我们假定盒的6 个输入端为6 1 6 2 岛6 4 以，在表中找出6 1 6 6 行，6 2 岛良岛列的元素，该元素就是墨盒的输出。例如s 的输入为1 1 0 0 1 0 ，a = l ，玩= o ，龟= ( 1 0 ) 2 = 26 2 岛6 4 如= ( 1 0 0 1 ) ：= 9由s 表可以查得墨( 2 ，9 ) = 1 2 ，故s 的输出为1 1 0 0 ，依次类推可以查得别的输出接下来我们来谈一下子密钥毛的生成，首先密钥囊经过p c 一1 的置换由6 4 比特转化为5 6 比特，并且分为左右两部分c 0 和d o ，c o 和d o 各为3 2 比特，然后经过表3 2中的循环左移，随后依次经过，c 一2 的转换得到1 6 个4 8 比特的子密钥。此处p c l 中不出现8 的倍数位，p c 一2 是从5 6 位中选出的4 8 位输出1 6西北大学硕士学位论文表3 - 2循环左移表选代顺序i1234567891 01 l1 21 31 41 51 6左移位敷l1122 2222t2222221举例如下：假设g = q c 2 d 3 = 盔如如我们查表可知第四次迭代应该左移循环两次，则c 4 = c 3 c 4 c 2 s q c 2 ，q = 砖以吐8 4 吃3 1 3d e s 算法的安全问题对于d e s 的安全性【1 3 1 【1 4 1 ；人们普遍感兴趣的是它的抗攻击性，也就是针对它密钥长度来做文章。事实上，d e s 的密钥仅有5 6 比特。d i f f i e 和h e l l m a n 曾花费千万美金造专用机，利用穷举法进行强行攻击。1 9 9 0 年e l ib i h a m 和a d is h a m i r 提出一种“差分分析法”。在选择明文条件下，复杂度有所下降。此外，d e s 算法在极端情况下，存在弱密钥和半弱密钥，给破译带来了便利。d e s 算法由于密钥太短，超期服役的时间也太长，再加上新的攻击手段不断出现，已经面临着实实在在的威胁【l s l 。其中最直接的威胁来自于专用设备，由于芯片的速度越来越快，造价越来越便宜，专用设备的造价也大大地降低。3 2r s a 加密算法r s a l 4 1 是由r i v e s t ，s h a m i r 和a d l e m a n 联合设计的。r s a 的基础是数论的欧拉定理。它的安全性依赖于大数分解的困难性，它既可以用于加密数据。也可以用于数字签名。3 2 1 r s a 算法描述1 r s a 加密算法密钥的生成：( 1 ) 选取两个大素数p 、q ：( 2 ) 计算出n = p q ，双哟= ( 尹一1 ) + ( q - 1 ) ；( 3 ) 随机选一整数e ，满足g c d ( e ，烈砌= l ；1 7西北大学硕士学位论文( 4 ) 计算d ，满足d e i l m o d 烈，1 ) ；( 5 ) 销毁p 和g 及伊( 彩；( 6 ) 得出所需的公钥和密钥：公钥为e = 他疗私钥为d = i d ，m2 r s a 加密、解密的变换首先将明文分块并数字化，每个数字化明文块的长度不大于l l o g ：厅j 。然后对每个明文块m ( o s 小s 吣依次进行加密变换和解密变换：( 1 ) 加密变换：使用公钥p 和加密密文班，即c = 聊。m o d n ：( 2 ) 解密变换：使用私钥d 将密文c 解密，获得明文所，即掰= 一r o o d n ：由于算法依赖于大数的因子分解的困难性，如果大数厅被分解成功，则r s a 便被攻破，所以建议p 和g 为1 0 0 位十进制数。到目前为止，本文认为r s a 是安全的，它能适应网络的开放性要求，且密钥管理问题也较为简单。由于r s a 涉及到高次幂运算，所以实现速度较慢，不适用于加密大数据量信息。下面给出了r s a 算法的流程图，如图3 7 所示。选择1 0 2 4 位的大素数p 和qi甩= p + 鸟l反力2 p l x g 1 )l选择加密密钥el求解密密钥dd = e - l = e r m d 议n )i加密c = ，矿m o d n解密m = m o d n图3 7l i s a 的实现过程1 8西北大学硕士学位论文3 2 2r s a 算法中n 、d 、e 的确定1 九的确定在l i s a 体制中，要求p ，q 必须是素数，否则算法不成立。因此在第一步选取p ，譬的时候，必须判定它是不是素数【1 6 l 。根据修改的欧拉定理，如果p 为素数，则对于x 的所有整数值，应满足：j ”1i l m o d p这是一个必要条件而非充分条件，不过，如果有5 个以上的x 值能满足上述条件，则p 可基本断定为素数。图3 , 8 是产生素数的流程图，该流程图