（计算机应用技术专业论文）基于椭圆曲线密码体制的门限签密研究.pdf

摘要 论文介绍了密码技术在信息安全中的研究背景、国内外研究的现状、意义， 以及在信息安全领域的应用和未来发展方向。本文分析了椭圆曲线公钥密码体 制、对称密码体制、门限秘密共享和基于椭圆曲线密码体制的门限数字签名方 案，研究了基于椭圆曲线密码体制的签密方案和门限签密。依据门限和签密的 思想，本文提出了一个带可信中心的基于椭圆曲线密码体制的( t ，n ) 门限共享 解签密方案，围绕本方案，本文着重做了以下的研究工作： ( 1 ) 使用标准参数值生成椭圆曲线并确定其阶和基点： ( 2 ) 基于d e s 算法的消息加密和解密实现； ( 3 ) 消息的数字摘要生成； ( 4 ) 签密算法的生成： ( 5 ) 门限共享解签密算法的验证； ( 6 ) 数据库设计。 该方案综合了对称密码、s h a m i r 门限方案和j u n n g 方案的优点，除了计算 量与通信量少外，还具有保密性、认证性、抵抗接收组成员欺骗等特点，满足 群体通信的要求，对存储容量和计算能力有限的硬件开发而言，本方案具有很 大的理论价值和应用莳燎。该方案在普通签密方案已有特性的基础上，进一步 实现了签密者身份的完全匿名性，从而在最大程度上保护了签密者的隐私。 最后本文在理论研究成果的基础上，利用j a v a 实现了基于椭圆曲线密码体 制的( t ，n ) 门限共享解签密方案的算法。实验的运行结果表明，本文提出的 方案不仅是切实可行的，而且还能够得到较好的保密性、安全性和认证性。 关键词：椭圆曲线离散对数问题；椭圆曲线密码体制；签密：解签密： 门限密码学 中图法分类号：t p 3 9 3 a b s t r a c t d i s s e r t a t i o ni n t r o d u c e sc r y p t o g r a p h i ct e c h n o l o g yt ot h er e s e a r c hb a c k g r o u n d ， t h ea c t u a l i t yo fh o m e a b r o a dr e s e a r c ha n ds i g n i f i c a n c e ，a n dt h ea p p l i c a t i o na tp r e s e n t f i e l dw i t ht h ed e v e l o p i n gd i r e c t i o ni ni n f o r m a t i o ns a f e t yi nf u t u r e i nt h ed i s s e r t a t i o n ， w ea n a l y s ee l l i p t i cc u r v ec r y p t o s y s t e m ，s y m m e t r i c a lc r y p t o s y s t e m ，t h et h r e s h o l d s e c r e ts h a r i n gs c h e m ea n dt h et h r e s h o l dd i g i t a ls i g n a t u r es c h e m eb a s e do ne c c t h e nw ei n v e s t i g a t et h es i g n c r y t i o ns c h e m ea n dt h et h r e s h o l ds i g n c r y t i o nb a s e do h e c c ，p r o p o s ea ( t ，n ) t h r e s h o l ds h a r i n gu n s i g n c r y p t i o ns c h e m ew i t hc a b a s e do nt h e e c c c o n s u l t i n gt h ep r i n c i p l et h r e s h o l da n ds i g n c r p t i o n i ti sd i dt h ec r u c i a lr e s e a r c h t ot h es c h e m e ： ( 1 ) t h ea r i t h m e t i co fe l l i p t i cc u r v e i sc r e a t e db yu s e dt h es t a n d a r dp a r a m e t e r ， a n dt h er a n da n dt h eb a s i cp o i n to fe cw e r ed e t e r m i n e db yt h ea r i t h m e t i co fe l l i p t i c c u r v ef o r m e d ( 2 ) t h ee n c r y p t i o na n dd e c r y p t i o no fm e s s a g eb a s e do nd e s i sr e a l i z e d ( 3 ) t h ed i g i t a ld i g e s ti sp r o d u c e d ( 4 ) t h es i g n c r y p t i o na r i t h m e t i ci sg e n e r a t e d ( 5 ) t h et h r e s h o l ds h a r i n gu n s i g n c r y p t i o na r i t h m e t i ci sv e r i f i e d ( 6 ) t h ed a t a b a s ei sd e s i g n e d t h ep r o p o s e ds c h e m ec o m b i n e st h ea d v a n t a g e so fs y m m e t r i cc r y p t o g r a m ， s h a m i r st h r e s h o l ds c h e m ea n dj u n n g ss c h e m e i tn o t o n l yp r o v i d e st h el o w c o m p u t a t i o na n dc o m m u n i c a t i o nc o s t ，b u ta l s os e c r e c y , a u t h e n t i c a t i o n ，r e s i s i t a n c eo f m a l i c i o u sr e c i p i e n t sm e m b e r sc h e a t i n g ，t h u si ts a t i s f i e st h er e q u e s to fg r o u p s c o m m u n i c a t i o na n dh a sg r e a tt h r e o r e t i cv a l u ea n da p p l i c a t i o np r o s p e c tf o rt h e r e s t r i c t i o no fs t o r a g ea n dc o m p u t a t i o nd e v e l o p e dh a r d w a r e e x c e p tf o rt h ec o m m o n c h a r a c t e r so ft h es i g n c r y p t i o ns c h e m e ，t h ep r o p o s e ds c h e m ec o m e st r u et h ec o m p l e t e a n o n y m i t yo ft h es e n d e r , w h i c hm o s t l yp r o t e c t st h ep r i v a c yo fs e n d e r s f i n a l l yt h e ( t ，n ) t h r e s h o l ds h a r i n gu n s i g n c r y p t i o ns c h e m ew a sr e a l i z e du s i n g j a v ab a s e do nt h ee c c a c c o r d i n gt ot h et h e o r e t i cr e s u l to ft h ed i s s e r t a t i o n i ti s e l u c i d a t e dt h a tt h ep r o p o s e ds c h e m en o to n l yi sf e a s i b l e ，b u ta l s ot h eb e t t e rs e c r e c y , t h eb e t t e rs a f e t y , t h eb e t t e ra u t h e n t i c a t i o n k e yw o r d s ：e 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 mp r o b l e m ( e c d l p ) ；e l l i p t i cc u r v e c r y p t o s y s t e m ( e c c ) ；s i 曲c r y p t i o n ；u n s i g n c r y p t i o n ；t h r e s h o l d c r y p t o s y s t e m 2 贵州大学硕j 研究生学位论文 附：学位论文原创性声明和关于学位论文使用授权的声明 原创性声明 本人郑重声明：所呈交的学位论文是本人在导师的指导下，独立 进行研究所取得的成果。除文中已经注明引用的内容外，本论文不包 含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研究 在做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完 全意识到本声明的法律责任由本人承担。 论文作者签名：垂2 主l 墨 日 期：2 0 0 7 年岁月 关于学位论文使用授权的声明 本人完全了解贵州i 大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权贵州大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：埘导师签名： 日期：2 0 0 7 年歹月 贵卅l 大学硕士研究生学位论文 第1 章引言 1 1 课题研究背景、目的及意义 随着网络技术、通信技术和信息技术的飞速发展，人们的日常工作和生活越 来越离不开网络，越来越多的社会活动、经济活动以及高技术条件下的军事行动 都需要借助网络来完成。与此同时，重要信息的传输要经过脆弱的公共信道，并 存储在“不设防”的计算机系统中，人们也必然要面对消息被窃取、篡改及破坏 等威胁。因此信息安全变得越来越重要，安全可认证地传输消息是信息安全的关 键技术之一。传统的方法是对消息先签名后加密，这不仅耗费计算资源，而且扩 展了原有消息的长度。在相同安全参数的前提下，如何能够以较少的计算时问和 通信带宽( 相对于带加密的数字签名而言) 传输任意长度的消息。这就提出了数字 签密，签密能在一个合理的逻辑步骤内对传输的消息同时实现签名和加密，大大 减少了消息保密认证传输所需的时间代价和通信带宽。对数字签密的研究具有重 要的意义。而椭圆曲线密码体制( e c c ) 是公钥体制之一，在相同的安全条件下， 和其它公钥体$ , 1 4 h 比所需的计算量少、存储量小、带宽窄等优点，这正是网络传 输系统所要考虑的问题，因此建立在e c c 上的密码机制成了解决安全问题的研究 热点之一。 利用e c c 的特点，将共享秘密k 以( t ，n ) 门限方案分散给多人管理，可 以分散责任，妥善解决秘密管理中秘密的泄漏和遗失问题，保证传输消息的机 密性，提高系统的安全性。因此设计开发一套基于椭圆曲线密码体制的门限签 密，成为我国目前己公开的最新椭圆曲线密码研究的新课题，预期能够在电子 商务、电子政务、政府、军事、金融等重要消息的加密存储和加密传输，以及 决策者的数字签名与验证方面提供更好的理论依据，并能较好地满足群体通信 对发送消息的保密且认证传输。对存储量和计算能力有限的硬件开发而言，本 方案具有很大的理论价值和应用前景。 1 2 国内外研究现状 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 提出了公钥密码体制的概念。 在公钥密码体制中，国际上推行的是r s a 算法和e c c 算法。就公钥加密算法来说， 贵卅l 大学硕士研究生学位论文 目前r s a 应用最为普及，但e c c 与r s a h 比有许多优点：安全性高、处理速度快、 密钥量小、带宽要求低、灵活性好。 秘密共享是密码技术研究的一个重要方向之一，提出这种体制最初是为了进 行秘密密钥的分散管理。自从b l a k l e y ”1 和s h a m i r 。在1 9 7 9 年分别提出了秘密共享 体制以来，有关秘密共享体制的研究受到了人们的广泛关注。假设一个组织或团 体共同拥有的秘密信息为k ，参与保管此秘密信息的参与者数目为n ，一个片段的 分配者使用一定的算法将秘密信息k 分为n 个片段分别授予n 个参与者来保管。当 符合要求的若干参与者合作时，利用他们所保管的片段采用一定的算法就可以恢 复原始的秘密信息k ，而不符合要求的若干参与者合作则不能恢复秘密信息k ，我 们把这种体制称为秘密共享体制。如果n 个参与者中任意t 个参与者合作可以恢复 秘密信息k ，而任意少于t 个参与者合作时不能恢复秘密信息k ，则称此秘密共享 体制为( t ，n ) 门限秘密共享体制。 群体密码学由d e s m e d t 在1 9 8 7 年提出，是面向社团或群体的密码体制。在群 体密码中，群体外的人都可以使用群体的唯一群公钥，向群体发送加密信息，而 只有群体的某些子集的成员合作才能解密这些信息。同样，群体密码学也有群体 签名问题，而群体外的用户只需知道群体的唯一公开密钥就可以验证该签名。门 限签名( t h r e s h o l dd i g i t a ls i g a n t u r e ) 是群体密码学的一个重要分支，特别 适合电子政务的某些安全要求。其方法是将一个群体的签名密钥颁发给群体中的 每个成员，使得任何成员个数不少于门限值的子集都可以产生签名，而任何成员 个数少于门限值的子集都无法产生签名。 签密作为一种新的密码学构件，y z h e n 9 1 4 】在c r y p t o 7 9 7 中首次提出了数字 签密( s i g n c r y p t i o n ) 的概念。随后y z h e n 9 1 5 1 提出建立在椭圆曲线上的签密方案， 相对建立在椭圆曲线上的先签名后加密方案来说能够节约大概5 8 计算代价和 4 0 的通信带宽。鉴于y z h e n g 的方案，当发送方的密钥被泄露时没有提供消息 的保密，j u a n g 等人1 6 l 在离散对数问题( d l p ) 的基础上提出了一种具有消息保 密的签密。签密能在一个逻辑步骤内同时完成数字签名和加密，远远小于先签名 再加密的常规消息传递的代价。当签密方案采用小的安全参数时( 公共模数为 5 1 2 位) ，与常规方法相比，签密的计算代价降低为5 8 ，消息扩展率为7 0 ； 当采用长的安全参数时( 公共模数为1 5 3 6 位) ，签密的计算代价降低为5 0 ，消 2 贵卅l 大学硕士研究生学位论文 息扩展率为9 1 ，签密的节省代价正比于安全参数的长度，当取较大安全参数时， 它的安全性能更佳。门限签密相对门限签名来说，门限签密能同时达到门限签名 和加密的双重目的，实现代价仅和门限签名相当。 1 9 8 5 年k o b l i t z ”1 ( 美国华盛顿大学) 和m i l l e r o ( i b m 公司) 提出了椭圆 曲线密码体制( e 1 1 i p t i cc u r v ec r y p t o s y s t e m ，即e c c ) ，第一次用椭圆曲线成 功地实现了一些已有的公钥密码算法( 如d i f f e r h e ll m a n 算法) 。椭圆曲线密码 体制是目前己知的公钥体制对每比特所提供加密强度最高的一种体制。1 9 9 7 年 以来，椭圆曲线密码体制及其安全性引起了密码学家及各界的极大关注与重视， 国际上e c c 的理论和应用工作都取得了许多卓有成效的成果，科研院所、高校、 商业组织及政府部门也从各个方面探索椭圆曲线密码技术，这种密码体制也引起 了“密码体制标准”研制者的极大兴趣，i e e e 标准p 1 3 6 3 d 8 ( 1 9 9 8 年l o 月版) 及p 1 3 6 3 d 9 ( 1 9 9 9 年2 月版) 对e c c 作了详尽的讨论。a n s i 授权的金融业标准 委员会x 9 正在制定椭圆曲线数字签名标准x 9 6 2 和密钥协商及传递标准x 9 6 3 ， r s a 实验室制定了编号为p k c s # 1 3 的椭圆曲线密码标准，该标准将融合、平衡其 他标准并与其他p k c s 标准有机结合，对椭圆曲线密码体制的实现作出了更具体 的规定。目前在椭圆曲线密码分析方面仍未取得实质性的进展，这种情况持续时 间越长，人们越来越相信脯圆曲线密码体制的安全强度。 德国、日本、法国、美国、加拿大等国的很多密码学研究小组及一些公司实 现了椭圆曲线密码体制，同时也有许多厂商已经或正在开发基于椭圆曲线的产 品。加拿大c e r t i c o m 公司是国际上最著名的e c c 技术公司，已授权3 0 0 多家企 业使用e c c 技术，包括c i s c o 、摩托罗拉、p a l m 等。m i c r o s o f t 将c e r t i c o m 公 司的v p n 嵌入微软视窗移动2 0 0 3 系统中，对于椭圆曲线密码的研究方兴未艾。 在椭圆曲线密码体制的标准化方面，i e e e 、a n s i 、i s o 、i e t f 、a t m 等都作了大 量的工作，它们所开发的椭圆曲线标准的文档有：i e e ep 1 3 6 3p 1 3 6 3 a 、a n s ix 9 6 2 x 9 6 3 、i s o i e c l 4 8 8 8 等。 国内e c c 相关文献较少，理论研究的成果相对其他方面的研究成果来说要少 得多：就应用方面来说，可用的资源也很少。一些密码学者开展了这方面的工作， 但我国e c c 的研究离标准化、产品化还有相当大的差距。现在，我国的高新技术 3 贵卅l 大学硕士研究生学位论文 研究发展计划及其它重人研究开发计划中，已经将e c c 列为重点研究内容，相信 不久的将来，我幽的e c c 研究和应用都将达到世界先进水1 f 。 本文将以基于身份的密码体制和e c c 为基础，对门限数字签名和签密理论进 行深入研究。 1 3 主要工作和本文的组织结构 1 3 1 主要工作 本文分析了椭圆曲线公钥密码体制、对称密码体制、秘密共享、门限方案和 基于椭圆曲线的门限数字签名方案，研究了基于椭圆曲线的签密方案和门限签 密。依据门限和签密的思想，提出了一个带可信中心的基于椭圆曲线密码体制的 ( t ，1 3 ) 门限共享解签密方案，围绕该方案着重做了以下研究工作： ( 1 ) 使用标准参数生成椭圆曲线以及阶和基点的确定； ( 2 ) d e s 算法以及签密消息的加密和解密的d e s 实现； ( 3 ) 消息的数字摘要生成； ( 4 ) 签密算法的生成； ( 5 ) 门限共享解签密算法的验证； ( 6 ) 数据库设计。 最后本文在理论研究成果的基础上，利用j a v a 实现了基于椭圆曲线密码体 制的( t ，n ) 门限共享解签密方案的算法。实验的结果表明，本文提出的方案不 仅是切实可行的，而且还具有较好的保密性、安全性和认证性。 1 3 2 本文的组织结构 本论文主要由六部分组成，具体组织结构如下： 第1 章引言。本章介绍课题的研究背景、目的和意义，国内外研究现状， 本文主要工作以及文章的总体框架。 第2 章椭圆曲线密码体制。本章重点介绍椭圆曲线的有关理论、性质以及 椭圆曲线密码体制的实现。 第3 章对称密码和门限秘密共享。本章介绍对称密码d e s 的实现原理、门 限密码学及其秘密共享的门限方案和实现算法、基于椭圆曲线密码体制的门限数 4 贵州i大学硕士研究生学位论文 字签名。 第4 章基于椭圆曲线密码体制的门限签密方案。本章是论文的重点，介绍 基于椭圆曲线的签密方案以及本人的创新点，即基于椭圆曲线密码体制的( t ，n ) 门限共享解签密方案以及方案的安全性分析。 第5 章算法实现。基于椭圆曲线密码体制的( t ，n ) 门限共享解签密方案 的实现，并对方案进行了分析，列出了部分程序的运行结果和程序流程图。 第6 章总结与展望。对本文作出总结和展望。 5 贵卅l 大学硕士研究生学位论文 第2 章椭圆曲线密码体制 椭圆曲线( 指定义在有限域上的椭圆曲线) 的安全性依赖于有限域上的椭圆 曲线点群中的离散对数问题的难解性，目前，解决椭圆曲线密码体制上的数学难 题的最好算法仍然需要完全指数时间。一方面，解决r s a 、d s a 上的数学难题 ( 分别为整数因子分解问题i f p 和离散对数问题d l p ) 只需要亚指数时间。这意 味着和r s a 等公钥密码相比，为获得同样的安全性，e c c 可以使用相对较短的密 钥。另一方面，为达到特定安全级别所需的密钥长度的增长要比使用有限群乙 的公钥体制慢得多。因此，e c c 特别适用于在通信带宽、处理能力、可利用资源 以及存储受限的场合( 例如蜂窝电话c e l l u l a rp h o n e 、无线通信、广播电台、 智能卡等) 。 国际上制定了椭圆曲线公钥密码标准i e e ep 1 3 6 3 “、a n s ix 9 6 2 、a n s i x 9 6 3 、s e c i 、s e c 2 、f i p1 8 6 2 。规范了椭圆曲线密码体制的各种参数的选择， 并给出了各级安全强度的一组椭圆曲线密码体制参数。另一类是应用标准，在具 体的应用环境中建议使用e c c 技术，主要有i s o i e c l 5 9 4 6 、i e t fp k i x 、i e t f t l s 等。 基于椭圆曲线离散对数问题( e c d l p ) 的公钥密码体制。包括椭圆曲线 d if f i e h e l i m a n 密钥交换方案，椭圆曲线型的密钥变换方案，椭圆曲线型的数 字签名方案等。 2 1 椭圆曲线密码体制的概述 椭圆曲线密码体制是基于e c d l p 的各种公钥密码体制，它是利用有限域上的 椭圆曲线有限群代替离散对数问题的有限群所得到的一类密码体制。因此，严格 地说它不是一种新的密码体制，它只是己有密码体制的椭圆曲线的翻版。如果按 照构造体制的方式分类，前面的体制可归纳为两类，椭圆曲线密码体制应当归纳 于离散对数问题的密码体制。但是，由于它有许多独特的性质，使得人们一开始 就对它进行单独考虑。 在椭圆曲线密码提出之初，并未引起太多注意，主要是因为当时还没有一种 实际有效的计算椭圆曲线上有理点的有效方法。其次，与当时已有的r s a 公钥密 码体制相比，椭圆曲线密码体制的计算过于复杂，它的实现速度较慢。到1 9 9 0 6 贵卅l 大学硕士研究生学位论文 年，m e n e z e s 曾经使用了某些特殊曲线，这种n n 线不仅其点数可直接计算而且实 现起来非常快。在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 发现了一种有效的攻 击e c d l p 的方法( 称为m o v 方法) ，这种方法能够将超奇异的椭圆曲线上的离散 对数问题在多项式时问内约化到该椭圆曲线域的某个次数较低的扩域上，进而可 以利用已知求解d l p 的算法对其进行求解1 。为了避免m o v 方法的攻击，椭圆曲 线密码体制不再使用特殊曲线。 为了解决曲线的选取问题，人们对任意椭圆曲线上有理点个数的计算已经有 了重大突破。最初由s c h o o l 在1 9 8 5 年提出计算椭圆曲线有理点个数的算法( 1 9 8 9 年到1 9 9 2 年之间) ，a t i k i n 和e l k i e s 对其作出了重大改进，而后在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 年人们己经能够较容易地计算出满足 密码要求的椭圆曲线有理点的个数。这使椭圆曲线的选取已经不再是椭圆曲线密 码实用化不可逾越的障碍。自从椭圆曲线密码提出以后，人们不懈的努力使得椭 圆曲线密码的实现速度比它提出之初有了很大的提高。 椭圆曲线密码体制和其它公钥密码体制相比具有如下的优点：所需的计算量 少、存储量小、带宽窄等优点，这正是网络传输系统所要考虑的问题。椭圆曲线 密码体制的优势逐渐地体现出来，在这样的一种背景和椭圆曲线密码理论逐渐走 向成熟的情况下，近几年椭圆曲线密码体制已经越来越引起了密码学界和学者专 家的关注。 椭圆曲线密码体制与r s a e 1 g a m a l 密码体制的比较如表2 1 所示。 表2 1 椭圆曲线密码体制与r s a e 1 g a m a l 密码体制的比较 r s a e l g a m a l椭圆曲线密码破解所需 密码长度( 比特)长度( 比特) 密钥长度比 时间( 年) 5 1 21 0 55 ：i1 0 4 7 6 81 3 2 6 ：1 1 0 8 1 0 2 41 6 0 7 ：11 0 1 1 2 0 4 82 l o1 0 ：1 1 0 m 7 贵卅l 大学硕士研究生学位论文 2 2 椭圆曲线的相关理论 2 2 1w e i e r s t r a s s 方程 设k 为一个域，i 表示k 的代数闭域。k 上的韦尔斯特拉斯( w e i e r s t r a s s ) 方程： y 2 z + a l x y z + a , y z 2 = x 3 + a z x 2 z + o _ x z 2 + 如z 3 ( 2 1 ) 其中a 。，a 2 ，a 3 ，a 4 ，钆k ，决定射影平面p = ! ( i ) 一条曲线e ，即适合上述方 程的点( x ，y ，z ) ( x ，y ，z 玄) 的集合。 将方程( 2 1 ) 改为形如f ( x ，y ，z ) = o 的方程，e 为非奇异是指e 上不存 在奇点，即e 上不存在使a f a x ，a f a y 和d f a z 同时为零的点。 当该曲线非奇异时，我们称它为定义在k 上的椭圆曲线，以e k 表示。 e 上有唯一的一个点( o ，1 ，o ) 具有坐标z = o ，称陔点为无穷远点，记为d 。 由于a f az ( o ) = l ，故d 不是奇点。当z # o 时，令x = x z ，y = y z ，方程( 2 - 1 ) 变为： y 2 + a i x y + a 3 y = x 3 + a 2 x 2 + a 4 x + 巩( 其中x ，y e k )( 2 2 ) 曲线e 由方程( 2 2 ) 的所有解( x ，y ) 及无穷远点d 组成。将方程( 2 - 2 ) 表示 为f ( x ，y ) = o 的形式，e 上不存在使a f o x = o 和a f a y = o 同时为零的点。e 上 的每个点( 无穷远点0 除外) 都有射影坐标( x ，y ，z ) 和仿射坐标( x ，y ) 两 种表示方式。 当k 的特征c h a r ( k ) 2 时，以y - a 。x 2 一a 。2 代入( 2 2 ) 中的y 得到 e ：y z = x 3 + b 2 x 2 4 + b 4 x 2 + b 6 4( 2 3 ) 其中 b 2 = 毛2 + 4 a 2 ， b 4 2 2 a 4 + a , a 3 ， b 6 2 a 3 2 + 4 a t ， b s _ a i + 4 a 2 a 6 一a - a 3 0 4 + a 2 a 3 2 一a 4 2 。 当k 的特征c h a r ( k ) 2 ，3 时，将x b 。1 2 代入( 2 3 ) 中的x 得到 e ：y z = x 3 + a x + b ( 2 4 ) 其中 8 贵卅l 大学硕士研究生学位论文 a = 一c ( 3 2 1 ) ，b = c 6 ( 3 3 2 5 ) c = b 2 2 _ 2 4 b ， c 。= b 2 3 + 3 6 b ：b 。一2 1 6 b 。 椭圆曲线e 的判别式“”定义为：a = - b ：2 b 。一8 b 4 3 _ 2 7 b 。9 b ：b 。b 。 ( 2 5 ) 当c h a r ( k 1 2 ，3 时， = ( c 4 a - a 6 2 ) 1 7 2 8 ( 2 6 ) 当o 时，椭圆曲线e 的j 一不变量“2 1 定义为 j = c 4 3 ( 2 7 ) 当c h a r ( k 1 2 ，3 时，e k 可在同构意义下化为( 2 4 ) 式，此时 一1 6 ( 4 a 3 + 2 7 b 2 ) ( 2 8 ) j = 一1 7 2 8 ( 4 a 3 ) ( 2 9 ) 当c h a r ( k ) = 3 时，将方程( 2 3 改写为 e ：y 2 = x 3 + a 2 x 2 + a 4 x + 钆 ( 2 1 0 ) 当且仅当= a ：2 一a 。2 一a ，a e a 4 3 o 时，e 为非奇异。若( 2 - l o ) 中a 2 = o ，则有 e ：y z = x 3 + a 。x + a 6 ， = 一4 a 3 ，j = o ( 2 一1 1 ) 当a z o 时，在方程( 2 1 0 ) 中以x + a 。a ：代入x ，则有 e ：y 2 = x 3 + a 2 x + o m ，= 一a z 3 a 6 ，j = 一a 2 3 a s ( 2 - 1 2 ) 当c h a r ( k ) ：2 时，将方程( 22 ) 化为以下两种基本形状“： ( 1 ) 若a l o 时，分别以a l z x + a 。a 。和a 。3 y + ( a 。2 幽+ ) a ，3 代入x 和y ，得 e ：y 2 + x y = x 3 + a z x 2 + a o ，x = a ，j = l a 6 ( 2 1 3 ) ( 2 ) 若a t = o 时，分别以x + a ：代入x ，得 e ：y 2 + f 1 3 y = x 3 + a 4 x + a o ，= a 3 ，j = 0( 2 1 4 ) 在以后的讨论中，除特别说明，一般都指c h a r ( k 1 3 的椭圆曲线。 2 2 2 同构和j 一不变量 k 上两条椭圆曲线： e l ：y 2 + a l x y + a 3 y = x a 2 x 2 + a 4 x + f l o e 2 ：y 2 十a l x y + a , y = x 3 十a 2 。x 2 + 钆x + a 6 称作是同构的，并记为e , k 兽e z k ，如果存在u ，r ，s ，t k ，u 0 使得变量替 9 贵卅l 大学硕士研究生学位论文 换( x ，y ) 一( u 2 x + r ，u 3 y + u 2 s x 4 t ) 将e t 变为欧。 定理2 1 1 当且仅当o 时，方程( 2 - 1 ) 定义的曲线e 是非奇异的。 定理2 1 2 定义在k 上的两条椭圆曲线在i 上同构，当且仅当它们具有相同 的j 一不变量。 2 2 3 椭圆曲线上点的加法 方程( 2 1 ) 所定义的椭圆曲线e 是射影平面p 2 ( 乏) 上的一条3 次曲线，平 面上任一直线与e 都有三个交点( 不一定互不相同) 。任取e 上两点p 、q ，连接 p 、q 的直线( 当p 与q 是同一点时，取过p 点的切线) 与e 交于第三点r 。连接 r 与无穷远点o 的直线与e 的第三个点记为p 毋q 。在实数平面上如图2 1 和图 2 2 所示。 l r 7 仁 ( u l r p 口 图2 1 椭圆曲线上点的加法( p q ) r 一 六 1 r p 口 图2 2 椭圆曲线上点的加法( p ：q ) 定理2 1 3 若p 和q 是曲线e 上的任意两点，p q 连线l 交e 于另一点r ，则： ( 1 ) ( p o q ) o r = o ： 1 0 贵卅l 大学硕士研究生学位论文 证明：将方程( 2 一1 ) 改写为形如ffx ，y ，z ) = o 的形式，易见 a f d x ( 0 ) - 0 ，a i ? d y ( 0 ) = o ，a f a z ( 0 ) = l e 与过0 点的切线z = o 有唯一的交点为0 ( 三重交点) 。由。的定义，通过p 国q 与r 的直线交e 于d ，而通过d 的切线与e 的第三个交点仍是d ，故得证。 ( 2 ) p 0 0 = p ： 证明：设r 为通过p 与d 的连线与e 的第三交点，则通过r 与d 的连线交e 于p ，即有p 毋0 = p 。 ( 3 ) p 国q = q 审p ： 证明：在。的定义中，p 与q 是对称的。 ( 4 ) e 上存在一点q ，使得p o q = 0 ，则q 称为p 的对称点，q = 一p ； 证明：将p 与0 的连线与e 的第三个交点记为r ，利用( 1 ) 与( 2 ) ，有 o = ( p o0 ) o r = p or ，即一p = r 。 ( 5 ) 对于e 上的任意点p 、q 、r ，( p o q ) o r = p o ( q o r ) 。 证明：利用以下将推导运算。的表达式，可得到申满足结合律。 下面推导e 的加法运算表达式，将方程( 2 - 2 ) 改写为： f ( x ，y ) = y 2 十a i x y + a 3 y x 3 一a 2 x 2 一a 4 x a 6 = o ( 2 1 5 ) 设p ( x 0 ，y o ) e e ，下面先计算一p 。 通过p 与d 的直线为l ：x = x 。，则l 与e 的第三个交点为一p 。 将x = x 。代入( 2 1 5 ) 得到y 的二次方程f ( x 。，y ) = 0 ，则它的两个解对应直 线l 与e 的两个交点：p = ( x 。，y o ) 及一p = ( x o ，y 。) ，可见 y o + y o = 一a i x o a 3 所以一p ：( x o ，一y o - a x o - 8 3 ) 。 设p 。= ( x ，y 。) ，p 2 = ( x 。，y z ) 为e 上的两点，则 ( 1 ) 当x i = x 2 ，y l + y 2 + al x l + a 3 ：0 时，p 。+ p 2 = d 。 ( 2 ) p - + p z 0 ，通过p 。与p ：的直线为l ：y = a x + v 。 若x i x 2 ，则a = ( y l y 2 ) ( x i x 2 ) ： 若x i x 2 ，由于p 。+ p 。o ，所以p l _ p ：，l 为过p 。的切线，a = - 堕( p 。) d x 芸( p 1 ) ，a 确定后可得v 。记l 与e 的第三个交点为p 3 ：( x 。，y 3 ) ，则p 十p 2 一p 3 。 d v 贵州i大学硕士研究生学位论文 将l 的方程代入( 2 1 5 ) 得到：f ( x ，ax + v ) = ( x - x ) ( x - x ：) ( xx 3 ) ，由于 x 。+ x 2 + x 。- a2 + a 1 a a 2 可计算出轴和y 3 。 从上面的定理可知：若将d 点看作为运算。的零元素，性质( 5 ) 证明关于 $ 运算交换律成立。性质( 5 ) 为：若p 点在曲线e 上，则曲线e 上关于。结合 律成立。为方便起见，以后将。简化为+ 。同理pop = 2 p ，依此类推： m p = p + p + + p 。总之，椭圆曲线上的点关于运算+ 构成a b e l 群。 石一 2 2 4 椭圆曲线的加法规则 设e 为方程( 2 - 1 5 ) 定义的椭圆曲线， ( 1 ) 设p ( x ，y ) e e ，贝0 一p = ( x ，一y - a x a 。) ，令 p i + p 2 = p 3 ，p i = ( x i ，y i ) e e ，i = l ，2 ，3 。 ( 2 ) 若x l = x 2 ，y ，十y 2 + a i x + a 3 = o 时，p l + p ：= d 。否则令 a = ( 3 ) p 。由卜，式给出 2 _ ) ，1 + 口1 h + n 3 当x i x 2 当x i = x 2 广x 产a2 + a l a a 2 - x 广x 2 ly 3 = a ( x , - - x 3 ) 一y 广aj x 3 a 3 特别，当p l p 2 时， 舢一加( 嚣卜( 嚣卜圹x t 屯一ji 而一j 当p j _ p ：时， x ( 2 p i ) 毫墼墼二垒 4 x i + 6 ：+ b 4 x 1 + b ( 2 1 7 ) ( 2 1 8 ) ( 2 一1 9 ) 对c h a r ( k ) 3 的椭圆曲线，方程( 2 1 ) 在同构意义下可化为方程( 2 4 ) ， 对方程( 2 - 4 ) ( 1 ) 当p 一p 2 时，则( 2 1 7 ) 式可表示为 贵卅l 大学硕士研究生学位论文 一嚣卜_ x 2 治。， b f 必x 2 - - x 11 ( x , - x d e 3 彳+ a 2 y 1 3 , 4 + 4 2 y i 2 2 5 椭圆曲线上点的阶 2 - 2 x ( 2 - 2 1 ) 定义p 是椭圆曲线e 上的一点；若存在最小的整数n ，使得n p = o ，其中d 是 无穷远点，则称n 是p 点的阶。 当然，不一定都存在有限的n ，但我们感兴趣的是椭圆曲线e 上其阶为有限 的点，特别是定义在有理数域上的椭圆曲线。 例2 1 y 2 = x 3 + x + 4 ( m o d2 3 ) 取x = o 。代入上式，有0 3 十0 + 4 = 4 = 4 ( m o d2 3 ) 取y = 2 2 2 ：4 ：4 ( m o d2 3 ) 故p = ( 0 ，2 ) 2 p = p + p ，由公式( 2 - 2 1 ) 有： 工= ( ( 3 0 2 + 1 ) ( 2 2 ) ) 2 2 0 = 0 4 ) 2 2 x 0 1 1 6 ：1 3 ( r o o d2 a ) 同理得：y = 1 2 ， 3 p = 2 p + p = ( 1 1 ，9 ) 公式( 2 2 0 ) 2 9 p = 0 + 即p = ( 0 ，2 ) 的阶为2 9 。 2 ，3 有限域上的椭圆曲线 2 3 1 椭圆曲线的阶 设k 2 f 。( 包含q 个元素的有限域) ，e k 为定义在有限域上的椭圆曲线。令 贵卅l 大学硕士研究生学位论文 e ( k ) = ( x ，y ) e ix ，y e k u 0 ) ， e ( k ) 称为e 的k 一有理点集合，它足一个有限集，我们通常把点的数日记为 # e ( k ) ，称之为椭圆曲线e 的阶。 计算艇( k ) 是研究有限域上椭圆曲线的一个核心问题。在方程( 2 2 ) 中， 当x 取遍r 的元素时，约有一半的情况使方程( 2 2 ) 左端的二次方程有二个解， 所以# e ( k ) 大致为q + l 。e a r t i n 在他的博士论文猜想有定理2 2 1 ，后来h a s s e 给出了证明。 定理2 2 1 ( h a s s e 定理) 设k e f 。，e k 为椭圆曲线，则i # e ( k ) 一q - l l 2 局， 定理的证明见 1 2 。 2 3 2 椭圆曲线的离散对数问题( e c d l p ) 设e 为定义在有限域f 。上的椭圆曲线，p 为e 上的点。e 的阶为n ，p 的阶为 n 。，已知点q ( p 生成的循环群) ，求正整数m ，使o = m p ( o m 3 的椭圆曲线a 2 4 1 点加法 椭圆曲线上的点可以用射影坐标( x ，y ，z ) 或仿射坐标x