（计算机应用技术专业论文）基于椭圆曲线的混合加密系统的研究实现.pdf

大连理t 大学硕士学4 节论文 摘要 网络安全密切关系到信息社会各方面的利益，其技术也成为信息技术中不可或缺的 组成部分。其中数据加密技术被誉为信息安全的核心技术。椭圆曲线公钥密码学 e c c ( e l l i p t i cc u r v ec r y p t o g r a p h y ) 是当今加密学中的研究热点之一，同已经广泛应用的 r s a 密码体制相比，有密钥短、带宽低、速度快等优势，目前国内外很多密码学研究小 组及一些公司开发了椭圆曲线密码体制相关产品，许多标准化组织已经或正在制定关于 椭圆曲线的标准。 但是e c c 的研究历史并不长，应用方面同r s a 等相比并不算成熟。目前加解密体 制中无有效的编码算法，其他算法也存在问题，导致加解密处理速度并不适合网络传输； 并且e c c 由于本身的公钥体制特点，算法复杂，效率方面不如对称算法。论文主要通 过研究改进椭圆曲线公钥密码学，设计实现了一个基于椭圆曲线的混合加密系统。 椭圆曲线数学运算较多，包括有限域运算和椭圆曲线点群运算，论文分析了椭圆曲 线快速算法，并在混合加密系统中加入了一种优化算法。其次椭圆曲线域参数和公私钥 要进行有效性验证以确保不产生漏洞，论文应用c a 认证技术、口令加密技术p b e 和椭 圆曲线密钥交换协议e c m q v ( e i i i p t i cc u r v em e n e z e s q u v a n s t o n e ) 来确保相关的安全。 为了实现混合加密系统，论文应用对称算法i d e a ( i n t e r n a t i o n a l d a t a e n c r y p t i o n a l g o r i t h m ) 来保证信息的保密性，对于i d e a 生成的会话密钥使用改进的椭圆曲线 m e n e z e s v a n s t o n e 算法加密来进行安全、快速有效分发传送，进一步加入椭圆曲线数字 签名e c d s a ( e l l i p t i cc u r v ed i g i t a ls i g n a t u r ea l g o d t h m ) 和消息摘要s h a l 算法来保证信 息的完整性、可验证性和抗抵赖性。测试结果表明论文的椭圆曲线混合加密系统同改进 前比提高了椭圆曲线加解密速度，更有效地实现网络中信息的安全。 关键词：网络安全；椭圆曲线；密码学 孟凡生：基于椭圆曲线的混合加密系统的研究实现 s t u d ya n dr e a l i z a t i o no fah y b r i dc r y p t o s y s t e m b a s e do ne l l i p t i cc u r v e a b s t r a c t t h es e c u r i t yo fn e t w o r ki sc l o s e l yr e l a t e dt ot h ei n t e r e s t so fo u ri n f o r m a t i o ns o c i e t y a n d t h et e c h n o l o g i e so ft h es e c u r i t yo fn e t w o r ka r ei m p o r t a n tr o l e si ni n f o r m a t i o nt e c h n o l o g i e s a m o n gt h e s e ，d a t ae n c r y p t i o nt e c h n o l o g yi ss a i dt ob et h ec r i t i c a lo n e e l l i p t i cc u r v e c r y p t o g r a p h yi so n eo ft h em o s ti m p o r t a n tc r y p t o g r a p h y ，a n dc o m p a r e dt or s aw h i c hi s a l r e a d yw i d e l yu s e d ，h a st h ea d v a n t a g e so fh a v i n gs m a l lk e ys i z e 、l o wb a n d w i d t ha n dh i | g h e n c r y p f i o ns p e e d n o w a d a y s ，m a n yg r o u p sa n ds o m ec o r p o r a t i o n sb o t hi n s i d ea n do u t s i d eo u r c o u n t r yd e v e l o pp r o d u c t so fc r y p t o s y s t e m so fe c c ，a n dm a n yo r g a n i z a t i o n sh a v eb e e n m a k i n gs t a n d a r d i z a t i o n sa b o u te c c b u tt h ei n v e s t i g a t i o nh i s t o r yo fe c ci ss h o r t e rt h a nr s aa n dt h ea p p l i c a t i o ni sa l s ol e s s n o wt h e r ei sn o ta n yv a l i dc o d i n ga l g o r i t h mi ne n c r y p t i o na n dd e c r y p t i o na n do t h e r s a l s o h a v es o m ep r o b l e m s ，s ot h es p e e do fe n c r y p t i n ga n dd e c r y p t i n gm e s s a g e si sn o ts u i t a b l ef o r n e t w o r kt r a n s m i s s i o n ；a l s ob e c a u s eo fi t so w nc h a r a c t e r i s t i c so fp u b l i ck e ys c h e m eo fe c c ， t h ea l g o r i t h mo fe c ci sc o m p l e xa n dl e s se f f i c i e n tt h a nt h es y m m e t r yo n e s b ys t u d y i n ga n d i m p r o v i n go ne c cm a i n l y ，t h i sa r t i c l ed e a l sw i t ht h ed e s i g na n de n c r y p t i o na l g o r i t h m i m p l e m e n t a t i o no fah y b r i dc r y p t o s y s t e mb a s e do ne l l i p t i cc u r v e t h em a t ha l g o r i t h mo fe l l i p t i cc u r v eh a sm a n yo p e r a t i o n si n c l u d i n gt h eo n e so v e rf i n i t e f i e l da n dp o i n tg r o u p ，a n dt h i sp a p e ra n a l y z e st h eo p t i m i z e da l g o r i t h mo n eo fw h i c hi sa d d e d i nt h eh y b r i dc r y p t o s y s t e m t h ev a l i d i t yo fd o m a i np a r a m e t e r s 、p u b l i ca n dp r i v a t ek e y so f e l l i p t i cc u l w es h o u l db ev e r i f i e d s o a st oa v o i dw e a k n e s s e s ，a n dt h i sp a p e ra p p l i e sc a a u t h e n t i c a t i o n 、p a s s w o r de n c r y p t i o nt e c h n i q u e sp b ea n de l l i p t i c c u r v ek e ya g r e e m e n t e c m q v t oe n s u r et h ec o r r e l a t i v es e c u r i t y a n di no r d e rt or e a l i z et h eh y b r i dc r y p t o s y s t e m ， t h i sp a p e ra p p l i e si d e at ok e e pt h ei n f o r m a t i o ns e c r e t ，t h es e s s i o nk e yo fi d e aw h i c hi s e n c r y p t e db ye c c i ss e c u r e l ya n de f f i c i e n t l yd i s t r i b u t e d ，a n dt h i sp a p e ra p p l i e se c d s aa n d m e s s a g ed i g e s ta l g o r i t h ms h a lt ok e e pm e s s a g e si n t e g r a t e d 、v e r i f i a b l ea n du n d e n i a b l e t h e t e s tr e s u l ti n d i c a t e st h a tt h eh y b r i dc r y p t o s y s t e mb a s e do ne l l i p t i cc b r v eh a sab e t t e rs p e e da n d m o r ee f f i c i e n t l yk e e p st h em e s s a g e st h r o u g hn e t w o r k ss e c u r et h a no l d e ro n e s k e yw o r d s ：n e t w o r ks e c u r i t y ：e l l i p t i cc u r v e ；c r y p t o g r a p h y 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名：圣坐日期：鲨生! 兰a 堕量 火连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文。 作者签名：逝 聊签名：) 缚 二塑生年旦月l 日 大连理r 大学硕士学位论文 1 绪论 1 1 课题背景 网络带来了信息社会的繁荣，日益影响社会的各个方面，从最初单纯的军事应用、 学术研究到如今政府上网、海关上网、电子商务、网上娱乐等一系列网络应用，正在快 速融入到人们生活的方方面面( a t m 取款和电子商务等) 。信息资源也要经过生产、分配、 流通、消费的环节，如果没有安全的网络通信措施，那么信息可用性会大大降低；更由 于网络的开放性，利益导致人为攻击，出于各种目的的信息窃取、网络入侵和攻击也越 来越频繁，黑客攻击事故频频发生，造成的损失越来越大；另一方面，网络应用已渗透 到金融、商务、国防等等关键领域，其安全日益成为与国家、政府、企业乃至于每一个 人的利益息息相关的大事。 通过计算机进行社会交流，就像面对面交流一样，某人是否就是他说的人，某人的 身份证明文件( 驾驶执照、医学学历或者护照) 是否有效，声称从某人那里来的文件是否 确实从那个人那里来的，这些事情都是通过鉴别、完整性和抗抵赖来实现的。数据加 密技术是最基本的网络安全技术，被誉为信息安全的核心，不仅可以保证信息的保密性， 而且可以保证数据的完整性、身份验证、抗抵赖性【1 】。椭圆曲线密码体制与量子加密、 混沌加密是当今密码学中的三大研究热点，其中椭圆曲线在公钥密码学( 即非对称密码 学1 领域中以其有安全性能高、计算量小、密钥长度短、处理速度快、存储空间占用小 和带宽要求低等特点而有着广泛的应用前景，目前有一些标准文档和产品问世。 1 2 课题研究的意义 目前看来，2 1 世纪密码学方面最有研究价值的是量子加密、混沌加密和椭圆曲线加 密。前两者的研究一般用于序列密码和其他加密方面，而椭圆曲线密码属于公钥加密领 域，是国际上研究较多的比较安全实用的公钥密码体制。并且目前建立的各种安全信息 传输和交换系统而言，他们的安全框架都是按照公钥密码学理论构筑的，如今椭圆曲线 的研究正成为热点 2 r 7 。椭圆曲线加密算法e c c 的安全性，是基于计算有限域上椭圆曲 线点集所构成的可交换群群上定义的离散对数的困难性。该算法具有安全性能高、计算 量小、处理速度快、存储空间占用小和带宽要求低等特点，己在速度要求苛刻的领域如 p d a 、手机、智能卡等方面得到应用。 椭圆曲线加密体制的优点主要表现为以下几个方面： ( 1 ) 节省存储空间 盂凡生：基丁i 椭圆曲线的混合加密系统的研究实现 在提供相同安全级时，e c c 的系统参数和密钥长度比其它的非对称加密算法短，这 可以节省较多的存储空间，使得其它程序可利用更多的存储器来完成复杂的任务。 ( 2 ) 节省带宽，提高实用性 采用e c c 所设计的安全服务，签名和加密短消息时，需要传输的数据相对较短， 从而减少了传送的时间并能够用于带宽受到限制的场合。 ( 3 ) 节省处理时间 其它公开密钥系统需要更多的计算时间。 ( 4 ) 能够适应未来更高安全的需要 当需要更高的安全性时，需要使用更长的密钥。e c c 能够继续提供安全服务而只需 增加很少的系统资源。 ( 5 ) 生成私钥公钥对很方便 在私钥公钥对生成方面，e c c 也具有独特的优点。当前使用其它椭圆曲线加密系统 的设计与实现类型公钥系统的应用中。因为计算复杂性的原因，在智能卡中产生密钥是 不现实的，私钥装入卡中要求在一个安全环境中来进行。但是在e c c 中，产生密钥对 的时间非常短，因为它基本上只需一个随机数生成器就可以了，即使在计算能力非常有 限的智能卡中也能够产生。基于上述特点，e c c 不仅可以用于现在使用r s a 的所有场 合，而且在存储空间受限，带宽低等不适合用r s a 算法的场合仍然适用，如用于移动 通信，智能卡等【8 j 。 上述分析可知椭圆曲线的优势所在【9 i ，因此椭圆曲线如果能够进一步研究，突破 些问题的限制，必然能够应用在加密的各个方面，有着广泛的发展前景。例如椭圆曲线 应用于电子商务、数字现金、分布式考试i 1 、软件注册保护12 1 、群签名 1 3 】、电子选 举、电- 子公文【1 5 1 、代理数字签名【1 6 】、不可逆签名1 7 1 等方i s i 2 , , 经成果斐然。按照当前 的电子信息化程度，它的应用主要在银行结算，电子商务和通信领域等。2 1 世纪是信息 的智能时代，以后椭圆曲线必将会扩展应用到人们社会生活和工作的各个层面， 因此， 椭圆曲线密码理论所发展成的技术必将有无限的商业价值。随着数字化的战争序幕拉 开，椭圆曲线密码也将体现巨大的军事价值，应用在信息战的高技术装备和通信指挥系 统上面。 本课题的研究意义主要在于应用椭圆曲线的巨大优势，使所设计实现的系统同以前 的相比拥有巨大的实用性。 1 3 椭圆曲线国内外研究概况和发展趋势 ( 1 ) 椭圆曲线研究简介 大连理1 = 大学硕士学位论文 椭圆曲线理论是一个古老而深奥的数学分支，已有1 0 0 多年的历史，一直作为一门 纯理论学科被少数数学家掌握。他被广大科技工作者了解要归功于2 0 世纪8 0 年代的两 件重要的工作。第一，w e i l 应用椭圆曲线理论证明了著名的费尔玛大定理。第二，n e a l k o b l i t z 和v s m i l l e r 把椭圆曲线群引入公钥密码理论中，提出了基于椭圆曲线的公钥密 码体制e c c ( e l l i p t i cc u r v ec r y p t o s y s t e m ) ，取得了公钥密码理论和应用的突破性进展。 椭圆盐线密码学是以有限域上的椭圆曲线理论为基础的。对它的研究有力的推动了 椭圆曲线理论的应用，椭圆曲线密码学的引入和椭圆曲线密码理论的研究对椭圆曲线理 论的研究产生了推动，与之相互作用与共同发展【l 】。椭圆曲线这个1 0 0 多年前就有的理 论博大精深，如果能够进一步应用当中的数学理论，并促进该理论的发展，对它的研究 成果将直接影响信息安全及电子商务的发展。椭圆曲线理论是代数数论、代数几何和解 析数论这三门学科的综合学科，其理论研究需要扎实和深厚的数学基础，椭圆曲线密码 实现是纯粹数学与计算机工程技术的结合。 f 2 ) 椭圆曲线研究现状 从现有的攻击算法可看出，椭圆曲线上的离散对数问题与乘法群上的离散对数问题 难度相当。而加解密速度相对来说较快，具有明显的技术优势。因此，在同级安全条件 下，采用基于椭圆曲线的加密和签名方案，运算速度比r s a 快得多，设计更简单，更 灵活。一般来说，e c c 没有亚指数攻击，所以他的密钥长度大大地减少，2 5 6 比特的 e c c 密钥就可以达到对称密钥1 2 8 比特的安全水平。e c c 的优势参见表1 1 、表1 2 。 e c c 的安全性和优势得到了业界的认可和广泛的应用： ( 1 ) 1 9 9 8 年被确定为i s o i e c 数字签名标准i s 0 1 4 8 8 8 3 ： ( 2 ) 1 9 9 9 年2 月e c d s a ( 椭圆曲线数字签名算法) 被a n s i 确定为数字签名标准 a n s i x 9 6 2 1 9 9 8 ，e c d h ( 椭圆曲线d i f i l e h e l l m a n 体制版本) 被确定为a n s ix 9 6 3 ： ( 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 。 现在椭圆曲线密码体制不仅是一个重要的理论研究领域，而且已经从理论研究转化 为实际可用的密码算法，促使密码技术走向产业化。当前，国内外很多公司都在大力进 行e c c 产品的开发。 目前，在椭圆曲线公钥密码体制的研究与应用方面处于世界领先地位的是加拿大的 c e r t i c o m 公司，是国际上最著名的e c c 密码技术公司，已授权3 0 0 多家企业使用e c c 密码技术，包括c i s c o 系统有限公司、摩托罗拉、p a l m 等企业。m i c r o s o f t 将c e r t i c o m 公司的v p n 嵌入微软视窗移动2 0 0 3 系统中。经过十多年的研究，c e r t i c o m 公司探索出 了实现椭圆曲线密码体制的先进方法。从1 9 9 7 年开始，全球各大公司和机构开始采用 孟凡生：基于椭圆曲线的混合加密系统的研究实现 c e n i o m 的椭圆曲线公钥密码体制技术或与之建立战略联盟。但是c e r t i c o m 公司的产品 和相关技术资料对中国是禁运的。 表1 1e c c 和r s a 的破译时间与密钥尺寸 t a b 1 1t h ea t t a c kt i m ea n dk e ys i z e so f e c ca n dr s a 表1 2e c c 和r s a 的运算速度对比( 同种条件下某一次运算) t a b 1 2t h eo p e r a t i o ns p e e db e t w e e ne c ca n dr s a ( ac e r t a i no p e r a t i o ni nt h es a m ec o n d i t i o n ) 密钥对生成 签名 认证 密钥交换( d h ) 3 8 3 0 ( e c d s a ) 1 0 7 ( e c d s a ) 7 3 ( e c d h ) 4 7 0 8 3 2 2 8 4 1 2 7 1 6 5 4 0 德国、日本、法国、美国、加拿大等国的很多密码学研究小组及一些公司实现了椭 圆曲线密码体制( 如b o u n c e c a s t l e 组织提供椭圆曲线j a v a 实现的第三方插件) ，我国也有 一些密码学者做了这方面的工作。许多标准化组织已经或正在制定关于椭圆曲线的标 准，同时也有许多的厂商已经或正在开发基于椭圆曲线的产品。对于椭圆盐线密码的研 究也是方兴未艾，从a s i a c r y p t o 9 8 上专门开辟了e c c 的栏目可见一斑。 在椭圆曲线密码体制的标准化方面，i e e e 、a n s i 、i s o 、i e t f 、a t m 等都作了大 量的工作，它们所开发的椭圆曲线标准的文档有：i e e ep 1 3 6 3p 1 3 6 3 a 、a n s ix 9 6 2 x 9 ：6 3 、i s o i e c l 4 8 8 8 等。 2 0 0 3 年5 月1 2 日中国颁布的无线局域网国家标准g b l 5 6 2 9 1 1 中，包含了全新的 w a p i ( w l a n a u t h e n t i c a t i o na n dp r i v a c yi n f r a s t r u c t u r e ) 安全机制，能为用户的w l a n 系 统提供全面的安全保护。这种安全机制由w a i 和w p i 两部分组成，分别实现对用户身 份的鉴别和对传输的数据加密。w a i 采用公开密钥密码体制，利用证书来对w l a n 系 大连理工大学硕士学位论文 统中的用户和a p 进行认证。证书罩面包含有证书颁发者( a s u ) 的公钥和签名以及证书 持有者的公钥和签名，这里的签名采用的就是椭圆曲线e c c 算法。 ( 3 ) 椭圆曲线的研究方向和问题 e c c 的安全性基于椭圆曲线离散对数问题( e c d l p ) 的难解性，试图寻找对e c d l p 的高效算法或改进已有的解决e c d l p 的算法是研究方向之一。 椭圆曲线这个1 0 0 多年前就有的理论博大精深，如果能够迸一步应用当中的数学理 论，并促进该理论的发展，对它的研究成果将直接影响信息安全及电子商务的发展。 超椭圆曲线理论是一个很重要的研究方向，如果进一步研究和实现将有巨大的应 用。 对e c c 中某些算法的改进，使其运算效率进一步提高。如对于其上有理点数的计算， 因此需要找到更好的办法。如改进椭圆曲线己经有的计算椭圆曲线上点数的算法或提出 新算法和椭圆曲线的快速实现算法。一般而言，椭圆曲线群不是循环群，但可以表示为 两个循环群的直和。只要椭圆曲线群的点数很大。则这两个循环群中必有一个的阶数很 大。在椭圆曲线上寻找阶数足够大的点是一个困难问题。 另外椭圆曲线加密的消息编码方案目前实用性较差，寻找有效的编码方案是重要的 椭圆曲线研究方向。 由此可知椭圆曲线加密体制目前存在的问题： 现有的椭圆曲线加密系统由于研究应用同r s a 等相比还不够成熟。 椭圆曲线加密体制中无有效的编码算法，其它算法加解密速度也不理想，给椭 圆曲线应用带来了不便。 现代密码学中加密算法主要分为对称加密算法和非对称加密算法，单独使用椭圆 曲线加密不会取得好的效果。因为其算法复杂，效率方面不如对称算法。两类算法各有 优点和不足，各有适宜的应用场合，因此，两类加密算法将长期共存。 1 4 本文的主要工作 本文所要解决的问题是设计一个基于椭圆曲线的混合加密系统，结合对称算法和其 它优化算法进行混合加密设计实现，并能够达到较好的安全性、效率和快速性。 ( 1 ) 改进m e n e z e s v a n s t o n e 算法形成新的加密体制，同改进前比大大减少了运算次 数，从而使得椭圆曲线加密速度大大提高，不仅可以用于加密混合加密系统中对称算法 产生的会话密钥，还可以用来加密大量的数据( 可抗击已知明文攻击，去掉了原来的数 据膨胀率) 。 5 孟凡生：基于椭圆曲线的混合加密系统的研究实现 ( 2 ) 该椭圆曲线混合加密系统，运用了椭圆曲线快速算法，其密钥通过e c m q v 等 进行了有效性验证和分发。 ( 3 ) 椭圆曲线数字签名和消息摘要技术采用带加密方式，更有效、快速实现了网络 通信中数据的安全保密性、完整性、身份验证和抗抵赖性。 大连理j 二大学硕士学位论文 2 密码学概述 2 1 信息安全与密码学 广义地讲，安全是指防止其他人利用、借助你的计算机或外围设备，做你不希望他 们做的任何事情，让你能够完成既定任务而不受任何干扰，真正安全的目的是保护存储 在计算机中的数据。 首先，在高科技时代，计算机安全是个人隐私的基础条件。计算机中存有大量纯属 私人的信息。某些最为敏感的数据一信用史，银行余额以及其他类似资料一都留存在那 些已经连入大网络上的机器中。 其次，也是最为重要的，计算机安全是一种好的习惯。如果人们希望自己不受侵扰， 他们就可以这样做，而不管你对他们怎样看。人们明确希望给自己的计算机系统保留一 席和平之地。 再次，现代社会越来越依赖计算机以及它们所包含的程序和数据的完整性。使用领 域从显而易见的( 如金融业，很容易印入脑海的) 到随处可见的( 由庞大计算机网络控制的 整个电话系统) ，直到与生命攸关的( 计算机化的医疗设备及医用信息系统) 等等。在这些 系统中，由缺陷或故障引起的问题很多：对由于未经授权就切换到另一个系统所引起的 破坏一不论是故意的或是无意的一心有余悸。计算机安全在信息时代是如此重要，就如 同一千年前用高墙围住城市一样f l8 1 。 目前针对i n t e m e t 系统安全，实施的防卫措施主要有防火墙、入侵监测、数据加密、 安全协议、内容检测( 防病毒木马) 等安全手段。 一般说来，安全涉及到技术安全、管理安全、法律政策。密码技术安全能确保最基 本的安全。有时需要在不安全链路上通信，但却不希望暴露自己的系统。密码学一一种 秘密变换的技术一便应运而生。密码学最普通的运用当然是保密。攻击者无法理解一个 适当加密的数据包。在因特网通信中，特别是在保护远距离的通信中，机密性通常是次 要的，相反人们对密码学所提供的蕴涵鉴别机制感兴趣。即，一个采用适当密钥进行加 密的数据包，用不适当密钥，将不可能解密成为任何可理解的东西。这极大地限制了攻 击者注入虚假报文的能力。 2 2 密码技术简介 2 2 1 加密学的基本概念和常见的攻击方法 ( 1 ) 密码学( c r y p t o l o g y ) 孟凡生：基于椭圆曲线的混合加密系统的研究实现 密码学是研究密码系统或通信安全的一门科学。密码算法也叫密码，是用于加密和 解密的数学函数，由五个部分组成：明码文空间m ，密码文空间l 密钥空间乜一 组加密变换e k ( m ) = c ；一组解密变换d k ( c ) = m 。它包含两个分支：密码编码学 ( c r y p t o g r a p h y ) ，密码分析学( c r y p t o a n a l y s i s ) 。密码学是设计和分析任何安全协议( 为抗拒 参与者各方内部与外部可能有不诚实者为了达到种种目的而进行安全破坏) 。 构造密码有两种方法：基于信息论与复杂性理论( 密文中是否含明文) ，即从可能性 与可行性角度构造密码，是密码理论的基础。信息论可以分析理论安全与实际安全( 一 次一密具有理论上的安全，不具有实际安全) ；而计算复杂性理论是现代密码学的基础， n p ( 不确定性多项式时间可解类) ，n p 完全类( 不确定性多项式时间可解完全类) 两类问题 的求解在计算上是不可行的，单向函数就是这样的问题。 密码学是密码体制与安全协议的总体，数学分支甚多。密码学中有四种基本理论： 单向函数、伪随机序列生成器、零知识证明、杂凑函数，理论上其存在性是等价的。在 某种意义上，数字签名、消息认证和身份识别等问题可看作保密通信问题的推广。共同 背景是在系统地参与者各方内部或外部可能存在不诚实者，为了各自的目的非法进行有 意破坏【19 1 。 密码编码学的主要目的是保持明文( 或密钥，或明文和密钥) 的秘密以防止偷听者( 也 叫对手、攻击者、截取者、入侵者、敌手或干脆称为敌人) 知晓。这里假设偷听者完全 能够截获收发者之间的通信。 密码分析学是在不知道密钥的情况下，恢复出明文的科学。成功的密码分析能恢复 出消息的明文或密钥。密码分析也可以发现密妈体制的弱点，最终得到上述结果f 密钥 通过非密码分析方式的丢失叫做泄露) 。对密码进行分析的尝试称为攻击。荷兰人 a k e r c i ( 1 1 0 脑最早在1 9 世纪阐明密码分析的一个基本假设，这个假设就是秘密必须全寓 于密钥中。k e r c k h o f f s 假设密码分析者已有密码算法及其实现的全部详细资料【1 8 】。 ( 2 ) 现代密码学中最基本的四种功能服务：保密性( c o n n d e n t i a l i t y ) ，身份验证 ( a u t h e n t i c a t i o n ) ，数据完整性( i n t c g r i t y ) 和不可否认性( n or e p u d i a t i o n ) 。 保密性：计算机网络中的信息只能由授予访问权限的用户读取。 数据完整性：计算机网络中的信息资源只能够被授予权限的用户改造。 身份验证：消息的接收者应该能够确认消息的来源；入侵者不可能伪装成他人。 不可否认性：发送者事后不能否认他发送的消息。 f 3 1 密码协议 密码学的用途是解决种种难题( 实际上，这也是计算机的主要用途) 。密码学解决的 各种难题围绕机密性、鉴别、完整性和不诚实的人。你可能了解各种算法和技术，除非 大连理工大学硕士学位论文 它们能够解决某些问题，否则这些东西只是理论而已，这就是为什么本文要先了解协议 的原因。 协议是一系列步骤，它包括两方或多方，设计它的目的是要完成一项任务。协议通 常来说就是密码学意义上的体制、机制、算法。包括单向函数、伪随机序列生成器、零 知识证明、杂凑函数。 加密机制根据密钥类型不同可以将现代密码技术分为两类：对称加密算法f 私钥密 码体系) 和非对称加密算法( 公钥密码体系) 。 私钥加密 在私钥密码体系中，数据加密和解密采用的都是同一个密钥，因而其安全性依赖于 所持有密钥的安全性。对称加密算法加解密高效快速、密钥简短、破译困难，但是存在 着密钥传送和保管的问题，而且无法完成身份认证等功能，不便于应用在网络开放的环 境中。 i d e a 算法是1 2 8 位的私钥密码算法，它于1 9 9 0 年由中国学者赖学嘉和著名密码学 家m a s s e y 开发成形，起初称为建议标准算法( p e s ) ，1 9 9 1 年，在b i h a ms h a m i r 对其采 用了差分分析之后，设计者为抗此种攻击，增加了他们的密码算法的强度。他们把新算 法称为i p e s ，即改进型建议加密标准。1 9 9 2 年进行了改进，强化了抗差分分析的能力。 这是近年来提出的各种分组密码中一个很成功的方案。1 9 9 9 年正式更名为i d e a 。目前 它已被i s o i e c 等组织列为登记的加密算法1 1 。 公钥加密 在公钥密码体系中，数据加密和解密采用不同的密钥，而且用加密密钥加密的数据 只有采用相应的解密密钥才能解密，更重要的是从加密密钥来求解解密密钥十分困难。 在实际应用中，用户通常对外公开加密密钥( 称为公钥) ，而秘密持有解密密钥( 称为私 钥) 。公钥密码体系能适应网络的开放性要求，密钥管理简单，并且可方便地实现数字 签名和身份认证等功能，是目前电子商务等技术的核心。缺陷是算法复杂，加密数据的 速度和效率较低。r s a 算法( r i v e s t ，s h a r r t i r ，a d l e n t a n 三人于1 9 7 8 年提出) 是目前非对 称加密领域内最为著名的算法。它的安全性是基于大整数素因子分解的困难性，其公钥 和私钥是一对大素数豹函数。另外本文研究的椭圆曲线算法是近年来非对称密码学的研 究热点，基于椭圆曲线离散对数问题的难解性。 ( 4 ) 常用的密码分析攻击 密码体制必须能够抗击各种密码分析攻击，否则是无用的。最好的算法是那些已经 公开的，并经过世界上最好的密码分析家们多年的攻击，但还是不能破译的算法，比如 r s a 和本文所用的椭圆曲线加密算法。好的密码分析家总会坚持审查，以图把不好的算 9 孟凡生：基于椭圆曲线的混合加密系统的研究实现 法从好的算法中剔除出去。密码攻击有四类，当然，每一类都假设密码分析者知道所用 的加密算法的全部知识： 唯密文攻击。密码分析者有一些消息的密文，这些消息都用同一加密算法加密。 密码分析者的任务是恢复尽可能多的明文，或者最好是能推算出加密消息的密钥来，以 便可采用相同的密钥解出其他被加密的消息。 已知明文攻击。密码分析者不仅可得到一些消息的密文，而且也知道这些消息 的明文。分析者的任务就是用加密信息推出用来加密的密钥或导出一个算法，此算法可 以对用同一密钥加密的任何新的消息进行解密。 选择明文攻击。分析者不仅可得到一些消息的密文和相应的明文，而且他们也 可选择被加密的明文。这比已知明文攻击更有效。因为密码分析者能选择特定的明文块 去加密，那些块可能产生更多关于密钥的信息，分析者的任务是推出用来加密消息的密 钥或导出一个算法，此算法可以对用同一密钥加密的任何新的消息进行解密。 自适应选择明文攻击。这是选择明文攻击的特殊情况。密码分析者不仅能选择 被加密的明文，而且也能基于以前加密的结果修正这个选择。在选择明文攻击中，密码 分析者还可以选择一大块被加了密的明文。而在自适应选择密文攻击中，他可选取较小 的明文块，然后再基于第一块的结果选择另一明文块，以此类推。 另外还有至少三类其它的密码分析攻击。 选择密文攻击。密码分析者能选择不同的被加密的密文，并可得到对应的解密 的明文。这种攻击主要用于公开密钥体制，在3 5 节中讨论对于椭圆曲线的攻击。选择 密文攻击有时也可有效地用于对称算法( 有时选择明文攻击和选择密文攻击一起称作选 择文本攻击。) 选择密钥攻击。这种攻击并不表示密码分析者能够选择密钥，它只表示密码分 析者具有不同密钥之间的关系的有关知识 软磨硬泡( r u b b e r h o s e ) 攻击。密码分析者威胁、勒索，或者折磨某人，直到他给 出密钥为止。行贿有时称为购买密钥攻击。这些是非常有效的攻击，并且经常是破译算 法的最好途径。 已知明文攻击和选择明文攻击比你想象的更常见。密码分析者得到加了密的明文消 息或贿赂某人去加密所选择的消息，这种事情时有所闻。密码分析者也许知道，许多消 息有标准的开头和结尾。加密的源码特别脆弱，这是因为有规律地出现关键字，加了密 的可执行代码也有同样问题。已知明文攻击( 甚至选择明文攻击) 在二战中已被成功地用 来破译德国和日本的密码【l 。 大连理】。大学硕十学位论文 2 2 2 密码学发展概况 密码学中密码设计与分析之间的不断斗争，通信技术计算技术的发展都是密码学发 展的推动力。 ( 1 ) 古典密码学 在计算机出现前的密码学，可称为古典密码学：密码由基于字符的密码算法构成， 不同的密码算法是字符之间互相代换( 置换密码) 或者是互相之间换位( 移位密码) ，好的 密码算法是结合这两种方法，每次进行多次运算。 第一次世界大战前，重要的密码学进展很少出现在公开文献中。第一次世界大战后， 情况开始变化，完全处于秘密工作状态的美国陆军和海军的机要部门开始在密码学方面 取得根本性的进展。香农( c l a u d es h a n n o n ) 的文章保密系统的通信理论出现在1 9 4 9 年贝尔系统技术杂志上。在1 9 6 7 年，一部与众不同的著作d a v i dk a h n 的破 译者出现了，破译者的意义不仅在于它涉及到的相当广泛的领域，而且在于 它使成千上万原本不知道密码学的人了解密码学。大约在同一时期，美国数据加密标准 ( d e s ) 开始研究，当时密码学的文献还不丰富，但却也包括一些非常有价值的东西。 ( 2 ) 现代密码学 密码学研究的基本问题，在1 9 7 5 年以前，仅限于通过公开通信媒体，设计和分析 密码体制：之后，构造不能伪造的数字签名问题和设计抗欺骗协议也成为密码学问题”9 1 。 当m a r t i nh e l l m a n 和w h i t f i e l dd i f f i e 在1 9 7 5 年提出公开密钥密码学时，一种间接 贡献是引入了一个看来不易解决的难题。2 0 世纪9 0 年代，最通用的公钥密码体制是r s a 公钥密码体制和d i f f i e h e l l m a n 公钥密码交换算法，密钥长度一般为5 1 2 比特。 随着计算机速度的提高以及计算机网络的发展( 可使用成千上万台机器同时进行大 整数分解1 ，分解大整数的方法f i 益进步与完善。要提高r s a 使用的安全性，则需采用 尽可能大的整数，因此密钥位数也一直在增加。然而，密钥越长，系统加解密速度越慢， 硬件实现也越来越难。但是1 9 9 9 年8 月2 2 同r s a 一5 1 2 被攻破，所以，这些公钥不得不 被加长。为了达到对称密钥1 2 8 比特的安全水平，n i s t 推荐使用3 0 7 2 比特的r s a 密 钥。显然这种密钥长度的增长。对本来计算速度缓慢的r s a 来说，无疑是雪上加霜。 椭圆曲线密码e c c 的提出改变了这种状况，实现了密钥效率的大突破，大有以强 大的短密钥优势取代r s a 成为新一代公钥标准( 事实标准) 之势。 另外2 l 世纪密码学方面最有研究价值的是量子加密、混沌加密和椭圆曲线加密， 他们代表了椭圆曲线发展的未来趋势。量子加密的高可靠性、混沌加密的序列密码应用 以及椭圆曲线的公钥制特点和优势都成为了研究方向。 孟凡生：基丁椭圆曲线的混合加密系统的研究实现 3 椭圆曲线数学基础 3 1 域表示 3 1 1 有限域、素数域和二进制域 ( 1 ) 有限域 有限域是由有限元素集f 构成，其中f 上二进制操作加法和乘法满足某种数学属性， 其中有限域的阶是该域中元素的个数。有限域存在当且仅当g 是一个素指数，记为b 。 如果g = 矿p 是素数肌为正整数) ，那么p 称为的特征值，m 称为r 的扩展度，有两 种表示方法：多项式基与优化正规基 2 0 。 ( 2 ) 素数域 素数域d 由整数集合 o ，1 ，2 ，3 ，p - l 组成，每个这样的整数可以用一个长 度恰为t = r l o g ：p ( 其中卜 表示不小于x 的最小整数) 的二进制表示，该表示由整数的二 进制表示及在其左边添加适当个数的0 组成。r 中元素具有以下算术运算 2 0 - 2 1 】： 加法：如果口，6 昂，则a + b = r ，其中r 是被p 除所得的剩余，o r 印1 。 乘法：如果口，6 昂，则口b = s ，其中s 是被p 除所得的剩余，o s5 p 一1 。 求逆：如果日是昂中的非零元素，日模p 的逆元，记为d ，是唯一的整数c b ， c 满足口c = 1 。 令表示昂中所有非零元素，可证明在昂中至少存在一个元素g ，使得昂中任 意非零元素可以表示成g 的方幂，如公式3 i 所示。这样的元素g 称为b 的生成元( 或 本原元1 。 只= g ：0 茎f s p 2 )( 3 1 ) 1 口= g7 c + 的乘法逆是二= g = g 1 “9 “，可见昂上一次求逆运算要进行p l f “ 次域乘法，显然p - l - f 的二进制长度为ll o g ：( p l f ) ，由数论知识，可对模幂运算优化， 使运算操作次数为o ( 1 0 9 ：( p 一1 一f ) ) 。即求逆在最坏情况下相当于o ( f l o g ：( p 一1 ) ) 次 域乘法。 f 3 ) 二进制域 大连理工大学硕士学位论文 特征为2 的有限域，称为二进制域，可以看作域r ( 有两个元素0 、1 ) 上的m 维 空间a 即存在。上的m 个元素，口l 一，口。，使得每个a t 。可以被唯一的表示成公 式3 2 t 2 0 - 2 1 ： 口= a o 口o + a l 口l + + a m _ i 口，一l ，口，e 0 , 1 )( 3 2 ) 对于一组 ，q ，口。) 称其为c ，的基。对于基，域元素d 可以表示为比特串 ( a 1 a 。一1 ) 。 只，有很多种不同的基。某些基可使得软硬件的数学运算更高效，a n s