（计算机应用技术专业论文）椭圆曲线公钥密码体系实现技术的研究.pdf

摘要 摘要 椭圆曲线密码系统( e c c ) 建立在椭圆曲线群上离散对数( e c d l p ) 的难解性这 一数学难题。与其他公钥密码系统相比，椭圆曲线密码系统除了安全性高外，还 具有计算负载小，密钥尺寸短，占用带宽少等优点。i e e e 、a n s i 、i s 0 、i e t f 、 s e c g 等组织已在椭圆曲线密码算法的标准化方面做了大量工作，分别形成了自 己的标准，椭圆曲线密码系统大有替代r s a 成为主流公钥密码体制的趋势。因此， 研究椭圆曲线公钥密码系统的实现技术具有很大的现实意义。 本文第二章首先介绍关于椭圆曲线密码系统中用到的群、环、域以及相关的 中国剩余定理等有关数学基础知识，然后详细阐述整个椭圆曲线密码系统，重点 介绍基于素数域和特征为2 的有限域上的椭圆曲线上点加、倍加、点乘等运算。 最后介绍安全椭圆曲线的攻击算法，阐述了攻击算法中用到的攻击技术理论，并 指出安全椭圆曲线参数选取时的注意事项和几种选取算法。 论文第三章一方面提出椭圆曲线密码算法中基于二进制表示的点乘算法的 半滑动窗口改进算法，通过进行基于素数域g f ( p ) 上的椭圆曲线密码算法中点乘 算法的实验，分析比较改进算法的效率。另一方面详细介绍基于椭圆曲线的 e c d s a 数字签名算法，并基于m i r a c l 库对其进行了基于素数域g f ( p ) 的实现。 论文第四章分析了单一认证的弱安全性，结合p k c s # 1l 标准和j 2 e e 平台的 e j b 组件技术，设计并实现了基于用户口令( p i n ) 认证和硬件u s b k e y 数字证书 身份认证的双重因素认证系统。最后讨论了椭圆曲线密码系统比基于r s a 的数字 签名系统的优越性，并分析了将椭圆曲线密码系统应用于双因素认证系统的可行 性。 论文第五章对本论文进行了总结和对以后工作的展望。 关键词：椭圆曲线；点乘算法；双因素认证； a b s t r a c t a b s t r a c t 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 ) i sb a s e do nt h em a t h e m a t i c a l p r o b l e m sw h i c h i sc a l l e de l l i p t i cc u r v ed i s c r e t el o g a r i t h m p r o b l e m ( e c d l p ) c o m p a r e dw i t ho t h e rp u b li c - k e yc r y p t o g r a p h i e s ，e c cn o to n l yh a s t h eh i g h e rs e c u r i t yb u ta l s oh a sl e s sc 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 ea n dn a r r o w e rb a n d w i d t h s o m eo r g a n i z a t i o n ss u c ha si e e e ，a n s i ， i s o ， i e t fs e c g ，h a v ed o n eal o to ft h es t a n d a r d i z a t i o nw o r ko na l g o r i t h mo f e l l i p t i cc u r v ec r y p t o s y s t e ma n de a c hh a sd e v e l o p e di t so w ns t a n d a r d t h e e x p e r t sb e l i e v et h a te c cw i l lb e c o m et h en e x tg e n e r a t i o np o p u l a rp u b l i c k e yc r y p t o g r a p h y t h e r e f o r e ，t h es t u d yo 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 e c h n o l o g yh a sg r e a tp r a c t i c a ls i g n i f i c a n c e i nt h ec h a p t e r2 ，w ef i r s ti n t r o d u c et h eb a c k g r o u n da n db a si c m a t h e m a t i cc o n c e p t sr e l a t e dt oe l l i p t i cc u r v ec r y p t o s y s t e ms u c ha sg r o u p ， r i n ga n df i e l d a n dt h ew h o l ee l l i p t i cc u r v ec r y p t o s y s t e mi sa n a l y z e di n d e t a i l t h e nt h eb a s i co p e r a t i o ns u c ha sp o i n ta d di sp r e s e n t e db a s e do n g f ( p ) o rg f ( 2 ”) n e x t ，t h ea l g o r i t h mo fa t t a c k st ot h ee c d l pi sa n a l y z e d ， a n dt h es e c u r i t yc r i t e r i o ni sp r o p o s e d t h es e c u r i t yc r i t e r i o nc a np r e v e n t t h ee l l i p t i cc u r v ef r o mb e i n ga t t a c k e d a tt h es a m et i m e ，s o m ea l g o r i t h m t og e n e r a t es e c u r ee l l i p t i cc u r v ei s l i s t e d i nt h ec h a p t e r3 ，t h es c a l a rm u l t i p l i c a t i o na l g o r i t h mf i r s ti s i n t r o d u c e d t h e nt h ei m p r o v e da l g o r i t h mo fs c a l a rm u l t i p l i c a t i o nc a l l e d h a l fs li d i n gw i n d o wa l g o r i t h mi s p r o p o s e d i ti sb a s e do nb i n a r y r e p r e s e n t a t i o no fm u l t i p l i e r n e x t ， w ec o l l e c tt h er e s u l td a t u mt h r o w s e v e r a le x p e r i m e n t sa n dr e p r e s e n tt h ee f f i c i e n c yw i t hc h a r tu s i n gm a t l a b a tl a s t ，t h ed i g i t a ls t a n d a r da l g o r i t h mo fe c ci si m p l e m e n t e d i ti sb a s e d o ng f ( p ) a n du s e dt h eii b r a r yo fm i r a c l i nc h a p t e r4 ，t h ei n s e c u r i t yo fs i n g l ep i ni sa n a l y z e d t h e nad u a l a b s t r a c t f a c t o ra u t h e n t i c a t i o ns y s t e mi sd e s i g n e d i tc o m b i n e sp u b l i ck e yc r y p t o s t a n d a r d # i i ( p k c s # 1 1 ) w i t he j bc o m p o n e n tt e c h n o l o g yo nt h eb a s i so fp i n a n du s b k e yd i g i t a lc e r t i f i c a t e f i n a l l y ，c o m p a r e dw i t hr s a ，t h ea d v a n t a g e o fe c ci sd i s c u s s e d t h e nw ea n a l y z et h ef e a s i b i l i t yt h a ta p p l y i n ge c co n t h ed u a lf a c t o ra u t h e n tic a tio ns y s t e m i nt h el a s tc h a p t e r ，t h ec o n c l u s i o na n dd e e p e rw o r ka r ep r e s e n t e d k e yw o r d s ：e lli p ti cc u r v ec r y p t o s y s t e m ( e c c ) ：s c a l a rm u lti p li c a ti o n a l g o r i t h m ；d u a lf a c t o ra u t h e n t i c a t i o n 厦门大学学位论文原创性声明 兹呈交的学位论文，是本人在导师指导下独立完成的研究成 果。本人在论文写作中参考的其他个人或集体的研究成果，均在 文中以明确方式标明。本人依法享有和承担由此论文产生的权利 和责任。 声明人( 签名) ：秀关 j 7 年5 明厂7 日 厦门大学学位论文著作权使用声明 本人完全了解厦门大学有关保留、使用学位论文的规定。厦门大 学有权保留并向国家主管部门或其指定机构送交论文的纸质版和电 子版，有权将学位论文用于非赢利目的的少量复制并允许论文进入学 校图书馆被查阅，有权将学位论文的内容编入有关数据库进行检索， 有权将学位论文的标题和摘要汇编出版。保密的学位论文在解密后适 用本规定。 本学位论文属于 1 、保密() ，在年解密后适用本授权书。 2 、不保密( u ( 请在以上相应括号内打“4 ”) 作者签名： 导师签名： 期：汐9 、) 年f 月f7 日 期：硼年阴7 日 第一章引言 第一章引言 随着计算机科学、通信和网络技术的迅速向前发展，信息化己成为社会发展 的趋势，人们也开始将一些现实行为在网络上实现，例如：网上银行，网上投票 等。然而由于网络本身的开放性和脆弱性，使得网络信息面临日益严重的威胁和 攻击，信息安全问题也日益严重和突出。伴随着社会的各个部门对网络安全性要 求的越来越高，特别是一些涉及机密性的机构和金融机构对更高安全性的需求， 使得信息安全的作用越来越明显。因此，设计好的密码系统也变得至关重要。 1 1 密码系统概述 一个密码系统的主角一般有三方，即发送方，接收方与攻击方( 密码分析者) ， 典型的密码系统如图1 - 1 所示。在发送方，首先将明文m 利用加密器e 及加密密 钥k e ，将明文加密成密文c = e ( m ，k e ) 。接着将c 利用公开信道送给接收方，接 收方收到密文c 后，利用解密器d 及解密密钥k d ，将c 解密成明文m = d ( c ，k d ) 。 发送方 接收方 公开信道 i 秘文 i c = e ( m ，k e ) ：明文 加密器解密器 l ( d e c r y p t o r ) r ( e n c r y p t o r ) 上 t ti i -i - 攻击方l 解密密钥 ： 加密密钥 ： k ek d 图1 - 1 典型密码系统方框图 一般而言，密码系统依其应用可对信息提供下列功能： ( 1 ) 秘密性：防止非法的接收者发现明文。 ( 2 ) 鉴别性：确定信息来源的合法性，也即此信息确实是由发送方所传送， 椭圆曲线公钥密码体系实现技术的研究 而非别人伪造。 ( 3 ) 完整性：确定信息没有被有意或无意的更改，及被部分取代、加入或删 除等等。 ( 4 ) 不可否认性：发送方在事后不可否认其传送过的信息。 现代密码学系统按密钥形式分为私钥密码系统和公钥密码系统。私钥密码系 统是收发双方加解密的过程所使用的密钥都相同的密码系统，又叫作对称密码 系统，传统的密码系统都属此类。公钥密码系统是指收发双方加解密的过程所 使用的密钥不相同的密码系统，又叫作非对称密码系统。 1 2 私钥密码系统概述 1 9 4 9 年s h a n n o n 发表的“保密系统的信息理论 为私钥密码系统建立了理 论基础，从此密码学成为- - v j 科学。私钥密码系统的优点在于密码算法简便，加 密速度快，保密度高；它的最大问题是密钥的分发和管理非常复杂、代价高昂。 比如对于具有n 个用户的网络，需要胛( 以一o 2 个密钥，在用户群不是很大的情 况下，对称加密系统是有效的。但是对于大型网络，当用户群很大，分布很广时， 密钥的分配和保存就成了大问题。另外，由于通信双方必须统一密钥，才能发送 保密的信息。如果发信者与收信人是素不相识的，就无法向对方发送秘密信息了。 常用的私钥密码算法有以下几种： ( 1 ) d e s 算法 d e s ( d a t ae n c r y p t i o ns t a n d a r d ) 是由i b m 公司研制的，美国国家标 准局公布的一种分组对称密码算法。自公布以来，它一直超越国界成为国际上商 用保密通信和计算机通信的最常用的加密算法。d e s 算法使用长度为5 6 比特的 密钥加密长度为6 4 比特的明文，获得长度为6 4 比特的密文。鉴于其密钥长度 比较短，随着硬件的发展，已经不再安全。 ( 2 ) 三重d e s 算法 三重d e s 算法用两个密钥对明文进行三次加密，假设两个密钥是k 1 和k 2 ， 加密步骤如下： 用密钥k l 进行d e s 加密。 用k 2 对步骤 的结果进行d e s 解密。 用步骤 的结果使用密钥k 1 进行d e s 加密。 2 第一章引言 利用三重d e s 相当于密钥长度加倍，安全性增强了，但是带来的问题是，加 密时间是原来的三倍。考虑到加密速度的问题，人们需要一种新的算法。于是， a e s 算法产生。 ( 3 ) a e s 算法 1 9 9 7 年美国国家标准技术研究所发起了征集a e s ( a d v a n c e de n c r y p t i o n s t a n d a r d ) 算法的活动，目的是为了确立一个非保密的、全球免费使用的分组密 码算法。a e s 的基本要求是比三重d e s 快而且安全级别有所提高，分组长度为1 2 8 比特，密钥长度为1 2 8 1 9 2 2 5 6 比特。a e s 作为d e s 算法的替代者将成为未来数 十年最重要的对称密码算法。2 0 0 1 年夏天，美国国家标准技术协会已经将j o a n d a e m o n 和v i n c e n tr i j m e n 提出的密码算法r i j n d a e l ( 算法名称采用了他们两人 姓的组合) 作为下一代对称密码算法的标准。r i j n d a e l 算法在设计时就考虑到 了3 个原则：抵抗已知的密码攻击方法；兼顾速度和代码大小以适应各种平台的 需求；设计思想简单。 1 3 公钥密码系统概述 1 9 7 6 年w h i t f i e l dd i f f i e 和m a r t i nh e l l m a n 发表了“n e wd i r e c t i o n si n c r y p t o g r a p h y ” 1 这篇划时代的文章，奠定了公钥密码系统的基础。公钥密码 系统是收发双方使用不同密钥的密码系统，又叫作非对称密码系统。该体制的最 大特点就是采用两个密钥将加密和解密能力分开：一个公开作为加密密钥；一个 为用户专用，作为解密密钥，通信双方无需事先交换密钥就可进行保密通信，系 统的保密性完全依赖于用来解密的秘密密钥。而要从公开的公钥或密文分析出明 文或者秘密钥，在计算上是不可行的。从而很好的克服了对称密码体制在实际应 用中遇到的困难，公钥密码体制的概念本身己被公认为密码学上的里程碑，是现 代密码学诞生的标志之一。 二十多年来公钥系统密码发展很快，不断有新的或修改的公钥密码系统提 出，但同时也有很多系统被攻破。比较成功的公钥密码系统主要有r s a ，背包， r a b i n ，e i g a m a l ，m c e li e c e ，椭圆曲线密码体制。目前被认为既安全又实用的公 钥体制根据它们所依据的数学难题可分为五类： ( 1 ) 基于大整数因式分解问题( i f p ) 的公钥密码体制，如：著名的r s a 体制和 r a b i n w i l l i a m s 体制； 椭圆曲线公钥密码体系实现技术的研究 ( 2 ) 基于有限域上离散对数问题( d l p ) 的公钥密码体制，如：d s a 、d i f f i e h e l l m a n 密钥交换方案、e i g a m a l 类加密体制和签名方案等； ( 3 ) 基于椭圆曲线离散对数问题( e c d l p ) 的公钥密码体制，如e c c ： ( 4 ) 基于双线性对d i f f i e h e l l m a n ( b d h p ) 问题。主要包括d b o h e n 和k f r a n k l i n 的i b e 方案、h e s s 的签名方案等一系列采用双线性对构造的签名方案； ( 5 ) 基于g a p 群在此群中d d h p ( d e c i s i o nd i f i e - h e l l m a np r o b l e m ) 问题可解，而 c d h p ( c o m p u t a t i o n a ld i f f i e h e l l m a np r o b l e m ) 问题不可解。包括一系列用双 线性对构造的签名方案。 最后这两个问题是近年椭圆曲线公钥密码发展的结果，而且其快速实现、安 全性以及今后的进一步应用都与椭圆曲线上的运算息息相关。目前应用比较广泛 的公钥密码体制主要为前两类。然而，随着计算机运算速度的迅速提高和网络分 布式计算能力的日益强大，经典如r s a ，d i f f i e - h e l l m a n 等两类的公钥密码体制 在密钥长度为5 1 2 b i t 下己经越来越不安全；在不出现新的密码系统的前提下，唯 一的解决办法只有增加密钥长度，而增加密钥长度虽然能增强安全性，但加、解 密效率会越来越低，根本满足不了现代通信与网络的要求，同时密钥的增长对系 统的要求也越来越高。 1 4 椭圆曲线密码体系 1 4 1 椭圆曲线密码体系的优势 椭圆曲线应用到密码学上最早是由v i c t o rm i l l e r 2 和n e a lk o b l i t z 3 在 1 9 8 5 年分别独立提出的。它是目前已知的公钥体制中，对每一比特所提供加密强 度最高的一种体制。与3 节中采用前两类数学难题为基础的密码体制相比，椭圆 曲线密码体制具有以下优点： ( 1 ) 椭圆曲线密码相对安全性更高 椭圆曲线密码体制具有最强的单比特安全性。每一比特椭圆曲线密码体制的 密钥至少相当于5 比特长的r s a 密钥的安全性如表卜1 ，并且这种比例关系随密钥 长度的增加呈上升趋势。可见，在同等条件下，安全要求越高，其“短密钥”的 优势越明显，换句话说，在相同密钥长度的条件下，e c c 比r s a 的安全性要高。目 前，1 6 0 b i t 的密钥长度便足以保证e c c 的安全性。 4 第一章引言 表1 - 1e c c ，r s a ，d s a 算法的性能比较 g s a d s a 密钥尺寸( b i t )5 1 2 7 6 81 0 2 42 0 4 8 3 0 7 27 82 1 0 e c c 密钥尺寸( b i t )1 1 3 21 6 02 2 0 2 5 63 8 46 0 0 r s a f c c 密钥尺寸近似比率5 ：i 6 ：1 7 ：11 0 11 2 ：l2 0 ：13 5 ：1 表注；本表是同等硬软件环境下的测试数据 ( 2 ) 椭圆曲线密码运算量小，处理速度快 在一定的相同的计算资源条件下，虽然在r s a 中可以通过选取较小的公钥( 可 以d x 至1 3 ) 的方法提高公钥处理速度，即提高加密和签名验证的速度，使其在加密 和签名验证速度上与e c c 有可比性，但在私钥的处理速度上( 解密和签名) ，e c c 远比r s a ，d s a 快得多。因此e c c 总的速度比r s a ，o s h 要快得多。同时e c c 系统的密 钥生成速度比r s a 快百倍以上。因此在相同条件下，e c c 有更高的加密性能。 ( 3 ) 椭圆曲线密码存储空间占用小 e c c 体制的密钥尺寸和系统参数较r s a 体制和e 1 g a m a l 类体制要小得多。表1 数据表明1 6 0 位e c c 与1 0 2 4 位r s a ，d s a 具有相同的安全强度，2 2 0 位e c c 则与2 0 4 8 位r s a ，d s a 具有相同的安全强度，这意味着它所占的存储空间要小。这对于密码 算法在资源受限制的环境( 比如智能卡) 的应用具有特别重要的意义。 ( 4 ) 通信带宽要求低 当对长消息进行加解密时，三类密码系统有相同的带宽要求，但应用于短消 息时e c c 的带宽要求却低得多。而公钥系统多用于短消息，如密钥交换和数字签 名，所以e c c 的这一特点使得其在无线网络领域具有广泛的应用前景。 ( 5 ) 灵活性好 有限域g f ( p ) 一定的情况下，其上的循环群也就定了；但g f ( p ) 上的椭圆 曲线可以通过改变曲线参数，得到不同的曲线，形成不同的循环群。因此，椭圆 曲线具有丰富的群结构和多选择性。 由于椭圆曲线以上的优点，尤其是其“短密钥的特点，可以带来更高的安 全性，同时很好的解决了前两类体制在应用上的难题，椭圆曲线密码体制越来越 成为研究工作者关注和争相研究的热点，大有取代r s a 等经典公钥体制之势。当 然，椭圆曲线也存在一些缺点，例如椭圆曲线的群运算比较复杂，不如r s a 算法 椭圆血线公钥密码体系实现技术的研究 那么简洁，r s a 中的运算只涉及整数的模运算，但椭圆曲线密码体制会涉及有限 域中的乘法和求逆运算：在同样的安全性下，与r s a 相比椭圆曲线密码体制在速 度上并不占明显的优势。而且在对椭圆曲线的研究及各种基于椭圆曲线加密、签 名方案提出的同时，针对椭圆曲线的攻击也越来越多，尤其是针对一些特殊椭圆 曲线的攻击上已经有了很有效的方法。但是对椭圆曲线的研究很有前景，许多组 织也在不停的做这方面的研究工作。 1 4 2 椭圆曲线密码体系的标准 椭圆曲线的安全性和优势得到了业界的广泛应用，& n s i 、i e e e 、i s o 、i e t f 、 s e c g 等组织已在椭圆曲线密码算法的标准化方面做了大量工作。1 9 9 9 年2 月椭圆 曲线数字签名算法e c d s a 被a n s i 确定为数字签名标准a n s ix 9 6 2 - 1 9 9 8 ，椭圆算法 d i f 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 旺1 3 6 3 2 0 0 0 ，同期，n i s t 确定其为联邦数字签名标准f i p s l 8 6 - 2 。s e c g 也为 e c c s u 定工业标准s e c l 和e c c 推荐的参数选择的标准s e c 2 。因此，e c c 比较核心的 标准包括a n s ix 9 6 2 ，a n s ix9 6 3 ，f i p s1 8 6 - 2 ，i e e ep 1 3 6 3 ，i e e ep 1 3 6 3 a ， i s o i e c1 4 8 8 8 3 ，。如表卜2 所示： 表1 - 2 基于椭圆曲线的密码机制的标准及草案 标准年份名称参考文献 a n s ix 9 。6 21 9 9 9 椭圆曲线数字签名算法 4 a n s ix 9 6 32 0 0 1 密钥协商和密钥传输 5 f i p s1 8 6 - 22 0 0 0 数字签名标准( d s s ) 6 i e e e1 3 6 3 - 2 0 0 02 0 0 0 公钥密码规范标准 7 i e e ep 1 3 6 3 a ( 草案)补充l ：附加的技术 8 i s o i e c1 5 9 4 6 一l2 0 0 2 基于椭圆曲线的技术部分一一部分一：概述 9 i s o i e c1 5 9 4 6 22 0 0 2 部分二：数字签名 1 0 i s o i e c1 5 9 4 6 32 0 0 2部分三：密钥建立 1 1 i s o i e c1 5 9 4 6 4 ( 草案)部分四：提供数据恢复的数字签名 1 2 i s o i e c1 8 0 3 3 2 ( 草案)加密算法一一部分二：公钥密码 1 3 s e c12 0 0 0 椭圆陆线密码 1 4 6 第一章引言 a n s ix 9 6 2 标准的e c d s a 用于财政金融行业，要求摘要函数使用s h a l ，椭圆 曲线参数 2 1 鲫，并且使用a n s i 所认可的伪随机数发生器等。 a n s ix 9 6 3 草案的密钥协商和密钥分发方案也用于财政金融行业，特别的， 它列出了基于e c i e s ，e c d h 、和e c m q v 的各种密码方案。像a n s ix 9 6 2 ，它也要求 h a s h 使用s h a 一1 ，椭圆曲线参数厅 2 旧，并且使用a n s i 所认可的伪随机数发生器 笙 寸o f i p s1 8 6 2 标准中的三个签名方案用于美国政府，a n s ix 9 6 2 的e c d s a 也是 其中之一。 i e e ep 1 3 6 3 标准的密码方案有基于大整数因子分解问题的，有基于传统离散 对数问题的，也有基于e c d l p 。基于e c c 的e c d s a ，e c d h 、和e c m q v 在i e e e p 1 3 6 3 分别称为e c s s a ，e c k a s - d h i ，e c k a s - m w 。 i e e ep 1 3 6 3 a 草案作为i e e e p1 3 6 3 的补充，包括e c i e s 。 i s o i e c1 5 9 4 6 草案采用基于e c c 的密码技术。i s o i e c1 5 9 4 6 - 2 指定了签名 方案，包括e c d s a , i s o i e c1 5 9 4 6 3 指定了密钥建立方案，包括e c d h ，e c m q v d 。 s e c g ( t h es t a n d a r df o re f f i c i e n tc r y p t o g r a p h yg r o u p ) 是由加拿大 c e r t c o m 公司( r s a 一5 1 2 破解的发起者) 发起的，包括v e r i s i g n ，m o t o r o l a 。s u n 等，致力于提供可互操作的安全解决方案的联盟。s e c l 和s e c 2 是s e c g 开发的e c c 标准，和绝大多数核心的e c c 标准兼容。 1 5 本文研究目标与内容 1 5 1 研究目标 1 对椭圆曲线( e c c ) 公钥密码体系的实现技术进行系统地分析，完成基于 素数域g f ( p ) 和特征为2 的域g f ( 2 ”) 上的椭圆曲线的剖析。 2 提出椭圆曲线密码算法中基于二进制表示的点乘算法的改进算法，并进 行基于素数域g f ( p ) 上的椭圆曲线密码算法中点乘算法的实验。 3 分析实验结果，并对改进算法与原算法进行比较。 4 分析设计出双因素认证系统，分析e c c 加密系统应用于可行性。 椭圆曲线公钥密码体系实现技术的研究 1 5 2 研究内容 1 研究椭圆曲线( e c c ) 公钥密码算法中点乘算法，提出改进点乘算法。 2 基于素数域凹( p ) ，实现椭圆曲线点乘算法以及改进算法，并画出图表， 分析算法的各种效率。 3 实验完成基于椭圆曲线素数域g f ( p ) 上n i s t 建议的5 中标准曲线的d s a 密码算法，并将改进的点乘算法用于其中。 4 设计双因素认证系统，完成基于j 2 e e 平台的双因素认证系统的软件实 现，并分析了e c c 加密系统地可行性。 8 第二章椭圆曲线密码体系的数学理论与概述 第二章椭圆曲线密码体系的数学理论与概述 椭圆曲线密码体系，即基于椭圆曲线离散对数问题的各种公钥密码体制，是 利用有限域上的椭圆曲线有限群代替基于离散对数问题的密码体制中的有限循 环群而得到的一类新型密码体制，是已有的各种密码编码方案在椭圆曲线上的实 现。 由于椭圆曲线领域所包含的内容非常庞杂，而现行的椭圆曲线密码体制只用 到了椭圆曲线的少数的几个特征，所以本章首先将着重介绍与椭圆曲线公开密钥 密码体制相关的椭圆曲线数学理论基础，例如：群、环、域等。 其次，详细阐述椭圆曲线相关的定义，并对椭圆曲线的结构特征做了论述。 2 6 和2 7 节着重介绍了素数域g f ( p ) 和特征为2 的有限域g f ( 2 ”) 上的椭圆曲线 及其基本运算，在加法定义下，椭圆曲线上的所有点可构成一个a b e l 群。 最后，介绍了椭圆曲线的安全性问题，介绍了最常用的攻击方法，并且简单 介绍了安全的椭圆曲线生成的几种算法。本部分不作为本文的重点，详细的介绍 请参考本章列出的参考文献。 2 1 群( g r o u p s ) 群是抽象代数中最早的而且是最基本的一个代数系统，它也是现代数学中一 个极其重要的概念。它是研究椭圆曲线密码系统的基础，本节以下介绍了椭圆曲 线密码系统中所使用的群的概念和基本性质。 定义2 1 设g 是一个非空集合，若在g 上定义一个二元运算“+ 满足下列 条件，称( g ，+ ) 是一个群。 ( 1 ) 封闭性：对任何，有a ，b g ，则a + b g 。 ( 2 ) 结合律：对任何a ，b ，c g ，有( 口+ 功+ c = 口+ ( 6 + c ) 。 ( 3 ) 单位元：存在唯一的元素e g ，使得对任何a g ，有a + e = e + a = a 。 称e 为g 的单位元，有时用1 表示。 ( 4 ) 对任何a g ，存在逆元a 一，使得a + a 一= a 。1 + 口= e 成立。 9 椭圆曲线公钥密码体系实现技术的研究 只满足( 1 ) ( 2 ) 两个条件，称( g ，+ ) 是一个半群。 定义2 2 若群g 还满足对任意a 9 b g ，有a + b = b + a ，则称g 为可交换群 或者阿贝尔( a b e lg r o u p s ) 群。 定义2 3 群g 中的元素个数称为群g 的阶( o r d e r ) ，记作撑g 。若群g 的阶 为有限数，即群g 中的元素个数igi 有限，则称g 为有限群；反之，称为无限群。 任意群( g ，+ ) ，a g ，元素a 的乘幕定义为0 ”= a o a 一口( n 个a 相乘) 。其 中n 为正整数。并规定：口o = l ( 1 为单位元) 。显然有口“口”= a 斛”。 群具有以下性质： ( 1 ) 群中的单位元是唯一的； ( 2 ) 消去律成立，即对任意的o ，b ，c g ，如果a b = a o c ，则b - - c ：如果b 口= c 口 则b = c ； ( 3 ) 群中的每一个元素其逆元是唯一的。 2 2 环( r in g ) 、域( f ieid ) 定义2 4 设g 是一个非空集合，若在g 上定义两个二元运算，一个是加法 运算“+ ，一个是乘法运算“ ，则满足以下条件的代数结构( g ，+ ，) ，称为环： ( 1 ) g 上元素关于加法“+ ，使( g ，+ ) 构成阿贝尔( a b e l ) 群。 ( 2 ) g 上元素关于乘法“ ，使( g ，) 构成半群。 ( 3 ) g 上乘法运算对于加法运算满足分配律。即：对于任意的a 9 b ，c g ， 有：( 口+ 6 ) c = 口c + b c ，口( 6 + c ) = 口b + a c 。 若( g ，) 是交换半群，则称g 为交换环；若( g ，) 有单位元，则称g 为含单位 元的环。 定义2 5 设g 是一个非空集合，若在g 上定义两个二元运算，一个是加法运 算“+ ，一个是乘法运算“9 9 9 则满足以下条件的代数结构( g ，+ ，) ，称为域： ( 1 ) g 上元素关于加法“+ ，使( g ，+ ) 构成阿贝尔( a b e l ) 群，零元素不 1 0 第二章椭圆曲线密码体系的数学理论与概述 妨用d 表不。 ( 2 ) g d 上( 即g 中非零元素) 关于乘法“，使( g ，) 构成阿贝尔( a b e l ) 群。 ( 3 ) g 上乘法运算对于加法运算满足分配律。即：对于任意的口，b ，c g ， 有：( 口+ 6 ) c = q o c + 6 c ，口( 6 + c ) = a b + a c 。 定义2 6 域中元素的个数p 称为域的阶。如果一个域的阶p 是有限的，此域便称 为有限域或伽罗瓦域g f ( p ) 。 定义2 8 令，是f 非零元素的集合，即f = f 0 。f 是阶为r = p ”一l 关于 乘法的循环群。若该群含有有限元素：1 ，a ，口2 ，a ”1 ， 口= l 则口称为域f 的本 原元素。 2 2 1 素数域及其运算 设p 为素数，则集合 o ，i ，2 ，p l 在铷加法和铷乘法下是阶为p 的域。由于 尺是由素数p 构成的域，所以通常也称尺为素数域，并卯( p ) 以表示。如= 7 ，便 得到素数域g f ( 7 ) 。 在g f ( p ) 中的运算定义如下： 加法：枷加法，口，6 g f ( p ) ，a + b = r ，r 是a + b 被p 除所得余数，e o ，p 一1 】。 乘法：模p 乘法，口 6 g f ( p ) ，a b = s ，s 是口6 被矽除所得余数，se o ，p l 】。 求逆：口若是卯( p ) 中的非零元，口的逆元就是g f ( p ) 中的唯一元素c ，且满足 a o c = 1 o 2 2 2 特征为2 的有限域g f ( 2 ”) 及其运算 定义2 7 一个多项式在f 域上，若不能表示为两个低次幕的多项式之积，则 称该多项式是f 域上的不可化约多项式。 多项式p ( 石) = 嘞+ a l x + a 2 x 2 + + a k x 七，口jef ，i = 0 ，1 ，k 如果f 的元素个 数为p ，则不同的多项式p ( z ) 个数为x “，即p ( 工) 和”1 位p 进制数鲰口七一l a 2 a l 口o 椭圆曲线公钥密码体系实现技术的研究 一一对应，其中口fe f ，扛0 ，l ，p 。 例1 ：当f = g f ( 2 ) = o ，1 时，设 ( 工) = o ，p i ( 力= l ，风i o ( x ) = x ，p o i i ( 功= z + l ， p l o o ( x ) - - - - x 2 ，a o l ( x ) = 工2 + l ，p l l o ( 功- - x 2 + 工，a l l ( x ) - - - - x 2 + x + l 很显然，p ( 力与二进制数i 一一对应。这些多项式的乘积可得次方超过2 的 多项式。若引进在舒( 2 ) 上的不可化约多项式厂o ) - x 3 + x + l 作为模约多