（通信与信息系统专业论文）基于ecc的数字签名及其在入侵容忍ca中的应用研究.pdf

武汉理工大学硕士学位论文 摘要 在网络得到快速发展的现代社会，人们越来越重视网络上信息的安全问题。 数字签名技术是当前网络安全领域的研究热点。自从n k o b l i t z 和m i l l e r 提出将 椭圆曲线应用于密码算法以来，以椭圆曲线离散对数的难解性为基础的椭圆曲 线公钥密码体制作为当今安全性最高的公钥密码体制，已经成为国内外计算机 密码学研究的重要课题之一。因此，深入研究椭圆曲线数字签名及其在门限签 名中的应用，具有重要意义。 本文主要是对椭圆曲线数字签名算法的研究，并在此基础上提出了一种基于 椭圆曲线的门限签名方案，主要完成了以下几个方面的工作： ( 1 ) 首先介绍了椭圆曲线密码体制的基本原理，分析了椭圆曲线数字签名 算法e c d s a 。提出了一种改进的数字签名算法p e c d s a ，p e c d s a 消除了 e c d s a 算法中的有限域上的逆元计算，提高了算法的效率，并使之能应用到秘 密共享中。 ( 2 ) 在已有的秘密共享方案的基础上，对一种不需可信中心的秘密共享方 案进行了改进，主要是提出了一种周期密钥更新方案，使其具有前向安全性， 并对此方案进行了实例分析，以论证其正确性。 ( 3 ) 利用改进的数字签名算法pe c d s a 便于秘密共享的特性，结合改进 的不需可信中心的秘密共享方案，提出了一种安全性增强的基于椭圆曲线密码 体制的( t ，n ) 门限签名方案t pe c d s a ，并对其安全性进行了分析，验证其安全性 能是可靠的。 ( 4 ) 将门限签名方案t pe c d s a 应用到入侵容忍c a ( c e r t i f i c a t ea u t h o r i t y ) 中，主要设计了c a 对证书签名的方案，通过将t 个签名者都需要完成的相同工 作转移到c a 一次完成，从而减少系统的计算开销，并且对比i t t c 项目的方案， 从可用性、安全性和效率三方面来分析了本方案的性能，证明了本方案的优越性。 ( 5 ) 设计了一种基于数字签名算法pe c d s a 的数字签名系统，分析了其 系统构架，并进行了实现。实现结果表明数字签名算法p _ e c d s a 是有效的。 关键词：椭圆曲线密码体制；数字签名；门限签名；入侵容忍 武汉理工大学硕士学位论文 a b s t r a c t n o w a d a y s ，n e t w o r k st e c h n i q u e i sa p p l i e dm o r ea n dm o r e ，p e o p l ep a ym o r e a r e n f i o nt ot h es e c u r i t yo ft h ei n f o r m a t i o ni nn e t w o r k s d i g i t a ls i g n a t u r et e c h n o l o g y c u r r e n t l yi sah o tr e s e a r c ha r e ao fn e t w o r ks e c u r i t y s i n c ee l l i p t i c a lc h i v ei sp r o p o s e d b yn k o b l i t za n dm i l l e rt h a ti tc o u l db ea p p l i e di ne n c r y p t i o na l g o r i t h m ，e l l i p t i c c u r v ec r y p t o g r a p h yi st h em o s ts e c u r ep u b l i ck e yc r y p t o g r a p h y , w h i c hi sb a s e do nt h e i n t r a c t a b i l i t yo ft h ee l l i p t i cc u w ed i s c r e t el o g a r i t h mp r o b l e m a n di th a sb e c o m ea m a j o rs u b j e c to ft h ec r y p t o g r a p h ya th o m ea n db r o a d t h e r e f o r e ，i th a si m p o r t a n t s i g n i f i c a n c e si nt h er e s e a r c hi ne c d s a a n di t sa p p l i c a t i o nt ot h r e s h o l ds i g n a t u r e t h i sp a p e rm a i n l yr e s e a r c h e se l l i p t i c a lc u r v ec r y p t o g r a p h y at h r e s h o l ds i g n a t u r e s y s t e mb a s e do ne l l i p t i c a lc l n v eh a sb e e np u t f o r w a r d t h e nt h ef o l l o w i n gw o r k sh a v e b e e nc o m p l e t e d ： ( 1 ) f i r s t ，t h eb a s i ct h e o r yo fe l l i p t i c a l c u r v ec r y p t o g r a p h yi si n t r o d u c e d e s p e c i a l l ye l l i p t i c c u r v ed i g i t a l s i g n a t u r ea l g o d t h r ne c d s ai s i n t r o d u c e da n d i m p r o v e d s oad i g i t a ls i g n a t u r ea l g o r i t h mp _ e c d s a i sp r e s e n t e d ，w h i c he l i m i n a t e s t h ei n v e r s ec a l c u l a t i o no ft h el i m i t e dd o m a i ni nt h ee c d s aa l g o r i t h ma n di m p r o v i n g t h ee f f i c i e n c yo ft h ea l g o r i t h m t h em o s ti m p o r t a n tt h i n gi st h a tp e c d s ac a r lb e a p p l i e dt ot h es e c r e ts h a r i n g ( 2 ) o nt h eb a s i so ft h ee x i s t i n gs e c r e ts h a r i n gs c h e m e s ，as e c r e ts h a r i n gs c h e m e w i t h o u tas h a r ed i s t r i b u t e dc e n t e ri si m p r o v e d m a i n l yas c h e m eo fu p d a t i n gt h e s e c r e tk e yb yp e r i o di sp r o p o s e d ，w h i c hm a k e st h es e c r e ts h a r i n gs c h e m eh a st h e f o r w a r ds e c u r i t y a ne x a m p l eo ft h es e c r e ts h a r i n gs c h e m ew i t h o u tas h a r ed i s t r i b u t e d c e n t e ru s i n gt h es m a l ln u m b e ri sg i v e nw h i c hv e r i f i e st h ec o r r e c t n e s so ft h es e c r e t s h a r i n gs c h e m e ( 3 ) a k i n d o fs e c u r i t ys t r e n g t h e n e d 化n ) t h r e s h o l ds i g n a t u r es c h e m et p e c d s a b a s e do ne l l i p t i c a lc u r v ec r y p t o g r a p h yi sp r o p o s e d ，w h i c hi sb a s e do nt h ea l g o r i t h m pe c d s aa n dt h ei m p r o v e ds e c r e ts h a r i n gs c h e m e t h e ns c h e m et p e c d s a s s e c u r i t yi sa n a l y z e dt ov e r i f yi t ss e c u r i t yp e r f o r m a n c ei sr e l i a b l e i i 武汉理工大学硕士学位论文 ( 4 ) t h r e s h o l ds i g n a t u r es c h e m et p e c d s a i sa p p l i e dt oi n t r u s i o nt o l e r a n tc a m a i n l y , as c h e m eo fc as i g n sc e r t i f i c a t e si sp r e s e n t e d t h i ss c h e m er e d u c e st h e c a l c u l a t i o no v e r h e a db yt r a n s f e r r i n gt h es a m ej o bt h a tts i g n e r sa r en e e d e dt of i n i s ht o c a b yc o m p a r i n gw i mt h ec as c h e m eo fi t t cp r o j e c tf r o mt h ea v a i l a b i l i t y , s a f e t y a n de f f i c i e n c y t h i ss c h e m e ss u p e r i o r i t yi sp r o v e d ( 5 ) m e a n w h i l et h i sp a p e rd e s i g n e dad i g i t a ls i g n a t u r es y s t e mb a s e d o nt h e p _ e c d s aa l g o r i t h m sa n da n a l y z e do fi t ss y s t e ma r c h i t e c t u r e t h e nw er e a l i z et h e d i g i t a ls i g n a t u r es y s t e mb yp r o g r a m m i n g t h er e a l i z a t i o nr e s u l ti n d i c a t e st h a tt h e d i g i t a ls i g n a t u r ea l g o r i t h mp _ e c d s a i se f f e c t i v e k e y w o r d ：e l l i p t i c a lc u r v ec r y p t o g r a p h y ；d i g i t a ls i g n a t u r e t h r e s h o l ds i g n a t u r e i n t r u s i o nt o l e r a n c e i i i 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人 已经发表或撰写过的研究成果，也不包含为获得武汉理工大学或其它教育机构的 学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己 在论文中作了明确的说明并表示了谢意。 签名 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即学校有权保 留、送交论文的复印件，允许论文被查阅和借阅：学校可以公稚论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 一燃新虢埤胁郾 武汉理工大学硕士学位论文 第1 章绪论 1 1 研究的背景和意义 从2 0 世纪9 0 年代以来，随着信息技术和计算机技术的飞速发展与广泛应 用，信息的处理和传递突破了时问和地域的限制，网络化与全球化成为了世界 潮流。大范围的网络应用已经广泛的深入到国防、电信、银行、金融、交通、 电子商务、能源以及大众商业等各个领域。与此同时，信息安全相关事件也逐 年上升，给实施信息系统的各方都带来严重的威胁，信息安全问题正在逐步成 为人们关注的焦点。 数字签名是当前网络安全领域的研究热点。数字签名在实现身份认证、数 据完整性、不可抵赖性等功能方面都有重要应用。其提出的初衷就是在网络环 境中模拟日常生活中的手工签名或印章，数字签名法律的出现使得数字签名与 手工签名一样具有法律效力。但是数字签名可以因消息而异，同一人对不同的 消息的签名结果是不同的，并且随着消息的修改签名结果也会相应的改变，原 消息与签名结果是不可分割的整体。所以，数字签名比传统的手工签名更可靠 更安全。 数字签名的实现基础是加密技术，其使用公钥加密算法和散列函数i l 】。常用 的数字签名算法有：r s a , d s s ，e c d s a , e i g a m a l ，s e h n o r r 等；还有一些用于特 殊用途的数字签名，如盲签名、群签名、失败一终止签名等。 在p k i 系统中，认证中心c a ( c e r t i f i c a t ea u t h o r i t y ) 是一个域中的信任中心。 其他设备或用户之间的通信和验证都依赖于c a 所签发的数字证书。数字证书就 是将一个公开密钥与用户的身份信息绑定在一起，用c a 的私钥签名后所得到的 数据。c a 认证中心是公正的第三方，并且它为建立身份认证过程的权威性奠定 了基础，为交易和作业的参与方提供安全保障，为网上交易构筑一个互相信任 的环境，同时解决了网上身份认证、公钥分发及信息完整性检验、不可抵赖验 证、控制访问等一系列问题。 c a 认证中心主要职责是颁发和管理数字证书【2 】。其中心任务是颁发数字证 书，并履行用户身份认证的职责。因此，c a 的私钥是非常重要的，如果c a 的 武汉理工大学硕士学位论文 私钥被攻击者获得，则c a 颁发的证书都会被窃取，从而用户的信息就会被攻击 者获取，这样引起的后果可想而知。由于不可能预知所有未知形式的攻击，也 不可能完全阻止新安全漏洞的引入，所以仍不可避免被一些攻击取得成功。因 此，将入侵容忍系统运用到c a 认证中心是必要可行的，它可以保证c a 在遭受 攻击时仍能提供服务，为网络上的电子交易和操作提供更高安全性。 门限密码掣3 l 提供了实现具有入侵容忍功能应用的新途径。门限密码学能够 灵活地产生、安全地存储和发放密钥，进而使系统在部分组件被攻破的情况下 仍能保护系统中用于加密、签名等的秘密信息，为开发入侵容忍系统提供了有 效的新技术手段。门限密码学提供了实现具有入侵容忍功能应用的新途径。斯 坦福大学的i t t c 项目【4 】中，着重研究了基于门限r s a 签名方案来实现入侵容 忍的应用；荆继武、冯登国“1 提出了一种基于门限r s a 的入侵容忍的c a 方案。 由于在r s a 基础上设计的门限密码体制具有结构上的简洁性和安全的易证明 性，因此，在已有的研究成果中，几乎所有的门限密码学的研究都集中在基于 r s a 的门限密码技术上。但随着计算机运算速度的迅速提高和i n t e r n e t 分布式计 算能力的日益强大，r s a 、d i f f i e h e l l m a n 等密码体制在密钥长度为5 1 2 b i t 下已 经越来越不安全，而增加密钥长度虽然能增强安全性，但效率会越来越低，同 时对系统的要求也会提高。 椭圆曲线密码体制e c c ( e l l i p t i cc u r v e sc r y p t o s y s t e m s ) ，即基于椭圆曲线离 散对数问题的公钥密码体制，最早于1 9 8 5 年由m i l l e r 和k o b l i t z 分别提出，它 是利用有限域上的椭圆曲线有限群代替基于离散对数问题密码体制中的有限循 环群后所得到的一类密码体制嘲。迄今为止，e c c 被技术界公认为能比r s a 等 其他公钥加密系统提供更好的加密强度、更快的执行速度和更小的密钥长度。 这些性能使得e c c 可用较小的开销和时延实现较高的安全性，特别能满足在带 宽、计算能力或存储能力等受限的各种特殊应用场合。另外，椭圆曲线密码体 制有取之不尽的椭圆曲线可用于构造椭圆曲线有理点群，且不存在计算椭圆曲 线有理点群的离散对数问题的亚指数算法。e c c 的安全性也正是基于椭圆曲线 群上离散对数问题的难解性。因此，e c c 及其应用己正在成为信息安全研究领 域中令人关注的热点。鉴于e c c 的独特优势，e c c 是一种能适应未来信息安全 技术发展的新型密码体制，它必将取代r s a 成为通用的公钥密码体制。因此， 基于e c c 的门限密码体制及其在入侵容忍中的应用的研究具有理论意义和重要 的实用价值。 2 武汉理工大学硕士学位论文 本论文以e c c 为基础，以门限数字签名为主攻对象和以入侵容忍等为应用背 景，开展了基于e c c n 限签名方案及其应用的研究。内容主要涉及数字签名方案、 秘密共享方案及基于e c c 的门限签名方案的研究以及它在入侵容忍c a 系统中的 应用。 1 2 国内外研究现状 由于本论文所研究的是基于e c c 的门限数字签名方案及其在入侵容忍c a 系 统中应用，因此，在本节中，我们将分别从e c c 密码体制、数字签名，入侵容忍 技术三个方面对相关研究工作的现状进行介绍。 1 2 1e c c 算法研究现状 加密算法分为两大部分，第一部分是转轮替换算法，包括数据库加密标准 算法( d e s ) 、t r i p l e d e s ( - - 重d e s ) 、r c 4 和r c 5 等，目前，还没有出版正式的 r c 5 规范；第二部分是公钥密码算法，主要包括r s a 、e c c 、r a b i n ( 平方根算法) 和d h 等。 椭圆曲线密码体制嘲 7 i e c c ，即基于椭圆曲线离散对数问题的公钥密码体制， 它是利用有限域上的椭圆曲线有限群代替基于离散对数问题密码体制中的有限 循环群后所得到的一类密码体制。随着密码学、计算机网络技术和其他相关技 术的不断发展，催生了e c c 。经过数学家长期分析，e c c 已经得到全球认可，成 为了继r s a 和d s s 之后的新一代密码算法。 e c c 的安全性是建立在极为困难的对数运算基础上的，即椭圆曲线的对数问 题e c d l p 。目前，对于所有椭圆曲线有限群上离散对数问题的算法，都是从一 般群g 上离散对数问题的算法平移而来，而一般群g 上离散对数问题算法可分为 两类：i n d e xc a l c u l u s 算法和碰撞搜索法。i n d e xc a l c f l m 算法具有亚指数时间复 杂度，是目前解决一般群g 上离散对数问题的最好算法，但对所有椭圆曲线有限 群上离散对数问题，该算法无论从理论上还是从实际上都不可行。碰撞搜索法 具有纯指数时间复杂度，这一类算法可以用于求解e c d l p ( e l l i p t i cc u r v ed i r e t e l o g a r i t h mp r o b l e m ) 。目前最好的碰撞搜索法有：p o l l a r d p 算法和p o l l l i 哥h e l l m 眦 算法。目前关于求解e c d l p 的方法并不多，为保证椭圆曲线密码的安全性，在 构造密码算法时就应该选取所谓的安全椭圆曲线。 武汉理工大学硕士学位论文 目前，在椭圆曲线公钥密码体制的研究和应用方面处于世界领先地位的是 加拿大的c e r t i c o m 公司。研究的热点是如何加快椭圆曲线上的点的运算，特别是 标量乘运算的速度等。e c c 是一种能适应未来信息安全技术发展的新型密码体 制，它在技术上的优势使其必将取代r s a 成为通用的公钥密码体制，发展前景十 分广阔。 1 2 2 数字签名研究现状 数字签名的概念d a d i f f i e 和h e l l m a n 鄹于1 9 7 6 年最先提出，目的是使签名者对 电子文件可以进行签名并且无法否认，而验证者无法篡改文件。目前，实现数 字签名的方法很多，采用较多的是公钥加密技术，如基于r s a 的d a t as e c u r i t y 公 司的p k c s ( p u b l i ck e yc r y p t o g r a p h ys t a n d a r d s ) 、p g p ( p r e t t yg o o dp r i v a c y ) 、 d s a ( d i g i t a ls i g n a t u r e a l g o r i t h m ) 等。并且目前数字签名的研究内容非常丰富，包 括普通签名和特殊签名。但是，现今使用的一些数字签名算法都是基于以下三 个数学难题 9 1 ： ( 1 ) 整数的因子分解问题：如r s a 算法； ( 2 ) 离散对数问题，如e 1 g a m a l 、d s a 、s c h n o r r 等算法； ( 3 ) 椭圆曲线离散对数问题( e c d l p ) ：如e c d s a 算法。 在公钥密码体制中，影响较大之一的是椭圆曲线密码体$ f j e c c 。但是关于椭 圆曲线的数字签名的研究还处于伊始状态，并且由于椭圆曲线自身的复杂性， 很多问题还没有有效的解决。我国的一些领域已经开始尝试采用新的椭圆曲线 数字签名算法，包括1 9 2 位椭圆曲线算法、2 2 4 位椭圆曲线算法和2 5 6 位椭圆曲线 算法。 1 2 3 入侵容忍技术研究现状 早在上个世纪8 0 年代中期，d o b s o n 和r a n d e u 1 0 】就提出了利用不安全并且不 可靠的部件来构建安全可靠的系统的方法，这实际上是入侵容忍的思想雏形， 1 9 8 5 年就g a j f r a g a 和d p o w e l l 式提出了入侵容忍的概念并一直延用至今。在 1 9 9 1 年，d e s w a r t e ，b l a i n 和f a b r e 开发了一个具有入侵容忍功能的分布式计算系 统。然而在此之后，入侵容忍的思想一直没有得到业内人士太大的关注。直到 近几年才开始对其进行相关的研究。 目前，国内外对入侵容忍技术的研究主要由入侵容忍系统的模型和框架设 4 武汉理工大学硕士学位论文 计、入侵容忍的体系结构和应用设计、入侵容忍的基本支撑理论研究三方面组 成。 国外方面，美国国防高级研究计划署( d a r p a ) 从1 9 9 9 年开始资助实施 o a s i s ( o r g a n i c a l l ya s s u r e da n ds t t r v i v a b l ei n f o r m a t i o ns y s t e m ) 计划【4 】，该计划 由近3 0 个项目组成，研究目标包括：( 1 ) 在组件具有潜在安全漏洞的基础之上 建立i t s ；( 2 ) 构造低成本的i t 机制；( 3 ) 开发评估和验证i t 机制的方法。并 且在该计划的支持下，s t a n f o r d 的i t t c 项目( i n t r u s i o nt o l e r a n c ev i at h r e s h o l d c r y p t o g r a p h y ) 首开基于门限密码的入侵容忍技术研究之先河。2 0 0 0 年1 月，欧 洲启动了m a f l l a ( m a l i c i o u sa n da c c i d e n t a lf a u l tt o l e r a n c ef o ri n t e r n e t a p p l i c a t i o n s ，用于因特网应用的恶意和意外故障容忍) 研究项目，以期系统地 研究入侵容忍模型，建立大规模可靠的分布式应用。m a f t i a 的主要研究成果包 括：( 1 ) 定义了弥补可靠性和安全性差异的入侵容忍结构化框架和概念模型； ( 2 ) 开发了一组建立i t 的机制和协议，包括：一组模块化和可伸缩的用于安全 群通信的中间件协议；一个用于大规模分布式入侵检测的体系结构，该结构本 身具有入侵容忍属性，以及入侵容忍的分布式认证服务；( 3 ) 提出了针对m a f t i a 中间件部分组件的形式化验证和评估方法。 在我国，则从2 0 0 1 年开始在入侵容忍方面出现了一些研究工作。如中科院 信息安全国家重点实验室、西安电子科技大学网络与信息安全重点实验室和武 汉大学软件工程国家重点实验室等几家单位，他们主要针对入侵容忍在分布式 网络中的应用、入侵容忍在保护机密信( 如w e b 服务器的密钥或c a 私钥) 中的 应用等。其中包括荆继武、冯登国等人设计并实现了一个基于门限密码学的入 侵容忍的c a 系统【5 】；张险峰等人基于门限椭圆曲线密码系统，分别提出了一种 入侵容忍的c a 和入侵容忍的w e b 方案“”n i f2 j ；郭渊博等研究了适合于i n t e m e t 等异 步环境的先应式( p r o a c t i v e ) 秘密共享问题i l o l ，以及能够直接用于容忍入侵系统 配置的基。目前，国内对入侵容忍技术的研究的广度还有所欠缺，研究工作总 体而言主要偏重于基于门限密码或秘密共享理论的入侵容忍模型与系统的设 计。 由上可见入侵容忍技术的研究和应用是有现实意义的。 1 3 主要内容和论文组织结构 本文在参阅了国内外大量的文献资料的基础上，进行了如下布局结构： 武汉理工大学硕士学位论文 首先对椭圆曲线密码算法、数字签名以及入侵容忍技术的研究背景及其研 究现状进行了分析和综述。 第二章，介绍了椭圆曲线密码算法的基本概念及理论基础，包括有限域，p 和 有限域e 的椭圆曲线及其参数选取、椭圆曲线上的离散对数问题、基于e c c 的 零知识证明方法。本章重点介绍了基于椭圆曲线的数字签名算法e c d s a ，在此 基础上提出了一种改进的数字签名算法pe c d s a 。 第三章，在现有研究的基础上，改进了一种不需要可信中心的秘密共享方 案，主要是提出了一种密钥更新方案，使其具有前向安全性，并对此方案进行 了实例分析，验证其正确性。同时结合改进的数字签名方案pe c d s a 及此秘密 共享方案，设计了一种安全性增强的基于e c c 的1 ) 门限签名方案t p _ e c d s a ， 并对其安全性进行了分析。 第四章，分析了方案t pe c d s a 在入侵容忍c a 中的应用，通过将t 个签名者 都需要完成的相同工作转移到c a 一次完成，从而减少系统的计算开销，并且对 比i t t c 项目的方案，从可用性、安全性和效率三方面分析了本方案的性能。 第五章，设计了一种基于数字签名算法pe c d s a 的数字签名系统，分析了 其系统构架，并对此系统进行编程实现。 第六章，对整篇论文的工作进行了总结，指出了进一步的研究方向。 6 武汉理工大学硕士学位论文 第2 章椭圆曲线数字签名方案 2 1e c c 原理 椭圆曲线是定义在有限域上的符合一个方程的点的集合。椭圆曲线密码体 制是建立在椭圆曲线上的。建立安全的椭圆曲线密码体制的基础是选择安全的 椭圆曲线。有两类有限域1 3 1 【1 4 1 可用来定义一个椭圆曲线：一是素数有限域耳； 另一个是特征为2 的有限域 2 1 1 有限域u 上的椭圆曲线 有限域耳由整数集合 0 12 ，p _ l 组成，每个这样的整数可以用一个长度 恰为r = 1 0 9i ( 其中胡表示不小于x 的最小整数) 的二进制表示，该表示由整数 的二进制表示及在其左边添加适当个数的0 组成。 砟中元素的加法运算定义如下：如果4 ，6 ，贝l j a + b = ，其中，是口+ 6 被p 除所得的剩余，0 ，p - i 耳中元素的乘法运算定义如下：如果口，b e ，则口b = s ，其中，s 是口b 被p 除所得的剩余，0 s p - i 。 令巧表示耳中所有非零元素，则已证明在昂中至少存在一个元素g 使得 耳中任意非零元素可以表示成g 的方幂，这样的元素g 称为昂的生成元，即 巧= k ：o f p 一2 ) 4 = g e 的乘法逆是1 口= g 一= g ( - o 瞅一。 域昂上的椭圆曲线e ( 乃) 是满足方程y 2 ；矿+ a x + b ( m o d p ) 的所有的点 7 武汉理工大学硕士学位论文 p = y ) ( x ，y z p ) 再加上一个无穷远点d 所构成的集合，其中a , b c 是常数， 并且满足4 口3 + 2 7 b 2 o ( m o d p ) 。 椭圆曲线e 上的两点p = ( ，y ，) 和q = ( x ：，y ：) 可以按照下面的规则相加： 如果而= 而，y 2 = 一y z ，贝l j p + q = 0 ；否则p + q = ( x 3 ，y 3 ) ，其中 而= 一一屯( m o d 力，乃= a ( 而- x s ) - y l ( m o d p ) 并且，如果尸q ，五：丝丛；否则五：3 x 一? + a a 。 x 2 一x l2 y l 满足：，+ 0 = d + p = 尸 椭圆蓝线e ( ) 上所有点的个数记为群联z ，) 。h a s s e 定理表明撑e 瞄，) 满足 下面的不等式： p + l - 2 x 石； 以名) ，+ 1 + 2 扛 其中，数，l 与椭圆曲线点p e ( 疋) 的乘法就是把点p 和它自身相加栉次的 过程，比如3 p = ，+ j p + 尸。利用上述加法规则，数乘运算可以非常有效地完成。 2 1 2 有限域f _ 2 m 上的椭圆曲线 特征为2 的有限域只含有2 ”个元素( m 1 ) ，它们可以表示为： 口1 x 。- l + 口_ 一2 x “一2 + + 口1 x + a o ，其中系数qe o ，1 域元素( 口x ”1 + 口x ”2 + + 吼x + ) 通常用长度为m 的二进制串 ( 。q ) 表示，使得 ，2 ( 口m - i o l a o ) ：口， 0 , 1 ) ) 因此巧中的元素可以用长度为朋的二迸制串的集合来表示。 有限域_ 上形如：y 2 + a l 耖+ a 3 - - x 3 + 口2 x 2 + a 4 x + a o 的非超奇异椭圆曲 s 武汉理工大学硕士学位论文 线( 超奇异椭圆曲线容易受到某些攻击) 在q o 时是可以转化为如下的形式： y 2 + x y = x 3 + a x 2 + 6 ，其中口，6 t g b 0 满足上述等式的所有整数对( 工，j ，) 和无穷远点组成的集合e 矿( 口，6 ) 定义一个 有限a b e l 群。对该上的椭圆曲线群，点的加法运算采用以下规则，对所有 p ，q 互( 口，6 ) ： ( 1 ) e + q = p ，d 是无穷远点，是椭圆曲线的单位元； ( 2 ) 对于所有的( x ，y ) e ，( x ，y 卜d 2 d + ( 五y ) 2 ( x ，y ) ； ( 3 ) 椭圆上的点p = “，y ，) ，则p + ( ，x 。+ y 1 ) = 0 ，点“，而+ y 1 ) 是p 的负 元； ( 4 ) 椭圆曲线e 上的两点p = ( 而，y 。) 和q = ( x 2 ，y 2 ) ，如果而如，则其和为 p + q - - ( x 3 ，_ ，) ，其中： 毛= 名+ 五+ _ + 工2 + 口， 乃= 足( + x 3 ) + 码+ 咒， 五= 翌粤，k y 3 ，五 x 1 + x 2 ( 5 ) 对任意满足x o 的点p = ( x ，y ) 只，有p + 尸= ( 如，乃) 。其中 屯= 磐十五+ a ， 乃= 工2 + ( 五+ 1 ) x s ， 五= 而+ y - - ，a - 1 , x s , y s ，名忍 毛 。 椭圆曲线e ( 0 ) 上所有点的个数记为撑e ( 墨) 。h a s s e 定理表明群e ( ) 满足 下面的不等式： 2 m + 1 2 歹牟e ( 只) 2 一+ l + 2 歹 其中，数聆与椭圆曲线点p e ( t ) 的乘法就是把点p 和它自身相加疗次的 9 武汉理工大学硕士学位论文 过程，域上椭圆曲线的数乘运算利用上述加法运算规则可以非常有效地完 成。 2 1 , 3 椭圆曲线域参数 椭圆曲线的域参数是指用以构造一个椭圆曲线密码系统所需要的参数集， 包括；有限域、椭圆曲线、椭圆曲线上的一个点( 称为基点) 、基点的阶。椭圆曲 线域参数是公开的，由通信双方共享。 1 有限域耳上的椭圆曲线域参数 域b 上的椭圆曲线域参数指定了椭圆曲线e 和e 上的基点p = ( 工，y ，) 。它 是一个六元数组：t = ( p ，口，b ，p ，撑，h ) 其中p 定义昂的素数，元素4 ，6 0 决定了由下面的方程定义的椭圆曲线 e ( ) ： y 2 ；，+ a x + b ( m o d 力 并且满足：4 a 3 + 2 7 b 2 o ( m o d p ) 素数盯是点尸的阶，整数矗表示椭圆曲线群的点数与行的商， = 撑e ( 乃) i n 2 有限域上的椭圆曲线域参数 有限域上的椭圆曲线域参数是一个七元组：t = ( 所，厂( 功，口，b ，p ，厅，功 其中m 决定有限域，( 工) 决定有限域的域多项式，4 ，b 为曲线方程 y 2 + x y = x 3 + 烈2 + 6 的系数，p 表示基点，玎是p 的阶，整数h 表示椭圆曲线 群的点数与”的商，h = # e ( f p ) n 2 1 4 椭圆曲线上的离散对数问题 离散对数问题【”1 是很多密码体制的安全基础，而椭圆曲线密码体制的安全 1 0 武汉理工大学硕士学位论文 性也是基于椭圆曲线离散对数问题e c d l p 。为使用椭圆曲线构造密码体制，需 要找出椭圆曲线上的数学困难问题。 在椭圆曲线构成的a b e l 群e 。( 口，6 ) 上考虑方程q = k p ，其中p ， q e p ( 口，6 ) ，k 3 ，并满足 4 a 3 + 2 7 b 2 o ( m o d p l 。 ( 2 ) p = ( b ，炸) 是e ( g f ( p ) ) 上的一个点，p 的阶为g ； 武汉理工大学硕士学位论文 ( 3 ) q 是一个素数，q 2 1 。且g 4 扛； ( 4 ) h 甜e ( g f ( p ) ) g 称为余因子，j i ，远小于q 。 3 3 不需可信中心的可验证秘密共享方案 鉴于椭圆曲线密码体制在加密强度、执行速度和密钥长度等方面所具有的 独特优势，本方案在基于e c c 的基础上，利用了椭圆曲线离散对数的问题难解 性，对一个没有可信中心的秘密共享方案【2 6 】进行了改进。在此方案中，每一个 秘密共享成员和一个可信中心一样工作，生成自己的密钥并分发其他的秘密共 享给其他的共享者。并且提出了一种密钥更新方案，使得此秘密共享方案具有 前向安全性。 3 3 1 密钥生成协议 ( 1 ) 每个秘密共享成员只随机选择z ( t 乙) ，并广播d 。p 给其他的秘密共 享者。然后每个秘密共享成员p 随机选择a u ( c = 1 , 2 ，f - 1 ) 来构造一个t - 1 次多 项式： z ( x ) = a ，o + 口n x + q 2 x 2 + + 口。( t - i ) x 一1 m o d q ( 1 ) 其中i = 1 ，2 ，胛且满足a j o = 吐。然后计算以= a l e p ( c = 1 , 2 t - 1 ) ，然后用 自己的私钥对以签名并对其他秘密共享者公开，不过要对保密，这就是基于 椭圆曲线离散对数问题的难解性。 ( 2 ) 每个秘密共享成员只计算r = ，( 0 ) p = d , p 作为部分群公钥，然后可计 算出组公钥= k p = r ，其中足是共享的秘密。是椭圆曲线e 上的点 i e 0 ( 3 ) 组中每个成员只与一个可信中心d 一样工作，将z 分配给其他的秘密 共享者，为每个用户只u 0 计算出一个秘密共享值： = f , ( i d j ) m o d q ( 2 ) ( 4 ) 只为其他的每个用户c ( _ ，i ) 选择一个随机数屯乙，将v ，表示为 武汉理工大学硕士学位论文 ( ) 上的点，并计算 岛= k y p 或= 巧+ 屯l ( 3 ) 然后将( b ，岛) 发送给其他的每个秘密共享成员p j ( j f ) 。 3 3 2 共享验证协议 要对每个秘密共享者持有的秘密共享值进行验证，则共享者p ( i = 1 ，2 ，卅) 通过下式来验证子秘密v ，的正确性。 t - i p = 一声( z e ) 。 ( 4 ) 如果上述等式成立， i p v j t 满足上式，则表示秘密共享者只收到的子秘密正 确；否则秘密共享者只收到的子秘密不正确，只拒绝接收此秘密共享值，需要 c ( _ ，f ) 重新发送，直到满足上式为止。 若参与者少于t 个，即使他们遵从共享验证协议并得到正确的秘密共享值， 也不能获得秘密。 3 3 3 秘密恢复协议 f 个秘密共享者职，最，只) 联合恢复出秘密足的方案如下： ( 1 ) 每个秘密共享者只( i = 1 , 2 ，卅) 恢复他们的共享的秘密，首先每个 共享者计算： = d 一z d ，( i , j e , j 力 ( 5 ) 然后从点矿。中取出秘密共享值v 。 ( 2 ) 如果这t 个秘密共享者要恢复出秘密z ，那么他们组成一个秘密恢复 共享组k 。然后首先，这t 个秘密共享者根据( 3 ) 式计算出他们各自的秘密共 享值v 。；然后根据3 3 - 2 节提出的共享验证协议来验证v 。是否正确。通过验证 之后，就形成了，个秘密共享点，分别为( 上d i ，) ，( z d 2 ，屹。) ，( 仞：，v 。) ， 然后采用拉格朗日插值定理【2 刀，可恢复出秘密d ，如下所示： z = 享，亦，击j z = 兀 j ，- i ，o 1 8 武汉理工大学硕士学位论文 最后运用随机数协议，计算出秘密置= 矾，由上可知秘密k 本身不需要 一个可信中心来产生和分配，这样增强了系捌的安全性。 3 3 4 周期秘密共享值的更新 为了实现前向安全【2 8 1 ，在每个时间周期的开始，每个参与者尸都要对分配 给其他秘密共享者p j ( j f ) 的秘密共享值进行更新。假设现在是周期r 的开始， 则p 可利用前一周期选择的随机数d ，把周期r 一1 的秘密k 的分配更新为周 期r 的分配。假设f 个秘密共享者嘏，只，) 参与共享秘密k ，更新方案如下 所示： ( 1 ) 在周期r ，每个秘密共享者只随机选择一个多项式： ，( 功= 口巾t - 1 + 口f l x + q 2 x 2 + + 4 ，f ，一i ) x 一一m o d q ，其中口j o t - 1 = d f 一1 由式( 2 ) 计算出d - 1 的秘密共享值嵋= ，7 ( z d ，) ，( 1 ，2 ，f ) ( 2 ) 对于每一个秘密共享者只，由式( 3 ) 将巧加密后得出( d y ，或) ，并 将( d f ，或) 公开地发送给秘密共享者0 ，( 1 ，2 ，f ) ，然后将口。t 。- 1 p 和 也= p 发送给其他的秘密共享者。 ( 3 ) 对于秘密共享者c ，利用式( 5 ) 解密计算出曙，然后从点曙中取 出秘密共享值v ；。 ，一i v o p = t - 1 尸+ 白( 以) ( 4 ) 两等式： “1 。若成立，则表示更新的秘密共 k p = i 以( 订p ) ，驴i 。7 南 享值通过验证，则只向其他参与者广播“确认”信息，否则广播“错误”信息直到 所有参与者p ，( ，f ) 广播“确认”信息后，则每一个只( _ ，f ) 产生一个新的秘密 共享值哆= b , v r 然后秘密销毁矿1 ，f ( 1 ，2 ，f ) 3 4 实倒分析 本节以一个( 4 ，6 ) 的门限秘密共享方案的实例来说明上面提出的方案的 有效性。设组成员的z d 为 l ，2 , 3 ，4 ，5 ，6 。 1 9 武汉理工大学硕士学位论文 令p = 2 3 ，有限域屹上的椭圆曲线e 为：y 2 = x 3 + x + 4 ，此椭圆曲线的 生成元为p = ( 0 ，2 ) ，p 的阶是2 9 ，则依次可以计算2