（机械电子工程专业论文）基于椭圆曲线的ca认证系统研究及应用.pdf

d i s s e r t a t i o ns u b m i t t e dt oz h e j i a n gu n i v e r s i 哆o ft e c f o rt h ed e g r e eo fm a s t e r r e s e a r c ha n d a p p l i c a t i o no fc a a u t h e n t i c a t i o n b a s e do ne u i p t i cc u r v e c a n d i d a t e ：s h e nt i a n g u o a d v i s o r ：p r o f e s s o rx u f a n g c o l l e g eo fm e c h a n i c a le n g i n e e r i n g z h e j i a n gu n i v e r s i 毋o ft e c h n o l o g y m a y2 0 1 0 浙江工业大学 学位论文原创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行研究工作 所取得的研究成果。除文中已经加以标注引用的内容外，本论文不包含其他个人或 集体己经发表或撰写过的研究成果，也不含为获得浙江工业大学或其它教育机构的 学位证书而使用过的材料。对本文的研究作出重要贡献的个人和集体，均己在文中 以明确方式标明。本人承担本声明的法律责任。 作者签名：c 吕元f 弱，日期珈f 哞厂月雩f 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本 人授权浙江工业大学可以将本学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 l 、保密3 ，在年解密后适用本授权书。 2 、不保密 ( 请在以上相应方框内打“”) 作者签名：、：乜丕l 弱 导师签名： 亳荔 日期矽，峰 日期：矽( d 年 j 月= ；日 厂月ji 日 浙江工业大学硕士学位论文 基于椭圆曲线的c a 认证系统研究及应用 摘要 p k i 是目前在应用层保障网络信息安全的最佳机制，但随着分步计算的发展以及对数 论研究的深入，p k i 广泛使用的r s a 公钥密码体制面临着前所未有的挑战。针对r s a 存 在的安全隐患，论文采用安全性与效率更高的e c c 作为p k i 密码技术的公钥密码体制， 并建立起基于p k i 密码技术的c a 认证系统，以解决在应用过程中交互双方身份的安全认 证、信息传输的完整性、机密性以及操作的不可否认性。论文的主要研究工作如下： 1 研究了p k i 体系和构建c a 认证系统所需的p k i 密码技术，从系统的高效性和安 全性角度出发，选择e c c 作为c a 认证系统的公钥算法，并对e c c 进行了深入的分析， 为实现p k i 密码技术奠定基础； 2 利用以e c c 为公钥算法基础的p 密码技术进行c a 认证系统设计与关键技术的 实现。首先基于c a 的功能需求和系统目标，构建了c a 认证系统的总体框架；然后在此 基础上运用p k i 技术重点设计了各模块在客户端和服务端物理组件中的处理过程；最后在 c a 认证系统设计的基础之上，利用开发工具实现了相关模块在物理组件中的关键技术。 3 对c a 认证系统及关键密码技术进行测试与分析。首先测试分析了构建c a 认证系 统所需的基于椭圆曲线的p 密码技术；然后对c a 认证系统进行了测试，证明基于椭圆 曲线的c a 系统比基于r s a 的c a 系统具有更高的效率和安全性；最后针对电子邮票系统 的网络安全需求，将c a 认证系统应用于电子邮票系统，实现了通信双方在交互过程中信 息安全传输。 关键词：公钥基础设施，椭圆曲线密码体制，c a 认证，e c c 数字证书，电子邮票 浙江工业大学硕士学位论文 r e s e a r c ha n da p p l i c a t i o no fc aa u t h e n t i c a t i o ns y s t e m b a s e do ne u i p t i cc u r v e a b s t r a c t p r e s e n t l y ，p k ii st h eb e s tm e c h a m s mt op r o t e c tn e 帆o r ki n f o n i l a t i o na tt l l e 印p l i c a t i o nl a y e r h o w e v e r ，w i 也t h ed e v e l o p m e n to fn l e 觚c t i o i l a ls t e pm e t h o da n di l l d e p 也s t u d yo fn 砌b e rm e o r y r s ap u b k e yc r y p t o s y s t e m ，w h i c hi sw i d e l yu s e db yp k i ，i sf a c i n gu n p r e c e d e n t e dc h a l l e n g e s f o rt h er s a s e c 嘶够r i s k s ，p a p e ra d o p t e de c c ，w h i c hi sm o r es e c 谢t ) ，a n de 伍c i e m ，a sm ep k i c r y p t o g r a p h j ct e c h i l i q u e s p u b - k e yc r y p t o s y s t e m ，t h e nb u i l tc a a u m e n t i c a t i o ns y s t e mb a s e do n p k ic 巧p t o 卿h i ct e c h n i q u e s ，t os o l v et l l ei d e n t i t ) ，a u t h e n t i c a t i o no f 铆oc o m m u n i c a t i o ns i d e si i l t h ei n t e r a c t i o np r o c e s s ，t 1 1 em e 酊够a n dc o n f i d e n t i a l 时o fi n f o m a t i o n 仃a 1 1 s m i s s i o 玛a 1 1 dt h e n o n r e p u d i a t i o no fo p e r a t i o n t h em a i nw o r k i nt h ep 印e ra sf o l l o w s ： 1 p a p e rs t u d i e dt l l ep k is y s t e ma n dp k jc t y p t o g r a p h i ct e c h n i q u e sw h i c ha r en e e d e dt o b 、l i l dc aa u t l l e n t i c a t i o ns y s t e m f r o mt 1 1 es y s t e m se 伍c i e n c ya n ds a f 嘶p o i n to fv i e w ，c h o s e n e c ca st l l ep u b - k e ya l g o r i t l l i no fc aa u ：n l e m i c a t i o ns y s t e m ，t 1 1 r o u 曲i 1 1 d e p t l la n a y s i so fe c c ， l a ym ef o u i l 妇i o nf o rm ea c m e v e m e n to f l h ep k ic 巧p t o 卿k ct e c h n i q u e s 2 t h o u 曲p k ic 聊t o g r a p m ct e c 王l i l i q u e s ，d l j c hb a s e do ne c cp u b - k e yc 聊t o s y s t e m ， d e s i g n e da n da c m e v e dc a a m h e n t i c a t i o ns y s t e m f i r s t l y ，o nt l l eb a s eo f 凡n c t i o n a lr e q u n m e 鹏 a n ds y s t e ma i m s ，p a p e rb u i l tt 1 1 eo v e r a l l 行锄e w o r ko fc aa u _ 1 1 1 e n t i c a t i o ns y s t e m s e c o n d l y ，o n t l l i sb a s i s ，p a p e ff o c u s e do nt h ed e s i 鳃o fc e n i f i c a t er e q u e s t i o n sp r o c e s si nc l i e n ts i d ea n ds e r v e r s i d e f 妇1 1y ，b a s e do nt 1 1 ed e s i g no fc aa u t h e n t i c a t i o ns y s t e m ，p a p e ra r c h i e v e dt h er e l e v a n t m o d u l e sk e yt e c m q u e si np h y s i c a lc o m p o n e n t sw i 血d e v e l o p m e mt o o l s 3 t e s t e da n da n a l y s i so f 也ec aa u t h e n t i c a t i o ns y s t e ma n dk e yt e c l l i l i q u e s f i r s t l y t e s t e d a n da n a l y s i so ft h ep k ic 巧p t o g r 印1 1 i ct e c h l l i q u e sw h i c hb a s e do ne l l i 砸cc u n ，ec 帅t o 卿h ya 1 1 d r e q u i r e db yc aa u t h e n t i c a t i o ns y s t e m s e c o n d l y ，t e s t e dc aa u m e n t i c a t i o ns y s t e m ，r e s u l t ss h o w 吐l a tt h ec a s y s t e mh a sl l i 曲e re 衔c i e n c ya j l ds e c 嘶哆w h i c hw e r eb a s e do ne l l i p t i cc u et h a i l b a s e do nr s a f i n a l l y t 0t l l en e t w o r ks e c u r i 够n e e d so fe s t 锄ps y s t e m 印p l i e dm ec a a u t l l e n t i c a t i o ns y s t e mt ot l l ee - - s t a m ps y s t e m ，i th a sa c h j e v e ds e c u r ea u t h e n t i c a t i o no fi d e m i t ) ， a i l ds e c u r et 啪s m i s s i o no fi 1 1 f o n n a t i o ni n 也ei n t e r a c t i o np r o c e s so ft 、v oc o m m u i l i c a t i o ns i d e s 。 浙江工业大学硕士学位论文 一 k e yw o r d s ：p u b l i ck e yi 1 1 触s 咖c t u r e ， e l l i p t i cc u ec u p t o g r a p h y ，c ac e n i f i c a t i o n ， e c cd i g i t a lc e r t i f i c a t e ， e l e c n o n i cs t 锄p 浙江工业大学硕士学位论文 目录 摘 要i a b s t r a c t i i 目录 第l 章 1 1 1 2 1 3 第2 章 2 1 2 2 2 3 2 4 2 5 第3 章 3 1 3 2 3 3 3 4 3 5 3 6 i 、r 绪论1 课题研究的背景和意义一1 p k i c a 国内外研究现状2 1 2 1 p k l 技术研究现状3 1 2 2 椭圆曲线密码体制研究现状一5 课题研究内容7 公钥基础设施( p k i ) 体系。9 j ；i 言9jj 口，7 p 基本组件与服务1 0 2 。2 1p k i 物理组件1o 2 2 2 p k i 核心服务1 1 p k l 密码技术1 2 2 3 1对称密钥体制1 3 2 3 2 非对称密钥体制1 4 2 3 3 散列函数一j 1 5 2 3 4 数字签名15 2 3 5数字信封1 6 椭圆曲线密码体制1 7 2 4 1 椭圆曲线点的群运算2 0 2 4 2椭圆曲线域参数的选择2 2 2 4 3 椭圆曲线公钥密码算法2 3 本章小结2 5 基于e c c 的c a 认证系统设计2 7 弓l 言2 77 l 苗：， 系统需求与功能分析2 8 设计目标2 9 总体框架3 0 系统功能模块设计3 0 3 5 1证书申请、发布3 0 3 5 2 证书更新3 1 3 5 3 证书撤销3 2 3 5 4 证书查询3 2 系统物理组件设计3 3 i v 浙江工业大学硕士学位论文 3 7 第4 章 4 1 4 2 4 3 4 4 4 5 第5 章 5 1 5 2 5 3 5 4 第6 章 6 1 6 2 6 3 第7 章 3 6 1 客户端组件设计。3 3 3 6 2 服务端组件设计3 5 3 6 2 1 注册中心3 5 3 6 2 2 认证中心3 7 3 6 2 3p k i 数字证书库4 2 本章小结4 3 基于e c c 的c a 认证系统关键技术实现4 4 弓l 言z 轴4 系统运行环境与开发工具“ 客户端关键技术实现4 5 4 3 1 e c c 加密解密密钥对私钥备份4 5 4 3 2e c c 数字证书申请4 9 服务端关键技术实现5 3 4 4 1认证中心5 3 4 4 1 1 e c c 数字根证书制作5 5 4 4 1 2 e c c 加密解密密钥对私钥恢复5 7 4 4 1 3e c c 数字证书撤销和签发c r l 5 8 4 4 1 4e c c 数字证书验证6 l 4 4 2 注册中心6 3 本章小结6 4 系统测试与分析“ 弓l 言6 6ji 口u u 基于椭圆曲线的密码技术测试分析6 6 5 2 1椭圆曲线数字签名算法6 6 5 2 2 椭圆曲线e l g a r n a l 加密方案6 7 基于椭圆曲线的c a 认证系统测试分析，6 8 5 3 1 系统功能测试6 8 5 3 2 c a 认证系统安全性和效率分析。7 2 本章小结7 3 c a 认证系统在电子邮票系统中的应用7 4 j ；i 言7 4 基于c a 的电子邮票系统7 4 6 2 1电子邮票7 4 6 2 2 基于c a 的电子邮票系统模型。7 5 6 2 3 双向认证7 6 6 2 4 信息传送7 6 本章小结7 8 总结与展望7 9 7 1 全文总结7 9 7 2 后续研究与展望8 0 参考文献。8 1 致谢8 4 攻读学位期间发表的论文。川 v 8 5 浙江工业大学硕士学位论文 第1 章绪论 1 1 课题研究的背景和意义 伴随着网络技术与信息技术在我国的迅速普及和发展，各种网络应用系统得到了快速 的发展，诸如电子商务、电子政务、网上证券、网上银行等，将传统的商务活动、办公模 式移到网络化、信息化的环境中来。但由于互联网的开放性以及各个网络应用系统的建设 缺乏统一的标准，使互联网在带给人们便利之余，也带来了网络信息安全这样一个备受傲 视会关注的问题。针对这一网络安全需求，一个安全可靠的解决方案不仅需要在基于o s i 或t c p p 网络协议的网络层上安装防火墙、路由器、入侵检测i d s ，同时也需要在应用层 上采用相关安全技术用于实现网络实体身份的认证，交付信息的完整性和交易各方对各自 交易的不可抵赖性等要求，以满足对象间信息的安全、自由传输。在应用层上，目前最好 的防范措施就是建立以数字证书为认证基础的安全机制。 公钥基础设施( p u b l i ck e yi n 行a s t m c t u r e 【1 3 】，简称p k i ) 以公钥密码体制( 亦称非对称 密码体制) 为基础，并以数字证书的形式管理实体的公钥，每个公钥都与相应的实体相对应， 即将实体的信息与公钥以数字证书为载体进行捆绑。完成这一工作的便是p i 叫摘耍值l 鬣酾簧翊 消息明文 一。下 比较 发送方 0 数字签名 + 私钥轴，4 、 数字签名 k 弋取 鬣摘要谴覆 u 、一 f 发送方 数字签名卜彳一公钥硒 j 一地龄篓孔一j 发送 i 一墅鞭墼 图2 5 数字签名生成与验证过程 具体实现过程如下： 1 ) 采用散列函数对消息明文进行计算，产生摘要值。 浙江工业大学硕士学位论文 2 ) 用发送方的私钥饰v 对上一步产生的摘要值进行加密处理，生成数字签名。 3 ) 将消息明文与数字签名结合起来并发送给接收方。 4 ) 接收方首先将消息明文与数字签名分离，然后用相同的h a s h 算法对分离出来的消 息明文进行计算产生出新的摘要值，同时接收方再用发送方所公布的公钥郧b 进行 分离出来的数字签名进行解密得到发送方计算出来的摘要值。 5 ) 发送方将解密得到的摘要值( 即发送方计算出来的摘要值) 与自己采用h a s h 算法得 到的新摘要值进行比较。如果两者相等，则说明消息明文没有受外界的干扰与破坏， 即保证了信息的完整性。 2 3 5 数字信封 采用对称密钥体制算法具有加密、解密效率高，且运行占用资源少等特点；而非对称 密钥体制算法在密钥管理与分发上具有特点。故一般不直接使用非对称密钥体制算法对明 文信息进行加密，只是用其加密对称密钥体制算法的密钥，即所谓的数字信封( d i g i t a l e n v e l o p e ) 技术。因此数字信封是一种以对称密钥体制与非对称密钥体制为基础，可用于数 据保密性服务的技术。典型的数字信封制作如图2 6 所示。 生成数字信封分解数字信封 - 。- - - ，- - l - - - - 图2 6 数字信封生成与分解过程 具体实现过程如下： 1 ) 对称密钥体制算法利用随机产生的会话密钥k 对消息明文加密，生成消息密文。 2 ) 发送方用接收方公布的公钥加密对称加密算法的会话密钥k ，并生成密钥密文。 3 1 将消息密文与密钥密文一起发往接收方。 1 6 浙江工业大学硕士学位论文 4 ) 接收方首先将消息密文与密钥密文分离，接着用自身的私钥解密密钥密文得到会话 密钥k ：然后利用解密出来的会话密钥解密消息密文，最后得到消息明文。 2 4 椭圆曲线密码体制 椭圆曲线密码体制是基于椭圆曲线离散对数问题( 详见2 4 4 节) 并利用有限域上的椭圆 曲线有限群替代离散对数问题的密码体制中的有限循环群而得到的一类新型密码体制。 椭圆曲线的研究来源于椭圆积分咚，其中例是x 的三次或四次多项式。而该 。e ( x ) 类积分无法用初等函数来表示，为此需引进椭圆函数。 定义2 1椭圆曲线指的是在域，上由以下韦尔斯特拉斯( w e i e r s t r a s s ) 方程所确立的 非奇异平面曲线： ： 少2 + 口砂+ 弘y = x 3 + 口：x 2 + 口。x + 瓯( 2 1 ) 这是椭圆曲线的一个仿射方程，其中口i ，口：，仍，仉，缘尸，且0 ，是的判别式， 曲线e 上所有的点与一个曲线上唯一的无穷远点共同构成了点集，而点集与定义在 其上面的运算共同构成了一个域，该域正是椭圆曲线密码体制的算法基础。而域是对常见 的数系( 如复数c 、有理数q 、实数尺) 及其基本特征的抽象，由一个集合o 和两种运算( 加 法和乘法) 共同组成。若集合o 是有限集合，则称域为有限域。所以一个有限域，具有两 种运算，即加法与乘法。 由于在实数域上的椭圆曲线密码群中的运算速度非常慢，并且准确度也不够。因此椭 圆曲线运算是基于有限域运算的，而加密椭圆曲线所在的有限域主要分为素数域和二进制 域。 式( 2 1 ) 介绍的是椭圆曲线的仿射方程，下面将介绍椭圆曲线的影射方程，设z o ， 矿v 令x = 鲁，夕= 专代入方程( 2 - 1 ) 得到椭圆曲线在影射平面上的影射方程： 】，2 z + 凸册z + 口，泫2 = x 3 + 口：2 z + 口4 爿z ：+ 瓯z 3 ( 2 - 2 ) 令f ( x ，】，z ) = y 2 z + 口，爿】_ z + m 】z 2 一x 3 一口：x ：z 一仉勉2 一仉z 3 ( 2 3 ) 对f ( 彳，】，z ) 求各变量的偏导数得当方程组： 1 7 浙江工业大学硕士学位论文 堡：a y z 3 x ：2 q l x z 吧z ： 以 堡：2 亿+ 口i ) ( z j r 伍3 z ： a y i 呈毒：y ：+ n a 了十2 q y q 2 x ：2 a 4 x z 3 q 。z ： 彪 。 ( 2 4 ) 显然，对于影射方程( 2 2 ) 而言，要使月陇z z ) 2 0 上所有的点非奇异，只要篆，善， 娑三者不同时为。即可。 o ：乙 定义2 2 由以下韦尔斯特拉斯( w e i e r s t r a s s ) 方程给出的定义在域，上的两个椭圆曲 线仿射方程局和局 l ： y 2 + 口- 拶+ 仍j ，2 x + 仍x 2 + 口。x + 球 邑2 ： y + 口l 砂+ 口3 y2 x + 口：x + 口a x + 口“ 一 一一一一 一 被称为在域，上是同构的，若存在变量( 阴，玎，s ，f 门且聊o ，使得利用下式的变换 xj 聊：x + 甩1 y j 所，y 埘麟+ 0 q 巧) 可将方程e 1 变成方程垦，则式( 2 5 ) 的变换称为变量的相容性变换。 根据上面的定义，将椭圆曲线的仿射方程( 2 1 ) 进行变量的相容性变换来简化，主要考 虑有限域f 的特征c h a r ( d 2 、3 和有限域f 的特征c l 状( 乃= 2 、3 两种情况。 1 ) 当有限域的特征c | l 状( 月2 、3 时，通过变量代换 p 熹x 一乌笋 旧去y 一务x 一止铲 可将仿射方程( 2 1 ) 变换为以下曲线： y 2 = z + 锻+ 6 ( 2 - 6 ) 其中口，6 f ，对应的判别式= 一1 6 ( 4 a 1 + 2 7 6 2 ) 。 若0 ，且口，6 bp 是大于3 的一个素数) ，则满足式( 3 6 ) 的曲线就是有限域昂上 的椭圆曲线。 2 ) 当有限域的特征c h a r ( 刁= 2 ，且方程( 2 1 ) 的口。o ，则通过变量代换 卜衍h 眚 【y p 警 浙江工业大学硕士学位论文 可将仿射方程( 2 1 ) 变换为以下曲线： 夕2 + 砂= ，+ 饿2 + 6( 2 7 ) 其中口，6 ，对应的判别式= 6 。若0 ，则符合式( 2 - 7 ) 的曲线称为非超奇异椭圆 曲线。该曲线属于有限域疋m 上的椭圆曲线。 3 ) 当有限域的特征c h a r ( d = 2 ，且方程( 2 1 ) 的口l = o ，则通过变量代换 髂 可将仿射方程( 2 1 ) 变换为以下曲线： y 2 + 钞= x 3 + 口x + 6( 2 8 ) 其中口，6 ，f f ，对应的判别式= c 4 。若0 ，则符合式( 2 8 ) 的曲线称为超奇异椭圆 曲线。该曲线也属于有限域足m 上的椭圆曲线。 4 ) 当有限域的特征c h a r ( d = 3 ，且西：一仍，则通过变量代换 l x j x + 盟等堕 j 翻+ 口2 y jy + 翻x + 皇塑；坐 【。 。 口i + 口2 可将仿射方程( 2 1 ) 变换为以下曲线： 少2 = x 3 + 戤2 + 6( 2 9 ) 其中口，6 f ，对应的判别式= 一口1 6 。 5 ) 当有限域的特征c h a r ( 用= 3 ，且口12 = 一酝，则通过变量代换 ；三；+ 口，z + 凸 可将仿射方程( 2 - 1 ) 变换为以下曲线： y 2 = x + 烈+ 6 ( 2 - 1 0 ) 其中口，6 f ，对应的判别式= 一口3 。 图2 - 7 ( a ) 和2 7 ( b ) 是椭圆曲线通过m a t l a b 下的图像。 1 9 浙江工业大学硕士学位论文 i 7 。 ， 一一 。 、 、 、 、t 、 - 、 ( a ) y 2 = 石+ 吉z + 1 ， 。 ? ，、 l 。， t t 、 。 、。- 图2 7 椭圆曲线示意图 o24s y 2 = x 一2 x 2 4 1椭圆曲线点的群运算 1 群的概念 群是抽象代数中最早的而且是最基本的一个代数系统，它也是现代数学中一个极其重 要的概念。它是研究椭圆曲线密码体制的基础。下面介绍椭圆曲线密码体制中所使用的群 的概念和基本性质。 定义2 3 设g 是一个非空集合，若在g 上定义一个二元运算“+ ”满足下列条件，称( g ， + ) 是一个群。 1 ) 结合律：对于所有的口，6 ，c g ，有a 木( 6 幸c ) = ( 口宰6 ) 木c 。 2 ) 交换律：对于所有的口，6 g ，有口6 = 6 木口。 3 ) 单位元：存在一个元素p g ，使得口木p = p 幸口= 口。 4 ) 逆元素：对于每一个口g ，都存在一个元素6 g ，使得口木6 = 6 宰口= p ，称元素6 为a 的逆元素。 群的运算通常称为加法( + ) 或乘法( ) ，并分别称为加法群和乘法群。 加法群的单位元用0 表示，加法群的元素口的逆元素通常用一口表示。 乘法群的单位元用1 表示，乘法群的元素口的逆元素通常用口1 表示。 定义2 4群g 中的元素个数称为群g 的阶，记作 g 。若群的阶为有限数，即群g 中 的元素个数有限，则称g 为有限群：反之，称为无限群。 2 点加 通过“弦和切线”的几何运算法则与无穷远点o 可以定义椭圆曲线上两个点相加的群运 算法则。令尸= ( 薪，抄) 和q = ( 耽，弘) 是椭圆曲线上两个相异的点，且尸一q 。若满足条件 尸+ q = r ，则r ( ，弘) 是连接尸和q 的直线与椭圆曲线相交点的负点，且该点是唯一的。 2 0 浙江工业大学硕士学位论文 如图2 8 所示。 -j 堰 一 j j q j p 、 、 -4-2o246 鼍 ?j， 图2 - 8 点的相加：尸+ q = r 设点一只的坐标为( 咒。，弘。) ，过尸，q 两点的直线为f ，则直线z 的斜率为： j i ：羔! = 2 ：， 得直线方程为：y 一弘= 露( x 一新) 。 于是解下面方程组： y _ 弘_ 忌( x 一_ ，可得： y = x 7 + x + d x 一七! 工2 + ( 口+ 2 x ，七2 2 砂一) x + ( 6 + 2 j b b 砂一j j 2 新2 一弘2 ) = 0 。 由根与系数的关系可以得到：+ 如+ 勋= 七：j 五。= 七2 一如一勋， 点一r 的纵坐标弘。= 七( z 一一勋) + 弘。 r 点的坐标( ，弘) 与一只点坐标( l 。，y 。) 存在如下关系： 洳2 孙 ， 推得 i 三复二：二孓弘，即 x r2 弘2 一x p x o x p x 8 、一 3 倍加 若满足条件尸+ 尸= 天，则尺是过尸点的切线与椭圆曲线相交点的负点，且该点是唯一 的。如图2 9 所示。设过p 点的切线为，则切线，的斜率为： 拈缸妒，以x ，j i 、 一，l，、l， 弘i 沙i警臀 浙江工业大学硕士学位论文 d v如 斑 而廖震楸= 守。 y 2 = x 3 + 口x + 6 。，1 利用上面点加的方法可以求得月点的坐标方程如下： i 一冬2 - 2 勋 ，即 l 弘= 七( 如一) 一弘 b 4 2 h8 - 2 埘 6 洳= ( 警) 2 也 少= ( 警) c 勋刊一弘 少2 l 万- 勋一赫) 一弘 么 。 彩 夕 l 、 - 。i。 南 4之0246 十j ，l j x ；j ji，j。 图2 9点的倍加：尸+ 尸= 月 2 4 2 椭圆曲线域参数的选择 构建椭圆曲线密码系统的域参数主要包括：有限域f 、椭圆曲线、椭圆曲线上的基点 g ，以及基点的阶刀。这些域参数由通信实体双方共享，因此是公开发布的。椭圆曲线密码 体制的实现主要用到的有限域类型是素数域乃( 其中尸是大于3 的素数) 和特征为2 的二进 制域足。针对两种不同的有限域，椭圆曲线域参数的选择略有不同。 1 有限域是素数域耶时 即有限域的特征c h a r ( 刃2 、3 ，则仿射方程( 2 1 ) 利用其同构性可变换为曲线 y 2 = x3 + 饿2 + 6 。椭圆曲线的素数域参数有6 个，即d = ( 尸- 口，6 ，g ，刀，| i z ) m ，其中尸表示定 义的素数域，a 和6 是曲线方程j ，2 = x + 锻2 + 6 的系数，g 表示选定椭圆曲线的基点，7 是 基点g 的阶，整数乃是余因子。为方便阐述，本文均采用素数域作为椭圆曲线加解密的有 限域。 2 有限域是二进制域最，时 浙江工业大学硕士学位论文 即有限域的特征c h a r ( d = 2 ，且函0 ，则仿射方程( 2 1 ) 利用同构性可变换为曲线 y 2 + 秽= r + 似2 + 6 。椭圆曲线的二进制域参数有7 个，即d = ( m ，厂( x ) ，以6 ，g ，九，乃) 【4 7 1 ，其 中聊代表二进制域，删决定二进制域的多项式，口和6 是曲线方程少2 + 拶= x + 锻2 + 6 的 系数，g 表示选定椭圆曲线的基点，船是基点g 的阶，整数办是余因子。 2 4 3椭圆曲线公钥密码算法 定义2 4 椭圆曲线离散对数问题( e l l i p t i cc u r v ed i s c r e t el o g 撕t h mp r o b l e m ，简称 e c d l p ) ：设是定义在有限域局( 其中g p ，2 ”) ) 上的椭圆曲线，给定曲线上阶为玎的基 点g e 隔) ，以及曲线上的点q ( g ) ，寻找一个整数i j ( 0 七玎一1 ) ，使q = 硒，则称整 数七为q 基于g 的离散对数，即| i = f d g g q 。 目前，对e c d l p 还不存在一般的亚指数时间的算法，故求解j j 是一个极其困难的问 题。而各种椭圆曲线公钥密码算法的安全性正是基于e c d l p 基础建立起来的。在椭圆曲 线上的公钥密码算法、方案有主要包括：椭圆曲线e i g 锄a 1 加密方案、椭圆曲线密钥交换 算法、椭圆曲线数字签名算法。 1 椭圆曲线e i g a m a i 加密方案 e c e s ( e l l i p t i cc u r v ee n c r y p t i o ns c h e m e - e i g 锄a 1v e r s i o n ) 作为非对称密码体制的加解 密算法适用于少量信息( 如对称密钥之类的信息) 的加解密。发送方会利用接收方的e c c 公 钥对所要传送的数据信息进行加密形成密文数据后发送；而接收方会利用自身的e c c 私钥 对接收到的密文数据进行解密。假设客户a 1 i c e 要发送信息m 给b o b ，则b o b 先选定一条 安全且符合式( 2 - 6 ) 的椭圆曲线，域参数为( 尸，口，6 ，g ，? ，厅) 。其中整数尸表示有限域昂，且大 于2 1 6 0 ；a ，6 随机选取，但需满足4 口3 + 2 7 6 2 o ( m o dp ) ；g 表示椭圆曲线的基点；玎是基点 g 的阶；厅表示余因子。根据该曲线随机产生e c c 密钥对( 如，q b ) ，并将域参数胪( 尸，口，6 7 g ，? ，厅) 和公钥q b 直接传给a l i c e 或a l i c e 通过c a 系统的l d a p 目录服务器下载。 1 ) a l i c e 获取b o b 传送来的域参数信息，并产生一个随机数j j ，l j j 力1 ； 2 ) 通过b o b 选定的椭圆曲线的基点g 计算出公钥c 1 = 硒； 3 ) 然后从数字证书中取得b o b 的公钥q b ，并计算出蚴； 4 ) 将待传送的明文m 分组，使其成为有限域p 上的明文信息块m ，然后将m 编码到 椭圆曲线上点p m ； 5 ) 最后计算c 2 = 尸m + 惫鳊，并同c 1 形成密文c m ，即点对 c 1 ，c 2 ： 6 ) 将c m 通过普通信道传送给b o b 。 浙江工业大学硕士学位论文 b o b 收到a l i c e 发过来的密文 c l ，c 2 ) 时，其解密过程如下： 1 ) b 0 b 用自己的私钥如计算如( c 1 ) ； 2 ) 计算q 如( c 1 ) 铮p m 十七q b - 如( 七g ) ； 3 ) 由于妨= 如g ，代入矽； 4 ) 尸m + 颤如g ) - 如( 七g ) = p m ； 5 ) 将尸m 的x 坐标的最低一字节去掉便解码得到信息明文m 。 在a l i c e 与b o b 传送信息过程时，攻击者可以看见c 1 c 2 幽d = ( 尸，以6 ，g ，7 ，办) ，但若想 通过c 】和g 求j 或通过g 和q b 求解如都是困难的，因为这都将面临求解椭圆曲线离散 对数问题。后面章节中的客户端备份和恢复私钥时将会用到该加密方案e c e s 。 2 椭圆曲线数字签名算法 椭圆曲线数字签名算法( e 1 1 i p t i cc u r v ed i g i t a ls i g n a n l r ea 1 9 0 r i t h m ，简称e c d s a ) 是数字 签名算法( d s a ) 基于椭圆曲线密码体制的变形。由于e c d s a 算法也是基于e c d l p 的难解 性，因此通过e c d s a 算法处理过的信息，任何人都无法伪造同样的签名，从而保证被签 名信息的唯一性。该签名算法e c d s a 将在后面的章节中普通使用。 假如a 1