（通信与信息系统专业论文）基于椭圆曲线的数字签名算法研究.pdf

西南交通大学硕士研究生论文第1 页 摘要 椭圆曲线密码系统的安全性是建立在有限域上椭圆曲线离散对数问题的难解性 上的。与其他公钥密码系统相比，椭圆曲线密码系统不但具有高安全性，而且具有计 算载荷小，密钥长度短，占用带宽少等优点。 深入研究椭圆曲线数字签名及其在特殊签名中的应用，具有深远的意义。本课 题的任务是完成对椭圆曲线数字签名算法的实现，以及设计出基于椭圆曲线的特殊签 名方案。 ( 1 ) 对传统的数字签名算法进行了研究，探讨了椭圆曲线密码的基本概念、椭 圆曲线上点的加、乘法运算等问题，同时对椭圆曲线密码系统的安全性和有效性进行 了分析。 ( 2 ) 采用v c + + 6 0 作为开发工具对椭圆曲线签名算法进行了软件实现，可以实 现对消息的正确签名与验证，并提出了新方案。 ( 3 ) 设计一个改进的基于e 1 g a m a l 的前向安全数字签名方案，与已提出的方案 相比，有效地提高了签名的速度。 ( 4 ) 设计一个改进的基于椭圆曲线的前向安全数字签名方案，使得改进方案真 正具有前向安全性和较强的抗伪造性，有效地提高了签名的速度。 ( 5 ) 结合椭圆曲线密码体制的特性设计了一个基于椭圆曲线的前向安全的指定 验证人代理签名方案。 关键词：椭圆曲线；数字签名；前向安全；代理签名 a bs t r a c t n es e c u 打t vo ft h ee l l i p t i cc u r v ec r y p t o g r a p h yi sb u i l tu p o n t h ed i f f i c u l t yo fs o l v i n g t h ee l l i p t i cc u r v ed i s c r e t ep r o b l e mw h i c hi n f i n i t ef i e l d i na d d i t i o n t oi t s1 l i 班 s e c u r i t y , e c ca l s oh a sm a n yo t h e rm e t i t so v e ro t h e rp u b l i c - k e yc r y p t o s y s t e m ss u c h a sl e s s c o m p u t a t i o no v e r h e a d s ，s h o r t e rk e y s i z e ，c o n s i d e r a b l eh a n d w i d t hs a v i n g s ，a n ds oo n i th a si m p o r t a n ts i g n i f i c a n ti 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 os p e c l a l s i 印a t u r e s t h i st a s ki st oc o m p l e t et h ep e r f o r m a n c eo f e c d s aa n dd e s i g no ft h es l 萨狐玳 b a s e do nt h ee c d s a ( 1 ) t h et r a d i t i o n a ld i g i t a ls i g n a t u r ea l g o r i t h mi s d i s c u s s e d t h e nt h eb a s i cc o n c e p to f e c c ，t h ep r o b l e mo ft h ea d d i t i o n ，m u l t i p l i c a t i o na n d s oo ni se x t r a c t e d l a s t l y , t h es e c u r i t y a n de f f e c t i v e n e s so ft h ee n i p t i cc u r v ec r y p t o g r a p h yi sa n a l y z e d f 2 ) s u a lc + + 6 0i st h em a j o rd e v e l o p m e n t t o o lt oi m p l e m e n tt h ea l g o r i t h mo fd i g i t a l s i 阱a t u r eo nt h ee l l i p t i cc u r v e ，i m p l e m e n tt h e s i g n a t u r ea n dv e r i f i c a t i o no fm e s s a g e c o r r e c t l y ( 3 1t h e 姗a r ds e c u r ed e s i g n a t e ds i g n a t u r eb a s e d o ne i g a m a li sd e s i g n e d , c o m p a n n g w i t ht h es c h e m ep r o p o s e d ，i m p r o v et h es i g n i n gs p e e d e f f e c t i v e l y ( 4 ) t h ef o r w a r ds e c u r ed e s i g n a t e ds i g n a t u r eb a s e do ne l l i p t i c c u r v ei sd e s i g n e d t h e 曲p r o v e ds c h e m en o to n l yh a v et h ef e a t u r e s o ff o r w a r d 。s e c u r ea n dr e s i s t m gt o r 伊n g a t t a c k ，b u ta l s oi m p r o v et h es i g n i n gs p e e de f f e c t i v e l y ( 5 1c o n s i d e r i n gt h ec h a r a c t e r i s t i c s o ft h ee l l i p t i cc u r v ec r y p t o s y s t e m ，t h et o n a r d s e c u r ed e s i g n a t e dv e r i f i e rp r o x ys i g n a t u r eb a s e do ne l l i p t i cc u r v e i sd e s i g n e d k e yw o r d s ：e c c ；d i g i t a ls i g n a t u r e ；f o r w a r ds e c u r e ；p r o x y s i g n a t u r e 西南交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并 向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授 权西南交通大学可以将本论文的全部或部分内容编入有关数据库进行检索，可以采用 影印、缩印或扫描等复印手段保存和汇编本学位论文。 本学位论文属于 1 保密口，在年解密后适用本授权书； 2 不保密巳雁用本授权书。 ( 请在以上方框内打“扩) 学位论文作者签名： 琴久缸 日期： 2 o o z 1 指导老师签名： 伥颓 日期：加，o 7 5 - 西南交通大学硕士学位论文主要工作( 贡献) 声明 本人在学位论文中所做的主要工作或贡献如下： ( 1 ) 以v c + + 6 0 作为开发工具，对椭圆曲线数字签名进行实现，完成了密钥对 的生成、文件的签名和验证，检验签名的正确性和完整性。同时还给出了椭圆曲线部 分运算的代码模块，用软件进行了仿真，并提出了新方案。 ( 2 ) 提出改进的基于e i g a m a l 的前向安全数字签名方案，并对其安全性进行了 分析。新方案大大减少了计算量，有效地提高了签名的速度。 ( 3 ) 提出改进的基于椭圆曲线的前向安全数字签名方案，并对其安全性进行了 分析。新方案具有抗伪造性，私钥的进化具有前向安全性。 ( 4 ) 最后结合椭圆曲线密码体制的特性设计了一个基于椭圆曲线的前向安全的 指定验证人代理签名方案，并对其安全性进行了分析。 本人郑重声明：所呈交的学位论文，是在导师指导下独立进行研究工作所得的成 果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰 写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中作了明确说明。 本人完全了解违反上述声明所引起的一切法律责任将由本人承担。 学位论文作者签名： 巧茛衣d 4 日期：0 i o 6 、工1 西南交通大学硕士研究生学位论文第1 页 1 1 课题的背景和意义 第1 章绪论 在当今的信息化社会中，随着信息化的逐步加深，计算机技术和互联网技术已经 在社会的各个领域中得到了广泛的应用，已经逐步渗透到社会的各行各业中。那么， 对信息是否可以被安全、高效、完整的传输要求越来越高，也越来越迫切。但是以此 为基础建立起来的各种信息系统，虽然给人们的生活、工作带来了很多便利和无限商 机，但同时也充斥着隐患与危险。由于网络很容易受到攻击，导致信息的泄漏，引起 重大损失。信息技术也已经成为综合国力的一个重要组成部分，因此信息安全已成为 保证国民经济信息化建设健康有序发展的保障。信息安全技术在信息化迅速发展的今 天己进入了高速发展的新时期，形成了密码技术、可信计算技术、电磁辐射泄露防护 技术、系统入侵检测技术和计算机病毒检测消除技术等多个安全防护技术门类。其中 大型的信息系统将计算机和智能化设备连接在一个通信网络中，使得整个网络共享大 量的计算机资源和数据文件，可以完成异地之间的数据通信和交换。网络安全技术很 多，目前在电子商务、电子政务、电子银行、电子邮件、电子银行等方面必备的关键 技术就是数字签名。 数字签名能够实现身份认证、数据完整性、不可抵赖性等功能，是信息完整性和 认证性的关键技术之一，也是电子商务及网络安全的关键技术之一，尤其是在密钥分 配、电子银行、电子证券和电子政务等许多领域中有重要应用价值。数字签名是当前 网络安全领域的研究热点，在社会生活的各个领域也有极其广阔的应用前景。数字签 名在实现身份认证、数据完整性、不可抵赖性等功能方面都有重要应用。 在平常生活中，使用手写签字和印章随处可见，如签署合同、办理证明等。如 果在网络上实现签字和印章的电子化，其好处与优点是无疑的。数字签名提出的初衷 就是在网络环境中模拟出日常生活中的手工签名或印章；而要使数字签名具有与传统 手工签名一样的法律效力，又催生了数字签名法律的出现。数字签名具有许多传统签 名所不具备的优点，如签名因消息而异，同一个人对不同的消息其签名结果是不同的， 原有文件的修改必然会反映为签名结果的改变，原文件与签名结果两者是一个混合不 可分割的整体等。数字签名的目的之一，就是在网络环境中代替传统的手工签字和印 章，其可以抵御的网络攻击有：防冒充( 伪造) 、防篡改( 防止破坏信息的完整性) 、防 重放、防抵赖和机密性( 保密性) 。所以，数字签名比传统签名更具可靠性。 “数字签名 用来保证信息传输过程中信息的完整和提供信息发送者的身份认证 和不可抵赖性，数字签名技术的实现基础是公开密钥加密技术，是用某人的私钥加密 的消息摘要用来确认消息的来源和内容。数字签名技术是不对称加密算法的典型应 西南交通大学硕士研究生学位论文第2 页 用。数字签名的应用过程是：数据源发送方使用自己的私钥对数据校验和或其它与数 据内容有关的变量进行加密处理，完成对数据的合法“签名”，数据接收方则利用对 方的公钥来解读收到的“数字签名”并将解读结果用于对数据完整性的检验，以确认 签名的合法性。目前普遍采用的数字签名算法，基本是基于下面三个数学难题的基础 之上【1 】： ( 1 ) 整数的因式分解( i n t e g e rf a c t o r i z t i o n ) i 口- j 题，如r s a 算法； ( 2 ) 离散对数( d i s e r e t el o g a r i t h i m ) l h - 题，如e 1 g a m a l ，d s a 等算法； ( 3 ) 椭圆曲线( e l l i p t i ec u v r e ) f 口- j 题，如e c d s a 算法。 1 2 国内外数字签名技术研究现状 数字签名机制作为保障网络信息安全的手段之一，可以解决冒充、篡改、重放和 抵赖等问题。数字签名必须具有以下的性质1 2 j ： ( 1 ) 防冒充：其他人不能伪造对消息的签名，因为私有密钥只有签名者自己知 道，所以其他人不能伪造出正确的签名数据结果。显然要求私钥的持有人保存好自己 的私钥，就像保存自己家门的钥匙一样。 ( 2 ) 防篡改：对于数字签名，签名和原有文件己经形成一个混合的整体数据， 不能篡改，从而保证了数据的完整性。 ( 3 ) 防重放：在数字签名中，如果采用了对签名报文添加流水号、时戳等技术， 可以防止重放攻击。 ( 4 ) 防抵赖：数字签名可以鉴别身份，不可能冒充伪造，那么，只要保存好签 名的报文，就好似保存好了手工签署的合同文本，也就是保留了证据，签名者就无法 抵赖。以上是签名者无法抵赖，那么如果接收者确实己收到对方的签名报文，却抵赖 没有收到呢? 要防止接收者的抵赖，在数字签名体制中，要求接收者返回一个自己签 名的表示收到的报文，给对方或者是第三方，或者引入第三方机制。如此这样，双方 均不可抵赖，这些涉及到不可否认签名理论。 ( 5 ) 机密性：有了机密性的保证，截收攻击也就失效了。手工签名的文件( 如合 同文本) 是不具备保密性，文件一旦丢失，文件信息就极有可能泄漏。数字签名，可 以加密要签名的消息，这些涉及到加密或签密理论。 数字签名可以用于认证技术，数字签名可以进行下面的认证： ( 1 ) 实体认证：在报文通信之前，采用可鉴别协议来认证通信是否在协定的通 信实体之间进行。 ( 2 ) 报文认证：经实体认证后，双方通信实体便可进行报文通信。为了保证数 据的真实性，应对报文进行认证，即接收实体应能验证报文的来源、时间性与目的的 真实性。通常也采用数字签名技术来实现。 西南交通大学硕士研究生学位论文第3 页 ( 3 ) 身份认证：用户的身份认证是许多应用系统的第一道防线，目的是防止数 据被非法用户访问。除了口令控制外，在身份认证环节采用数字签名技术无疑大大的 提高了访问控制的力度。 1 9 7 6 年由d e f f i e 和h e l l m a n 在文献 3 中首次提出了“公开密钥密码体制”，导致 了密码学上的一场革命。公钥密码体制的最大特点是采用两个不相同但相互对应的密 钥进行加密和解密，其中一个密钥是公开的，称为公钥( 公开密钥) ；另一个密钥是保 密的，称为密钥( 秘密密钥) 。这种体制有两种工作模式：( 1 ) 发送实体用公钥作为密 码运算的输入得到秘密信息；接收实体用私钥恢复发送实体所产生的秘密信息，私钥 能够且只能够恢复相应公钥产生的秘密信息。( 2 ) 发送实体用私钥作为密码运算的输 入得到秘密信息：接收实体用公钥恢复出发送实体所产生的秘密信息，公钥能够且只 能够恢复出相应私钥产生的秘密信息。就加密而言，前者以公钥作为加密密钥，以用 户私钥作为解密密钥，则可实现多个用户加密的消息只能由一个用户解密；反之，后 者以用户的私钥作为加密的密钥而以公钥作为解密密钥，则可实现由一个用户加密的 消息可以由多个用户解密。显然，( 2 ) 中的公钥体制适合于数字签名的构造。因为， 同一个实体产生的多个签名应该能被不同的接收实体验证，这也正是数字签名的基本 要求。 数字签名技术引起了学术界尤其是密码学界和计算机网络界的广泛重视，特别是 随着i n t e r n e t 的飞速发展和电子商务的提出，数字签名技术获得了更加广泛的研究和 应用。各国都己经制定详细研究计划开始着手对数字签名进行研究，都希望建立自己 的数字签名标准。我国近几年也随着信息技术的高速发展在数字签名方面做出了很多 的研究工作，有越来越多的人进行着有关数字签名理论和应用方面的研究工作。我国 也开始了对本国数字签名标准的征集工作。在国外一些国家不仅提出很多实际可行的 数字签名方案，而且相应的还建立了数字签名法案，使数字签名得到司法机关的认可， 具有法律效应。 最早的数字签名有r s a 数字签名方案【4 】【5 1 、d s a 数字签名方案【6 】，e c d s a 数字 签名方案【7 j ，此三种签名方案于2 0 0 0 年2 月1 5 日被美国国家标准技术研究所f n i s t ) 在新标准法案f i p s l 8 6 2 中指定为美国的数字签名标准，同时他们也是目前世界上普 遍使用的一般数字签名方案，都已经形成商业的签名软件供商家和个人使用。其中 r s a 数字签名方案是由r s a 公司提出的基于r s a 公钥密码体制的签名方案，其数学 基础是大数因子分解的困难性。d s a 数字签名方案是基于e 1 g a m a l 提出的e 1 g a m a l 公钥密码体制其数学基础是在有限域上求解离散对数的困难性。e c d s a 数字签名方 案是基于椭圆曲线密码体制的签名方案，它是将d s a 签名方案移植到椭圆曲线密码 体制中来得到的，它的数学基础是求解椭圆曲线上离散对数的困难性。目前由于椭圆 曲线密码体制较其他公钥密码体制有密钥短、速度快、安全性高的优点使得椭圆曲线 密码体制和e c d s a 数字签名方案越来越受到更高的重视。 西南交通大学硕士研究生学位论文第4 页 随着计算机技术和互联网技术的广泛应用，数字签名存在各种各样的应用背景， 在不同的环境下对数字签名提出了更多的要求。面对这样的需求，具有特殊用途的数 字签名方案被提出，形成了数字签名研究的多个值得关注的方向。如：前向安全数字 签名【8 1 、盲签名【9 1 、不可否认签名1 0 1 ( 证实签名【1 l 】) 、门限签名群签名代理签名【1 4 】、 短签名【1 5 】、环签名【埔j 等等。 目前，密码理论与技术主要包括两部分，即基于数学的密码理论与技术( 其中包 括公钥密码、分组密码、流密码、认证码、数字签名、h a s h 函数、身份识别、密钥 管理、p k i 技术等) 和非数学的密码理论与技术( 包括信息隐形、量子密码、基于生物 特征的识别理论与技术) 。 实现数字签名有很多方法，目前数字签名采用较多的是公钥加密技术，如基于 r s ad a t as e c u r i t y 公司的p k c s ( p u b l i ck e yc r p t o g r a p h ys t a n d a r d s ) 、d s a ( d i g i t a l s i g n a t u r ea l g o r i t u n l ) 、x 5 0 9 、p g p ( p r e t t yg o o dp r i v a c y ) 。1 9 9 4 年美国标准与技术协会 公布了数字签名标准( d s s ) 而使公钥加密技术广泛应用。同时应用散列法( h a s h ) 也是实 现数字签名的一种方法。在个别领域，我国开始尝试采用新的椭圆曲线数字签名算法 ( 包括1 9 2 位椭圆曲线算法、2 2 4 位椭圆曲线算法和2 5 6 位椭圆曲线算法) 。 而在众多算法中，椭圆曲线密码体制由于在同等安全的条件下具有密钥长度短、 数字签名快、计算数据量小、运算速度快、灵活性好等特点，己经广泛地被应用。由 于e c c 能实现较高的安全性，只需要较小的开销和延迟，较小的开销体现在如计算 量、存储量、带宽、软硬件实现的规模等；延迟体现在加密或签名认证的速度方面。 所以e c c 特别使用于计算能力和集成电路空间受限( 如i c 智能卡) 、带宽受限( 如高速 计算机网络通信) 等情况。 目前国内对于椭圆曲线公钥的快速实现、智能卡应用等研究较多。由基于它本身 的优点也特别适用于无线m o d e m 、w e b 服务器、集成电路卡等方面。但是综合浏览 后，发现关于在要进行大量安全交易的电子商务领域中研究比较有限。随着网上交易 的频繁，必将成为今后研究的热点。 1 3 本文的章节安排 本文主要研究了基于椭圆曲线的前向数字签名算法，具体章节安排如下： 第一章简要介绍了本课题研究的背景和意义、研究现状以及本文的章节安排。 第二章对椭圆曲线密码算法进行研究，包括椭圆曲线的数学理论、椭圆曲线的数 学运算等，对椭圆曲线理论进行全面、详尽的论述，同时分析了有限域上安全椭圆曲 线的生成。最后通过密钥长度、安全性等方面特性对几种典型公钥算法进行比较，论 述了椭圆曲线密码体制的优越性和实用性。 第三章首先介绍了数字签名体制，包括基本理论、分类，接着介绍几种典型数字 西南交通大学硕士研究生学位论文第5 页 签名，最后重点引出了前向数字签名和代理数字签名的概念，为第五章新方案的提出 打下理论基础。 第四章分析了椭圆曲线密码系统在数字签名上的应用，详细介绍了对椭圆曲线数 字签名的研究，并对其安全性作了分析，最后用软件实现了e c d s a 签名算法。 第五章采用将当前私钥或与当前密钥有关的信息引入对消息的签名过程的方法， 根据有限域上的困难性问题对两种前向安全数字签名方案给出了改进方案，分别是基 于e 1 g a m a l 的前向安全数字签名方案和基于椭圆曲线的前向安全数字签名方案。最后 结合椭圆曲线密码体制的特性设计了一个基于椭圆曲线的前向安全的指定验证人代 理签名方案，并对其安全性进行了分析。 第六章总结全文，展望未来的研究工作。 西南交通大学硕士研究生学位论文第6 页 第2 章椭圆曲线密码体制 2 1 椭圆曲线密码体制的概述 相对于r s a 等密码体制来说，椭圆曲线密码体制是比较新的技术，在椭圆曲线 密码体制中，首要问题就是安全椭圆曲线的选取问题，如果选取的椭圆曲线本身是不 安全的，那么基于该椭圆曲线的任何方案都是不安全的。如何选取基点也是构造椭圆 曲线密码体制的关键要素。所以在本章介绍椭圆曲线密码体制的常用攻击方法，在大 素数域上如何选取安全的椭圆曲线和基点，并仿真椭圆曲线部分运算，给出椭圆曲线 密码体制的优点。 有限域上的椭圆曲线密码体制的安全性依赖于有限域上的椭圆曲线点群中的离 散对数问题的难解性。目前，解决这个数学困难问题的最有效的算法仍然需要完全指 数时间【1 7 】。同时由于r s a 密码体制中所要求的密钥长度越来越大，导致工程实现变 得越来越困难，人们发现椭圆曲线密码体制是克服此困难的一个有效的方案【i 引，因此 椭圆曲线密码体制成为了一个研究热点。 s c h o o f 首先于1 9 8 5 年提出计算椭圆曲线有理点个数的算法，a t i k i n 和e l k i e s 于 1 9 8 9 年到1 9 9 2 年之间，对其作出了重大改进，随后经过c o u v e r g n e s 、m o r a i n 、l e r c i e r 等人完善，到1 9 9 5 年人们己经能较容易地计算出满足密码要求的椭圆曲线有理点的 个数 1 9 】，从而解决了椭圆曲线的选取问题和对任意椭圆曲线上有理点个数的计算问 题，为椭圆曲线密码系统的实现铺平了道路。 现在已有许多的厂商已经或正在开发基于椭圆曲线加解密和数字签名的产品。加 拿大c e r t i c o m 公司是国际上最著名的e c c 密码技术公司，己授权多家企业使用该公 司的e c c 密码技术产品。 2 0 0 0 年武汉己经开发成功首套椭圆曲线加密软件，采取与目前国际上通行的r s a 加密法迥异的一种数论计算方法，其核心技术指标达到国际网络安全性认证标准。 2 0 0 3 年5 月1 2 日中国颁布的无线局域网国家标准g b l 5 6 2 9 1 1 中，涉及到证书的 签名采用的就是椭圆曲线e c c 算法。 2 0 0 5 年，清华大学微电子研究所的白国强等人设计完成椭圆益线密码芯片 t h e c c 2 3 3 1 0 0 ，是国内第一块e c c 芯片。该芯片具有完全自主知识产权。数字签 名算法采用了i e e e l 3 6 3 标准中的算法。经电路板验证，在1 0 0 m h z 的工作频率下芯 片工作稳定，每秒可以连续完成数字签名4 0 0 0 次。 椭圆曲线密码体制和其它公钥密码体制相比具有如下优点：所需的计算负载小、 存储要求低、所占带宽窄，这些问题正是网络传输系统所要考虑的。随着网络的日益 普及、椭圆曲线密码理论的日益成熟，椭圆曲线密码体系的应用日益成为各国学者研 西南交通大学硕士研究生学位论文第7 页 究的热点问题，引起了世界标准组织及密码学界越来越广泛的关注。 2 2 椭圆曲线的定义 椭圆曲线定义：设k 是一个数域，则由w e i e r s t r a s s 方程如式( 2 1 ) 所示： y 2 + 口1 x y + a 3 y 2 x 3 + 口2 x 2 + 口4 x + a 6 ( 2 - 1 ) 在k 上的解集连同一个称之为无穷远点的特殊点o 所确定一条曲线e ，称为k 上的椭 圆曲线。 若k 的特征为2 ，则方程可以变换为如式( 2 2 ) 所示： y 2 + 砂= x 3 + a x 2 + 6 ( 2 - 2 ) 若k 的特征为3 ，则方程可以变换为如式( 2 3 ) 所示： y 2 = 工3 + 戤2 + h + c ( 2 3 ) 若k 的特征大于3 ，则方程变换为如式( 2 4 ) 所示： y2=z3+ax+c(2-4) 设f ( x ，y ) = 0 为上述各椭圆曲线方程的隐式方程，则若点p ( x ，y ) 使得b f 3 x ， 护a y 不同时为零，称p 为非奇异点。 2 3 建立在椭圆曲线上的密码体制 2 3 1 椭圆曲线离散对数问题及其攻击方法 给定椭圆曲线e ( e ) 上的一个基点g 和一个整数k ( 1 k ，z 一1 ) ，求数乘 k g = q ( m o d p ) ，q 也是e 上的一点，计算k g = g + g + + g ( 阶g 相加) 相对容易； 但若给定椭圆曲线上两点g 和q ，求一整数k ，使k g = q ( m o d p ) ，特别是当g 是较 高阶的基点时，则非常困难。这就是椭圆曲线离散对数问题( e c d l p ) 。 椭圆曲线离散对数问题( e c d l p ) ：寻找一个k c ，使得当p ，q 时有q = k p 。 由于e c d l p 的代数对象仅由一个基本的运算构成，就是椭圆曲线上点的加法。这使 得椭圆曲线离散对数问题比大整数因数分解和一般有限域上的离散对数更加难解。对 于现有的攻击离散对数问题的方法是建立在有限阿贝尔群g 上的，同样，这些方法也 可用于求解e c d l p 。因为在椭圆曲线上点加操作比较复杂，所以这些方法总体来说 西南交通大学硕士研究生学位论文第8 页 量oi _i_ii 一一, , , i f 鼍曼曼皇皇曼量曼皇量曼曼曼舅舅曼曼舅曼曼鼍皇曼曼曼量曼皇皇曼曼鼍 比较慢。攻击方法可以归纳总结如下： ( 1 )穷举搜索法 这是一种直观的方法，就是简单的计算p 的连续倍数：p ，2 p ，3 p 直到得到 q = k p 为止，这种方法最坏的情况是计算k 步，平均情况下是k 2 步。因此为了安全 起见可以通过选择参数k 足够大的椭圆曲线，使得穷举搜索的计算量不可实际实现 ( 如k 2 8 0 ) 。 ( 2 ) 大步小步法 设p 为椭圆曲线e ( c ) 上的点，p 的阶为刀，己知点d e ( p 生成的循环群) ， 求正整数七，使得q = 护( o 尼h ) 。将七表示为七= c i + d ；其中，。c ，d i 司 这里i 石l 表示不小于石的最小正整数。令尉= d = d p ，存储关于尺d ( o d l 铜) 的 表，对于c - - 0 ，l i 铜一1 ，依次计算- - c i ii p 。将与r d 表中的点比较，若某个 足。与心。相同，则有后= c o + i 司d o 。计算r d 叫做小步，计算足。可叫做大步。小步 和大步都要求d ( i ) 次e ( c ) 上点的计算，所以此方法的时间复杂度为d ( i ) 这个方 法把穷搜索中的部分时间换为存储，即空间换取时间，它需要存储大约d ( ，z ) 个e 点。 ( 3 ) p o l l a r d p 算法 这个方法是p o l l a r d 提出的，它实际上是小步大步法的一个变形，它的运行时间 与小步大步法差小多，但它比小步大步法优越之处是它的预存储时间是可以忽略不计 的。在p o l l a r d p 方法中使用一种简单的规则将包含p 的有限群( 尸) 分成三个大致相 等的子集s ，s ：，j s r ，通常是以点的横坐标模3 的结果作为分类的规则。 由此可以看出，使用大步小步或是p o l l a r d p 方法计算椭圆曲线问题，需要的时 间与生成元的阶的平方根大小有直接关系。因此，为了使椭圆曲线密码系统具有足够 的安全性，生成元的阶要足够大。目前认为当椭圆曲线的阶为1 6 0 位的二进制数可以 提供足够的安全性。 ( 4 ) 分布式p o l l a r d p 算法 分布式p o l l a r d - p 算法是对p o l l a r d - p 算法的并行处理，使得算法分m 个过程并行 西南交通大学硕士研究生学位论文第9 页 处理，运行时间大约为翮2 m 步，分布式p o l l a r d p 算法是目前已知的对一般椭圆 曲线对数问题最好的攻击方法。 ( 5 ) p o h l i g h e l l m a n 算法 设点p 为椭圆曲线e 上的一点，它的阶是，z ，q = k p 。首先，分解n = k l i 蟹k 3 ， 则寻找k 便归结为寻找k m o d k 7 ( 1 f s ) ，然后利用中国剩余定理计算出k 。该算法 适用于任何有限阿贝尔群上的离散对数问题，它利用中国古代剩余定理，将阶有限 群g 上的离散对数问题转化为素因子的循环子群上若干离散对数问题，当生成元的阶 的因子全部是小素数因子时，这种算法非常有效。 ( 6 ) 异常曲线 对于一些特殊的曲线，还有m o v ，同构攻击，s s s a 攻击，g h s 等攻击其中m o v 是针对超奇异椭圆曲线的有效方法，设椭圆曲线的所在的域的特征值为p ，椭圆曲线 的迹为t 是p 的整数倍时，称椭圆曲线为超奇异的。其中s s s a 算法于1 9 9 7 年由s m a r t 、 s a t o h 、s e m a e v 和a r a k l 提出，是一种针对异常椭圆曲线的有效算法。设q = p ”，p 2 ，3 为素数，e ( ) 为椭圆曲线，尸e ( ) 的阶为p 。当q = p 时，椭圆曲线的迹为1 ， 称为异常椭圆曲线。这些方法都是将求解e c d l p 问题成功约减为求解d l p 问题。 2 3 2 有限域上安全椭圆曲线的选取 安全椭圆曲线的选取需要满足下面的安全准则： ( 1 ) q = p 或q = 2 ”，其中m 是素数； ( 2 ) 椭圆曲线是非超奇异的； ( 3 ) 基点的阶，z 不整除g 一l ( a k c ) ( 4 ) 椭圆曲线是非异常的。 下面基于这些准则，来介绍选取安全椭圆曲线的方法。获取安全的椭圆f h j 线主要 有以下四种办法： ( 1 ) 有限域g f ( q ) 上随机生成一椭圆曲线，直接计算其阶，判断阶是否为大素数或 含大素数因子，若是即确定，否则继续选取曲线，直至符合条件。 ( 2 ) 取具有一定特殊性椭圆曲线的系数，计算该椭圆曲线的阶，对该阶进行判断， 直至找到所需要的安全曲线。 ( 3 ) 如果q = 2 ”，其中m 能被一个比较小的整数d 整除，我们首先在有限域 西南交通大学硕士研究生学位论文第1 0 页 g f ( q i ) ( g l = 2 d ) 上选择椭圆曲线e 并计算其阶，根据此值，利用w e i l 定理计 算该曲线在其扩域g f ( q ) 上的阶，若此阶符合安全标准，我们再找曲线e 在域 g f ( q ) 上的嵌入e ，则e 即为所需的安全椭圆曲线。 ( 4 ) 首先给出具有安全条件的曲线阶，然后构造具有此阶的椭圆曲线。 2 3 3 椭圆曲线密码系统 椭圆曲线密码是公钥密码的一种，公钥密码的加密原理本质上是一样的：发送方 用接收方的公钥对明文消息进行加密产生密文；密文通过公共信道传送到接受方；接 收方用自己的私钥对密文进行解密得到相应的明文。原理如图2 1 所示： 接收方公钥接收方公钥 图2 1 椭圆曲线加密系统原理图 2 4 椭圆曲线密码体制的运算 2 4 1 点加运算 椭圆f h j 线上的加法如图2 - 2 所示。设p = ( x 1y 。) ，q = 0 2 ，y 2 ) 是e 上的任意两点， 三是通过p 、q 两点的直线。若p 和q 重合与一点，则上为过p 点的切线，三和椭圆 曲线相交与另一点r ，该点关于x 轴的对称点j r 也在椭圆曲线上，定义为r = 尸+ q ， 若p 和q 关于x 轴对称，即与y 轴平行，则三和椭圆曲线相交与无穷远点o 。 西南交通大学硕士研究生学位论文第11 页 i 一仑 p 最 捻 ；， j t ? n ? ：r 。| o夕 。卜 汲 图2 2 椭圆曲线上“加法示意图 椭圆曲线上的加法运算有如下性质： 1 若直线三和尺相交于p ，q ，r 三点，则尸+ q + r 。= 0 ； 2 对v p e ，有p + 0 = p ； 3 对v p ，q e ，有p + q = q + p ； 4 对v 尸e ，存在e 上一点，记为一p ，是p + ( 一p ) = 0 ； 5 若p ，q ，s e ，则( p + q ) + s = p + ( q + s ) ； 如果记2 p = p + p ，3 p = p + 尸+ 尸，舻= p + + p ( ，z 个尸相加) ，则称，舻为椭 圆曲线e 上的点乘运算，如果存在最小的正整数刀，使得n p = 0 ，则称，z 是点p 的阶。 有限域g f ( p ) 上( p 为素数) 的椭圆曲线： 有限域g f ( p ) 上的椭圆曲线是对于固定的a ，b 值，满足形如方程： y 2 兰x 3 + a x + b ( m o d p ) 的所有点( z ，y ) 的集合与一个零点或无穷远点0 的并集。其中 口，beg f ( p ) 。该椭圆曲线只有有限个点。 有限域g f ( 2 ”) 上的椭圆曲线： 有限域g f ( 2 册) 上的椭圆曲线是对于固定的a ，b 值，满足形如方程： y 2 + x y - - 工3 + a x + b 的所有点( 工，y ) 的集合与一个零点或无穷远点0 的并集。其中 口，b g f ( 2 所) 。该椭圆曲线只有有限个点。 2 4 2 点乘运算 西南交通大学硕士研究生学位论文第1 2 页 标量乘法是椭圆曲线的核心计算，指如下的式子：q = k p 。这里q ，p 是椭圆衄 线上的点，k 为整数，并且t 不能大于p 的阶。在密码体制的实现中，它的运算速度 直接影响到整体速度椭圆曲线上的点加运算与倍点运算归根结底是为标量乘法服务 的。 目前标量乘的快速算法主要有：二进制方法，m 进制法，二进制展开法，辨进制 展开法( 对进行变换) ，固定基点窗口法 f i x e , d - b a s ew i n d o w i n ga l g o r i t h m ) ，非邻接法 ( n o n a 嘶a c c n t f o r m n a f ) ，固定基点梳形法( f i x e c l - b a s e c o m b d g o n n l i n ) ，坐标变换法等。 在标量乘法的快速算法中最基本的算法是二进制的d o u b l e a d d 方法，是把整数女 用二进制表示。然后进行点加、倍点运算。 2 4 3 求逆运算 一般来说，求椭圆曲线上某元素的逆元，是非常费时间的一种运算。求某元素的 逆元是指：己知口，g c d ( 口， ) = 1 ( 即d ，”互为质数) ，满足等式似；l m o d n 的z e 只 称为有限域中的逆，可以表示为口m o d n 。求模逆的算法有许多种一般采用推广的 欧几里德算法( e e a e x t e n d e de u e l i d e a na l g o r i t h m ) 。歇几里德算法又称辗转相除法， 主要用于因数分解和求公因子。对于整数口和n ，若g o d ( a ，n ) = 1 ，利用欧几里德算法 可找出两个常数u ，r 使得u a + = 1 ，于是是口模n 的乘法逆。测试结果如图2 - 3 所示。 d 瞎目 r g旺嘧妊y 蜩i 舳仆 霄 a ：17 2 3 8 7 2 3 4 2 1 1 d - 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ar o o dn 晌逆- s g 3 g 4 6 9 2 3 0 7 7 g o g 7 图2 - 3 求模逆运算示意图 2 5 椭圆曲线密码体制的优点 西南交通大学硕士研究生学位论文第13 页 ( 1 ) 安全性能更高 加密算法的安全性能一般通过该算法的抗攻击强度来反映。e c c 和其他另外几种 公钥系统相比，其抗攻击性具有绝对的优势。椭圆曲线的离散对数问题( e c d l p ) 计算 困难性在计算复杂程度上目前是完全指数级的，而r s a 是亚指数级的，因此e c c 比 r s a 的每比特安全性更高。 ( 2 ) 计算量小和处理速度快 在相同的计算资源条件下，在处理私钥的速度上( 签名和解密) ，e c c 远比r s a 和d s a 快得多，因此e c c 总体速度比r s a 、d s a 要快得多，同时e c c 系统的密钥 生成速度比r s a 快百倍以上。假设能够提供与8 0 b i t 、1 1 2 b i t 、1 2 8 b i t 、1 9 2 b i t 、2 5 6 b i t 的对称密码等价的安全性，r s a 、d l 和e c 密码的参数规模如表2 1 所示。 表2 1等级强度的参数比较大小 e c c 的密钥尺寸和系统参数与r s a 、d s a 相比要小得多。1 6 0 位e c c 与1 0 2 4 位r s a 、d s a 具有相同的安全强度，这就意味着它所占用的存储空间要小得多。这 对于加密算法在资源受限环境上( 如智能卡等) 的应用具有特别重要的意义。若安全性 的级别是k 位，则意味着用己知的最好的算法进行攻击，大约需要计算2 步通过比较 可知，对于给定的安全级别，e c c 比r s a 和d l 有更小的参数。安全级别越高，参 数大小的差异就越明显。更小的参数带来的好处是计算速度更快、密钥更短和密钥证 书更小。由于密钥短，所以工程实现的加解密速度较快，并且可节省能源、带宽和存 储空间，特别适合那些需要高安全性的应用。由于椭圆曲线密码具有上述优点，e c c 必将取代r s a ，成为通用的公钥加密算法。 2 6 本章小结 本章介绍了椭圆曲线的基础知识，其中包括椭圆曲线的概念、运算、离散对数问 题、攻击现状、安全选取等问题，并且给出椭圆曲线部分运算的代码模块，用软件进 行了仿真实现，总结了椭圆曲线密码体制所具有的优点。 西南交通大学硕士研究生学位论文第14 页 3 1 数字签名概述 第3 章数字签名研究 3 1 1 数字签名的概念 数字签名( d i g i t a ls i g n a t u r e ) 在i s 0 7 4 9 8 2 标准中定义为：“附加在数据单元上的 一些数据，或是对数据单元所作的密码变换，这种数据和变换允许数据单元的接收者 用以确认数据单元来源和数据单元的完整性，并保护数据，防止被人进行伪造 。美 国数字签名标准( d s s ，f i p s l 8 6 2 ) 对数字签名作了如下解释：“利用一套规则和一个 参数对数据计算所得的结果，用此结果能够确认签名者的身份和数据的完整性”。由 此可见，所谓“数字签名”就是通过某种密码运算生成一系列符号及代码组成电子密 码进行签名，来代替手写签名或印签，以防止消息的伪造或篡改，亦可用于通信双方 的身份鉴别，是手写签名的电子模拟。 数字签名和传统的手写签名有很大的区别【2 3 】： ( 1 ) 手写签名是被签署文件的物理组成部分，而数字签名必须设法使签名“绑 到所签名的文件中。 ( 2 ) 手写签名不易拷贝，而数字签名正好相反，因而必须阻止一个数字签名消 息被重复使用。一般要求消息本身带有诸如日期等信息来达到阻止签名被重复使用的 目的。 ( 3 ) 手写签名是通过与一个真实的手写签名比较来进行验证，而数字签名是通 过一个公开的验证算法进行验证。数字签名是由0 和1 组成的数字串，它因消息而异， 当出现争端时，它能够为仲裁者提供足够的证据来进行裁决，其安全性要远远高于手 写签名，此外，数字签名依托与计算机网络，其时效性也远远大于手写签名。 一般数字签名方案包括3 个部分：即系统的初始化过程、签名产生过程和签名验 证过程。下面给出数字签名的形式化定义【2 4 】： ( 1 ) 初始化过程 产生签名方案中的基本参数( m ，s ，k ，s i g ，v e r ) ，其中m 是消息集合，s 是签名集 合，k 是密钥集合，包含公钥集合麒和私钥集合s k ，s i g 是签名算法集合，v e r 是 签名验证算法集合。 ( 2 ) 签名产生过程 对于密钥集合足，相应的签名算法s i g 娃s i g ，s i g 政：m s ，对任意的消息 m m ，有s = s i g 曲( m ) ，那么s s 为消息m 的签名，将( m ，s ) 发送到签名验证者。 西南交通大学硕士研究生学位论文第15 页 ( 3 ) 签名验证过程 对于密钥集合k ，相应的有签名验证算法 玩：m x s 一 t r u e , f a l s e v e r p