（计算机软件与理论专业论文）椭圆曲线数字签名与加密研究.pdf

椭圆曲线数字签名与加密研究 摘要 椭圆曲线密码系统的安全性是建立在有限域上椭圆曲线离散对数问题的难解性 上的。与其他公钥密码系统相比，椭圆曲线密码系统不但具有高安全性，而且具有计 算载荷小，密钥长度短，占用带宽少等优点。因此日益受到人们的关注，成为公钥密 码学的研究热点。 本文首先对密码学的发展现状及其发展趋势进行了分析和综述，阐述了椭圆曲线 研究现状及研究意义。其次，探讨了椭圆曲线密码的数学基础、有限域上椭圆曲线的 基本概念、椭圆曲线密码体制的实现、椭圆曲线上点的加、乘法运算等问题，同时对 椭圆曲线密码系统的安全性和有效性进行了分析。第三，在分析各种典型数字签名算 法之后，提出一种基于e c c 的e i g a m a l 数字签名方案，并验证了该方案的正确性。 第四，分析椭圆曲线加密系统，并对现有的椭圆曲线m e n e z e sv a n s t o n e 加密系统做出 改进，提出m v l 加密算法。此外将椭圆曲线和e 1 g a m a l 加密算法相结合，提出e c c e 加密算法并给出密码学性能分析，并结合a e s 加密算法给出其在电子信封技术中的 应用框架。最后，对建构椭圆曲线设计中的两个关键技术：安全椭圆曲线的构建和基 点的选取做出了分析总结，并对椭圆曲线的选取算法做出有效改进。 关键词：椭圆曲线密码；信息安全；数字签名；加密；e i g a m a l s t u d yo ne c cd i g i t a ls i g n a t u r ea n d e n c r y p t i o n a bs t r a c t t h es e c u r i t yo 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 nt 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 nt oi t sh i g hs e c u r i t y , e c ca l s oh a sm a n yo t h e rm e r 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 ha 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 ys 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 o0 1 1 s o m o r ea n dm o r ep e o p l ea r ea t t r a c t e db yt h i st a s k ，a n di th a sb e c o m et h eh o t s p o to fp u b l i c c r y p t o g r a p h y t h i st h e s i sf i r s ta n a l y s e sa n ds u m m a r i z e st h es t a t u sq u oa n de v o l u t i o nt r e n do f c r y p t o g r a p h y ，a n di n t r o d u c e st h er e s e a r c hs t a t u sa n d r e s e a r c hs i g n i f i c a n c eo fe c c s e c o n d ，t h ep r i n c i p l eo fe c ci sd i s c u s e d ，i n c l u d i n gt h em a t hf o u n d a t i o no fe c c ，b a s i c c o n c e r p t i o no fe l l i p t i cc u r v e ，c o n s t r u c t i n gi d e ao fe c c ，o p e r a t i o no nt h ee l l i p t i cc u r v e a n ds oo n m e a n w h i l e ，t h es e c u r i t ya n de f f i c i e n c yo fe c ca l ea n a l y z e d t h i r d ，a f t e r a n a l y s i sv a r i o u st y p i c a ld i g i t a ls i g n a t u r ea l g o r i t h m ，t h ev a r i a t i o no fe l g a m a ls i g n a t u r e a l g o r i t h mb a s e do ne c c i sp r e s e n t e da n di t sv a l i d i t yi sp r o v e d f o u r t h ，a n a l y s e se l l i p t i c c u r v es y s t e m ，a n di m p r o v et h ec u r r e n te l l i p t i cc u r v es y s t e m - m e n e z e sv a n s t o n ee n c r y p t i o n s y s t e mt om v 1 e n c r y p t i o ns y s t e m i na d d i t i o n ，c o m b i n ee l l i p t i cc u r v e sa n de 1 g a m a l a l g o r i t h m sw i l lb et og i v et h ef e a s i b i l i t yo fe c c - ee n c r y p t i o na l g o r i t h ma n da n a l y s e si t s p e r f o r m a n c eo fc r y p t o l o g y , t h e nc o m b i n e di t 、兢t l la e se n c r y p t i o na l g o r i t h m g i v ei t s d 滔t a le n v e l o p et e c h n o l o g yf r a m e w o r k f i n a l l y , a n a l y s ea n ds u m m a r i z et h et w ok e y t e c h n o l o g i e so fc o n s t r u c te l l i p t i cc u r v e s ：c o n s t r u c t i o no fs e c u r ee l l i p t i cc u r v ea n d s e l e c t i o no f b a s ep o i n t s ，a n di m p r o v et h ee l l i p t i cc u r v ec o n s t r u c ta l g o r i t h m i i k e yw o r d s ：e l l i p t i cc u r v ec r y p t o g r a p h y ；i n f o r m a t i o n s e c u r i t y ：d a t a d i g n a t u r e ；e n c r y p t i o me l g a m a l i i i 浙江师范大学学位论文独创性声明 本入声明所呈交的学位论文是我个人在导师指导下进行的研究一作及 取得的研究成粱。沦文中除了特别加以标注和致谢的地方外，不包含其他人 绒其 也机构已经发袭或撰写过的研究成祭其他同态对本研究的霸发和所傲 的贫献均已在论文中作了明确的声明并表示了谢意。本入完全意识到本声明 的法律结粜醢i 本人承规。 份者簇名； 撼期；) 口年问堰翻 学位论文使用授权声明 本人宪垒了斛浙江师范大学有关缳留、使用擘缀论文的规定。郄：学拨褥投 傺掰并翔困家衡关机关或移l 构送交论文豹复印纷嗣电子文耥，允许论文被套阕嗣 嚣| 阅，可以采用影印、编印线扫描铃手段缫存、汇编学位论文。嗣意浙江鄹范大 学可以用不网方式在不问媒体上发袭、传锸论文的全郄或部分内容。 保密的学位论文在解密蔚遵守此协议。 作者签名：谘墨吞 导师签名： 同躲铋月 p 浙江师范大学学位论文诚信承诺书 我承诺自觉遵守浙江师范大学研究生学术道德规范管理条 例我的学位论文中凡引用他人已经发表或朱发表的成果、数 据、观点簿，均已明确注明并详细列出有关文献的名称、作者、 年份、刊物名称零l 出版文献的出版机构、出版地和版次等内容。 论文中未注明的内容为本人的研究成采。 如有违反，本人接受处罚并承担一切资任。 承诺入( t i 珊 究生) ：融去 指一师m 奠 第1 章绪论 随着i t 技术迅猛的发展，各个行业的信息化、网络化的增强，信息的安全性越 来越得到人们的重视。一个完整的、先进的信息系统无不考虑到信息安全技术的应用。 密码学时信息安全的基础的基础理论，密码技术是保证信息安全的关键技术之一。 1 1 密码学研究现状 密码学有着悠久而神秘的历史，人们很难对密码学的起始时间给出准确的定义。 初期的密码技术主要用于军事、外交、情报等敏感领域，受到特殊应用环境的影响发 展缓慢。1 9 4 9 年美国科学家s h a n n o n 的一篇文章“保密系统的信息理论 ，他在研究 保密机的基础上，提出将密码建立在某个已知数学难题基础上的观点。随着电子技术 的广泛应用，以及公开密钥思想的提出，都极大地促进了现代密码体制的发展【lj 。 按照加密体制的不同，现代密码学可以分为：私钥密码体制和公钥密码体制，后 者因为所需的密钥数量少很适合目前的网络环境，因此得到了广泛的应用。 公钥加密系统都是基于数学难题建立的，由于计算步骤复杂因而其计算速度比私 钥加密系统要慢很多。当r s a 算法的模为5 1 2 比特，硬件实现时，d e s 的运算速度 大约比r s a 快1 0 0 0 倍，软件实现时，d e s 的运算速度大约比r s a 快1 0 0 倍。 公钥密码体系的安全性是基于求解数学中困难问题的。目前比较流行的公钥密码 体制中既具有一定安全性又能比较容易实现的，按照所基于的数学难题类型可分为如 下三类：基于大整数分解问题的公钥算法( 如r s a ) ；基于有限域上的离散对数问题 的公钥密码( 如d s a ) ；基于有限域上椭圆曲线的离散对数问题的公钥密码( 如e c c ) 。 第1 章绪论 1 2 椭圆曲线研究现状及意义 1 9 8 5 年n e a lk o b l i t z l 2 1 和v s m i l l e r 3 1 分别独立提出在公钥密码系统中使用椭圆曲 线的思想，这是首次将椭圆曲线的研究成果应用到密码学中。 从1 9 8 5 年到1 9 9 5 年大约十年时间，人们对椭圆曲线密码技术的理论研究做了很 多工作，对椭圆曲线密码系统的安全性作了深入的分析，提出了许多快速实现椭圆曲 线密码系统的算法方案，其中最为显著的研究成果是对有限域和域操作算法。1 9 9 5 年之后，椭圆曲线密码技术的实际应用越来越多的得到人们的关注，人们做了很多行 之有效的工作，进一步改善椭圆曲线密码算法的性能，降低其计算复杂度，一些实验 性的椭圆曲线密码系统也被实现，并且其性能基本上达到实际应用的要求。 随着对椭圆曲线研究的成熟，各个技术标准组织也做了大量工作，使椭圆曲线的 理论与应用标准更加合理、更加严谨。1 9 9 8 年椭圆曲线密码系统被确定为i s o i e c 数 字签名标准i s o1 4 8 8 8 3 ；1 9 9 9 年椭圆曲线数字签名算法e c d s a 被a n s i 确定为数 字签名标准a n s i9 6 2 1 9 9 8 ，椭圆曲线算法d i f f e h e l l m a n 体制版本e c d h 被确定 为a n s ix9 6 3 ；2 0 0 0 年被确定为i e e e 标准i e e e1 3 6 3 2 0 0 0 ，同期，n i s t 确定其 为联邦数字签名标准f i p s l 8 6 2 4 1 。 目前，国外对e c c 的应用取得了不少的成果，其中最突出的是加拿大的几位学 者开设的c e r t i c o m 公司。c e r t i c o m 已经开发出在商业领域内安全、实现高效e c c 技 术的方法，并推出一些列的安全产品，被几家大公司采用。相比之下，国内对e c c 基本上仅限于理论研究，信息安全产品大多数是基于r s a 公钥密码体制的，利用e c c 体制的较少。因此，对e c c 密码体制和基于e c c 的签名研究具有重要的理论研究意 义和良好的应用前景。本文的研究工作也是基于e c c 密码体制展开的。 1 3 作者所做的工作 作者在查阅了大量文献的基础上做了如下工作： 2 第1 章绪论 ( 1 ) 3 4 节中，在总结分析现有签名方案基础上，对椭圆曲线密码体制进行了探 索，提出一种改进的椭圆曲线签名算法并给出可行性证明。 ( 2 ) 在4 2 节，对现有的椭圆曲线m e n e z e s v a n s t o n e 加密系统做出改进，提出 m v l 加密算法；将椭圆曲线和e 1 g a m a l 算法相结合，提出e c c e 加密算法并给出密 码学性能分析，最后给出e c c e 算法在电子信封技术中的应用框架。 ( 3 ) 在第5 章中，对建构椭圆曲线设计中的两个关键技术：安全椭圆曲线的构 建和基点的选取做出分析总结，并对椭圆曲线的选取算法做出有效改进。 1 4 本文组织结构 本论文的结构主要由六部分组成，具体组织结构如下： 第1 章引言。本章介绍密码学研究现状，作者所做的主要工作以及文章的组织 结构。 第2 章椭圆曲线密码体制。本章重点介绍椭圆曲线的有关数学理论、性质以及 椭圆曲线密码体制的实现。 第3 章基于椭圆曲线的数字签名研究。本章首先对数字签名进行概述，并分析 典型的签名算法，并在椭圆曲线的基础上进行探索，提出一种改进的椭圆曲线签名算 法并给出理论证明。 第4 章基于椭圆曲线的数据加密研究。总结分析了椭圆曲线加密系统和椭圆曲 线上m e n e z e s v a n s t o n e 加密系统，并在椭圆曲线加密算法的基础上提出两种改进的加 密算法m v l 、e c c e 加密算法并给出密码学性能分析。最后给出e c c e 算法在电子 信封技术中的应用框架。 第5 章安全椭圆曲线的构造和基点的选取。本章对建构椭圆曲线中的两个关键 技术：安全椭圆曲线的构建和基点的选取做出了分析，并对椭圆曲线的选取算法做出 改进。 第6 章总结与展望。对本文所做的工作进行总结以及研究工作的展望。 3 第2 章椭圆曲线密码体制 有限域上的椭圆曲线的安全性依赖于有限域上的椭圆曲线点群中的离散对数问 题的难解性。目前，解决这个数学困难问题的最有效的算法仍然需要完全指数时间【5 】。 同时由于r s a 密码体制中所要求的密钥长度越来越大，导致工程实现变得越来越困 难，人们发现椭圆曲线密码体制是克服此困难的一个有效的方案，各种研究不断展开。 随着椭圆曲线公钥研究的深入，椭圆曲线公钥体制的趋于完善，国际制定了椭圆曲线 公钥密码标准【6 】和应用标准，为椭圆曲线的广泛应用奠定了坚实的基础。 2 1 椭圆曲线密码体制的概述 椭圆曲线密码体制是基于e c d l p 的各种公钥密码体制，它是利用有限域上的椭 圆曲线有限群代替离散对数问题的有限群得到的一系列密码体制。目前基于有限域上 椭圆曲线离散对数问题的公钥密码体制，包括基于椭圆曲线d h 密钥交换方案、基于 椭圆曲线型的密钥交换方案、基于椭圆曲线型的数字签名方案等。 椭圆曲线密码刚被提出时，由于理论还不成熟，计算难度过于大，运算实现速度 慢，并没有引起密码学界太多的关注。1 9 9 0 年，m e n e z e s 提出使用某些特殊曲线可以 达到快速实现，但后来发现这些曲线存在着某些不足，攻击者可以利用这些不足，达 到攻击目的。1 9 9 1 年m e n e z e s 、o k a m o t o 和v a n s t o n e 联合提出m o v 方法，这种方法 能够将超奇异的椭圆曲线上的离散对数问题在多项式时间内约化到该椭圆曲线域的 某个次数较低的扩域上，进而利用已知求解d l p 的算法对其进行求解( _ 7 1 。为了避免 系统受到m o v 方法的攻击，椭圆曲线密码体制放弃使用特殊曲线。 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 年人们己经能够较容易地计算出满足密码要求的椭圆曲线有 4 第2 章椭圆曲线密码体制 理点的个数【8 】，从而解决了椭圆曲线的选取问题和对任意椭圆曲线上有理点个数的计 算问题，为椭圆曲线密码系统的实现铺平了道路。 椭圆曲线密码体制和其它公钥密码体制相比除了安全性高外还具有如下优点：所 需的计算负载小、存储要求低、所占带宽窄，这些问题正是网络传输系统所要考虑的。 随着网络的日益普及、椭圆曲线密码理论的日益成熟，椭圆曲线密码体系的应用同益 成为各国学者研究的热点问题，引起了世界标准组织及密码学界的关注。 椭圆曲线密码体制与r s a e 1 g a m a ll 密码体制的比较如表2 1 1 9 所示。 表2 1 椭圆曲线密码体制与r s a e i g a m a l 密码体制性能对比表 r s a e 1 g a m a l 椭圆曲线密码密钥长度比破解所需 密码长度( 比特) 长度( 比特)时间( 年) 5 1 21 0 55 ：1 1 0 4 7 6 8 1 3 2 6 - l 1 0 8 1 0 2 41 6 07 ：1 1 0 1 1 2 0 4 82 1 01 0 ：1 1 0 2 0 2 1 0 0 06 0 03 5 ：1 1 0 7 8 2 2 椭圆曲线的数学理论 本节介绍椭圆曲线密码学的数学基础：w e i e r s t r a s s 方程、j 不变量和同构、椭圆曲 线上点的加法法则及椭圆曲线的阶【1 0 】【1 1 1 1 1 2 】【1 3 】【1 4 1 。随后各章介绍的椭圆曲线密码技 术，都是建立在本章密码学理论基础之上的。 2 2 1w eie r s t r a s s 方程 曲线e ： y 2 + a l x y + a 3 y - - x 3 + a 2 x 2 + a 4 x + a 6 口1 ，a 2 ，码，a 4 ，口6 k 域 这里k 域不妨先假定是实数域r 或有理数域q 。 5 ( 2 1 ) 或 引进变量置换 代入式( 2 1 ) 得 y = y 2 第2 章椭圆曲线密码体制 ( 2 2 ) y 2 一( a t x + a 3 ，y + 百1c q 2 x 2 + 2 口。口，x + 口，2 ，+ 口。z y l ( a 。x + a 3 ， + 口， y l ( a 。x + a 3 ， 整理得 其中 最后得 或 2 x 3 + a 2 x 2 + a 4 x + a 6 】，2 + q x y + a 3 y =x 3 + a 2 x 2 + a 4 x + a 6 a l = ( - a l + a 1 ) = 0 a 3 a 2 = ( - a 3 + 口3 ) = 0 口：+ 虿1 口，2 一百1 口1 2 = 口：+ 百1 口。2口2 + 虿口l 一百口12 口2 + 百口1 111 l 口42 a 4 一互口l 口3 + 互口l 口3 + 互口l 口3 = 0 4 + j 口l 口3 1 2 1 2 1 2 口62 a 6 一百口3 + j 口32 + 百口3 y 2 = x 3 + 1 7 2 x 2 + 三6 4 x + 丢6 62 4 ” 6 2 = a 1 2 + 4 a 2 ，6 4 = 2 a 4 + a i a 3 ，吃= a 3 2 + 4 a 6 ( 2 3 ) ( 2 4 ) ( 2 5 ) 对于k 域的特征值c h a r ( k ) 3 ，实数域r ，有理数域q 都满足此条件，再引进 x ：x + 土6 2 1 2 x ：x 一土6 2 1 2 6 ( 2 6 ) 第2 章椭圆曲线密码体制 代入整理得 其中 故得 l ，2 = x 3 + c 2 x 2 + q x + c 6 铲3 击6 2 一三也= o 铲l b 2 2 - 2 去b 2 2 + l b 4 = 一去冉三6 4 气= i 1b 。一i 1 b3 + l - 罢t b 2 3 - 1 b 2 b 4 】，2 = x 3 + 酗+ i 也就是将w e i e r s t r a s s 方程归结为一种标准形式： y 2 = x 3 + 吼x + a 6 2 2 2j 不变量和同构 一般的w e i e r s t r a s s 方程 可推导出其判别式为 其中 e y 2 + c h x y + a a y = x 3 + a 2 x 2 + a 4 x + a 6 = 而2 2 6 8 8 b 4 3 2 7 b 6 2 + 9 b 2 b 4 b 6 推导从略见文献 1 0 】。 其中 = 口1 2 口6 + 4 a 2 口6 一口l a 3 a 4 + 口2 口3 2 一口4 2 b 62a 3 2 + 4 a 6 b 42 1 i a 3 + 2 a 4 如= a 1 2 + 4 a 2 = 3 划2 8 + 等2 c 42 b 2 2 2 4 b 4 7 ( 2 7 ) ( 2 8 ) ( 2 9 ) ( 2 1 0 ) ( 2 1 1 ) 第2 章椭圆曲线密码体制 c 6 = 一b 2 3 + 3 6 b 2 b 4 2 1 6 b 6 ( 2 1 2 ) 称为不变量，当两条椭圆曲线的j 相同时，该两条椭圆曲线同构。 定理2 1 当且仅当a 0 时，方程( 2 1 ) 定义的曲线e 是非奇异的。 2 2 3 椭圆曲线上点的加法 e ：y 2 = x 3 + a x + 6 设p = ( x i ，y 。) ，q = 2 ，y 2 ) 都是e 上k 的有理点，且 p q ，令p + q = ( x 3y 3 ) 连p 和q 的直线交e 于r ，j i c 。点也是有理点，尺。关于x 轴的对称点r 为p + q 。 这里所谓有理点指它的坐标是属于k 域元素的有理式。 特别应指出的若p = q 时，p 点的切线交e 于r 。，r 关于x 轴的对称点r 便成为 2 p 点。 在实数平面j ，2 = x 3 一x 上的加法如图2 1 和图2 2 所示。 r 。 j 1 j 纱 l 彳鼎 _ 文锄 ： ji 7 弦 一j j i ： 。 ： v ： j l 。 j 1 j 。 ： l p 粤l 。 1 飞 0如 l ：r j ! j y 。2 名- x 也 ： 。 ： ： ! 。 ： ： 图2 1 椭圆曲线上点的加法( p q )图2 2 椭圆曲线上点的加法( p = q ) 定理2 2 若p 和q 是曲线e 上的任意两点，尸q 连线三交e 于另一点尺，则 ( 1 ) ( 尸+ q ) + r = 0 ，证明略； 8 第2 章椭圆曲线密码体制 ( 2 ) p + o = p ，证明略； ( 3 ) p + q = q + p ，证明略； ( 4 ) e 上存在一点q ，使得p + q = 0 ，则q 称为p 的对称点，q = 一p ，证明略； ( 5 ) 对于e 上的任意点p 、q 、r ，( p + q ) + r = p + ( q + r ) 。证明见文献【1 4 】。 2 2 4c h a r ( k ) = 2 的加法法则 c h a r ( k ) = 2 的域在椭圆曲线中扮演了特殊的角色。 c h a r ( k ) = 2 时， e ：y 2 + a l x y + a 3 y = x 3 + a 2 x 2 + 0 4 x + a 6 ( 2 1 3 ) 若口。= 0 ，作置换 x = x 7 + a 2 ，y = y y 2 + a 3 y = ( x 7 + 口2 ) 3 + 口2 ( x 7 + a 2 ) 2 + a 4 ( x + 口2 ) + 口6 ：x 3 + 2 口2 2 x 7 2 + 口4 + 口6 = 屯+ 口4 + a 6 ( 2 1 4 ) 即x 2 项消失。正规型为 若a l 0 ，作置换 y 3 + 口3 y 2 x 3 + 口4 x + a 6 x ：口1 2 x 7 + 生，y = a 1 3 y + 生2 毕2 口l口1 。 结果y 项和x 项消失，x 3 项系数和y 项系数相等，得 y 2 + x y 2 x 3 + 口2x 2 + 口6 ( 1 ) _ ，0 ，e ：y 2 + 砂= x 3 + 口2 x 2 + 口6 y ( y + x ) = a 3 + 口2 x 2 + 口6 q ( 2 1 5 ) ( 2 1 6 ) ( 2 1 7 ) 第2 章椭圆曲线密码体制 即( x ，y ) 和( x ，x + y ) e 。 若p q ，p = ( 一，y 1 ) ，q = ( x 2y 2 ) ，m = 则 x 32 y 32 ( 必) z + 丛丛 x i + x 2x l + x 2 y l + y 2 x l + x 2 若p ：q ，垅：_ o f a f ： o x ， 则 y 1 + y 2 x 1 + x 2 ，b2 y l + m x l + x l + x 2 + 口2 ( x 3 + x 1 ) + x 3 + y l x 2 + y ( ，j + 6 ) 2 + x ( ，麟+ 6 ) = x 3 + a 2 x 2 + 口6 x 3 = m 2 + m + 口2 = ( x 1 2 + y l ：x 。：4 - 乓 2 x l 了 x 1 ) 2 + ( x 1 2 + y 1 ) + a 2 y 3 = m x 3 + b + x 3 = m x 3 + ( y l + r n x l ) + x 3 x 1 2 + y 1x 3 + _ 2 + x 3 ( 2 ) 若_ ，= 0 ，y 2 + a 3 y = x 3 + 口4 x + a 6 ，竹2y 2 + y l x 2 + x l 代入y 2 + a 3 y = x 3 + 口4 x + a 6 得 ，y = m x + ( y l + m x l ) ( 2 1 8 ) ( 2 1 9 ) ( 2 2 0 ) ( 2 2 1 ) 陬+ ( y l + m x l ) 】2 + 口3 陋+ ( y l + m x l ) 】_ x 3 + 口4 x + a 6 ( 2 2 2 ) 比较x 2 项系数：m 2 ，故 1 0 第2 章椭圆曲线密码体制 x 3 ：( 2 1 二堕) 2 + x l + x 2 x l + x 2 y 3 ：( ! l 丰丝) x 3 + ( 2 1 二堕) x l + y 。 x l + x 2x l + x 2 ：( ! 互车旦) ( x 3 + x 1 ) + y 1 z ，+ 五 p = q 同理可证肌= 鬻= 孚 则 x 3 = 毕+ 2 4 2 x l y ，：血( 而+ 屯) + 乃 ( 2 2 3 ) ( 2 2 4 ) ( 2 2 5 ) ( 2 2 6 ) 这里一个值得注意的问题，若最和最是关于x 轴曲线e 上的两个对称点，即 舅= ( 一，y ，) ，昱= ( x 。，- y 。) ，丑和最的连线交e 的第三点是曲线上的无穷点。 2 3 有限域上的椭圆曲线 2 3 1 椭圆曲线的阶 设k = 艺( 包含q 个元素的有限域) ，兰1 1 为定义在有限域k 上的椭圆曲线。令 a e ( k ) = ( x ，j ，) eix ，y k ) u d ， e ( k ) 称为e 的k 一有理点集合，它是一个有限集，通常把点的数目记为群e ( k ) ， 称之为椭圆曲线e 的阶17 1 。 定理2 3 ( h a s s e 定理) e ：y 2 = x 3 + a x + 6 口，b g f ( p ) 第2 章椭圆曲线密码体制 a = 4 a 3 + 2 7 b 2 0 ，n p 是( x ，y ) g f ( p ) 2 的数目，则 i 群e ( k ) 一q 一1 1 3 的素数) 上的一条椭圆曲线产生的a b e l 群，对 于e 。( 口，b ) 上任意两点p 和q ，寻找一个整数k p 使得q = k p 。明显的，如果已知k 和p ，q 可直接求得；反之，由p 和q 难以计算出k ，特别是当k 很大时，这个难度 不亚于对k 的分解。这个问题称为椭圆曲线上的离散对数问题。有限域上的椭圆曲线 提供了构造离散对数一个新的途径，可以将这种建立在椭圆曲线上的离散对数问题应 用于公钥密码体制的构造。 2 4 椭圆曲线密码体制的实现 1 2 第2 章椭圆曲线密码体制 要建立一个安全的椭圆曲线密码体制，先要确定一个合适的有限域及在其上 选一条安全的椭圆曲线e ( f q ) 1 4 1 。有两种选择方式：大素数域乙或特征为2 的有 限域凹( 2 ”) ，实践证明【1 6 】【1 8 】大素数域更加安全有效。椭圆曲线的选取则更要考虑安 全性、实用性等诸多因素，有些密码体制( 如e i g a m a l 签名体制、d s s 签名体制) 需 要知道e 的阶 e ( ) 包含一个大素数因子，另一些体制( 如d i f f i e h e l l m a i l 密码交换 协议、e 1 g a m a l 加密体制) 虽然不需要知道e ( ) 的阶，但为了避免p o h l i g h e l l m a n 攻击，需保证群e ( ) 中有大素数因子。对椭圆曲线密码体制来说，最基本的操作是 计算 p = f 七1 尸= p + p + p + + 尸 ( 2 2 8 ) 、- ，- - - - - - - - - _ ， k 个p 一般把方程( 2 2 8 ) 中计算【七】尸的运算称为点乘法或标量乘法。其中，p 是曲线 上的点，k 是一个整数且1 k 。依次做倍点计算2 p ，4 p ，8 p ，2 m - 1 e ，然后将对应乃= 1 的那些项相加。设k j ( o j m 一1 ) 中有w 个1 ，则该方法需做聊一1 次倍点运算，w 一1 次加法运算，w 的平均值为詈。 设p = ( x ，y ) ，则一p = ( x ，一y ) ，这是一个可以利用的简单运算，将k 表示为 k = s 2 7 ，一 - 1 ，0 ，1 ) ，称它为二进制带符号表示，s j ( 0 3 ； 输出：安全椭圆曲线方程y 2 = x 3 + a x + 6 ，口，b f ； ( 1 ) 随机生成椭圆曲线参数口，b g f ( p ) ； ( 2 ) 检测参数口，b 是否合法：a b 0 ，= 4 a 3 + 2 7 b 2 0 ；若不然，返回第1 步， 3 9 第5 章安全椭圆曲线的构造和基点的选取 重新选取新的曲线参数d ，b ； ( 3 ) 对a t k i n 素数，由a t l a 切方法计算z ( 4 ) 对e l k i e s 素数，当， 3 ； 输出：e 上的一个随机的非零基点g = ( x ，y ) 。 ( 1 ) 随机选择0 x p ； ( 2 ) 口卜x 3 + a x + b m o d p ： ( 3 ) 若口= 0 ，则输出g = ( x , 0 ) ，退出。 ( 4 ) 求解平方剩余问题2 言a m o d p ： 若2 兰a ：m o d p 无解，返回第1 步，重新选择x ； 若有解，则产生随机位，置y 卜( 一1 ) , f l m o d p ： ( 5 ) 检查g 点的阶，若不符合要求，则重新选择； ( 6 ) 输出g = ( x ，y ) 。 由有限域中关于平方剩余的e u l e r 判断可知，若整数口为奇素数p 的某一个平方 剩余，则必须有口川彪三1 m o d p 。若整数口是奇素数p 的非平方剩余，则有 口p _ 1 陀三一i m o d p 。下面分两种情况讨论。 ( 1 ) 当p = - - 3 m o d 4 时，对口= x 3 + 饿+ 6 ，若2 = a m o d p 有解，则有 口p - 1 坨三1 m o d p ，在方程两边同时乘以口，则有 口( p 一1 ) 7 2 兰c r m o d p ( 6 1 ) 因为p _ - - 3 m 。d 4 ，孕是整数，则 口p + 1 坨= ( 口p + 1 ) 4 ) 2 ( 6 2 ) 第5 章安全椭圆曲线的构造和基点的选取 由式( 6 1 ) 和式( 6 2 ) 易知 所以有 所以 ( 口，+ 1 7 4 ) 2 三am o d p = 口川7 4 m o d p ( 6 3 ) ( 2 ) 当p 兰l m o d 4 时，类似地，若2 = a t m o d p 有解，则有口p - 1 他兰1m o d p ， 口( p 一1 ) 坨一1 兰0 m o d p 由于p 三1 m o d 4 ，孕是整数，对方程式( 6 4 ) 分解可得 p 一1 ) h 一1 ) ( 口p 一1 7 4 + 1 ) 毫0m o dp 显然，只有当口，。1 h 三_ + 1 m o d p 时，方程2 = a m o d p 有解，否则无解。 若口p _ 1 “三1 m o d p ，则方程2 = a m o d p 两边同时乘以口，有 所以 ( 口p + 3 7 8 ) 2 = 口口p 一1 7 4 三am o dp = 口p + 3 7 8m o d p 若口p 。1 三一1m o d p ，则由有限域中的互倒定理和平方剩余的性质有 所以 2 ( p 一1 ) 7 2 三一1 m o d p 口( ，一1 ) 7 4 兰2 ( p i ) 2m o d p 等式两边同时乘以2 ( p - 1 ) 佗t ；t 有 由2 p 1 暑1 m o d p ，有 所以 2 ( p - i ) 2 口( p + 3 ) 7 4 兰2 p - iam o d p ( 2 ( p - 1 ) 4 口p + 3 7 8 ) 2 三am o dp = 2 t p 一1 7 4 口p + 3 7 8m o dp 4 2 ( 6 4 ) ( 6 5 ) ( 6 6 ) ( 6 7 ) ( 6 8 ) ( 6 9 ) ( 6 1 0 ) 第5 章安全椭圆曲线的构造和基点的选取 因此，根据奇素数p 和口p 。h 的情况，从方程式( 6 3 ) 、方程式( 6 6 ) 和方程式 ( 6 1 0 ) 中选择合适的公式即可求出或者判定平方剩余方程2 三c t m o d p 无解。 5 3 本章小结 构造随机性好的安全椭圆曲线和基点对于椭圆曲线密码体系是至关重要的。本章 讨论了这两个关键技术，并在s e a 算法基础上，改进了椭圆曲线的选取算法，使算 法效率得到提高。此外，对基点的选取算法进行了验证。 4 3 6 1 研究工作总结 第6 章总结与展望 椭圆曲线密码系统以它的每比特最高的安全强度迎合了未来人们对信息安全性 的需求，赢得了众多密码学家的关注，对它的研究越来越深入。因此，在不久的将来 椭圆曲线密码系统必定会得到广泛应用。 通过一年多对椭圆曲线密码系统相关知识的学习和研究，本文主要完成以下三个 方面的工作： ( 1 )在总结分析现有签名方案基础上，结合椭圆曲线密码体制进行了探索， 在3 4 节中提出一种改进的椭圆曲线签名算法并给出可行性证明。 ( 2 ) 在4 3 节中，对现有的椭圆曲线m e n e z e s v a n s t o n e 加密系统做出改进，提 出m v l 加密算法，并将椭圆曲线和e 1 g a m a l 算法相结合，提出e c c e 加密算法并给 出密码学性能分析。最后给出e c c e 算法在电子信封技术中的应用框架。 ( 3 )第5 章，对建构椭圆曲线设计中的两个关键技术：安全椭圆曲线的构建 和基点的选取方面做出了分析总结，并对椭圆曲线的选取算法做出有效改进。 6 2 研究工作展望 椭圆曲线密码算法是目前最有活力的公钥算法之一，在其被广泛应用的同时，各 种椭圆曲线密码的改进算法也层出不穷。本文也在椭圆曲线密码算法的基础上提出了 一种改进的签名算法。另一方面，阈下信道是数字签名中一种普遍存在的现象，椭圆 曲线密码算法及其改进算法的阈下信道存在性，阈下信道的容量大小，以及如何封闭 阈下信道都是值得研究的问题。同时，e i g a m a l 算法有很多变形方案，在e c c 基础 第6 章总结与展望 上，如何根据不同的应用环境选择不同的e i g a m a l 变形算法，也是需要进一步研究的 方向。 电子信封技术很好的解决了公钥体制加密速度慢，私钥体制中私钥分发困难的问 题，将公钥密码体系和私钥密码体系结合起来。作者提出了一种改进的公钥加密算法， 可以将其和a e s 算法相结合，实现电子信封技术。本文只给出了实现框架，具体的 实现还需要一定的工作。此外，在电子信封技术实现时还可以引入信息隐写技术，进 一步提高信息的安全性。 4 5 参考文献 1 李建华现代密码技术 m 北京：机械工业出版社，2 0 0 7 ：3 7 3 8 2 n e a lk o b li t z e 1 1i p t i cc u r v ec r y p t o s y s t e m s j ，m a t h e m a t i c so fc o m p u t a t i o n a m e r i c a nm a t h e m a t i c a ls o c i e t y ，1 9 8 7 ，4 8 ( 1 7 7 ) ：2 0 3 2 0 9 3 v s m i l l e r u s eo fe l l i p t i cc u r v e s i nc r y p t o g r a p h y c ，i nc r y p t o 8 5 ： p r o c e s s d i n g so fc r y p t o ，s p r i n g e r ，1 9 8 5 ：4 1 7 4 2 6 4 胡向东，魏琴芳应用密码学教程 m 北京：电子工业出版社，2 0 0 5 ：1 0 7 1 0 5 m r o b s h a w ，v y i n e l l i p t i cc u r v ec r y p t o s y s t e m s r a nr s al a b o r a t o r i e s t e c h n i c a ln o t e 1 9 9 7 6 卢开澄计算机密码学 m 北京：清华大学出版社，1 9 9 8 ：1 5 1 6 7 m e n e z e s a l f r e d j ，o k a m o t o t a t s u a k i ，v a n s t o n e s c o t t a r e d u c i n ge l l i p t i c c