（计算机应用技术专业论文）基于椭圆曲线的数字签密研究.pdf

鞍山科技大学硕士论文 摘要 摘要 随着计算机网络技术的发展，信息安全问题日益突出，其核心技术基 础之一的数字签名技术，被广泛地应用于军事、通信和电子商务等领域， 它在身份认证、数据完整性和抗否认等方面具有其它技术无法替代的作 用。 本文首先在阅读大量国内外文献的基础上，全面分析了数字签名的研 究现状与传统算法，主要针对签密进行了系统的研究，然后在以下几方面 取得了创新性的成果： ( 1 ) 本文对传统的数字签名算法进行了研究，特别是基于椭圆曲线的 数字签名算法，提出了一种具有指定接收者的签密方案。该方案具有保密 性、认证性、完整性和不可否认性等优点，特别是减少了签名验证过程中 的求逆步骤，大大加快了运算速度。 ( 2 ) 针对已有的多重数字签名进行了一定的研究，同时提出了一个新 的基于椭圆曲线的多重数字签密模型，该模型实现了签名的有向性，即只 有指定的接收者才可以验证签名的有效性，同时模型中加密技术可以灵活 选取，因而在电子商务和其它领域中都可得到广泛的应用。 ( 3 ) 根据多重签密模型构造了一个安全的网上遗嘱签署协议，该协议 具有保护立遗嘱者个人隐私的特性，防止任何人泄露遗嘱内容，是一个安 全、高效、简单、实用的协议。 最后阐述了作者在本课题研究过程的心得和体会，指出今后进一步探 索和研究的方向。 关键词：椭圆曲线，数字签密，多重数字签名，离散对数 鞍山科技大学硕士论文 ab s t r a c t t h ei n f o r m a t i o ns e c u r i t yh a sb e c o m em o r ea n dm o r ec r u c i a lw i t ht h e d e v e l o p m e n to fc o m p u t e ra n dn e t w o r kt e c h n o l o g i e s t h ed i g i t a ls i g n a t u r ei s o n eo fk e yt e c h n i q u e si ni n f o r m a t i o ns e c u r i t y ，e s p e c i a l l yi nt h ea u t h e n t i c a t i o n ， d a t a i n t e g r i t y a n dn o n r e p u d i a t i o n i th a sb e e n w i d e l y u s e di n m i l i t a r y ， c o m m u n i c a t i o na n de - c o m m e r c e e t c s t a t eo fd i g i t a ls i g n a t u r ea n dc o n v e r t i o n a la l g o r i t h ma r ef i r s t l yd i s c u s s e d i n t h isp a p e rb a s e do nr e a d i n gm a n yl i t e r a t u r e s ，t h e n d i g i t a ls i g n cr y p t i o ni s m o s t l ys t u d i e d t h ef o l l o w i n gi so u rm a i nc r e a t i v er e s e a r c hw o r k s ： ( 1 ) w es t u d yc o n v e r t i o n a la l g o r i t h mo fd i g i t a ls i g n a t u r e ，e s p e c i a l l yb a s e d o nt h ee l l i p t i cc u r v ec r y p t o s y s t e m0 fd i g i t a ls i g n a t u r ew ep r e s e n tan e w s i g n c r y p t i o ns c h e m ew i t ht h es p e c i f i e dr e c e i v e r c o n f i 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 e g r a l i t ya n dn o n r e p u d i a t i o na r ea l la d v a n t a g e so ft h es c h e m e ，e s p e c i a l l y t h es c h e m ed o e s n t o p e r a t e m o d e li n v e r s i o ns ot h a tm a k e s o p e r a t i o n a c e e l e r a t e ( 2 ) w es t u d yt h ee x i s t i n gm u l t i s i g n a t u r ea n dp r o p o s ean e wm u l t i s i g n c r y p t i o nm o d e lb a s e do ne c c t h es i g n e dm e s s a g ec a nb er e v e r t e do n l y b ya p p o i n t e dr e c e i v e rb e c a u s eo fi t so r i e n t a b i l i t yi nt h en e wm o d e l a tt h e s a m et i m ev a r i o u se n c r y p t i o n sc a nb ec h o s e nf l e x i b l yi nt h em o d e ls ot h a ti t h a sb e e nw i d e l yu s e di ne - c o m m e r c ea n do t h e rf i e i d s ( 3 ) w ep r o p o s eas a f et e s t a m e n tp r o t o c o li n i n t e r n e tb a s e do nm u l t i s i g n c r y p t i o nm o d e l t h ep r o t o c o lc a np r o t e c tp r i v a c yo fp r o m i s e ra n dp r e v e n t a n y o n er e x ，e a l i n gm e s s a g e sa n d i t i sa s a f e e f f i c a c i o u s ，s i m p l e 、p r a c t i c a l p r o t o c o i f i n a l l y t h ea u t h o rr e v i e w st h ew h o l ew o r k a n dg i v e ss e i f - e x p e r i e n c ei n r e s e a r c hi n t o d i g i t a ls i g n a t u r et h i sp a p e r m a k e sa no u t l o o kf o r d i g i t a l s i g n a t u r ef u r t h e rr e s e a r c h k e yw 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 c r y p t i o n ，d i g i t a l m u l t i s i g n a t u r e ，d i s c r e t ei o g a r i t h m 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为 获得鞍山科技大学或其它教育机构的学位或证书而使用过的材料，与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示了谢意。 关于论文使用授权的说明 本人完全了解鞍i lj 科技大学有关保留、使用学位论文的规定， 即：学校有权保留送交论文的复印件，允许论文被查阅和借阅：学校 可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手 段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：f 羽葺算导师签名：习i 乏 日期：删；伊 签名：f 劐望匝聋 导师签名：皇三2日期：乏堑兰： 鞍山科技大学硕士论文第一章绪论 1 1 课题背景 第一章绪论 在今天的信息社会里，通信安全保密问题的研究已不仅仅出于军事、 政治和外交上的需要。科学技术的研究和发展及商业等方面，玉一不与信 息息息相关。由于信息是共享的，信息的扩散会产生社会影响，所以保护 信息的安全是信息时代的迫切需要。 在传统交易中，例如书面的政治、军事、外交等的文件、命令和条约， 商业中的契约以及个人之间的书信等，我们使用手书签字或印章以便在法 律上能够认证、核准、生效，保证交易各方的利益。在世界已经缩小为一 个地球村的今天，我们希望通过电子设备实现安全、快速的远距离交易。 计算机通信网的发展为系统间进行数据传送提供了手段，同时带来了电子 商务和电子政务的迅猛发展，网络世晃变得生机勃勃，快速、巨大地改变 我们的工作和个人生活的方方面面。在计算机通信系统中，维护电子文档 的安全成为至关重要和非常敏感的问题，特别在政府机关、商业部门以及 外交和军事领域。数字签名应运而生，并开始用于商业、政治等各种用途 中，如电子邮件、电子转账和办公自动化等。此类交易伙伴间的关系表现 为一种新型的关系，交易双方问没有在交易前首先去了解自己的交易伙伴 并建立起信任，而是越来越多地在这类交易中使用数字签名技术。 数字签名是密码学中的重要问题之一，手写签名的每一项业务都是数 字签名的潜在用场。数字签名类似于手写签名，具有不可伪造性和不可否 认性，一个签名消息是一种以电子化形式存贮的信息，可以在通信网上传 输。在商业通信网上传输，如电子邮件、电子现金、办公自动化等系统， 数字签名得到了广泛应用【2j 。 数字签名的基础是密码学的公钥密码，然而，现在广泛使用的r s a 公 钥密码系统已很难满足未来人们对信息高安全性的需求。椭圆曲线密码系 统( e c c ) 是迄今为止每比特具有最高安全强度的密码系统。所以在椭圆曲 线密码系统的基础上研究数字签名便成为研究的新课题。 鞍山科技大学硕士论文 第一章绪论 1 2 椭圆曲线密码的研究现状 1 9 8 5 年n e a lk o b l i t z i3 1 和vsm i l l e r 4 1 把椭圆曲线的研究成果应用到密 码学中，分别独立提出在公钥密码系统中使用椭圆曲线的思想。他们虽没 有发明出种新的公钥密码算法，但他们采用椭圆曲线技术实现了已存在 的密码算法如d i f i e h e l l m a n 算法等，这就是椭圆曲线密码学的开端。 从椭圆曲线密码技术被提出到l9 9 5 年大约十年间，人们对椭圆曲线密 码技术的研究主要以理论为主。这段时间，人们对椭圆曲线密码系统的安 全性作了进一步的探讨；对椭圆曲线密码算法进行了初步的研究，提出了 许多实现e c c 操作的算法，其中对域和域操作算法的研究成果最为显著。 1 9 9 5 年以后，人们对椭圆曲线密码技术的研究丌始偏重于应用方面。除了 继续改善椭圆曲线密码算法的性能外，一些实验性的e c c 系统也被实现， 并且其性能也得到分析。 e c c 的安全性和优势得到了业界的认可和广泛的应用，i e e e 、a n s i 、 s o 、i e t f 等组织已在椭圆曲线密码算法的标准化方面做了大量工作。1 9 9 8 年被确定为i s o i e c 数字签名标准l o s l 4 8 8 8 3 ；1 9 9 9 年2 月椭圆曲线数字签 名算法e c d s a 被a n s i 确定为数字签名标准a n s i x 96 2 19 9 8 ，椭圆算法 d j f i e h e l l m a n 体制版本e c d h 被确定为a n s ix 9 6 3 ；2 0 0 0 年2 月被确定为 i e e e 标准i e e e l3 6 3 2 0 0 0 ，同期，n i s t 确定其为联邦数字签名标准 f i p s18 6 2 ”i 。 目前国外已有用椭圆曲线进行加解密和数字签名的产品出现在市场 上。这些产品被广泛应用于保密通信、网络安全、电子商务等方面。国内 也有几家公司和研究机构在做e c c 的实现，还未发现有比较成功的产品出 现 6 1 。 1 3 数字签名技术的研究现状 数字签名的研究内容非常丰富，包括普通签名和特殊签名。特殊签名 有盲签名、代理签名、群签名、不可否认签名、公平卣签名、门限签名、 具有消启、恢复功能的签名等，它与具体应用环境密切相关。显然，数字签 名的应用涉及到法律问题，美国联邦政府基于有限域上的离散对数问题制 定了自己的数字签名标准( d s s ) ，部分州已制定了数字签名法。法国是第 鞍山科技大学硕士论文 第一章绪论 一个制定数字签名法的国家，其他国家也正在实施之中。在密钥管理方面， 国际上都有一些大的举动，比如l9 9 3 年美国提出的密钥托管理论和技术、 国际标准化组织制定的x 5 0 9 标准( 已经发展到第3 版本) 以及麻省理工学 院开发的k e r b o r o s 协议( 已经发展到第5 版本) 等，这些工作影响很大1 7 1 。 国内学者对基于椭圆曲线的数字签名进行了一定的研究，一系列的椭 圆曲线的数字签名方案被相继提出，如基于椭圆曲线的数字签名的盲签 名，基于椭圆曲线的代理数字签名，基于椭圆曲线的多重数字签名方案， 基于椭圆曲线的可验证门限签名方案，基于椭圆曲线的可转移不可否认的 数字签名方案，基于椭圆曲线的限制代理签名方案等等。所以研究椭圆曲 线数字签名是现代密码技术的一个热点问题，对其进行全方位的研究是很 有必要的。 目前我国数字签名技术与国外还有一定的差距。美国联邦政府己对基 于椭圆曲线上的离散对数问题制定了自己的新的数字签名标准( f i p s l8 6 2 ) 。可以预见，中国急需自己的数字签名标准。在公钥算法的选定上， 国外已经开始选用安全系数较高的椭圆曲线数字签名算法e c d s a 进行数 字签名，而国内仍然处于选用r s a 或d s a 的状况。因此，我们必须加强对 e c c 的研究，在现有理论和技术基础上充分吸收国外先进经验，开发自己 的算法、自己的标准、自己的体系，形成自主的创新的密码技术，以对付 来自国际社会的挑战i ”。 。 1 4 研究的工作和成果 本人在认真学习大量文献资料的基础上，对椭圆曲线密码、数字签名 和多重数字签名进行了一定的研究，所做的主要工作及成果如下： ( 1 ) 研究椭圆曲线上的数字签名算法是很有意义的，目前已有的椭圆 曲线数字签名在验证签名的过程中需要进行求逆运算，使运算复杂，并且 系统性能未达到最优；同时传统的数字签名实际上分“两步实现”，即发 送者先对消息签名，然后利用加密技术对消息及对消息的签名进行加密， 并将加密所得的信息发送给消息的接收者。然而，无论是签名还是加密， 每一步操作都会耗费一定的机器周期，并为原始消息增加许多冗余比特。 针对e c c 签名系统中存在的上述两个问题，在保证签名算法安全性的前提 下，本文提出了一种新的基于椭圆曲线的签密方案，同时该方案具有有向 性，只有特定的接收者才可以由签名恢复被签消息，验证签名的有效性。 鞍山科技大学硕士论叉第一章结论 ( 2 ) 在多重数字签名这一领域，国内大多仅仅研究基于大整数因子分 解难题或者离散对数难题的多重数字签名算法，本文对基于椭圆曲线的多 重数字签名进行了一定的研究，同时提出了一个新的基于椭圆曲线的多重 数字签密模型，提高了运算速度。采用椭圆曲线密码体制进行多重数字签 名，不仅使多重数字签名建立在椭圆曲线离散对数难题上，具有了更高的 安全性，而且可以充分利用椭圆曲线密码体制的各种优点，缩短了密钥长 度、提高了执行速度、减少占用存储空间、提高签名效率并且占用的带宽 减小。 ( 3 ) 数字签名的应用非常广泛，已广泛应用于商业、金融、军事等领 域本人根据多重签密模型构造了一个安全的网上遗嘱签署协议，该协议具 有保护立遗嘱者个人隐私的特性：防止任何人泄露遗嘱内容，是一个安全、 高效、简单、实用的协议。 1 5 本文的组织结构 本文参考了很多的学术文献，主要研究了基于椭圆曲线的数字签名， 本文共分为六章。 第一章，主要是介绍一下论文的研究背景，并概述了椭圆曲线密码及 数字签名技术的研究现状。 第二章主要介绍本论文中将用到的有关椭圆曲线密码体制方面的基 本理论知识。首先给出椭圆曲线的定义及椭圆曲线上的核心运算，然后介 绍椭圆曲线离散对数的概念，攻击现状，最后讨论选取安全椭圆曲线的条 件及优势。本章中所涉及的论题和所指出的结果是椭圆曲线密码的基础， 也是椭圆曲线数字签名技术的数学根基。 第三章首先介绍数字签名的有关理论及目前流行的各种数字签名方 案，然后介绍了椭圆曲线数字签名算法和签密的理论知识，最后提出了一 种新的基于椭圆曲线数字签密算法。通过第三章我们对各种数字签名方案 有了一个准确的把握。 第四章对几种基于不同数学基础的多重数字签名方案进行了介绍并 提出一种新的基于椭圆曲线的多重数字签密模型。安全性分析表明，该方 案可以有效的抵抗攻击，因而该方案在对安全性要求较高的电子商务、电 子政务和军事指挥中可以具有实际的应用前景。 第五章主要介绍数字签名在电子商务、网上遗嘱签署、电子投票等领 鞍山科技大学硕士论文第一章绪论 域的实际应用，并根据设计的多重签密模型给出了一个安全的网上遗嘱签 署协议具体的实现方案。 第六章是对全文总结，并给出下一阶段的研究方向。 鞍山科技大学硕士论文第二章椭圆曲线密码学基础 第二章椭圆曲线密码学基础 1 9 8 5 年n e a lk o b l i t z 手1 v s m i l l e r 把椭圆曲线的研究成果应用到密码 学中，分别独立提出在公钥密码系统中使用椭圆曲线的思想。这种思想的 基础是定义在有限域上的椭圆曲线的有理点集可以构成a b e l i a n 群，由此可 以定义其上的离散对数，即椭圆曲线离散对数。求解椭圆曲线离散对数是 非常困难的，所以通信双方可以据此构造公钥密码体制一一椭圆曲线密码 体制( e l l i p t i cc u r v ec r y p t o s y s t e m ，缩写为e c c ) 。 2 1 椭圆曲线的概念 椭圆曲线并非椭圆，之所以称为椭圆曲线是因为它的曲线方程与计算 椭圆周长的方程类似。一般用韦尔斯特拉斯f w e i e r s t r a s s ) 方程描述： y 2 + a l x y + a 3 y - x 3 + a 2 x 2 + a 4 x + a 6 ( 2 1 ) 其中a f ，i - 1 ，2 ，3 ，4 ，5 ，6 。f 是一个域。f 可以是有理数域、复数域，还可 以是有限域f 。满足上面方程的点( x ，y ) 就构成椭圆曲线。定义中包括一 个称为无穷点的元素，记为0 。密码学中普遍采用的是有限域上的椭圆曲 线，有限域上的椭圆曲线是指曲线方程定义式( 2 1 ) 中，所有系数都是某一 有限域f 。中的元素，这里可以选择q 一个2 的幂。这样，在q = p 的情况下， p ，p 是一个大的奇素数：或者q = 2 ， 选择的域便是f 。，p 是模数；在q = 2 “ 的情况下，选择的域便是f 2 。其中最为常用的是由式( 22 ) 定义的曲线方 程： y 2 5 x + a x + b ( m o dp ) ( a , b f d 4 a 3 + 2 7 b 2 ( r o o dp ) 0 ) ( 22 ) 令e ( f p ) 表示基于有限域f p 上的椭圆曲线；点p 对应一对坐标( x ，y ) ， 其对称点用一p 表示，一p 的坐标为( x , - y ) 。 定义2 1 在基于有限域f 。的椭圆曲线上的点构成的群的元素个数称为 陔群的阶，常表示为# e ( f 。) 。 定义2 2 设p 是椭圆曲线e ( f 。) 上的一点，如果存在最小的整数，使得 n p = 0 ，那么称p 点的阶为n 。由群的性质知n 是椭圆曲线群的阶# e ( f 。) 的因 子。 下面从几何的角度介绍一下椭圆曲线e ( f 。) 上的“加法”，如图2 1 所 鞍山科技大学硕士论文第二章椭圆曲线密码学基础 示：p ( x 1 ，y 1 ) 和q ( x 2 ，y 2 ) 是椭圆曲线e ( f 。) 上不同的两个点，连接点p 和q 交曲线于另一点，过该点作平行于纵坐标轴的直线与曲线相交于点r ( x 3 ， y 3 ) ，则r 为p 和q 两点之和，记为r = p + q ，p + q 称作点加。在图2 ，2 定 义了曲线上任一点自加，记为2 p 2 p + p ，过点p 作曲线e ( f 。) 的切线与曲线 交于一点，过该点作平行于纵坐标轴的直线与曲线相交于点r ( x 3 ，y 3 ) 。若 切线和纵坐标轴平行即交曲线于无穷远处，则p + p = o 。若k 个相同点相加 即p + p + + p 表示为k p ，称为点乘或数乘。 l 厂_ g 玉蜘 ：二：二： 杖7 p ( x 1 ，y 1 ) 幽2 1 p ( 。1 ，y 1 ) 7 i厂弋 r r ( 。3 y 3j 、 鞍山科技大学硕士论文第二章椭圆曲线密码学基础 有限域上的加法规则如下： ( 1 ) 与零点o 相加，v p e ( f 。) ，有p + 0 2 0 + p 2 p ( 2 ) 与对称点相加，vp e ( f 。) ，有p + ( 一p ) = ( 一p ) + p 2 0 ( 3 ) 两相异点相加，v 两点p 、q ，p 、q e ( f ，) ，且p 土q ，令p = ( 。j ，yj ) q = ( x 2 ，y 2 ) ，p + q = ( x 3 ，y 3 ) ，那么有 x 3 = 五2 一r i x 2 ( m o d p ) y 3 = 五( x l x j ) 一y 1 ( r o o d p ) 丑：! 些 x 2 一r 1 ( 4 ) 两相同点相加( 点的倍数) ，v p - ( x l ，y 1 ) e ( f 。) ，要求p 一p ，那 么p + p = 2 p = ( x 3 ，y 3 ) ，有 x 3 = a 2 2 x 1 ( m o d p ) y 3 = 丑( x l x 3 ) 一y 1 ( r o o d p ) ：堕竺 2 y 1 2 2 椭圆曲线的核心运算 2 2 1 点加运算 我们知道有限域上椭圆曲线的一般方程为y 2 一x 3 + a x + b ( m o dp ) ，则它 的加法公式如下： 设p = ( 、i ，y 1 ) ，q = ( x 2 y 2 ) ，p + q = ( x3 y 3 ) ，他们都是椭圆曲线上的点，有 如下的计算公式： 加法公式五：上 苎 x 2 一l z = 五2 一j 1 一x 2 ( m o d p ) y 3 = 五( x i x 3 ) 一y l ( m o d p ) 五：型竺 鞍山科技太学硕士论文第二章椭圆曲线密码学基础 屯= 五2 2 x 】( m o d p ) y 3 = 2 ( x 1 一x3 ) 一y 、( m o d p ) 下面是点加运算的实现： 函数功能：p 3 = p l + p 2 参数： 点p 1 _ ( x l ，y 1 ) ，p 2 = ( x 2 ，y 2 ) ，椭圆曲线的系数c u r 作为输入 c u r 包含方程y 2 ；x 3 + a x + b ( m o dp ) 的系数a ，b ，p 点p 3 作为输出 p o i n te s u m ( p o i n tp1 ，p o i n tp 2 ，c u r v ec u r ) p o i n tp 3 ； i n tr ； i n tx ，y ； i f ( ( p 2 x 2 2 0 ) & & ( p 2 y 22 0 ) ) r e t u r np l ； i f ( ( p1 x 2 2 0 ) & & ( p1 y 22 0 ) ) r e t u r np 2 ； x 2 p lx - p 2 x ： y = p 1 y p 2y ； r = m u l m o d u l ( x ，y ，c u r p ) ； p 3 x2 m o d u l ( ( r + r p 1x p 2 x ) ，c u rp ) ； p 3y2 m o d u l ( ( r + ( p lx p 3 x ) 一p 1 y ) ，c u r p ) ； r e t u r np 3 ； 倍点算法的实现： 函数功能：p 3 = 2 + p 1 参数： 输入为p l = ( x l ，y 1 ) ，椭圆曲线c u r 的系数 输出为p 3 p o i n te d b l ( p o i n tp1 ，c u r v ec u r ) p o i n tp 3 ； i n tr ： i f f p l y 22 0 ) o ! 型生! 垫苎兰竺曼燮 篁三主笪堕些垒童里兰茎型 p 3 x = o ； p 3y 2 0 ； ej s e r 2 m u l m o d u l ( ( 2 + p 1 y ) ，( 3 + p 1 x + p 1 ，x + c u r a ) ，c u r p ) ； p 3 x 2 m o d u l ( ( r + r - 2 + p 1 x ) ，c u r p ) ； p 3y - m o d u l ( ( r + ( p 1 x p 3 x ) - p1y ) ，c u rp ) ； 】 r e t u r np 3 ； 2 2 2 点乘运算( 标量乘法) 标量乘法是椭圆曲线的核心计算，指如下的式子：o = k p 这里q ，p 是椭圆曲线上的点，k 为整数，并且k 不能大于p 的阶。在密码体 制的实现中，它的运算速度直接影响到整体速度，椭圆曲线上的点加运算与 倍点运算归根结底是为标量乘法服务的。 目前标量乘的快速算法主要有：二进制方法，m 进制法，二进制展开 法，m 进制展开法( 对k 进行变换) ，固定基点窗口法( f i x e d b a s e w i n d o w l n 2 a l g o r i t h m ) ，非邻接法 8 1 ( n o n a d j a c e n tf o r mn a f ) ，固定基点梳形法 ( f i x e d b a s ec o m ba l g o r i t h m ) ，坐标变换法1 9 i 等。 在标量乘法的快速算法中最基本的算法是二进制的d o u b l e - a d d 方法 ”，是把整数k 用二进制表示，然后进行点加、倍点运算。 输入：k = ( kj _ l k j _ 2 kj k o ) 2 输j ：k p q = o f o rif r o m1 1t o0d o q = 2 q i f k i 2 1t h e nqq + p r e t u r nq 鞍山科技大学硕士论文第二章椭圆曲线密码学基础 点乘运算的实现： p o i n tm u l ( p o i n tp ，c u r v ec u r ，i n tk ) p o i n tp 3 ； p 3 x = 0 ： p 3y = o ； i n tc o u n t = f 转化k 的表示方法 i n td i v i d e n d ，r ； c h a rb i n a r y 8 0 】； d i v i d e n d = k ； w h i l e ( d i v i d e n d = 2 ) r = d i v i d e n d 2 ； d i v i d e n d = d i v i d e n d 2 ； b i n a r y + + c o u n t _ ( r = = o ) 7 0 ：1 ； ) b i n a r y + + c o u n t = ( d i v i d e n d = = o ) ? 一0 ：1 ； 完成对k 的表示 f o r ( i = c o u n t ；i = o ；i - - ) p 3 2 e d b l ( p 3 ，c u r ) ； i f ( b i n a r y i = = 1 、 p 3 = e s u m ( p 1 ，p 3 ，c u r ) ； ) r e t u r np 3 ； 2 2 3 求逆运算 一般来说，求椭圆曲线上某元素的逆元，是非常费时间的一种运算。 求某元素的逆元是指：已知a f 。，g c d ( a ，p ) = l ( 即a ，p t i l 为质数) ，满足等式 a x e1m o dp 的x f p 称为有限域中的逆，可以表示为a m o dp 。求模逆的 算法有许多种，一般采用推广的欧几里德算法( e e a - - e x t e n d e de u c l i d e a n 竖生殳垫查兰竺主堕墨 笙三兰! 哩业坠墅里里塑 a i g o r i t h m ) i 。欧几里德算法又称辗转相除法，主要用于因数分解和求公 因子。对于整数a 和p ，若g c d ( a ，p ) = l ，利用欧几里德算法可找出两个常数 1 1 , v 使得u a + v p - 1 ，于是u 是a 模p 的乘法逆。使用传统的扩展欧几里德算法 进行求逆操作，大概相当于8 0 多次大整数乘法操作，所以在实现中最好尽 量避免求逆操作。 在本文中介绍一种不同于e e a 的算法来计算乘法逆元，这种算法的基 本思想是：保持等式a a + d p = u 与c a + e p = v 不变，其中d 和e 的值在运算过程中 不必计算出来，当u = o 时，算法结束，此时v - i ，c a + e p = l ，显然c = a 。m o d p 。 利用此算法求乘法逆元不需要进行大数的乘除运算，效率要高于e e a 算法 【1 2 1 。 函数功能：关于模p 的求逆 参数：输入：素数p ，整数a 0 ，p 一1 】 输出：a 一1m o d p i n ti n v e r s e ( i n ta ，i n tp ) i n tu ，v a ，c ； u = a ；v 2 p ；a 2l ：c 2 0 ： w h i l ef u ! = 0 、 w h i l e ( u 2 。2 0 、 u = u 2 ； i f f a 2 2 2 0 1 a = a 2 ； e l s e a = ( a + p ) 2 ； w h i l e ( v 2 2 2 0 ) v = v 2 ； i f ( c 2 5 2 0 、 c - c 2 ； e l s e 1 鞍山科技大学硕士论文 第二章椭圆曲线密码学基础 c = ( c + p ) 2 i f ( u = v 、 u = u v ： a = a c ： e l s e v = v u ： c = c a ： c p ； 2 3 椭圆曲线离散对数及其攻击现状 2 3 1 椭圆曲线离散对数 从数论的角度说任何公钥密码系统的安全性都是基于求解某个数学难 题的或者说是建立在一个n p 问题( 无法处理的问题) 之上，即对于特定的问 题我们没有办法找到一个多项式时间的算法求解该问题，一般求解此类问 题的算法都是指数时间或者亚指数时间，现有的计算机体系结构不适于求 解此类问题。有了这个理论依据，我们就可以放心地公开或者发送公钥给 任何人，而不用担心攻击者利用公钥反推出我们的私钥。 离散对数问题是很多密码体制的安全基础，而椭圆曲线密码体制的安 全性是基于椭圆曲线离散对数问题( e c d l p ：e l l i p t i cc u r v ed i s c r e t e l o g a r i t h mp r o b l e m ) 的。 有限域上离散对数问题：给定一点n e ( f 。) ，求解整数x ，使x g = n 。这 里的x g 表示数乘，容易看出，对它的攻击依赖于在有限域f 。上求解方程： g xe nm o dp 或计算x = l 0 9 6 nm o dp 。 鞍山科技大学硕士论文第二章椭圆曲线密码学基础 有限域上离散对数问题的求解非常困难，椭圆曲线离散对数问题比有 限域上的离散对数问题更难求解。 椭圆曲线上的离散对数问题为：设e ( f 。) 是定义在有限域f 。上的椭圆曲 线，给定曲线上任一点p ，e ( f p ) 的阶为n ，p 的阶为n p ，椭圆曲线离散对数 问题是指给定曲线上阶为n 的点p ，已知点q e ( f 。) ，求f 整数m ，使得 q = m p ( 0 4 4 p ； ( 2 ) e ( f 。) 是非超奇异的； ( 3 ) e ( f 。) 不是正规的； 目前椭圆曲线的选取一般有两种方法：构造法和随机选取法。构造法 即先确定有限域f 。和其上的椭圆曲线e ( f 。) 的阶，然后再构造满足要求的 椭圆曲线。而要使椭圆曲线密码体制具有最好的安全性，目前被理论界普 遍认同的一种观点是应使用随机曲线，即应当随机的选取定义于f p 上的椭 圆曲线e ( f p ) ，然后计算它的阶# e ( f p ) ，如果满足上述要求，则可以选择 e ( f 。) 构造安全的e c c 体制，否则舍弃该曲线，并重新选取予以验证。二 可见计算 e ( f 。) 是一个很基本的问题，一般称为e c p c ( e l l i p t i cc u r v e p o i n tc o u n t i n 9 1 问题。l9 8 5 年，s c h o o f l ”】提出了一种计算复杂度是多项式 时间的算法，因为整个算法实现过程中所需存储量很大，所以仍不太可行， 之后，a t k i n l t e l l 7 1 和e l k i e s h ”1 对s c h o o f 算法进行一些改进，已经能比较容 易的计算出有理点的个数，即s e a 算法。 。 定理2 1 ( h a s s e 定理) ：如果e 是定义在域g f ( p ) d 2 的椭圆曲线，n 是e 上的点( x ，y ) g f ( p ) 的个数，则： n 一( p + 1 ) 1 s 2 扛 定理2 2 ( 中国剩余定理) ：令r 个整数m l ，m 2 ，m ，两两互素，a l ，a 2 ，a ， 是任意r 个整数，则同余方程组x 5 a r o o dm i ，1 5 i 5 r ，模m = m l m 2 m ，有惟 一解x = d ，肘，y ，其中m i = m m i ，y i 2 m i r o o dm i ，1 5 i 5 r 仁1 由h a s s e 定理知，# e ( f p ) = p + 1 c ，其中h s 2 扛，并且满足( p 2 一c q ) + p = 0 ， 这里( p 是f r o b e n i u s 变换，即( p ( x ，y ) = ( x 9 ，y 9 ) ，所以如果能够确定出c ，也就确 定出了# e ( f 。) 。s e a 算法的基本思想：先对一些小素数l i 计算c i = cm o dl i ，滓1 ， 2 ，t ，且f l c ， 4 i ，然后利用中国剩余定理1 19 1 求出c ，最后得# e ( f p ) i = i 2 p + l c 。 下面给出利用s e a 算法选取大素数域上的安全椭圆曲线的步骤： 鞍山科技大学硕士论文 第二章椭圆曲线密码学基础 输入：有限域的大小p ； 输出：椭圆曲线e ( f p ) ，# e ( f p ) = n h n 是大的素因子，n 2 ”o 且n 4 p ( 1 ) 随机产生f p 上的一条椭圆曲线e ( f 。) ：y z = x 3 + a x + b ( 2 ) 利用s e a 算法计算出# e ( f 。) ： ( 3 ) 利用大整数分解算法分解# e ( f p ) ，并检测# e ( f 。) 的分解中有无大于 2 ”o 的素因子n ，如果没有，返回到f 1 ) ： ( 4 ) 检测n p ，否则返回到( 1 ) ；( 检查椭圆曲线是否为非正规曲线) ( 5 ) 检测p “l m o d n ，k = 1 ，2 ，l 。否则返回到( 1 ) ，l = 10 9 2 p 8 ：( 检查椭圆 曲线是否为超奇异曲线) ( 6 ) 输出a ，b # e ( f p ) ，n ，h - # e ( f 。) n 。 2 5 椭圆曲线的优势 椭圆曲线密码体制的研究历史较短，但是由于其优点突出，已经得到 了密码学界的重视并广泛应用。它是目前已知的所有公钥密码体制中能够 提供最高比特强度( s t r e n g t h p e r b i t ) 的一种公钥密码体制。 f 1 1 安全性能更高 加密算法的安全性能一般通过算法的抗攻击强度来反映。e c c 和其他 另外几种公钥系统相比，其抗攻击性具有绝对优势。椭圆曲线的离散对数 问题计算困难性在计算复杂度上目前是完全指数级的，而r s a 是亚指数级 的。这体现为e c c 比r s a 的每b i t 安全性能更高。 ( 2 ) 计算量小和处理速度快 在相同的计算资源条件下，虽然在r s a 中可以通过选取较小的公钥( 可 以小到3 ) 的方法提高公钥处理速度，即提高加密和签名验证的速度，使其 在加密和签名验证速度上与e c c 有可比性，但在私钥的处理速度上( 解密 和签名) ，e c c 远比r s a 、d s a 快得多。因此e c c 总的速度比r s a 、d s a 要快得多。同时e c c 系统的密钥生成速度比r s a 快百倍以上。因此在相 同条件下，e c c 则有更高的加密性能。 f 3 ) 存储空间占用小 e c c 的密钥尺寸和系统参数与r s a 、d s a 相比要小得多。意味着它多 占的存储空间要小得多。这对于加密算法在资源受限环境上f 如智能卡等1 的应用具有特别重要的意义，如表21 所示。 鞍山科技大学硕士论文第二章椭圆曲线密码学基础 表21 等价强度的密钥尺寸大小比较 e c c 密钥长度位r s a 密钥长度位破解时问m i p s 年r s a e c c 密钥尺寸比率 1 0 6 5 12l0 4 5 ： 1 1 6 0 10 2 4 1 0 l l7 ：l 2 l o2 0 4 81 0 1 0 10 ：1 6 0 02 1 0 0 01 0 7 8 3 5 ：l ( 4 ) 带宽要求低 当对长消息进行加解密时，e c c 、r s a 、d s a 三类密码系统有相同的 带宽要求，但应用于较短消息时e c c 带宽要求却低得多。而公钥加密系统 多用于短消息，例如用于数字签名和用于对对称密码系统的会话密钥加密 传递。带宽要求低使e c c 在无线网络领域具有更加广泛的应用前景。 下面再用图的形式与r s a 和d s a 算法比较其安全性，见图2 3 量 v 扣 z 鞲 啦 2 6 本章小结 破译时间( m 1 p sy e a f s ) 幽2 3r s a 、d s a 、e c c 的抗攻击性比较幽 本章系统的介绍了椭圆曲线的基础知识，其中包括椭圆曲线的概念、 运算、离散对数问题、攻击现状、安全选取等问题，并给出椭圆曲线核心 运算的代码模块。由于本文是在椭圆曲线的基础上实现的数字签名算法研 究，因而在本文后面将提出两种椭圆曲线基础上的数字签名算法。 鞍山科技大学硕士论文第三章基于椭圆曲线的数字签名研究 第三章基于椭圆曲线的数字签名研究 基于椭圆曲线的数字签名方案的安全性是以椭圆曲线密码体制的安全 性为保证的，而椭圆曲线密码体制的安全性是基于椭圆曲线离散对数问题 的难解性之上的。由于目前还没有对椭圆曲线离散对数问题的有效解法， 所以基于其上的数字签名方案是安全的。合法用户采用椭圆曲线数字签名 方案方法处理信息之后，非法用户不能伪造合法用户的签名，因为在不知 道合法用户秘密钥的情况下是不能对椭圆曲线离散对数问题求解的。同样 基于椭圆曲线离散对数问题的难解性，非法用户也就不可能得知双方交换 信息的内容，也就无法对截获的信息进行流量分析、重传以及修改或伪造 等。 3 i 数字签名概述 手写签名是一种传统的确认方式，如写信、签订协议、支付确认、批 复文件等。在数字系统中同样有签名应用的需要，如假定a 发送一个认证 的信息给b ，如果没有签名确认的措施，b 可能伪造一个不同的消息，但 声称是从a 收到的：或者为了某种目的，a 也可能否认发送过该消息。很 明显，数字系统的特点决定了不可能再沿用原先的手写签名方法来实现防 伪造或抵赖，这就提出了如何实现数字签名的问题。 数字签名是电子信息技术发展的产物，是钊+ 对电子文档的一种签名确 认方法，所要达到的目的是：对数字对象的合法性、真实性进行标记，并 提供签名者的承诺。随着信息技术的广泛使用，特别是电子商务、电子政 务等的快速发展，数字签名的应用需求越来越大。 3 i i 与手写签名的比较 数字签名与传统的手写签名有很大的差别。 ( 1 ) 手写签名是所签文件的物理部分，而数字签名中签名和消息是分 开的这就需要一种方法将签名与消息绑定在一起。 f 2 ) 一个手写签名是通过和一个真实的手写签名相比较来验证的，相 对而言不安全而且比较容易被伪造。而数字签名是通过一个公开的验汪算 鞍山科技大学硕士论文 第三章