（计算机系统结构专业论文）椭圆曲线密码算法及其应用.pdf

摘要 摘要 椭圆曲线密码体制是公钥密码学领域的一个重要课题。这种密码体制具有安 全性能高、计算量小、密钥长度短、处理速度快、存储空阳j 占用小和带宽要求低 等特点，因而在安全领域具有广泛的应用前景。 本文从数论和代数的角度出发介绍椭圆曲线是如何应用到公钥密码中的，分 析椭圆曲线密码的优越性和安全性。作者所作的主要工作有： ( 1 ) 研究了基于大素数域上的椭圆曲线密码在加密解密、密钥交换、数字签名等 方面的密码协议并分析了每种协议的安全性能； ( 2 ) 在现有基于身份的数字签名方案的基础上提出了基于身份的群签名系统并讨 论了群签名在数字现会中的应用； ( 3 ) 给出了椭圆曲线密码在电子拍卖系统、密钥认证系统方面的实现方案。 关键词：椭圆曲线密码体制椭圆曲线离散对数群签名电子拍卖密钥认证 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 g r a p h y ( e c c ) i sa ni m p o r t a n ts u b j e c ti nt h ef i e l do fp u b l i ck e y c r y p t o g r a p h y i tp r o v i d e sh i g h e rs e c u r i t y , s h o r t e rk e ys i z e ，l e s sc o m p u t a t i o n ，f a s t e r p r o c e s ss p e e d ，l e s sm e m o r ys p a c ea n dl o w e rb a n d w i d t h ，s oi t h a sw i d ea p p l i c a t i o n p r o s p e c ti ni n f o r m a t i o ns e c u r i t yf i e l d i nt h i sp a p e lt h ea u t h o rp r i m a r i l yi n t r o d u c e sh o w e l l i p t i cc u r v e sh a v eb e e na p p l i e d t op u b l i ck e y c r y p t o g r a p h yf r o ma l g e b r aa n dn u m b e rt h e o r y ，a n a l y z e st h ea d v a n t a g ea n d s e c u r i t yo f e c c t h ew o r k t h ea u t h o rh a sd o n ei s ： ( 1 ) s t u d y t h ea r i t h m e t i co fe c co nt h ee n c r y p t i o n d e c r y p t i o n ，d i g i t a ls i g n a t u r ea n d k e y e x c h a n g es c h e m e s a n d a n a l y z e t h e i rs e c u r i t yp e r f o r m a n c e ； ( 2 ) p r o p o s ean e wi d - b a s e dg r o u ps i g n a t u r ew i t he x i s t e di d - b a s e dd i g i t a ls i g n a t u r e a n dd i s c u s si t sa p p l i c a t i o ni nd i g i t a lc a s h ； ( 3 ) r e a l i z et h ee l e c t r o n i ca u c t i o ns y s t e ma n dk e ya u t h e n t i c a t i o ns y s t e mw i t he c c k e y w o r d s ：e l l i p t i cc u r v e g r o u ps i g n a t u e c r y p t o s y s t e m se l l i p t i c c u r v ed i s c r e t e l o g a r i t h m a u c t i o ns y s t e m k e y a u t h e n t i c a t i o n 声明 y 5 8 3 3 5 6 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：纽 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容可以允许采用影印、缩印、或其它复印手段保存论文。( 保密的论 文在解密后遵守此规定) 本人签名 导师签名 日期 f 1 期 卵磁，? 6 五晒幺z ：虚 第章绪论 第一章绪论 1 1 椭圆曲线密码的研究背景和意义 随着网络环境的逐渐成熟，网络基础设施的不断完善，用户在数字世界中进 行的活动越来越频繁。为了确保信息的保密性、完整性、可用性、可控性，避免 国家或个人的信息收到非法获取、破坏、篡改等形式的威胁，人们提出了用密码 技术来保障以电子形式保存或传送的数据。 信息隐私性的保护使用了一种对称性算法。其中以d e s 为代表。它需要在通 信的每一方之间交换加密密钥。这样如果肝个用户都能够秘密交换信息，则每个用 户需要n ( n 一1 ) 2 个密钥。这种巨大的密钥量给密钥的分配和管理带来了极大的困 难。不仅如此，对称算法没有涉及到数据的可鉴别性和抗抵赖性，不能自然地提 供证实用户身份的功能，不能确认消息来源的真实性和用户的身份。然而随着网 络通信的发展，这些都是必不可少的。 1 9 7 6 年，w h i t f i e l dd i f i l e 和m a r t i nh e l l m a n 发表了密码学的新方向提 出了第一个公钥密码体制( 又称为非对称密码) 。同时r m e r k l e t a i 也独立提出了这一 体制，这是密码学史上一个划时代的事件。这种新的密码体制解决了传统对称密 码存在的问题，是密码学由传统的政府、军事等应用领域走向商用、民用的基础， 使得人们可以利用i n t e r n e t 这样的公开性网络进行安全通信或商业活动。公钥密码 的思想是：密码系统的加密密钥、解密密钥是可以不同的，由加密密钥和密文很 难求得解密密钥和明文，从而这种系统的加密算法和加密密钥可以公开，系统的 安全保密性完全依赖于秘密的解密密钥。 一般的公钥密码系统的加密、解密过程如下：每个用户【，选择一对密钥k 、k ， 分别称为公钥和私钥，并构造出自己的加密算法e 。和解密算法d 。，。和d 。应当 使得对每个可能的明文m ，等式d 。( b ( m ) ) = m 成立。每个用户将他的加密密钥和 加密算法公 ，可以被任何用户查找，而解密密钥则由用户自己保密管理。如果 用户a 要给用户口传送密码信息m ，用户a 首先查到用户b 的公钥，形成用户b 的 加密算法。，用。对明文m 加密得密文c = e 。( 埘) ，并将c 发送给用户b 。用户b 接受到密文c 后，用自己的私钥确定的解密算法d 。来。陬复明文： 州= d 8 ( c ) = d # ( e h ( 川) ) 。 公钥加密系统不存在对称加密系统中的密钥分配和保存问题，对于具有一个用 椭侧曲线密码掉法及其应用研究 j 1 ，的删络，仅需要2 ”个密铡。公钥密码系统除了用于数据加密，还可用于数字签 躬。公钥加密体制可提供以下功能： ( 1 ) 保密通信：保密通信是密码学产生的动因。使用公钥密码体制进行保密通信 h _ j ，信息发送者使用接收者的公开密钥加密所发送的信息，只有拥有该公丌密 钥对应的秘密钥的接收者才可以解密该信息。 ( 2 ) 数字签名：数字签名技术可以代替传统的手写签名，而且从安全的角度考虑， 数字签名具有很好的防伪造功能。 ( 3 ) 秘密共享：秘密共事技术是指将一个秘密信息利用密码技术分拆成 个称为共 享因子的信息，分发给i 1 个成员，只有k ( ksn ) 个合法成员的共享因子才可以 恢复该秘密信息，其中任何一个或m ( m 女) 个成员合作都不知道该秘密信息。 利用秘密共享技术可以控制任何需要多个人共同控制的秘密信息、命令等。 例如，一一个国家的核发射命令只有国家元首、国防部长、军队司令等人都同 意时才。能发射；银行金库有两个以上的管理人员管理钥匙；利用可验证的秘 密共享技术可以实现可分的电子现金系统。 ( 4 ) 认证功能：在公开的信道上进行敏感信息的传输，攻击者有可能对所传输的 信息进行篡改、重放，或者可能冒充通信方接受或发送信息，因此必须对所 传输的信息进行真实性、完整性的认证。对通信方的身份进行真实性认证。 可以采用签名技术实现对消息的真实性、完整性进行验证，通过验证公钥证 书实现对通信主体的身份验证。 ( 5 ) 密钥管理；设计安全的密码算法和协议并不容易，而密钥管理则更困难。密 钥是保密系统中更为脆弱的环节，其中分配和存储可能是最棘手的。 由于对称算法和公钥算法各有优缺点，在实际应用中通常综合使用。对称算 法运算速度非常快，适合用于对数据本身的加解密操作。而公钥密码体制加解密 所需要的计算量很大，在需要传输大量信息时效率不高，但是公钥算法能对数据进 行签名，可以证明数据发行者的身份并保证数据在传输过程中不被篡改，所以对 称算法的密钥( 会话密钥) 般是用公钥算法加密后在通讯双方之划交换的。 现在通用的公钥算法是1 9 7 8 年由r i v e t 、s h a m i r 、a d e l m a n 提出的r s a 算法。 r s a 方法的优点主要在于原理简单、易于使用。但是随着安全需求的增加，r s a 算法所需要密钥的位数一直在增加，密钥长度的增加导致了其加解密的速度大为 降低，存储空间显著增加，硬件实现变得越来越难以忍受，应用越来越受到限制。 1 9 8 5 年，n e a lk o b l i t z t3 】和v s m i l l e r i 4 】分别独立提出了一种能在低要求的计算环境 中达到高强度加密的一种新的公钥算法一一椭圆曲线加密体制e c c ( e l l i p t i cc u r v e c r y p t o g r a p h y ) 。椭圆曲线加密体制自8 0 年代中期被引入以来，逐步成为一个十分 令人感兴趣的密码学分支，特别是9 7 年以来，对于该体制的研究形成了一个研究 第一章绪论 热点。这种密码体制受欢迎之处在于在安全性相当的前提下，可用较短的密钥。 一般认为q 元域上的椭圆曲线密码体制，当q 的长度为1 6 0 b i t 时，其安全性相当 于r s a 使用1 0 2 4 b i t 模式。密钥短意味着存储空间占用少、带宽要求低等。e c c 的这些特点使得业内人士普遍认为它在某些计算能力和存储空涮受限的领域，如 p d a 、手机、智能卡等方面的应用将取代r s a ，并成为下一代最通用的公钥加密 算法标准。 1 2 椭圆曲线密码技术的发展 椭圆曲线由于其丰富的数学意义，一直是代数和数论重要的研究对象。它有长 达几个世纪的漫长的研究史，但是它引起密码学领域的关注却还只是十几年前的 事情。 1 9 8 5 年n e a lk o b l i t z 和v s m i l l e r 把椭圆曲线的研究成果应用到密码学中，分 别独立提出在公钥密码系统中使用椭圆曲线的思想。他们虽然没有发明出一种新 的公钥密码算法，但是第一次用椭圆曲线成功地实现了已有的些公钥密码算法 包括d i f f e r - h e l l m a n 算法。这就是椭圆曲线密码学的开端。 椭圆曲线从提出到现在近二十年的时间里得到了快速发展，大致可以分成两 个阶段： ( i ) 1 9 8 5 年一1 9 9 5 年：这段时间人们对椭圆曲线密码技术的研究主要以理论为主。 通过大约十年的研究，人们逐渐克服了椭圆曲线密码体制的两大弱点：一是 没有一种实际有效的计算椭圆曲线有理点个数的算法，致使人们在选取曲线 时遇到了难以克服的困难，从而阻碍了椭圆曲线密码的实用化。1 9 8 5 年， s c h o o f 最早提出了计算椭圆曲线有理点个数的算法，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 年时人们已能够较容易地计算出满足密码要求的任意 椭圆曲线有理点的个数了。二是由于椭圆曲线中的加法运算过于复杂，使得 实现椭圆曲线密码时速度较慢。随着研究的不断深入，椭圆曲线密码的实现 速度也不断提高。此外，这段时间人们还对探讨了椭圆曲线密码系统的安全 性；初步研究了椭圆曲线密码算法，提出了许多实现e c c 操作的算法，其中 对域和域操作算法的研究成果最为显著。 ( 2 )1 9 9 5 年至今，人们对椭圆曲线密码技术的研究除了继续改善椭圆曲线密码算 法的性能外，丌始偏重于应用方面。这段时间，各种椭圆曲线加密、签名、 密钥交换的软、硬件也相继问世。美国r s a 数据安全公司在1 9 9 7 年公布了 包含e c c 的密码引擎工具包b s a f e4 o ：以加拿大c e r t i c o m 为首的安全公 椭圆曲线密码算法及其心州研究 司和工业界联合也研制、生产了以椭圆曲线密码算法为核心的密码产品。由 r 椭圆曲线密码系统具有安全性能高、计算量小、密钥长度短、处理速度快、 算法效率好、存储空阳j 占用小和带宽要求低等优点，e c c 技术在信息安全领域 中的应用将会越来越广。 现阶段，e c c 技术的研究主要集中于以下几个方向： ( 1 ) 随机曲线的选取 虽然现有的实现方案基本上都采用了“子域曲线”或其它些特殊的曲线， 但是一般人为要取得最佳安全性必须采用随机曲线。对随机选取的曲线，虽 然有s e a 算法能计算所选曲线的有理点数，但是要找到一条合适的曲线仍然 并不容易。如何能够更快地找到大量合适的随机曲线仍需进一步研究。 ( 2 ) 加快点乘的运算速度 在e c c 系统中，椭圆曲线点乘运算使最耗时间的运算，它决定了整个e c c 系统的性能。对一些特殊曲线或固定基点p ，现在已经有了较好的算法。但 是对一般曲线或对随机点p ，如何快速地计算m p 仍无一个好的方发。因此， 进一步加快计算点乘的速度，从而提高整个e c c 系统的性能正成为一个热门 的研究领域。 ( 3 ) 快速产生椭圆曲线参数 要使用椭圆曲线密码系统首先要先确定系统的各个参数，这是建立e c c 系 统最花时间的一个步骤。虽然可以以离线的方式产生椭圆曲线参数，并且一 旦产生了一条安全的椭圆曲线后，以后就可一直使用该曲线来建立椭圆曲线 密码系统但如何快速地以在线地方式产生可用于密码学地安全地椭圆曲线 参数使密码学者一直在谋求解决的问题。 ( 4 ) 椭圆曲线密码系统的实现 e c c 的特点使得它特别适合于在计算机能力弱的环境( 如w a p 和i c 卡) 下 实现，如何在计算能力弱的环境下实现e c c ，特别使如何充分利用e c c 的计 算量小，占用存储空间少，安全性高等优势，在不增加成本的前提下，在i c 卡上实现e c c 系统，同时提高i c 卡的实用性，是目前学术界和商界都在积 极考虑的问题，i c 卡在e c c 的结合不仅可提高i c 卡的安全性，降低i c 卡 的成本，而且还会为i c 卡带来新的用途。 ( 5 ) 设计硬件结构加速e c c 的计算效率 如果象r s a 一样，能用硬件实现e c c 系统，那么用e c c 加解密数据的效率 将大大提高，因此如何设计有效的硬件结构来实现e c c 也是人们正在研究的 一个方向。 ( 6 ) 椭圆曲线密码协议的设计 第一章绪论 要推广椭圆曲线密码技术的应用，就必须要有基于椭圆曲线密码技术的椭圆 曲线密码协议的支持，目前支持椭圆曲线技术的密码协议还很少，因此设计 新的基于椭圆曲线密码系统的密码协议是学者们现在和将来的一项任务。 1 3 本文各章节的主要内容 本文主要研究了椭圆曲线密码的算法及其在实际中的应用。 第二章主要介绍本论文中将用到的有关椭圆曲线密码体制方面的基本理论知 识。首先给出椭圆曲线的定义及定义在椭圆曲线上的加法群的群运算法则，然后 介绍椭圆曲线离散对数的概念，攻击现状，最后讨论选取安全椭圆曲线的条件； 第三章主要研究了基于椭圆曲线密码离散对数难题的加密解密、密钥交换、 数字签名等几种典型的密码协议并分析了每种协议的安全性能： 第四章首先主要介绍了基于椭圆曲线密码的群签名技术。首先介绍了普通的 群签名方案，在此基础上设计了改进的基于身份的群签名系统，并简要介绍了与群 签名相关的其他签名技术，最后讨论了群签名技术在数字现金中的应用； 第五章主要介绍椭圆曲线密码在电子拍卖、密钥认证等领域的实际应用，给 出了具体的实现方案。 椭恻曲线密码算法及其应h j 第二章椭圆曲线密码体制 1 9 8 5 年n e a lk o b l i t z 和v s m i l l e r 把椭圆曲线的研究成果应用到密码学中，分 别独赢提出在公钥密码系统中使用椭圆曲线的思想。这种思想的基础是定义在有 限域上的椭圆曲线的有理点集可以构成a b e l i a n 群，由此可以定义其上的离散对数， 即椭圆曲线离散对数。求解椭圆曲线离散对数是非常困难的，所以通信双方可以据 此构造公钥密码体制一一椭圆曲线密码体制。 2 1 基本数学原理 2 1 1 椭圆曲线的概念 定义：设k 是一个域( 可以是有理数域，实数域或者有限域) ，i 和k 分别为 其代数闭域和乘法群，椭圆曲线e ( 足) ( 简汜为e ) 定义为乏i 上满足w e i e r s t r a s s 方程的点加上所谓的无穷远点d 的集合 e ：y 2 + 口l 爿y + 口3 y = j 3 十口2 x 2 + 口4 鼻+ a 6其中口f k 定义如下参数： 6 2 = 口l + 4 a 2 ， 以= 口l d 3 + 2 a 4 ， b 6 = a 3 十4 d 6 ， b 8 = a 1 1 - 口6 + 4 a 2 6 一a l a 3 a 4 + 日2 口3 2 一d 4 2 ， c 。= b 2 2 2 4 b 4 ， c 6 = 一6 2 + 3 6 b 2 b 4 2 1 6 b 6 ， = 一b 22 b 8 8 b 4 3 2 7 b 6 2 + 9 b 2 6 d b 6 ， 其中是椭圆曲线的判别式，当且仪当0 时椭圆曲线为非奇异曲线。( 所谓“非 奇异”或“光滑”的，在数学中是指曲线上任意一点的偏导数不能同时为0 。即满 足方程的任意一点都存在切线。) 此时可定义椭圆曲线的j - i n v a r i a n t ( j 一不变量) j ( e ) = c 。3 , 5 。 第二章椭圆曲线密码体制 2 1 2 椭圆曲线群运算 假设域k 为实数域，椭圆曲线e 上的加法几何意义如图l 所示：e ( x ，y ，) 和 q ( x 2 ，y ：) 是e 上不同的两个点，连接点p 和q 交曲线e 于另一点，过浚点作平行 于纵坐标轴的直线与曲线e 相交于点r ( x ，儿) ，则尺为尸和q 两点之和记为 r = p + q ，这就是椭圆曲线的加法运算。在图2 定义了曲线e 上任一点自加，记 为2 p = p + p ，过点p 作曲线e 的切线与曲线交于一点，过该点作平行于纵坐标轴 的直线与曲线e 相交于点r ( - ，y ，) 。若切线和纵坐标轴平行即交曲线于无穷远处， 则p + p = 0 ，即点尸是椭圆曲线e 上阶为2 的点。对于k 个相同点的相加，即 尸+ 尸+ + p ，可表示为舻，称为点积或数乘。 _ 嘲7歹 ：二二 p ( x 1 y 1 ) r 。( 3 j入 躅l p = ( x 1 y 立7 一 7 歹 厂、 r h i y 人 、 幽2 椭吲曲线密码算法及其应“j j 以证明，椭圆曲线e ( k ) 上的点在加法运算下构成一个a b e l i a n 群，无穷远 点o 为单位元。卜面是具体的群运算法则： ( 1 ) | ) + o = o + p = p ，一o = o ； ( 2 ) p + q = q + j p ； ( 3 ) 若j d = ( _ ，y 。) 则 一p = ( x l ，一y i 一日l x l 一a 3 ) ； ( 4 ) 求和：设r = ( 扎，y 3 ) ( f = 1 , 2 ，3 ) ，r = 尸+ q 则当一= x 2 ， 且 y ，十y 2 + q i x2 十d 3 = 0 时，p + o = 0 否则，r 的坐标x 3 ，y 3 由下式给出 f x 3 ；名+ g i 五一日2 一z l x 2 【y 3 = 一( + 口1 ) x 3 一一口， 其中 l 堕丛，当x x 2 时 ：j 屯= - 一 i 型兰譬? c 盟净：时 【2 y l + a l + a 3 7 。 = y i x 2 一y 2 x ，当x x 2 时 x 2 一x 1 t 血尝止业，曳时 2 y 1 + d l x l + 3 下面，根据足的特征c h 州k ) ( 域足取作实数域) ，可以将w e i e r s t r a s s 方程转 化为更为简单的形式并给出相应的群运算法则。 1 ) 特征值不为2 和3 ，即c h a r ( k ) 2 , 3 椭圆曲线e 可以用简单的形式表示 e ： ，2 = x3 + a x + 6 b k 此时判别式= 一1 6 ( 4 a 3 + 2 7 b2 ) ，不变量j ( e ) = 一1 7 2 8 ( 4 a ) 3 a 。椭圆曲线e 为 ix il ：满足方程y2 = x3 + a x + b 的点和单位元0 ( 即无穷远点) 的集合，在加法 运算f 构成一个a b e l i a n 群。 在椭圆曲线群中，点p = 0 ，y ，) 的逆元是一p = o p ，- - y ，) ；群的单位元是无穷 远点0 。点p ( x 。y ，) 和q ( x 。y 。) 的加法运算法则分为以下四种情况： 发r ( x ”，y ) = p + o a ) p 和q 是两个不同点，且p - q ，则 l x r2 允_ ，- - x q 【”= ( x ，一x r ) 五一y p 此时丑：些二生 x ( ，一xp 第二章椭圆曲线密码体制 9 b ) p 和q 是两个不同点，p = 一q ，则 p + q = o c ) p = o ，且y ，0 时，设置= 2 p i z n = 2 2 x p ( m o d p ) i y r = ( x p x r ) 一y p ( m o d p ) 此时 ：竺! ! 砂r d ) p = o ，且y ，= 0 时，过点的切线垂直与轴，不于椭圆曲线相交，此时 r = 2 p = o 2 ) 特征值为2 ，即c h a r ( k ) = 2 j 一不变量的表达式简化为j ( e ) = 口。”。当j ( e ) = 0 ，即w e i e r s t r a s s 方程中 的a = 0 时，称椭圆曲线时超奇异的。这类曲线的点数可直接计算，而且实现起来 非常快，但是在密码系统中应避免使用超奇异椭圆曲线，因为它易受m o v 的攻击。 这种方法能够把超奇异椭圆曲线在多项式时间内约化到椭圆曲线基域的某个次数 较低的扩域上，进而可利用已有的求解离散对数的算法对其进行求解。 如果，( 五) 0 ，椭圆曲线可以简化为 e ：】，2 + 翼】，= x 3 + n ，2 + a ， 如果j ( e ) = o ( 即e 是超奇异椭圆曲线) ，椭圆曲线可以简化为 e ：l r 2 + 口3 y = x 3 + 0 4 x + a 6 ， 椭圆曲线占为满足上式的点0 ，y ) 和单位元0 的集合，这些点在加法运算下也构成 一个a b e l i a n 群。因为超奇异椭圆曲线不够安全，所以只讨论非超奇异椭圆曲线的 情况。 在椭圆曲线群中，点p = b ，y ，) 的逆元是与点同坐标的另一个点 一p = ( x p ，x ，+ y ，) ；群的单位元是无穷远点0 。点p ( x p ，y ，) 和q ( x 。，y e ) 的加法运 算法则分为以下四种情况： a ) p 和q 是两个不同点，且p - o ，则 l x h = + 五十口2 + x p + x o ， 【y r = ( x p + x n ) 兄+ x r + y p ， 此时五：兰! 生 x 口+ x p b ) p ：- q ，则 p + q = 0 c ) p = q ，且y p 0 时，设r = 2 p l x n = + 五十日i 【y = x p + ( + 1 ) x r 此时五：! ，| ! ! ： o椭圆曲线密码算法及其麻川 d )| p = o ，且y ，= 0 时，过点的切线垂直与轴，不于椭圆曲线相交，此时 r = 2 p = o 3 1 特征值为3 ，即c h a r ( k ) = 3 因为在实际中很少用到这类曲线，这里不作讨论。 2 1 3 有限域上椭圆曲线阶的计算 是包含p 个死素的有限域，设k = ，酬k 为定义在有限域上的椭圆曲线。 椭圆曲线e 的阶：令( k ) = ( x ，y ) e iz ，y k u o ) ，e ( k ) 称为e 的k 一有 理点集合，它是一个有限集，把有理点的数目记为拌e ( ) ，称之为椭圆曲线e 的 阶； 椭圆啦线点p 的阶：定义p 是椭圆盐线e 上的一点，若存在最小的整数n ，使 得 j p = 0 ，其中0 是无穷远点，则称一是点尸的阶。 关于椭圆曲线的阶的计算，有定理如下： h a s s e 定理：设k e ，e l k 为椭圆曲线，则 i # e ( k ) 一p l 峰2 4 p 如果# e ( k ) = p ，则椭圆曲线纠足是一类特殊的椭圆曲线，称为“畸形”曲线。 如果要准确求出椭圆曲线的阶，有定理如下： 定理：给定椭圆曲线，则e ：y 2 = x 3 + 删+ b ( 其中口，b 只) ，则 # 孵) = l + ( 1 + ( 掣) ) ，( x 讪其中9 表礼g e n d r e 特， 即 f 1 ，当j 是p 的平方剩余 ( 二) = l0 当p s l l ，当s 不是p 的平方剩余， 其中，一是整数，g c d ( a ，p ) = 1 证明：对任意x ，若p ( x ，+ o xq - 6 ) ，方程y 2 = x 3 + 甜+ b 有一个解，椭圆曲 线卜有相应的一个点( x ，0 ) 。 若x 3 + n x + b 是p 的平方剩余，方程y 2 = x 3 + “+ b 有两个解，椭圆曲线上有 以x 为横坐标的两个点。 若x 3 + t ：x + b 不是p 的平方剩余，方程y 2 = x 3 + a x + b 无解，椭圆曲线上 没有以z 为横坐标的点。 对任意x 只，x3 + a x + p 总是以上三种情况之一，因此椭圆曲线上以x 为 横坐标的点有( 1 + ( 羔二! 型兰) ) 个。 第二章椭圆曲线密码体制 另外，椭圆曲线包括一个无穷远点。 所以，椭圆曲线上的点数为：社e ( ) = 1 + ( 1 + ( 掣) ) ( 工) 2 2 椭圆曲线离散对数问题 从数论的角度说任何公钥密码系统的安全性都是基于求解某个数学难题的1 5 1 ， 或者说是建立在一个n p 问题( 无法处理的问题) 之上，即对于特定的问题我们没有 办法找到一个多项式时间的算法求解该问题，一般求解此类问题的算法都是指数 时间或者亚指数时i n j ，现有的计算机体系结构不适于求解此类问题。有了这个理 论依据，我们就可以放心地公丌或者发送公钥给任何人，而不用担心攻击者利用 公钥反推出我们私钥。 这些数学难题可以分为三大类： 大整数因数问题：两个大素数p 和口相乘得到乘积疗比较容易计算，但从它们 的乘积n 分解为两个大素数p 和盯则十分困难。如果 t 为足够大，当前的算法不可 能在有效的时间内实现。 有限域乘法群上的离散问题( d l p ) ：设a ，b 为有限域乘法群z 上的一个元素， 找出x z ，使得口。= b 的运算称为有限域乘法群z 上的离散对数。求解它有亚指 数时间算法。 椭圆曲线上的离散对数问题( e c d l p ) ：设e ( c ) 是定义在有限域c 上的椭 圆曲线，给定曲线上任一点p ，e 的阶为n ，p 的阶为n 。椭圆曲线离散对数问题是 指给定曲线上阶为n 的点p ，已知点q ( p ) ( p 生成的循环群) ，求正整数m ，使 q = m p ( 0 m 4 v p 2 对每一个，b ，艺名，计算 g c d ( x 9 一爿，中，( j ，_ ，) ) 当g c d ( x ”一x ，中，( x ，) ) 1 时，可知，为e l k i e s 素数，进一步计算 g c d ( x ”一x ，中，( 片) ) 的一个根后转入3 ； 当g c d ( x 9 一x ，o ，( x ，助= 1 时，则，为a t k i n 素数，此时逐一计算 g c d ( x ”x ，中，( x ) ) ，i = 2 ，3 ，求出使 g c d ( x ”一x ，巾，( x ，) ) = 中，( x ，) 成立的最小整数i ，且记为r ，然后转入第4 步； 3 出e l k i e s 的改进，计算出c m o d ，： 4 由a t k i n 的改进，计算出c m o d l 的一个可能值集合； 5 通过3 ，4 步，利用中国剩余定理，可得c 的一个可能的集合 c = c i ，c 2 ，c 。) ； 6 利用大步小步法确定c 和# e ( r ) = p + 1 一c ； 2 ) s a t o h f g h 算法 s a t o h f g h 算法的基本思想是对于给定的有限域y q ( 其中q = p 。) 上的椭圆曲 线，将其提升到定义在p a d i e 环z q 上的椭圆曲线。利用模多项式中。通过提升曲 线的，不变量可以把椭圆曲线提升到乙，但这种方法需要环z 。，上的f r o b e n i u s 计 算，速度很慢。s a t o h 对此进行了改进，同时提升，及其共扼，而不是单独提升 - ，这样可以避免计算f r o b e n i u s ，利用多变量的n e w t o n 迭代可以很方便的实现。 h a r l e y 等人已经成功地运用该方法计算出基于有限域f ( 其中q = 2 s ”) 上的椭圆 曲线的点，是迄今为止已实现的规模最大的椭圆曲线上点的计算。在国际标准a n s i x 9 6 2 ，a n s ix 9 6 3 ，a n df i p s1 8 6 2 中规定密钥最短为1 6 0 b i t ，而h a r l e y 利用 s a t o h f g h 计算密钥长度为1 6 0 比特的椭圆曲线的点只需要2 5 秒，这为椭圆曲线 密码体制广泛应用提供了峰实的基础，为了提高安全性，一个系统可以很方便的 更换曲线，而我们采用s e a 算法至少需要几分钟，当然我们也不能抛弃s e a 算法， 这是曰前计算基于大素数域的椭圆曲线上点的最快方法。 椭圆曲线密码算法及其廊用 2 5 小结 这一章我们主要介绍椭圆曲线密码体制的基本理论，为后面几章椭圆曲线密 码体制的实现做准备： 1 )首先给出椭圆曲线的概念和基本特性，并讨论建立在有限域上的椭圆曲线及曲 线上的群运算法则： 2 ) 然后介绍椭圆曲线离散对数问题( e c d l p ) ，详细从多个角度比较了现存的三种 重要的公钥体制的优缺点； 3 ) 接着介绍了目前对一般和特殊椭圆曲线离散对数的常见的几种攻击方法： 4 ) 最后讨论安全椭圆曲线的选取，介绍了两种寻找椭圆曲线上点的个数的方法： s e a 算法和s a t o h f g h 算法。 第三章椭圆曲线密码协议 第三章椭圆曲线密码协议 很多基于有限域乘法群上的密码协议，例如d h 密钥交换，e i g a m a l 加解密， e i g a m a l 数字签名，d s a 数字签名等都可以移植到椭圆曲线上，这样的椭圆曲线 密码系统具有与现存的公钥密码体制具有相同的安全性，但密钥长度却相对要短。 较短的密钥意味着较窄的带宽和较小的内存要求。这些密码系统在某些内存和处 理能力都受限的环境如智能卡的设计中是相当重要。这些密码系统大致可以分成 以下几类：密钥交换密钥协商方案、消息加密解密方案、具有消息恢复不具有消 息恢复的数字签名方案、认证方案、r s a 类型的椭圆曲线密码系统、建立在环上 的椭圆曲线数字签名方案等。下面我们研究几类典型的椭圆曲线密码协议。 3 1 密钥交换协议 由于公钥体制比对称密码进行加解密速度慢很多，所以在实际的加密系统中 通常是利用会话密码( 分组密码或流密码) 对数据加解密，用密钥交换算法如d h 传递会话密码，该算法允许通信双方在不安全的媒介上安全地交换密钥。 e c d h 密钥交换如下：设e 是定义于某有限域c 上的有限加法群，p 是e 的 一个点， 是e 的包含点p 的一个循环子群，其阶为玎，系统公开e ，p ，n 。 1 ) a l i c e 随机产生吒e 2 ，打一2 】，计算包= 丸g ，并将q 发送给b o b ； 2 ) b o b 随机产生k 。【2 ，盯一2 】，计算q 6 = k g ，并将幺发送给a l i c e ： 3 ) a l i c e 计算。，岛= 女。k g ； b o b 计算k q 。= 女6 k 。g ； 于是，他们拥有的共同密钥是q = 。k g 安全性：窃听者可在a l i c e 与b o b 之间的公开信道上截获a l i c e 发给b o b 的见，( 或 b o b 发给a l i c e 的g ) 窃听者能破解他们共同密钥的关键是从q = 。g 中求出k 。， ( 或从q 。= k g 中求出k 。) ，显然这是椭圆曲线离散对数问题。所以该密码协泌的安 全性与求解椭圆曲线离散对数问题的困难性等价。 3 2 加密解密协议 3 2 1 e i g a m a l 椭圆曲线加密系统 e 1 g a m a l 是既可以用于加密又可以用于签名的密码体制。e l g a m a l 椭圆曲线自i 椭圆曲线密码算法及其麻瑚 律j 系统吲如下：设e 是定义于某有限域r 上的有限加法群，g ee ( c ) 是一个固定 点g 【j 点