（计算机软件与理论专业论文）具有消息恢复功能的椭圆曲线签名方案的研究与实现.pdf

具有消息恢复功能的椭圆曲线签名方案的研究与实现 摘要 随着电子商务和电子政务的深入发展，数字签名技术变的越来越重要。与 r s a 密码体制相比，在密钥长度相同的情况下，椭圆曲线密码体制安全强度更 高，因此基于椭圆越线密码体制的数字签名方案得到了广泛的关注。消息恢复 数字签名方案具有签名消息短的特点，对基于身份的公钥密码系统和密钥交换 协议具有重要意义。然而，目前已知的椭圆曲线数字签名方案都不具有消息恢 复功能，因此有必要基于椭圆曲线密码体制建立消息恢复数字签名方案。 本文对基于椭圆曲线的消息恢复数字签名方案进行了研究，主要包括以下 几方面的内容： ( 1 ) 通过对椭圆曲线上标量乘的分析，提出了在g f ( 2 ) 域上的非超异椭圆 曲线标量乘的一种快速算法。在参数r n 选取最优的情况下，该算法比二进制 算法效率提高约5 0 。 f 2 ) 通过对e c c 签名方案进行分析，构造了新的签名方案，该方案避免了 e c c 签名方案中的求逆运算，并且解决了e c c 签名方案不能实现消息恢复的 问题。 ( 3 ) 在作者构造的签名方案的基础上设计了基于身份的无信任限制的公钥 和具有相互认证功能的一次传输密钥交换协议。 f 4 ) 对作者构造的消息恢复数字签名方案进行了实现。 关键词：椭圆曲线数字签名消息恢复点乘 r e s e a r c ha ndi m p i e m e n t a t i o no f e l l i p t i cc u r v ed i g i t a l s i g n a t u r es c h e m ew i t hm e s s a g er e c o v e r y a b s t r a c t w i t hp r o f o u n d l yd e v e l o p m e n to fe l e c t r o n i cb u s i n e s sa f f a i r sa n de l e c t r o n i c g o v e r n m e n ta f f a i r s ，d i g i t a ls i g n a t u r et e c h n o l o g yb e c o m em o r ea n dm o r ei m p o r t a n t c o m p a r e dt or s a ，w i t hk e y so ft h es a m el e n g t h ，e l l i p t i cc u r v ec r y p t o g r a p h y ( e c c ) o f f e r sm o r es e c u r i t ys t r e n g t h ，t h u se c c - b a s e dd i g i t a ls i g n a t u r es c h e m e a t t r a c t st h em o s ta t t e n t i o n d i g i t a ls i g n a t u r es c h e m ew i t hm e s s a g er e c o v e r yh a st h e a d v a n t a g eo fs h o r t e rs i g n a t u r e ，t h i si si m p o r t a n tf o ri d e n t i t y b a s e dp u b l i ck e y s w i t h o u tr e s t r i c t i o n si nt r u s ta n df o r o n e - p a s sk e yp r o t o c o l w i t hm u t u a l a u t h e n t i c a t i o n h o w e v e r ，a l lk n o w n e de c c - b a s e dd i g i t a ls i g n a t u r es c h e m e sc a nn o t r e c o v e rm e s s a g ef r o ms i g n a t u r e t h u s ，r e s e a r c ha n di m p l e m e n t a t i o no fe l l i p t i c c u r v ed i g i t a ls i g n a t u r es c h e m ew i t hm e s s a g er e c o v e r yd om a k es e n s e t h i sd i s s e r t a t i o nf o c u s e so nt h er e s e a r c ho fd i g i t a l s i g n a t u r es c h e m ew i t h m e s s a g er e c o v e r yb a s e do ne c c t h ec o n t r i b u t i o n so ft h ed i s s e r t a t i o na r ea s f o l l o w s ： ( 1 ) a na l g o r i t h mi sp r e s e n t e dw h i c hs p e e d ss c a l a rm u l t i p l i c a t i o no nn o n s u p e r s i n g u l a re l l i p t i cc u r v ed e f i n e do v e rg f ( 2 ”) w i t ht h i so p t i m i z e dv e r s i o no fb i n a r y m e t h o d ，t h ee f f i c i e n c yo ft h ea l g o r i t h mi si m p r o v e d5 0p e r c e n tw h e no p t i m a lc h o i c e o f m i su s e d ( 2 ) w i t ha n a l y s i so ft h ee c c b a s e dd i g i t a ls i g n a t u r es c h e m e ，an e ws i g n a t u r e s c h e m ei sp r e s e n t e d ，w h i c ha l l o w ss i g n a t u r ew i t hm e s s a g er e c o v e r ya n dw i t h o u t i n v e r s i o n ( 3 ) t h en e ws i g n a t u r es c h e m ei sa p p l i e dt oc r e a t ea ni d e n t i t y - b a s e dp u b l i c k e y ss y s t e mw i t h o u tr e s t r i c t i o n si nt r u s ta n dao n e p a s sk e ye x c h a n g ep r o t o e o lw i t h m u t u a la u t h e n t i c a t i o n ( 4 ) f i n a l l y ，e c c - b a s e dd i g i t a ls i g n a t u r es c h e m ew i t hm e s s a g er e c o v e r yi s i m p l e m e n t e d k e y w o r d s ：e l l i p t i cc u r v e ，d i g i t a ls i g n a t u r e ，m e s s a g er e c o v e r y ，s c a l a rm u l t i p l i c a t i o n 图目录 2 1 传统密码体制的简化模型6 2 2 公钥密码体制的简化模型8 3 1 椭圆曲线上的点加运算，1 7 3 2 椭圆曲线上点的倍加运算1 8 3 3e c c 和r s a d s a 安全性比较图2 9 5 1 携带冗余信息的消息m 的表示4 4 5 2 系统整体结构图4 5 5 3 点乘运算的层次结构4 7 5 4 系统参数5 4 5 5 产生密钥5 5 5 6 消息签名。5 6 5 7 验证签名5 7 5 8 从签名中恢复出原始消息5 7图图图图图图图图图图图图图 表目录 表2 1 安全服务和安全机制问的关系， 表3 1 基本方法与改进方法需要的点乘次数的比较 表3 2 利用p o l l a r d 方法来破解e c d l p 所需要的计算能力 表3 3r s a d s a 和e c c 安全模长比较 表5 1 新签名方案与e c d s a 签名方案实验数据对比( 时间： 表5 2 新签名方案与e c d s a 签名方案平均运行时间比较 5 2 4 2 6 2 8 5 8 5 8 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及 取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论 文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 合肥工业大学或其他教育机构的学位或证书而使用过的材料。与我 一同工作的同志对本研究所傲的任何贡献均已在论文中作了明确的说明 并表示谢意。 学位论文作者签名：禽l 僻渺签字日期：扣年，月1 7 日 学位论文版权使用授权书 本学位论文作者完全了解佥魍王些太堂有关保留、使用学位论文的 规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许 论文被查阅和借阅。本人授权金胆王些太堂可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：1 反傈妒 签字日期：跏衫年，月工1 日 学位论文作者毕业后去向： 工作单位：擎爹才苎术嘲弼鼢审 通讯地址： 导师签名 签字日期缈6 年厂月叫日 电话： 邮编： 致谢 值此论文完成之际，谨向我的导师叶震副研究员表示最真挚的感谢! 论文是在叶老师的指导下完成的。在论文的撰写过程中，叶老师提出了很 多指导性的意见，并多次对文稿进行了悉心的审阅。三年来，不论是在学 习上还是在生活上，叶老师都给了我极大的关心和帮助。叶老师严谨的治 学态度、广博的知识、敏锐的学术思想更是给了我深刻的影响。 感谢一起学习的师兄弟们。 感谢指导和帮助过我的老师；感谢帮助过我的同学。 感谢我的父母，感谢他们对我的养育之恩，没有他们的支持，我不可 能取得今天的成绩。 最后，感谢尹家生同学，在我读研的三年中，对我学习的督促、鼓励 和支持。 作者：侯保花 2 0 0 6 年4 月 第一章导论 1 1 消息恢复数字签名的研究现状 数字签名的概念由d i f i l e 和h e l l m a n u 于1 9 7 6 年最先提出，目的是使签名 者对电子文件可以进行签名并且无法否认，验证者无法篡改文件。随着密码学 研究的不断深入，数字签名作为现代密码学的主要研究内容有了进一步发展。 从1 9 9 4 年n y b e r g 和r u e p p l e 首次提出了一类具有消息恢复功能的数字签名方 案以来，出现了多种具有消息恢复功能的数字签名方案。 消息恢复数字签名是指在对消息进行签名以后，验证者可以直接从签名恢 复出原消息的一类数字签名方案。因为可以从签名中恢复出原消患，因此不用 象一般的数字签名那样，必须把签名和消息m 进行绑定传输，即在传送签名的 过程中，可以不传送被签名的消息m 。因此，其优点是可以减少通信量，并且 在某些应用中可以提高系统的安全性。 这种方案适用于对短消息进行签名，下面是它的几个典型应用： 1 会话密钥协商，现在常用的对称密码体制a e s 的密钥长度可以为5 6 、 1 2 8 、1 9 2 位，满足短消息的条件，因此可以有效的用消息恢复数字签名方案设 计出一次传输密钥协商协议。 2 在公钥密码系统中，如果使用的公钥体制是e c c ，则公钥的长度1 6 0 位 就可以满足安全的需要，因此c a 可以使用消息恢复数字签名方案对用户的公 钥进行签名，在这种情况下，在c a 的证书中可以不包含用户的公钥，因为， 其它用户在验证c a 签名对可以恢复出被签名的公钥，从而可以减少通讯量。 3 此外，消息恢复数字签名方案对信用卡、员工令牌等小型身份认证系统 也是非常有效的。 r s a 算法是大家熟悉的公钥密码算法，用它可以实现消息恢复数字签名。 然而r s a 算法是基于大整数分解难题上的，由于计算机的计算水平的提高，人 们逐渐可以用计算机分解更大的整数。椭圆曲线密码系统( e c c ) 具有密钥短， 运算速度快的特点。目前最好的算法表明，1 6 0 比特的椭圆曲线密码算法的安 全性相当于1 0 2 4 比特的r s a 算法。因此，基于椭圆曲线建立消息恢复数字签 名系统，可以在很大程度上改善消息恢复数字签名系统的安全性和性能。 目前，基于整数分解和离散对数的消息恢复数字签名方案已经有了比较深 入的研究，并且有相应的标准i s o i e c 9 7 9 6 。由于椭圆曲线自身的复杂性，目 前对基于椭圆曲线的消息恢复数字签名方案的研究并不多。 1 2 椭圆曲线密码体制的研究现状 当前，国际上主流的公钥加密技术采用的仍然是r s a 密码体制。但是，先 进的椭圆曲线公钥密码体制已经得到了业界的广泛认可。1 9 9 9 年a n s ix 9 6 2 标准的发布成为椭圆曲线密码体制标准化的一个重要的里程碑。同年美国政府 的国家标准与技术委员会( n i s t ) 发布了新的规定，确定了椭圆曲线密码体制 的地位。现在已经颁布的有关椭圆曲线密码体制的标准还有f i p s1 8 6 2 、i e e e p 1 3 6 3 、i s o i e c l 4 8 8 8 、s e c l 、s e c 2 、a t mf o r u m 等，这将提高椭圆曲线公钥 密码体制在世界范围内的通用性，使椭圆曲线公钥密码体制在全球的广泛应用 成为可能。 目前，在椭圆曲线公钥密码体制的研究和应用方面处于世界领先地位的是 加拿大的c e r t i c o m 公司。经过十多年的研究，c e r t i e o m 公司探索出了可以商用 的实现椭圆曲线密码体制的方法。从1 9 9 7 年开始，全球各大公司和机构开始采 用c e r t i c o m 的椭圆曲线公钥技术或与之建立联盟。 椭圆曲线密码系统和r s a 1 3 s a 相比有许多优点，如能用较短的密钥实现 同等的安全强度、计算量小且处理速度快、带宽要求低等。现在经过理论研究 和科学实践，已经可以将椭圆曲线密码系统由理论转化为实际的可用的密码算 法，并将其应用于安全产品之中。国际权威密码机构已经确认椭圆曲线密码系 统将逐渐取代r s a 密码系统成为公钥密码系统的主体，发展前景十分广阔。 1 3 本文结构 本文的后续章节安排如下： 第二章介绍了o s i 安全框架中的安全服务，安全攻击和安全机制，现代 密码学中公钥密码体制、私钥密码体制以及公钥密码体制的重要应用一一数字 签名的基本概念和常见的几种数字签名方案。 第三章对在椭圆曲线加密中常用的有限域只。和有限域只进行了介绍，包 括用于表示有限域只，上元素的多项式基和正规基。总结了椭圆曲线密码系统 基本理论，目前椭圆曲线的攻击现状以及基于椭圆曲线的应用：e c d s a 、e c d h 、 e c e s 。对椭圆曲线加密中重要的运算点乘迸行分析，并提出新的算法。 第四章通过对e c c 签名方案进行分析，在保证签名算法安全性的前提下， 构造了新的签名方案，解决了e c c 签名方案中存在的需要求逆运算和不能实现 消息恢复的问题，大大的简化了运算的复杂程度。在该签名机制的基础上设计 了无信任限制的公钥密码机制和具有相互认证功能的一次传输密钥交换协议。 第五章对冗余函数进行设计，对提出的新的签名方案进行实现。 第六章对整篇论文的工作进行了总结，指出了进一步研究的方向。 第二章网络安全与现代密码学 随着通信网络特别是i n t e r n e t 的高速发展，利用网络进行信息交流和信息 处理变的越来越普遍，社会的传统事务和业务运作模式受到前所未有的冲击。 目前，无论是国家政府还是企业都正融入这场网络革命中，从其原来的传统工 作模式向网络模式演化。未来的电子政务、电子商务、电子业务将成为不可逆 转的发展趋势。在与曰俱增的网络活动中，人们越来越关心信息安全这个问题， 这集中体现在： r l 】信息和数据的保密性一个人或系统机密信息和数据的保护 ( 2 ) 网络的身份认证一一确认网络客户的真实身份 ( 3 ) 信息和数据完整性一防止不合法的数据修改 ( 4 ) 不可抵赖性一一网络环境下行为的事后不可抵赖 对于后三个要求，可以采用数字签名同时解决，对于第一个问题可以采用 加密技术。信息安全中最核心的技术是密码技术，密码技术基本上可分为序列 密码、对称密码( 又称分组密码) 、非对称密码( 又称公钥密码) 三种。其中非 对称密码技术的一个非常重要的应用就是数字签名。 2 1 网络安全 信息化进程的深入和互联网的快速发展，网络化已经成为企业信息化的发 展大趋势。但是，紧随信息化发展而来的网络安全问题日渐突出，网络安全问 题已成为信息时代人类共同面临的挑战。 i t u tx 8 0 0 标准将人们常说的“网络安全( n e t w o r ks e c u r i t y ) ”进行逻辑上 的分别定义1 ，即安全性攻击( s e c u r i t ya t t a c k ) ( 网络威胁1 ，指损害机构所拥有攻 击信息安全的任何行为；安全机制( s e c u r i t ym e c h a n i s m ) ，指设计用于检测、 预防安全攻击或者恢复系统的机制；安全服务( s e c u r i t ys e r v i c e ) ，指采用一种 或多种安全机制以抵御安全攻击、提高机构的数据处理系统安全和信息传输安 全的服务。 21 1 安全服务 x 8 0 0 将服务分为五类 1 】： ( 1 ) 认证：保证通信实体是它所声称的实体。认证分为同等实体认证和数 据源认证：同等实体认证指用于逻辑连接时为连接的实体的身份提供可信性； 数据源认证指在无连接传输时保证收到的信息来源是声称的来源。 ( 2 ) 存取控制：阻止对资源的非授权使用。 ( 3 ) 数据保密：保护数据免于非授权泄漏，最主要是流量保密。 ( 4 ) 数据完整性：保证收到的数据是授权实体所发出的数据，即没有修改、 插入、删除和重放。 ( 5 ) 不可否认性：在整个和部分通讯过程中，防止任一通信实体进行否认 的行为。其中包括源不可否认性和宿不可否认性：源不可否认证明消息是由特 定方发出的；宿不可否认证明消息被特定方收到。 2 1 2 网络威胁 x 8 0 0 和r f c 2 8 2 8 都使用了一种有用的方式来对安全性攻击进行分类，即 被动攻击和主动攻击。被动攻击试图了解或利用系统的信息但不影响系统的资 源。主动攻击试图改变系统的资源或影响系统的运行。 被动攻击的特点是对传输进行窃听和监测。攻击者的目的是获得传输的信 息。信息内容泄漏和流量分析就是两种被动攻击。被动攻击由于不涉及对数据 的更改，所以很难觉察。然而，通过加密的手段阻止这种攻击却是可行的。因 此，应对被动攻击的重点是预防，而不是检测。 主动攻击包括对数据流进行篡改或伪造数据流，可以分为四类：伪装、重 放、消息篡改和拒绝服务。 伪装是指某实体假装别的实体，重放是指将获得的消息再次发送以在非授 权情况下进行传输。消息篡改是指修改合法消息的一部分或延迟消息的传输以 获得非授权使用。拒绝服务阻止或禁止正常的使用或管理通讯设施。它或者是 使网络失效，或者是使其过载以降低其性能。 被动攻击虽然难以被检测但可以防止。与被动攻击相反，主动攻击难以防 止，但容易检测，所以重点在于检测并从破坏中恢复。 2 1 3 安全机制 安全机制指用来保护系统兔受侦听，阻止安全攻击及恢复系统的机制。 x 8 0 0 中定义的安全机制可分为两类：一类在特定的协议层实现，一类不属于 任何的协议层或安全服务。 特定安全机制包括：加密、数字签名、存取控制、数据完整性、认证交换、 流量填充、路由控制、公正。 普遍安全机制包括：可信功能、安全标签、事件检测、安全审计跟踪、安 全恢复。 安全机制和安全服务的关系如表2 1 ，由表可以看出，安全的网络通信要依 赖于一定的加密算法。所以安全并且高效的密码算法是实现网络安全的保障与 基础，也是两络信息安全中研究的重点。本文的重点是对椭圆曲线密码系统的 理论及数字签名理论进行分析总结，在此基础上，提出基于椭圆曲线的消息恢 复数字签名方案。这是属于密码学研究的范畴，下面对现代密码学作一些简介。 表2 1 安全服务和安全机制之间的关系 加数字访问数据认证流量路由公 密签名控制完整性交换填充控制正 同等实体认证 y yy 数据源认证 yy 存取控制 y 保密性 y 流量保密性 y yy 数据完整性 yyy 不可否认性 yyy 可用性 yy 2 2 现代密码学 在广泛使用数据处理之前，企业主要使用的是物理手段和行政手段来保证 重要信息的安全。采用的物理手段如将重要的文件放在上锁的柜子中，采用的 行政手段如对雇员的检查制度。 最近几十年中，企业对信息安全的要求经历了两个重要的变革。 第一个变革是由于计算机的应用，需要有自动工具来保护保存于计算机中 的文件和其它消息，对于共享系统尤其如此。用于保护数据和阻止黑客的工具 称为计算机安全。 第二个变革是，分布式系统，终端用户与计算机之间以及计算机与计算机 之间传输数据的网络和通讯设施的应用。在信息传输时，需要有网络安全措施 来保护数据传输。网络安全和计算机安全并没有明确的界限。 迄今为止，确保网络与通信安全的最重要的工具是加密。 密码学( c r y p t o l o g y ) 是研究密码系统或通信安全的一门科学。它主要包 括两个分支，即密码编码学和密码分析学。密码编码学的主要目的是寻求保证 消息保密性或认证性的方法，密码分析学的主要目的是研究加密消息的破译或 消息的伪造。密码学的发展历史大致可以划分为三个阶段： 第一个阶段是从古代到1 9 4 9 年。这一时期可以看作是科学密码学的前夜时 期，这阶段的密码技术可以说是一种艺术，而不是一种科学，密码学专家常常 是凭直觉和信念来进行密码设计和分析的，而不是推理证明。 第二个阶段是从1 9 4 9 年到1 9 7 5 年，s h a n n o n 在1 9 4 9 年发表了“保密系统 的信息理论”一文为私钥密码系统建立了理论基础【3 】，从此密码学成为一门科 学。 第三个阶段是从1 9 7 6 年开始至今。1 9 7 6 年d i f f i e 和h e l l m a n 发表了“密 码学的新方向”一文h j ，使密码学发生了一场变革，他们首次证明了在发送端 和接收端无密钥传输的保密通信是可能的，从而开创了公钥密码学的新纪元。 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 公钥密码体制 5 l 。从那时起，人们基于不同的计算问 题提出了许多公钥密码体制，其中最著名的是基于离散对数问题的e 1 g a m a l 公 钥密码体制。但就各方面而言，r s a 密码体制都有其不可替代的优势，因而r s a 密码体制从诞生至今一直都是公钥密码体制的主流。人们发现椭圆曲线离散对 数问题是比大整数因子分解问题和离散对数问题难的多的数学难题，出于该难 题，k o b l i t z 【6 1 和m i l l e r l 7 1 在1 9 8 5 年分别提出了椭圆曲线密码体制。 根据密钥的特点，密码体制可以分为对称密码体制和非对称密码体制。对 称密码体制又称为单钥密码体制或传统密码体制，非对称密码体制又称为双钥 密码体制或公钥密码体制。在对称密码体制中，加密密钥和解密密钥是一样的 或彼此之间容易相互确定。在非对称密码体制中，加密密钥和解密密钥不同， 从一个难以推出另一个。私钥密码体制的主要应用是数据加密，公钥密码体制 的主要应用是数字签名和密钥交换。 22 1 私钥密码体制分析 私钥密码体制是公钥密码体制产生之前的唯一的一种加密技术，从一定意 义上说，密码学的基本目的是保护隐私，也就是通信双方通过某一不安全的信 道传递信息时，只有对方才能破译这信息。在过去，这一愿望是通过私钥密 码体制来实现的，迄今为止，它仍是两种类型的加密中使用最广泛的一种。 私钥密码体制是一种传统密码体制，代表性的有：d e s 、a e s 、i d e a 、r c 5 等， 它们的安全性都是基于复杂的数学运算。 对称加密体制有五个基本成分，如图2 1 。 收发双方共享的密钥收发双方共享的密钥 厂、厂、 vu j 加密算法解密算法 图2 1 传统密码体制的简化模型 若以m 表示所有的明文信息，c 表示所有的密文信息，k 是所有的密钥。则 私钥密码体制是由这样一组函数对构成的： e k ：m 斗c d k ：c - m ，k k 在这里，对于所有的晰m 及k k ，都有磷( e t ( 川) ) = r 。 使用这一系统时，通信双方a 和b 需要事先达成某一秘密密钥k k ，他 们可以通过直接会晤或者通过可以信赖的信使来互相得到对方的密钥。之后， 若a 想发送一组明文给b ，他传送的是密文信息f e 。( 砌。b 根据c 通过解密 函数q 复原信息。显而易见，加密系统应当具有的特点是：d 和e i 易于应 用以及在第三方了解除选用密钥的方法之外的保密系统的其它信息之后，仍然 不可能根据c 得到m 。 对称加密系统最著名的是美国数据加密标准d e s 、a e s ( 高级加密标准) 和 欧洲数据加密标准i d e a 。1 9 7 7 年美国国家标准局正式公布实施了美国的数据 加密标准d e s ，公开它的加密算法，并批准用于非机密单位和商业上的保密通 信。随后d e s 成为全世界使用最广泛的加密标准。但是，经过2 0 多年的使用， 已经发现d e s 很多不足之处，对d e s 的破解方法也日趋有效。a e s 将会替代 d e s 成为新一代加密标准。 尽管私钥密码体制能够满足许多应用的要求，但由于存在以下缺点而限制 了它在一些情况下的应用。 ( 1 ) 密钥分发问题，如上所述，在传送信息的双方在不安全的信道上交流 之前，需要预先选定某一密钥。在某些情况下，传输密钥的秘密信道是不存在 的。 ( 2 ) 密钥管理问题。对于有h 个网络用户的网络系统来讲，每一对用户之 间存在着一个密钥，总共需要n ( n 一1 ) 2 个密钥。如果系统比较大的话，则会因 为密钥量太大而不容易管理。 ( 3 ) 难以实现数字签名。数字签名是手写体的电子信号，它可以使信息的 收到方向第三者确认该条信息是从发送者传送来的。在一个私钥密码系统中， a 和b 双方具有相同的加密和解密能力，也就是说b 无法向第三方证明来自a 的信息确实是由a 发出的。 私钥密码体制的解密密钥和加密密钥相同或容易从加密密钥导出，因而加 密密钥的暴露会使系统变的不安全。私钥密码体制的一个严重缺陷是在任何密 文传输之前，发送者和接收者必须使用一个安全信道预先传送密钥，在实际应 用中这一点是很难做到的。例如，假定发送者和接收者之间的距离很远，他们 要使用电子邮件来通信，在这种情况下，通信双方可能没有合理的安全信道。 2 2 2 公钥密码体制分析 公钥密码学的发展是整个密码学发展历史中最伟大的一次革命，也许可以 说是唯一的一次革命。从密码学产生至今，几乎所有的密码体制都是基于替换 7 和置换这些初等的方法来完成的。几千年来，对算法的研究主要是通过手工计 算来完成的。随着轮转加密解密机器的出现，传统密码学有了很大进展，利用 电子机械轮转可以开发出极其复杂的加密系统，利用计算机甚至可以设计出更 加复杂的系统，最著名的例子就是l u c i f e r 在i b m 实现数据加密标准d e s 时所 设计的系统。轮转机和d e s 加密是密码学发展的重要标志，但它们都是基于置 换和替换这些初等方法之上的。 公钥密码学与其之前的密码学完全不同。首先公钥密码基于数学函数而并 非基于替换和置换。更重要的是，与只使用一个密钥的对称密码体制不同，公 钥密码是非对称的，它使用两个独立的密钥。在公钥密码体制中，解密密钥和 加密密钥不同，从一个难以推出另一个，解密和加密是可以分离的。公钥密码 体制有六个组成部分，如图2 2 ( a ) 。 a 的私钥 。 加密算法解密算法 ( a ) 加密 a 的私钥 o 加密算法解密算法 ( b ) 签名 图2 2 公钥密码体制的简化模型 若以x 表示所有的明文信息，y 表示所有密文信息，公钥集合k u ，私钥 集合k r 。则公钥密码体制是由这样一组函数对构成的： e k u ：x 寸y d ：y 寸x 在这里，对于所有的x x 及k u k u ，k r k r ，都有d 柚( e i u ( 曲) = x 。 公钥密码体制中任何一个密钥都可用来加密，另一个用来解密，这样可以 用公钥密码体制实现认证功能， 签名过程：d ，。：x _ y 验证过程：e 。：y _ x 具体过程如图2 2 ( b ) 。 公钥密码体制可以提供以下功能： ( i ) 机密性( c o n 丘d e n t i a l “y ) ：保证非授权人员不能非法获取信息。通过数 据加密来实现。 ( 2 ) 认证( a u t h e n t i c a t i o n ) ：保证对方属于所声称的实体。通过数字签名来 实现。 ( 3 ) 数据完整性( d a t ai n t e g r i t y ) ：保证信息内容不被篡改，入侵者不可能用 假消息代替合法消息。通过数字签名来实现。 ( 4 ) 不可抵赖性( n o nr e p u d i a t i o n ) ：发送者不可能事后否认他发送过消息， 消息的接收者可以向中立的第三方证实所指的发送者确实发出了消息。通过数 字签名来实现。 从上面可以看出公钥密码体制满足信息安全的所有主要目标，然而却存 在一些对公钥密码体制的一些误解： ( 1 ) 认为公钥密码体制比传统的密码体制更安全。例如g a r d n e r 在 “s c i e n t i f i c a m e r i c a n ”上发表的一篇著名的文章中 8 就提出了这样一种观点。 事实上，任何加密方法的安全性依赖于密钥的长度和破译明文所需要的计算量。 从密码分析的角度看，原则上不能说传统密码优于公钥密码，也不能说公钥密 码优于传统密码。 ( 2 ) 认为公钥密码是一种通用方法，所有传统密码已经过时。其实正相反， 由于现有的公钥密码所需的计算量大，所以取缔传统密码几乎不太可能。就象 公钥密码的发明者之一所说的1 9 】“公钥密码仅限于用在密钥管理和签名这类应 用中，这几乎是已被广泛接受的事实。” ( 3 ) 认为传统密码中密钥分配中心的握手是件异常麻烦的事情，与之相 比，用公钥密码实现密钥分配则非常简单。事实上使用公钥密码也需要某种形 式的协议，该协议通常包含一个中心代理( c a ) ，并且它包含的处理过程既不比 传统的密码中的那些更简单，也不比之更有效。 在实际应用中，公钥密码体制并没有完全取代私钥密码体制，这是因为公 钥密码体制基于尖端的数学难题，计算非常复杂，它的速度远比不上私钥密码 体制。因此，在实际应用中可以利用二者各自的优点，采用私钥密码体制加密 文件，而采用公钥密码体制加密“加密文件”的密钥，这就是混合加密体制。 自从1 9 7 6 年公钥密码的思想提出以来，国际上已经提出了许多种公钥密码 体制，但是比较流行的主要有两类：一类是基于大整数分解问题的，其中最典 型的代表是r s a ：另一类是基于离散对数问题的，比如g l g a m a l 公钥密码和影 响比较大的椭圆曲线公钥密码。由于分解大整数的能力日益增强，所以对r s a 的安全带来了一定威胁。目前7 6 8 比特模长的r s a 已不安全，一般建议使用1 0 2 4 比特模长，预计要保证2 0 年的安全就要选择1 2 8 0 比特的模长，增大模长增加 了实现上的难度。而基于离散对数的公钥密码体制在目前技术下5 1 2 比特模长 就能保证其安全性。特别是椭圆曲线上的离散对数的计算要比有限域上的离散 对数的计算更困难，目前技术下只需要1 6 0 比特模长即可，适合于智能卡的实 现，因而受到到国内外学者的广泛关注。 2 2 3 数字签名 数字签名是公钥密码学发展过程中最重要的概念之一，它可以提供其它方 法难以实现的安全性。 数字签名是对手写签名的一个模拟。手写签名和数字签名的主要差别在于： 签署文件方面，一个手写签名是所签文件的物理部分，面一个数字签名并 不是所签文件的物理部分，所有使用数字签名方案必须设法把签名“绑定”到 所签的文件上。 验证方面，一个手写签名是通过和一个真实的手写签名比较来验证的，当 然，这种方法不是一个很安全的方法，相对而畜是比较容易伪造某人的手写签 名。而数字签名能通过一个公开的算法来验证，这样一来，“任何人”都能验证 一个签名，安全的数字签名方案的使用将阻止伪造数字签名。 拷贝方面，一个手写签名不容易拷贝，因为一个文件的手写签名的拷贝容 易与原文件区别开来，而一个数字签名容易拷贝，这个特点要求人们必须阻止 一个数字签名消息的重复使用，一般要求消息本身包含诸如日期等信息来阻止 重复使用签名。 数字签名需要一个仅被签名者知道的密钥和被签名的消息。签名必须有效， 如果对某一方是否签名引起争议，应该有第三方能够在不需要签名者密钥的情 况下公正的解决这个争议。当签名者否认签名或伪造者伪造签名都会引起争议。 故一个签名方案至少满足以下三个条件： 夺签名者事后不能否认自己的签名 夺接收者能够验证签名，而其他任何人都不能伪造签名 夺当双方关于签名的真伪发生争执时，一个法官或第三方能解决双方之间 发生的争执 2 3 常见的数字签名方案 ( 1 ) r s a 数字签名 基于r s a 公钥密码体制建立的数字签名方案称为r s a 数字签名方案1 们。 选取两个素数mg ，计算n = p q ，矿( ) = ( p 1 ) ( g 1 ) ；随机选取整数p ，满足 g c d ( e ，庐( 月) ) = l ，e 为公钥；计算d ，满足d e ；l ( m o d 妒( n ) ) ，d 为私钥。公开值月、 e ，值p 、q 、d 保密。 签名方程：s = m 4 m o d n 验证方程：m = ，r o o d n 因为s 8 m o d h g ( m 4 1 。m o d n i m “m o d n e ds l ( m o d 驴( n ) ) e d ；1 + z 矿( 疗) j ，2 ( ”) ；l m o d n 所以s 8 r o o d n = m 上面方法的缺点是不具有保密性，可按下面方法签名，其中a 的公钥和私 钥分别为e 。，d 4 ；b 的公钥和私钥分别为e 口，d 。 a 方的签名为： s = 舻m o d n a c j s “m o d n 口 b 方的验证为：c 如s 吼r o o d n 日s s s e h r “r o o d n | ；m ( 2 1e l g a m a l 数字签名 e i g a m a l 于1 9 8 5 年基于离散对数问题提出了一个既可以用于加密又可以用 于数字签名的密码体制川。e i g a m a l 密码体制是基于群z ( 其中的p 为素数) 上 的离散对数问题，也可以将e 1 g a m a l 密码体制一般化到基于任意有限群上的离 散对数问题。 选择一大数p ，另选q 是p l 或p - 1 的大素数因子。然后选择g ，其值在1 和p 之间并且满足9 9 = l ( m o d p ) 。私钥x 小于q ，公钥y = g 。( m o d p ) 。对m 签名 时，取随机数k ，并且满足g c d ( k ，q ) = 1 ，并计算r = g km o dp ，则有： 签名方程：s k = 珥+ r x ( m o d 们 验证签名：r 5 = g ”y ( m o d p ) 签名为一对数：( r ，s ) ( 3 ) d s a 数字签名( d s a ) 在机构f i p s ( f e d e r a li n f o r m a t i o np r c e s s i n gs t a n d a r d ) q b 被制 定，它被称为数字加密标准( d s s ) 1 2 】。它的安全性是基于素数阶子群z ，的离散 对数( d l p ) 的难解性。d s a 数字签名实际是e l g a m a l 签名的一个变体。 1 ) d s a 系统参数的产生： 1 选择一个1 6 0 位的素数q 和一个1 0 2 4 位的素数p ，且q | p - 1 2 选择一个元素h z ：，计算g = h 印。1 v 9 m o d p ，直到g l 3 系统参数即为p 、q 、g 2 ) d s a 密钥对的产生： l 选择一个随机或伪随机的整数x ，1 x q l 2 计算y = g 。r o o d p 3y 为a 的公钥，x 为a 的私钥 3 ) d s a 数字签名的产生，m 为待签名的消息，a 为签名者： l 选择一个随机或伪随机的整数k ，1 k q 一1 2 计算x = g m o d p ，r = x m o d q 。如果r = 0 转到步骤1 3 计算k - 1 m o d 盯 4 计算p = s h a1 ( m ) 5 计算s = k 。和+ x r ) m o d q ，如果s = 0 ，转到步骤1 6 a 对m 的签名为( r ，s ) 4 ) d s a 签名的验证： 1 证明r 和s 在区间 1 ，q 一1 内 2 计算e = s h a1 ( m ) 3 计算1 4 = s 。m o d q 4 计算毡= e w m o d q ，“2 = r w m o d q 5 计算x = g “g “m o d p ，v = x m o d q 6 若v = r ，接受签名 ( 4 1 椭圆曲线数字签名 在1 9 8 5 年n e a lk o b t i t z 和v i c t o rm i l l e r 提出椭圆曲线加密( e c c ) ，这可以 被看作用椭圆曲线对较老的离散对数加密进行模拟，椭圆曲线加密安全的数学 基础是椭圆曲线离散对数的难解性。 s c o o tv a n s t o n e 在1 9 9 2 年首次提出e c d s a i ”】，该方案的提出是作为对n i s t 机构征集d s a 的第一个提案的响应，e c d s a 实际上是用椭圆曲线模拟d s a 。 因为e c d l p 比d l p 难解，因此椭圆曲线系统比传统离散对数系统的单位密钥 安全强度更高。因此椭圆曲线系统要想获得与d l 系统相同的安全强度可以使 用较小的参数。小参数可以带来快速，小密钥，小证书等优点。这些优点对于 处理能力、存储空间、带宽和计算能力受限的环境是非常重要的。因为椭圆曲 线密码系统的诸多优点，e c d s a 很快被很多知名国际组织采纳作为标准，其中 包括在1 9 9 8 年，被i s o 接受作为标准【1 4 1 ，在1 9 9 9 年被a n s i 采纳作为标准【l “， 在2 0 0 0 年分别被i e e e 1 6 和f i p s t 】采纳作为标准。 随着信息技术和网络技术的发展，信息安全问题日益引起人们的重视。密 码学特别是现代密码学则是保证网络安全的基础。网络就是以密码为工具来保 证信息的完整性、不可否认性、身份认证、机密性和存取控制的，其中前三项 都可以通过数字签名来实现。因此，数字签名在网络安全中占有非常重要位置。 1 2 第三章椭圆曲线密码体制基本理论 椭圆曲线密码体制，即基于椭圆曲线离散对数问题的各种公钥密码体制。 最早予1 9 8 5 年由m i l l e r 和k o b l i t z 分别提出。它是利用有限域上椭圆曲线韵有 限点群代替基于离散对数问题密码体制中的有限群所得到的一类密码体制。因 为椭圆曲线离散对数问题是比一般离散对数问题难解的多的困难问题，园此与 般离散对数密码系统相比，椭圆曲线密码系统的比特安全强度更高。所以， 在相同安全级下，e c c 所需要的参数比离散对数密码系统更小。小的参数能带 来许多优点：计算量小，处理速度快，存储空间占用少，带宽要求低。尤其在 计算能力、存储空间、带宽、功率消耗等资源受限制的环境，这些优点非常重 要。 3 1 有限域 在这部分作者将介绍有限域，因为篇幅有限，详细内容请参考k o b l i t z 1 8 】， m e e l i c e 【19 】，l i d l 和n i e d e r r e i t t e r 【2 0 a 域f 有时记为 f ，+ ，x 1 ，是有两个二