（系统分析与集成专业论文）基于椭圆曲线的事务数字签名算法的研究.pdf

学位论文独创性声明 本人所呈交的学位论文是我在导师的指导下进行的研究工作及取褥的研究成果。据 我所知，除文中已经注明引用的内容外，本论文不包含其他个人已经发表或撰写过的研 究成果。对本文的研究做出重要贡献的个人和集体，均己在文中作了明确说明并表示谢 意。 储躲啊修嘲翌生! 学位论文使用授权声明 本人完全了解华东师范大学有关保留、使用学位论文的规定，学校有权保留学位论 文并向国家主管部门或其指定机构送交论文的电子版和纸质版。有权将学位论文用于非 赢利目的的少量复制并允许论文进入学校图书馆被查阅。有权将学位论文的内容编入有 关数据库进行检索。有权将学位论文的标题和摘要汇编出版。保密的学位论文在解密后 适用本规定。 学位论文作者签名：甲蕴为导师签名学位论文作者签名：，2 l 移导师签名 荔乞火 日期：巡：6 ：!日期：趔砝6 ：旦 华东帅范人学计算帆系坝 学位论文 摘要 电子政务提供的平台上有相当多的重要公文在流转，冈此，保证其中的信息安全1 r 常重要。政 务机关内部具有严格的办事流群平程序规定，一旦违反了业务群序；i l j 流程，会造成严重后果。通常 的数字签名提供了信息发送者的身份验证，但却无法保证事务处理流程的正确。 本文介纠了一种事务数字签名算法，该算法能够验证整个事务处理流程的正确性。事务数字签 名算法的安全性建立在椭剧曲线离散对数问题的难解性之上。作者以椭圆曲线密码体制为基础，完 成了该事务数字签名算法的实现。事务数字签名协议包括生成事务签名，和对接收到的签名进行验 证两部分。 目前，对定义在特祉值为2 或者人素数的有限域上的椭圆曲线计算已经有了比较深入的研究， 因此本文讨论了定义在特征3 的有限域上的椭尉曲线运算，采刚多项式基表示法实现。作者对定义 在有限域z ，。上的椭圆曲线，详细分析了曲线上的点构戚的循环群结拗。椭圆曲线点群 中元素之间的运算构成了事务数字签名算法的基本运算。 本文考虑两种基本的事务类， l ! ：一种是各个部门按顺序依次处理某事务，简称“串联”：另一种 是除处理事务的起始部门雨j 最终部i 、1 之外，其余各个部门并行处理某事务，简称“并联”。不同类j r ! ! 的事务有不同的处理流样，对某一类型的事务，作者根据其规定的处理流程，完成了事务数字签名 的生成。 椭劂曲线上的t a t e 配对具有烈线性性质，本文利j = | j 这一性质对收到的事务数字签名进行验证。 计算t a r e 配对采h jm i l l e r 算法，在特征3 的有限域上实现。m i l l e r 锋。法的基本思想是将椭蹦曲线点 乘中的加法利倍点运算与点加过群中的直线函数估计联系起来。 本文将上述事务数字签名协议应_ l = j 剧电子政务中，用来检验政务系统里事务处理流群的正确性， 提出了个分布式安全事务平台的构建方案。根据事务活动的特征及存在的宜全问题，为分布式电 子事务活动提供一个安全、可锥的运行环境。该平台遵循分布式组件标准c o r b a 进行设计，本文 给出了平台的i d l 编什接口定义和系统类结构的定义。 关键词：事务数字签名，椭剧曲线，特征3 ，有限域，t a t e 配对m i l l e r 算法，安全平台 。芦东帅范人学计算机系 坝i 学位论史 a b s t r a c t t h e r ea r eal o to fs i g n i f i c a n td o c u m e n t sf l o w i n gi nt h ep l a t f o r mo f f e r e db yt h ee l e c t r o n i cg o v e r n m e n t ， s oi ti se s s e n t i a lt ok e e pt h ei n f o r m a t i o nc o n f i d e n t i a li nt h eg o v e r n m e n l ，t h es t r i c tr e g u l a t i o no fa f f a i r si s c a l l e dt o r i nc a s eo fa c t i n ga g a i n s tt h er e g u l a t i o n t h es e r i o u se f f e c tw o u l db em a d ea sw ek n o w ，u s u a l d i g i t a ls i g n a t u r ej u s to f f e r ss e n d e ra u t h e n t i c a t i o n ，h o w e v e r i tc a n n o tg u a r a n t e et h ec o r r e c t n e s so ft h e t r a n s a c t i o np r o c e s s i n g i nt h i sp a p e r , w eh a v ed i s c u s s e da na l g o r i t h mo ft r a n s a c t i o ns i g n a t u r e t h i sa l g o r i t h mc a nv e r i f yt h e c o r r e c t n e s so ft h ew h o l ep r o c e d u r e t h es e c u r i t yo ft h ea l g o r i t h mi sb a s e do nt h ec o m p l e x i t yo fs o l v i n g e l l i p t i cc u r v ed i s c r e t el o g a r i t h mp r o b l e m w ei m p l e m e n tt h ea l g o r i t h mo ft r a n s a c t i o ns i g n a t u r e ，b a s eo n e l l i p t i cc u r v ec r y p t o g r a p h y p r o d u c i n gad i g i t a ls i g n a t u r ea n dv e r i f y i n gt h i ss i g n a t u r ec o n s t i t u t et h e t r a n s a c t i o ns i g n a t u r ep r o t o c 0 1 a b o u tt h ec o m p u t a t i o n so ft h ee l l i p t i cc u r v e so nf i n i t ef i e l d so ft ：h a r a c t e r i s t i c2o ra l a r g ep r i m e n u m b e rp ，t h e r ea r eal o tp r o f o u n ds t u d i e sa l r e a d y i nt h i sp a p e r , w ec o n c e n t r a t eo nc o m p u t a t i o n so nt h e f i n i t ef i e l do fc h a r a c t e r i s t i c3 ，a n di m p l e m e n ti to np o l y n o m i a lb a s e t oi l l u s t r a t et h i sa l g o r i t h m ，w eh a v e d i s c u s s e ds e v e r a lc o n c r e t ee x a m p l e s ，t h ee l l i p t i cc u r v e so nf i n i t ef i e l d s f ，- i nt h o s ee x a m p l e s ， w ef i r s ta n a l y z et h es t r u c t u r eo fc y c l i cg r o u p sa n dt h eb a s i cc a l c u l a t i o n si nd e t a i l s ，w h i c hc o n s i s to ft h e p o i n t so f e l l i p t i cc u r v e s ，a n dt h e ne s t a b l i s ht h ec o n s t r u c t i o no f t h ed i g i t a ls i g n a t u r e t h e r ea r et w ob a s i ct y p e so fm a n a g i n go n et r a n s a c t i o n o n ei sc a l l e d s e r i e sc o n n e c t i o n ”，i nw h i c h e a c hd e p a r t m e n tc o m p l e t e l yd e a lw i t ht h et r a n s a c t i o ni ns e q u e n c e t h eo t h e ri s c a l l e d ”p a r a l l e lc o n n e c t i o n ”， i nw h i c he v e r yd e p a r t m e n te x c e p tt h es t a r t i n gd e p a r t m e n ta n dt h ee n d i n gd e p a r t m e n ts y n c h r o n o u s l y t r a n s a c ii t s i n c et h et a t ep a i r i n go nt h ee l l i p t i cc u r v ei sd o u b l yl i n e a r , w eu t i l i z e - t h ep r o p e r t yt ov e r i f yt h ed i g i t a l s i g n a t u r e a b o u tt h ec a l c u l a t i o n so f t a t ep a i r i n g ，w ea d o p tm i l l e ra l g o r i t h m ，a n di m p l e m e n ti to nt h ef i n i t e f i e l do fc h a r a c t e r i s t i c3 m i l l e r sa l g o r i t h mi s b a s i c a l l yt h eu s u a l d o u b l ：a n da d d a l g o r i t h mf o re l l i p t i c c u r v ep o i n tm u l t i p l i c a t i o nc o m b i n e dw i t ha ne v a l u a t i o n o fc e r t a i ni n t e n n e d i a t ef u n c t i o n sw h i c ha r et h e s t r a i g h tl i n e su s e di nt h ea d d i t i o np r o c e s s t oa p p l yt h et r a n s a c t i o ns i g n a t u r ep r o t o c o lt oc h e c kt h et r a n s a c t i o n p r o c e s s i n gi nt h ee l e c t r o n i c g o v e r n m e n t ，w ep r o p o s ead e s i g no fd i s t r i b u t e dt r a n s a c t i o n s e c u r i t yp l a t f o r ma c c o r d i n g t ot h e 4 仁东帅池人学汁算机系 l ! l ! l j 学位论义 c h a r a c t e r i s t i co ft r a n s a c t i o na n de x i s t e dp r o b l e mr e l a t e dw i t hs a f e t y ，t h ep l a t f o r mw i l lp r o v i d eas e c u r ea n d c r e d i b l ee n v i r o n m e n tf o rt h ed i s t r i b u t e de l e c t r o n i ct r a n s a c t i o n t h ed e s i g n e dp l a t f o r mc o n f o r mw i t ht h e d i s t r i b u t e dc o m p o n e n ts t a n d a r d ，t h ec o m m o no b j e c tr e q u e s tb r o k e ra r c h i t e c t u r e t h ei d ld e f i n i t i o na n d s y s t e ms t r u c t u r ei sg i v e no nt h ef o l l o w i n gp a p e r k e y w o r d s ：t r a n s a c t i o ns i g n a t u r e ，e l l i p t i cc u r v e ，c h a r a c t e r i s t i ct h r e e ，f i n i t ef i e l d ，t a r ep a i r i n g ，m i l l e r a l g o r i t h m ，s e c u r i t yp l a t f o r m 5 | 十算机系 i ! j ! l 学位论文 1 1 本文的研究背景 第一章引言 随着信息技术的迅猛发展，特别是互联网技术的普及应刚，电子歧务的发展已经成为当代信息 化最重要的领域之一。电子政务的目的是以网络技术为基本手段，面向政府机构的业务模式、管理 模式和服务方式的优化午lj 扩展，将信息技术在政府机构的应州从简单的取代手j ：劳动提高到i 一作方 式的新层次。电子政务提供的平台上有相当多的政府公文在流转，其中不乏重要情报，关系剑国家 安全和社会稳定。内此，信息安全是【b 子政务中的头等人事。 电子政务的安全需求有以i j 1 点： ( 1 ) 隔离：由丁政府部门的特殊性，其传统运营方式k 期封闭式运营，造成了相对独立的系统。 在新形势新要求r ，政府部门之间、政府乖l 企业或个人之间仍1 日必须保持这种隔离的状态。隔离的 实现分为物理隔离、链路加密与虚拟私b x ( v p n ) 。 ( 2 ) 加密：任何时候任何层次，政务数据必须进过加密才能在网络中( 包括内网) 传送。 ( 3 ) 签名与认证：政务数据必须具有不可抵赖性和完整性需要引入签名雨认证机制。 ( 4 ) 权限管理：在政务系统中，人既是行为实体，义是权限实体。所以需要对系统角笆进行 划分，不同级别具有不同的权限。 ( 5 ) 内容控制保护：政务数据的重要性要求对于数据内容要能够进行抗毁保护、反扩散保护和 抵赖保护。 ( 6 ) 严格的程序和流科要求：政务机关山部具有严格的办事流转i 和程序规定，如果违反了它的 业务程序和流抖会造成严重影响。 1 2 国内外研究现状 电子政务中网络信息安全研究的内容很多，它涉及安全体系结构、安全协议、密码理论和技术、 安全监控、应急处理等。密码披术是解决电子政务中网络信息安全的戈键技术。依靠密码技术，可 以解决嘲络中身份识圳、信息存储年传输的加密保护、信息完整性以及信息不可抵赖等信息安全问 题。 为解决在信息化、网络化珂、境f 的安全问题，_ ：界各国经过多年的研究，初步形成了一套完整 的解决方案，即公钥基础设施( p u b l i ck e yi n f r a s t r u c t u r ep k i ) 。p k i 是基 ：公开密钥理论和技术建 6 仁东帅范夫学 计算机系 伽 卜学位论立 立起来的安全体系，是提供信息安全服务的具有普遍适应性的安全基础设施。该体系通过标准的接 口为电子商务平| i 电子政务提供必需的队证、保密 i l 不可否认服务。作为一种技术体系p k i 为网络 应用提供可靠的安全保障。 p k i 中的数字签名雨j 身份认证系统保证了信息传输过程中的完整性，提供了信息发送者的身份 认证和不可抵赖性。而电子政务系统除了要保证信息发送者的正确性外，还霸望能够保证政务机关 内部办事流群的止确性，传统的数字签名无法做到这点。 电子政务实际上是电子协作活动，它具有如r 特点：活动本身可以细分为若干具有独立活动 属性的原子活动，且活动具有可定义性：细分后的原于活动相互关联、互相依存，在时间维上呈 序列性，在逻辑j 二警依存性：各原子活动分布在网络的不同服务器和终端机上。我们称此类协同 l ：作的电子活动为分布式的书务活动。 分布式的电子事务活动存在如f 的安全问题：活动对象信息需要通过网络传输，信息可以铍 无关的人截获并加以修改或仿冒：参与事务活动的土体存在铍仿冒的可能；事务活动存在冈原 子活动的冈果序列被非法政变而无法止常进彳亍的可能；利用现今的数字签名协议，采刚数字签名 嵌套的办法，无法在活动的任一时刻验证已经发生的每一个原子活动的真实性和有效性，原子活动 序列的止确性。 1 3 本文所做的工作 1 介纠了一个事务数字签名算法，该算法能够验证原子活动的真实性和原子活动序列的止确性， 分析了算法的数学原理平安全性。 2 讨论了定义在特征3 的有限域上的椭圆曲线计算，在椭倒曲线点构成的循环群上定义运算， 并在此基础上生成了事务数字签名。 3 利川椭圆曲线上t a t e 配对韵烈线性性质，对事务数字签名进 ? - r i , y 。计算t a t e 配对的值采 用m i l l e r 算法米实现。 4 将事务数字签名协议廊_ l i 剑电子政务中，刖米验证事务处理流程的正确性，提出了一个分布 式安全事务平台的构建方案。 1 4 本文的组织结构 本文的锕彭 结构如f ： 第章引言，介纠了论文选题的背景和论文所做的主要研究r 作。第二章介绍了公钥密码学方 。卢东帅_ _ 1 ：f 大学计算机系硕i 学位论文 面的基础知识，平现有的数字签名算法。第二章分析了椭圆曲线密码体制的特性，讨论了定义在特 征2 成人素数的订限域上椭吲曲线的计算性质，介蜊r 现有的椭削曲线密码系统。第四章描述r 事 务数字签名算法的数学原理雨| 实现方法，分析了定义在特征3 的有限域上的椭圆曲线点计算的特性， 并在此基础上实现了事务数字签名葬法，利 ：| 椭剧曲线上的t a t e 两：对完成了事务数字签名的验证， 并分析了签名算法的交全性。第行章以该事务数字签名算法为核心，提出了一个分布式安全事务处 理平台的殴计方案。第j i 章对本文的j ：作进行了总结，并提出了进一步研究的建议。 华东f j 1 j 范大学 计算：机系 碳 j 学位论文 第二章公钥密码体制与数字签名 自1 9 7 6 年公钥密码的思想提出以米，国际上已经提出了f 【：多种公钥密码体制，比较有效的主要 有三类：一类是基丁人整数i = ；i 子分解问题的，其中最典型的代表是r s a 密码体制：另一类是基r 离 散对数问题的，比如e l g a m a l 密码体制：第二类是基于椭圆曲线离散对数问题的，即椭蚓曲线密码 体制。由丁分解人整数的能力日蔬增强，对r s a 的安全带米了定的威胁。需要取1 0 2 4 比特的密 钥才能保证其安全性，但密钥k 度增加的同时，也带米了实现上的难度。而基于离散对数问题的公 钥密码在目前技术r5 1 2 比特模艮就能够保证其安全性。特别是椭恻曲线上的离散对数的计算要比 有限域上的离教对数的计算更幽难，目前技术r 只需要1 6 0 比特模i 女即可。 2 1 密码学概述 2 1 1 密码学的发展历史 密码学的发展历史人致可以划分为三个阶段：第一阶段是从古代到1 9 4 9 年。在这- t , t 期密码 学专家常常是凭缸觉和信念来进行密码设计和分析的，而不是推理证明。第二阶段是从1 9 4 9 年剑 1 9 7 6 年。s h a n n o n 住1 9 4 9 年发表了“保密系统的信息理论”一文”i ，将密码学的研究纳入了科学的 轨道。第三个阶段是从1 9 7 6 年开始至今。1 9 7 6 年d i f f ew 和h e l l m a nm 发表了“密码学的新方向” 一文“1 提出了一种崭新的新纪元，使密码学发生了一场变革。他们首次证明了住发送端和接收端 无密钥传输的保密通信是可能的。1 9 7 7 年由r i v e s t 、s h a r n i r 和a d l e m a n 提出了第一个比较完善的公 钥密码体制，这就是蒋名的r s a 公钥密码体制”l 。从那时起，人们基丁不同的计算问题提出了许多 公钥密码体制，其中最著名的是基丁离散对数问题的e l g a m a l 公钥密码体制，和基丁椭圆曲线离散 对数问题的椭圆曲线密码体制。 2 1 2 密码学的基本概念 密码简单地蜕就是一缎含有参数k 的变换e 。设己知信息m ，通过变换西得密文c 即c = e k ( m ) 这个过牲称之为加密，参数k 称之为密钥。加密算法e 确定之后由。r 密钥不同密文c 也不同。 当然不是所有含参数k 的变换都可以作为密码，它要求计算毋) 不凼难，而且若第三者不掌握密钥 k ，即使截获了密文c ，他也无法从f 中恢复信息m ，也就是反过来从t ? 求m 极其困难。通常称为 兰查! ! ! ! ! 些盔堂 生塑! ! 墨 堡! ：兰g 燮一一 明文。 通信双方一为发信方，或简称为发方，另一方为收信方或简称为收方。传统的保密通信机理可 刚图2 1 表示。 发方：m 坡方 秘密信道 图2 i 传统的保密通信机理 从密文恢复明文的过榉称之为解密。解密算法d 是加密算法e 的逆运算，解密算法也是含有参 数的变换。传统密码加密州的密钥i 与解密_ l f j 的密钥i 娃相同的，所以有时也称对称密码。通信 双方用的密钥t 是通过秘密方式由般方私下约定的，只能由通信烈方秘密掌握。如果丢火密钥t 则 密码系统不攻臼破。 由脚可见，数据加密所依据的密码系统包括以f 四个方面： ( 1 ) 明文信息空问m ：邯信息本来的原始空间。 ( 2 ) 密文信息空间c ：即明文经过加密变换厉成为难以识读的信息空间。 ( 3 ) 密钥空间k ：它控制算法的实现，是由通信双方学握的专门保密的信息空问。 ( 4 ) 密码算法：即数据的加解密变换，它规定了明文与密文之闻的变换方式。它可以是数学问 题求解的公式、法则城样序。密码算法包括： 加密算法：邑：m c ，其中女k ： 解密算法：d ：c + a ，其中七k ； 在密码技术中密钥捌密码算法是两个摄重要的、最基本的阅素。一般米说密码算法搓公开的、 确定的；而密钥是可变的、保密的。从某种意义上米说，算法可以石作是常萤，密钥町以石作是变 鳍。在不改变算法时，只要采瑚不同的密钥，就可以将相同的明文加密成不同的密文。冈此密码中 关键问题是密钥的产生与密码算法的没计。其基本要求是：一是户方便；二是应具有较强的抗攻 击能力即具硝较高的保密强度。也就是说即使1 f 通信烈方的其他人知道了密文c ，甚至掌握了 加密、解密的算法本身，也稂难擞据这些己知条中卜米推导出密钥来，网而无法从已知的密文得到原 来的明文。 + # 末蛳j 把人学计箨税系碳 j 学位论义 2 1 3 密码体制分类 根据密钥的特点，s i m m o n s 4 l ：隐密码体制分为对称密码体制( s y m m e t r i cc r y p t o s y s t e m ) 和 竹对称 密码体制( a s y m m e t r i cc r y p t o s y s t e m ) 蜒秘e 1 对称密码体制 所谓对称密码体制，即加密和解密使州的密钥是相同的，网此该体制又称作单密钥密码体制。 它璃 侮统密捣，丧这种体制中。鄱使有时加密、解密密铜不褶嗣倦它们之闻仍存在蓑一定静联 系，是择易棚且推导山米的。d e s 魁这种密码体制的代表。 霹称密磷俸稍存盘袭灞个主要黼蓬：一楚滋镄携势配岛管瑾方瑟鹃遴难。蕊整与鼹密筏弼麓是 相同冉勺密钥，收发烈方必颁知道同个密钥，他”j 必须事兜通过某种秘密途径商定密钥。另外当n 个人遥穗嚣季，需要兹密锈数为口取- - 豫兮，菪玄1 0 0 拿大，掰嚣要瓣密键鼗裁是4 9 5 0 令。掰就， 有关密钥的分配、安全传送、保密静理是一件很幽难的事情。二是数据的完整性保护方面的嘲难， 幽j ：豫密翅蘩凝方燕具露共同豹龆、瓣密密钢，信息豹接受方可班缀套易地篡改琢文内赛，薅信息 的发送方也w 以否认自融所发的内释。对称密码体制在数字签名和身份认证方面的应川是相当凼难 繁l 不现实的。 2 非对称密码体制 所谓1 f 对称密码体制，却加密和解密使删舶密钥是不糊周的，也称之为取密钥密码体制。非对 称密码体黼瓣基本思想遗：不仅公开蕊密算法，两苴加密黼的密钥也公开。繇可默梅每一豫户的加 密密钥作为公钥文f t t ，象电活号码簿一样公开只要解密密钥保密就可以了而魁再j ! 户的解密密 钢由蔷拜j 户鑫己裸密保管。若瑁户a 耍肉强户1 3 发送信惠，a 霹敬款公铸文住中霞蜘b 静鞠密密锈 制_ i _ 它向b 敏送密文，b 收剑密文脐利州只有自己知道的解密密钥解密得到明文。由丁这种密码体 铡黥麴密密钢楚公舅瓣，鬻魏叉豫逡秘龆整舔割为公帮密钥密疆搏割，篱拣蛰钢俸翻。它在豢锈簧 珊与使j h 方耐为h j 户带米了明显的好处，在数字签名与身份认证领域育着j 。阔的前景。 2 2 公钥密码体制 2 2 。1 公钥密码体截酶原理 公开密铜畿妈 毒剿中，积密密钥与瓣密密甥强箕且分离。虽然扶理论上讲，解豢密甥可痰麴密 密钥计筇出，位娃这种谢码体制建：巍的思想基础魁使这种逆向计算在实际上成为不可行。也就是醢， 华东师范人学 汁算机系坝i 。学位论史 在实际中，解密密钥不可能由加密密钥或加密信息、加密技术以及破译技术简单地产生喊推算出来。 如果解密密钥需要世界上最快的计算机运行数年才能算i ，那么这种密码事实上就是安全的。公钥 密码体制的加密算法都是基丁一一种特殊的数学函数，即单向陷r j 函数，因此公钥算法均满足以f 二 个条1 ，| = ： ( i ) d 是e 的逆。 ( 2 ) e 雨l d 都容易计算。 ( 3 ) 仅根据e 去找山计算d 的简单算法则是缀剀难的。 其数学描述不火一般| 生有： 口d ( ( x ) ) 2x e “t d 、k t x l l 。x 其中是公钥体制中每个t j 户的加密算法，即单向i f j f j 函数d 是解密算法，是e 的逆变换函 数。e 羽d 具有等同性也可以是不同的。础是公开的加密密钥，矗是保密的私有密钥。 所谓单向幽数，即从一个方面搬容易求值，而其逆向汁箅却十分划难。比如说：对丁函数y = m ) ， 任意给定自变量卫则能够很容易地计算山函数j ，的值，而由任意给定的j ，值，即使是按 ! 已知的 函数关系的性质也很难求出的值。公钥密码体制l 救刚单向陷门函数这一独特的性质，使得计莽加 密豳数e 对1 i 任何人都是简单可行的，然而住没有给定的条什r 仅仅根据已知的加密函数e 去逆向 求解解密函数d ，在计葬上是极其凼难的，甚至是不可能的。这种“条件”或者说是“专门信息”， 称作为陷。所谓“j i f ；门”是指一口掌握了保密的“陷门”信息，求其逆函数是容易的。公钥密码 体制使不掌握“陷fj 的破译者1 f ! ! i ：解密过稗中将不可避免地遇到特定的计算上的难题。冈此，公钥 密码体制的安全性依赖丁这种单向| f f ；门函数，但这种单向陷f j 函数是比较难以找到的。 在公钥密码体制r ，任何人都可以使川其他j ；l j 户的公开密钥来对数据进行加密，但是只有拥 有保密的私有密钥的h 户才能对加密的数据解密。在这种体制f ，刨使知道丁加密算法和加密密铜 也不会闭此泄露解密密钥。 1 9 7 7 年，r i v e s t 、s h a m i r 千a d l e m a n 提山了著名的r s a 公钥密码体制l ”。从此以后，人们基丁 不同的计算问题，提出了人鼙的公钥密码算法，这些加密方法的安全性都是基丁复杂的数学难题。 对丁某种数学难题，如果利川通川的算法计算出密钥的时间越，那么基下这数学雉题的公钥密 码体制就铍认为越安全。根据所基于的数学难题来分类，以f 三类密码体制日f j 茸被认为是安全和有 敛的： ( 1 ) 基 i 粘数冈子分解的鬻码体制( 如r s a 密码体制) 。 ( 2 ) 基 。离敞对数问题的密码体制( 如e l g a m a l 密码体制) 。 1 2 毕东师范人学汁算机系 坝i j 学位论史 ( 3 ) 基- r 椭圆曲线离散对数问题密码体制( 即椭圆曲线密码体制) 。 f 面对儿种典删的密码体制进行分析讨论。 2 2 2r s a 密码体制 r s a 公钥密码体制的理论基础是一种特殊的可逆模指数运算。它的安全性是基丁分解人整数的 凼难性。以f 是r s a 算法的描述15 j ： 设n 是两个不同的奇素数p 嗣ig 之积，即 1 l = p q ，( n ) = ( p 一1 ) ( g 一1 ) k = ( ”，p ，q ，d ，b ) 1 月= p q ，p 羽q 是素数，口6 = l ( m o d o ( n ) ) 对每一个k = ( 1 7 ，p ，吼a ，b ) ，定义 加密变换为：e r ) = z 6 ( m o d n ) ，x z 解密变换为：d k ( y ) = y “( m o d ”) ，y z ，。 公开月和b ，保密p ，q 垌l 口。 为了建立密码系统，州户b 。ir i 要完成以下步骤： ( 1 ) 随机选取两个人素数p 和g ( 保密) ： ( 2 ) 计算h = p q ( 公开) 和( 月) = ( p 一1 ) ( g 一1 ) ( 保密) ； ( 3 ) 随机选取整数6 使满足g c d ( 6 ，( n ) ) = l ：4 0 b ( ”) 。将b 公开，即为加密密钥。 ( 4 ) 计算a ，满足a b ；l ( m o d o ( n ) ) 。a 保密即为解密密钥。 r s a 密码体制的安全性依赖r 两个人素数p 平9 ，若”= p q 被冈式分解f j ! jr s a 便被击破。 冈为若p ，q 己知，j l | l j 矿( 肝) = ( p 1 ) ( g 一】) 便可莽出，解密峦钥口关丁b 满足曲= i ( m o d 舻( 甩) ) ， 故a 也不难求得。冈此r s a 的宜全性依赖t ：因式分解的凼难性。由于计算水平的提高，人们逐渐可 以刚计算机分解更人的数。冈此r s a 算法的密钥也就越米越艮。在l j 1 子商务的s e t 协议中，规定 刚户使1 0 2 4 比特的r s a 密钥，认汪中心c a 使州2 0 4 8 比特的r s a 密钥。带来两个问题，一是 运算速度较慢，另一个是密钥存储和管理问题。 一一 ! ! 堡些丝查兰生墼! ! 墨 堡! ：兰些笙兰 2 2 3e l g a m a l 密码体制和离散对数 1 离散对数i 司邈 对实数来说，取幂运算( 计算扩剑一指定精度) 不比它的逆运算( 求l o g 盯到一定精度) 容易 得多。但对有限域米讲，i l j 快速取幂算法，可以相当快地对较人的整数x 计算出b 。，但如粜给定一 个元素y t 且己知存在一个整数x ，使得对一州定的基b ，有y = ，如何求山x ，则是一个1 f 常困难 的问题这个问题就是离散对数问题f 6 j 口 定义：离散对数问题( d l p ) 是指：给定一个素数p z ，的一个生成元a 及一个元素z ：， 寻找一个整数x ，0 x p 一2 ，使得d 。i f l ( m o d p ) 。通常州j o g 。米表示j 。 一般地，如果仔细选择p ，那么认为该问题是凼难的。特枷是，目前还没有找到汁算离敌对数 问题的多项式时间算法。为了抵抗己知的攻击，p 应该至少是1 5 0 位十进制整数，并且p - 1 至少有一 个人的素冈子。之所以离敖对数问题在密码环境中是有用的，是田为找离散对数是凼雉的，但模指 数逆造算可使州“平方一乘”方法有效地计算。即对适当的素数p ，模p 指数运算是一个单向函数。 2 e l g a m a l 密码体制 e l g a m a l 算法7 l 是在密码协议中有着大量麻刚的一类公钥密码算法，它的安全性是基丁解离散 对数问题的凼难性。以f 是e l g a m a l 算法的详细描述： 首先每个使_ l j 者( h ja b 表示) 按如r 方法生成自己的一对公钥和私钥： ( 1 ) 生成一个人的随机素数p 萃f f 整数模p 的乘法群z ：的一个生成元口。 ( 2 ) 选取一个随机整数口，l n p 2 ，t t g a 。( r o o d p ) 。 ( 3 ) a 的公开密钥是( p ，d ，岱。) ：a 的私钥是a 。 假改b 加密消息m 给a ，a 解密h | e l g a m a l 体制的加解密过程如f ： ( 1 ) b 执行如r 步骤： 获墩a 的真实公玎密钥( ，口，口“) ： 将消息i t 表示成 o ，l ，p 一1 范罔内的整数； 选取随机整数女，i k p 2 ： 计算y = 口。( m o d p ) 年占= r n ( 口“) ( m o d p ) ； 发送密文c = ( y ，占) 给a 。 1 扫东师范大学计算帆系删j 。学位论义 ( 2 ) 为从c 中恢复出明文m ，a 执行： 使_ j 私钥口计算，”“( r o o d p ) ( 注：y + “( m o d p ) = ，= 口一“) ； 通过计算( y ”) 8 ( r o o d p ) 恢复出m 。 a 能够恢复山m 是由于( y 叫) 占三a 一时m 2 甜暑r e ( r o o d p ) 。 攻击e l g a m a l 密码体制，即从给山的p ，口，t 2 “，y 利占中恢复山m ，等价丁解离散对数问题。非 常重要的一点是，要用不同的随机整数k 来加密不同的消息。假设同一个随机整数k _ l _ | j 来加密两个 消息m 1 和m 2 ，所得到的密文对分别是( ，l ，匹) 和( y 2 , 屯) ，则芭8 2 = m l m 2 ，故当m i 已知，m 2 可以很快计算出来。 e l g a m a l 密码体制的一个缺点是“消息扩展”，即密文艮度是所对应的明文k 度的两倍。 2 2 4 椭圆曲线密码体制 椭圆曲线密码算法是基于有限域上的椭圆曲线的点群中的离散对数问题e c d l p ( e l l i p t i cc u r v e d i s c r e t el o g a r i t h mp r o b l e m ) 。e c d l p 是比因子分解问题更难的问题，目前对撇倒曲线离教对数还没 有一般的子指数时间的算法，至今己知虽好的算法需要指数时间。这就意味着j ；j 椭圆曲线米实现的 密码算法可以用小一些的数来达到使用更大的有限域所获得的安全性。从目前己知的最好求解算法 来看，1 6 0 比特的椭哑曲线密码算法的安全性相当于1 0 2 4 比特的r s a 算法。椭圆曲线密码体制有 以p 两个明显的优点： ( i ) 具有短的密钥长度，这意味着小的带宽羊存储要求，这些冈素在某些应川场台十分有用， 诸如在智能 系统中。 ( 2 ) 所有的川户可选择同一基域，上的不同的椭圆曲线e 这可使所有的_ l i = | 户使j l i _ j 同样的硬件 完成域算术，为保证安全性，只有椭圆曲线e 的选择的不同。 本文第三章将对椭圆曲线密码体制作详细分析，这里先简单介绍其加解密过稗吼 1 系统的建立和密钥的生成 选取一个基域t 一个定义在上的椭圆曲线e 和e 上一个阶为素数 的点p 点p 的坐标 用( x ，y ，) 表示。有限域椭圆曲线方程，点p 和阶n 是公开信息。 系统建成后，每个使) t d - 昔( 简称实体) 进行r 列计算： ( j ) 在区问【1 ，n - 1 】中随机选取一个整数d 。 # 东帅地人学 汁算机系 颅i ：学位论史 ( 2 ) 计算点q = 扩。 ( 3 ) 实体的公开密钥包含点q ，实体的私钥是整数d 。 2 椭圆曲线加密体制 加密过程： 当实体b 发送消息m 给实体a 时实体b 执行r 列步骤： ( j ) 卉找a 的公开密钥g 。 ( 2 ) 将数据m 表示成一个域元素m e 凡。 ( 3 ) 在区间【l ，月- 1 】中随机选取一个整数k 。 ( 4 ) 计算点“i ，y 1 ) = 舻。 ( 5 ) 计算点，! ) = 女q ，如果x 2 = 0 ，则同刮第3 步。 ( 6 ) 计算c = m x 2 。 ( 7 ) 传送加密数据( x 1 ，y l ，c ) 给a 。 解密过群： 当实体a 解密从b 收剑的密文旺，y l ，f ) 时a 执行f 列步骤： ( 1 ) 使州它的私钥d 计算点( 趣，y 2 ) = d o | ，h ) 。 ( 2 ) 通过计算m = c ，恢复出数据m 。 上述过科中，q = d p 是公开的，如果除a ，b 外的第三者能解椭圆曲线上的离散对数问题，就 能从d p 中求出d ，从而解密消息。 2 3 数字签名方案 2 3 1r s a 数字签名方案 一般地，一个数字签名方案土要由两个算法，即签名算法和验证算法组成。签名者能使_ 【_ j 一个 ( 秘密) 签名算法s 堙( ) 签一个消息x ，导致的签名s 强( x ) 可通过一个公开的验证算法p 钉( ，_ ) 来验 证a 给定一对( x ，y ) 验让筇法根据签名是否真实米作山一个“真”戏“假”的同咎。一个数字签 名方案可由满足f 列条什的五重组( p ，a ，丘sr ) 米描述： ( 1 ) p 是所有可能消息组成的一个有限集合。 ( 2 ) a 是所有可能签名r 成的一个有限集合。 ( 3 ) k 足所有可能密钥组成的一个有限集合，即密钥空间。 i 兰墨塑垫叁兰生竺! ! 墨堡! ：兰竺堡墨 ( 4 ) 对每一个 k ，舀一个签名算法踞女( ) s 雨一个对应的验证算法v e r a , ) va 每 + s i g 女( ) ：p a 车| l 地( ，) ：p x a 辛 真，假) 是满足r 列等式的函数：对每一个消息x p 和每 一个签名y a ，有舱丘( x ，y ) = 真，当且仅当y = 踞女0 ) 。对每一个k ，阮 ( - ) 平| l v e r a ，_ ) 都是多项式时间函数，比“( ，) 是一个公开函数而s i g 。( ) 是一个秘密函数。 f 面介! “r s a 数字签名方窠吼 设”= p q ，p 平q 是两个素数，定义k = ( ”，p ，吼口，6 ) in = p q ，p 平g 为素数， a b z l ( m o d o ( n ) ) 。值h 雨jb 是公开的，p ，q 羽i 口是保密的一 对k = ( ”，p ，g ，日，b ) 定义s ；g k ( x ) = x 。( r o o d n ) ，工z 。， 舱k ( x ，y ) = 真爷z 5 y h ( m o d n ) x ，y z 。 如果b 使j jr s a 解密规j i | l jd 。签一个消息x ，那么b 是能产生签名的唯一的人这是冈为d 一 是保密的。验证算法使川r s a 加密规! j ! j je i 。因为昧是公开的，所有任何人都能验证一个签名。 r s a 数字签名算法的弱点如r ： ( 1 ) 任何人能通过对某一y ，计算r = i ) 伪造一个随机消息x 关y - b 的签名y ，这是冈为 y = s 喀k ( x ) 。 ( 2 ) 如果消息x i 和x 2 的签名分刖是y l 平【y 2 ，则拥有x l ，y i 。2 ，n 的任何人可伪造b 关t ：消 息x ix 2 的签名y i y 2 ，这是冈为踞k ( x l x 2 ) = s g k ( x 1 ) s g r 2 ) ( m o d n ) 。 ( 3 ) 签名者b 每次只能签 1 0 啦川比特艮的消息，获得同样长的签名。一般来说，所要签的消息 都很& 如粜直接消扈、进行签名只能先把所要签的消息分成 1 0 9 2 月】比特k ：的组，逐组进行签名。因 为r s a 数字签名中所涉及的运算都是模乘法运算和模指数运算所以这样做速度慢，而且签名太艮。 2 3 。2e l g a m a l 型数字签名方案 e l g a m a l 丁1 9 8 5 年基丁离散对数问题提出了一个既可心丁加密义可删于数字签名的密码体制。 这个数字签名方案的一个修改已做美国国家标准技术研究所( n i s t ) 采纳为数字签名标准。e l g a m a l 数字签名方突像e l g a m a