（计算机应用技术专业论文）椭圆曲线密码体制的优化与设计.pdf

本文主要针对g ( 只) 域的椭圆曲线密码体制( e c c ) 进行了研究及优化。首先， 对点乘和应用层的核心运算舻+ 硷进行优化。接着，研究和分析了基于e c c 的各类 密码协议。针对密钥交换协议不能进行身份鉴别以及存在第三方攻击的问题，对其加 以改进；同时，对数字签名协议中的签名方程重新构造，并将优化的舻+ 堙算法用 于验证过程，提高了协议的执行效率。在上述研究基础上，本文根据具体应用需求进 行密码方案的设计。基于改进的椭圆曲线数字签名协议( e c d s a ) ，设计了一个安全、 商效的多重数字签名方案；将签名和加密相结合，给出一个具有前向安全性的、支持 第三方验证的签密方案。最后，根据上述的优化改进，设计和实现了一个椭圆曲线密 码系统，并将其应用于虚拟专用网的设计中 实验证明，本文的优化工作，使椭圆曲线密码系统的运行效率和安全性能在一定 程度上得到了提高，从而使它更适用于v p n 、无线网络、智能卡等资源受限的应用 环境。 关键词：椭圆曲线密码，域运算，点乘算法，密钥，密码协议 _，气n1# jt! t口；n、 苏州大学学位论文独创性声明及使用授权声明 学位论文独创性声明 9 5 6 9 8 7 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行研究工作所 取得的成果。除文中已经注明引用的内容外，本论文不含其他个人或集体已经发表或 撰写过的研究成果，也不含为获得苏州大学或其它教育机构的学位证书而使用过的材 料。对本文的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本人承 担本声明的法律责任。 研究生签名： 灶日 学位论文使用授权声明 期：丝蔓：墨：望 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论文合作部、中国 社科院文献信息情报中心有权保留本人所送交学位论文的复印件和电子文档，可以采 用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论 文的全部或部分内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 研究生签名：当垫聋 日期：垫翌( ：芰：兰墨 导师签名： 靼l 日期：型孥 椭圆曲线密码体制的优化与设计 引言 引言 随着互联网的迅速发展，人们可以方便地获取许多免费资源，但与此同时，信息 在传输过程中极容易受到攻击。对于这些网络攻击，除了制定相应法律来规范外，更 需要从技术层面上采取保护措施。密码技术就是一种有效的方法，它可以有效地应用 于信息加密、信息鉴别、数字签名等过程，从而防止网络电子欺骗。密码学的研究对 信息系统的安全起着极其重要的作用。 现代密码学的研究主要沿着两个方向前进，以d e s 为代表的对称密码体制和以 r s a 为代表的公钥密码体制。其中对称密码体制是传统密码技术所采用的方法，在 对称密码系统中，通信的双方协商一个预共享密钥，在对信息进行加密和解密时使用 相同的密钥。但对称密码系统存在着以下问题：首先密钥在协商过程中易被第三方窃 取，并且由于系统的每一对通信方都要有一个不同的预共享密钥，对于具有n 个用户 的网络，需要n ( n 1 ) 2 个密钥，在用户群不是很大的情况下，对称加密系统是有效的， 但是对于大型网络，当用户群很大，分布很广时，密钥的分配和保存就成了问题。随 着密码学的应用发展，这种密码体制的局限性越来越明显，人们迫切需要寻找新的更 加有效的密码体制。在这种情况下，公钥密码体制应运而生了。 公钥密码体制的设想最初是在1 9 7 6 年由d i f f i e 和h e l l m a n i l l 提出的。采用公钥密 码系统的每个用户都有一对选定的密钥，其中一个是公开的，称为公钥，另一个由用 户自己秘密保存，称为私钥在对信息处理时，分别使用用户的公钥和私钥进行加解 密，并且由公钥推导出私钥在计算上是不可行的。由于公钥密码体制的密钥分配和管 理简单，并且比较容易实现数字签名，因而在安全领域得到了广泛应用。目前已经有 若干种公钥密码体制问世，这些体制的安全性都基于复杂的数学难题。目前公认比较 安全和有效的公钥密码系统主要有三类：大整数因子分解系统、离散对数系统以及椭 圆曲线离散对数系统。基于前两种数学难题的典型公钥密码系统主要有r s a 和d s a ， 这也是现在广泛应用的公钥密码系统。但随着计算能力的提高，大数因子的分解速度 越来越快，人们必须采用更长的密钥才能保证系统的安全性，而密钥长度的增加带来 了加解密以及签名验证时运算量的增加，同时导致存储空间及网络传输数据量的随之 f f l t t 椭圆曲线密码体制的优化与设计 第一章概述 第一章概述 1 1 研究背景 目前，由于计算机网络技术的迅速发展，由网络通信而带来的安全问题引起了人 们的普遍关注，作为网络安全基础理论之一的密码学引起了人们的关注，吸引着越来 越多的研究人员投入到该领域的研究当中。同时，由于现实生活中的实际需要以及计 算技术的发展变化，在密码学的每个研究领域都出现了许多新课题、新方向。 在公开密钥密码领域，椭圆曲线密码体制( e c c ) 以其独特的优点引起人们的关 注，成为近几年来公开密钥密码学领域研究的新课题。e c c 是基于椭圆曲线离散对 数问题而设计的公钥密码体制，与现在广泛应用的公钥密码体制r s a d s a 相比，它 主要具有以下技术优势： ( 1 ) 安全性高 加密算法的安全性能一般通过该算法的抗攻击强度来反映。c e r t i c o m 的实验表 明，e c c 和其它几种公钥密码系统相比，其抗攻击能力具有绝对的优势。其中，1 6 0 位的e c c 与1 0 2 4 位的r s a d s a 具有相同的安全强度，而2 1 0 位的e c c 与 2 0 4 8 位的r s a d s a 具有相同的安全强度。由此可见，在相同的密钥长度下，e c c 所能提供的安全性要高得多 ( 2 ) 计算量小、处理速度快 虽然r s a 可以通过选取较小的公钥尺寸来提高公钥处理速度，从而提高加密和 签名验证的速度，但在私钥的处理速度上，e c c 远比r s a 快得多，实验已经证明， 在相同的安全强度下，e c c 总的速度可比r s a 快一个数量级。 ( 3 ) 存储空间占用小 一 e c c 的密钥尺寸和系统参数与r s a 相比要小得多，意味着它所占用的存储空 间要小得多，这对于密码算法在受限环境中的应用具有特别重要的意义。 ( 4 ) 带宽要求低 当对长消息进行加解密时，e c c 与r s a 具有相同的带宽要求，但当应用于短消 息时e c c 的带宽要求却低得多。而公钥加密系统多用于短消息。例如数字签名和对 称系统会话密钥的加密传递，因此带宽要求低使e c c 在无线网络领域具有广泛的应 第一章概述 蛰啮缋密码体制的优化与设计 用前景。 由于e c c 所具有的这些其它公钥密码体制所无法比拟的优势，使其迅速成为密 码学界研究的热点。在e c c 成为新的通用标准公钥密码体制之前，对它进行完善， 进一步加快它的运行速度，是密码学界的重要任务。 1 2 研究动态 目前，国内外很多研究机构及公司都开展了关于椭圆曲线密码技术方面的研究开 发，并且已经形成了各种相关的草案和标准文档。在标准化方面，g e e 、a n s i 、i s o 、 i e t f 、a t m 等都做了大量的工作，这些组织所开发的关于椭圆曲线密码体制的文档 标准大体可分为两类：一类是技术标准，即描述以技术支撑为主的e c c 体制，主要 有g e ep 1 3 6 3 、a n s ix 9 6 2 、a n s ix 9 6 3 等，这些技术标准规范了e c c 各种参数的 选择，并给出了各级安全强度下的一组e c c 参数。另一类是应用标准，即在具体的 应用环境中建议使用e c c 技术，主要有i s oh e c l 5 9 4 6 、i e t fp k i x 等。 1 2 1 国外研究动态 由于e c c 是一种非常有前途的公钥密码体制，很多国家都开展了对它的研究开 发工作。德国、日本、法国、美国、加拿大等国家的研究小组及一些公司已实现了基 本的椭圆曲线密码系统，已经有一些基于标准( 或草案) 的各种椭圆曲线加密、签名、 密钥交换的软、硬件问世。美国n e x tc o m p u t e r 公司已开发出快速椭圆曲线加密算 法。加拿大的c e n i c o m 公司开发了可实用的用于e c c 的集成电路，可实现高效加密、 数字签名、认证和密钥管理等。这些产品被广泛应用于保密通信、网络安全、电子商 务等方面。目前，椭圆曲线密码体制( e c c ) 已被一些公司、组织所采纳并应用到一 些资源受限的环境中，如嵌入式系统、智能卡等。c e c u m 公司已授权3 0 0 多家企业 使用它的e c c 密码技术，包括c i s c o 系统有限公司、摩托罗拉、p a i m 等企业。m o t o r a l a 公司将e c c 用于其c i p h e r n e t ，以此将安全性加入应用软件美国政府已经在移动、 无线环境中开始使用椭圆曲线密码算法。安全电子商务协议一s e t 协议的制订者已经 把椭圆曲线密码体制作为下一代s e t 协议中默认的公钥密码算法；几个国际标准化 组织也已把椭圆曲线密码体制作为新的信息安全标准。最近，在2 0 0 5 年2 月份，美 国国家安全局( n s a ) 已把e c c 指定为保护美国政府敏感信息和非普通通信的公钥 4 椭圆曲线密码体制的优化与设计第一章概述 系统的唯一标准。可以预见，e c c 技术在信息安全领域中的应用将会越来越广泛。 1 2 2 国内研究动态 近几年，我国的一些研究机构及公司也已开始对椭圆曲线密码体制进行研究开发 和应用，在“十五”期间，椭圆曲线密码技术被列为国家重点研究课题。 信息安全国家重点实验室己设立了一些与椭圆曲线密码技术相关的实验项目，并 已有一些理论成果问世。深圳市明华澳汉科技股份有限公司所开发的智能卡操作系统 s m a r t c o s 已经通过国家密码管理委员会、中国人民银行、各政府部门和国内外多个 大型商业机构认证。海南信安数据系统有限公司是一家专业研究椭圆曲线密码算法的 公司这两家公司联合开发出了国内第一个带椭圆曲线算法的智能卡s m a r t c o s - p k ( e c c ) 。另外，一些高校和研究机构也都投入到了对e c c 技术的开发研究中。 在中国颁布的无线局域网国家标准g b l 5 6 2 9 1 1 中，包含了全新的w a p i ( w l a n a u t h e n t i c a t i o na n dp r i v a c yi n f r a s t r u c t u r e ) 安全机制，这种安全机制由w a i 和w p i 两 部分组成，分别实现对用户身份的鉴别和传输数据的加密w a i 采用公开密钥密码 体制，利用证书对系统用户和a p 进行认证证书里含有证书颁发者以及证书持有者 的公钥和签名，这里的签名采用的就是e c c 的数字签名算法。 从总体上看，虽然椭圆曲线密码技术已引起了国内一些公司、组织、高校的关注， 相关的研究也越来越多，但目前国内对于e c c 的研究成果和成功产品还比较少。 1 3 研究内容及意义 1 3 1 本文研究内容 本论文的研究内容来源于江苏省自然科学基金项目：基于p k i 、e c c 的高强度 v p n 安全网关技术与核心系统的研究。基于项耳需求，本文对椭圆曲线密码技术进 行研究，对它的算法和协议进行了优化，在此基础上实现了密码系统，将其应用在 v p n 中。论文的研究内容主要包括以下几个方面： ( 1 ) 研究椭圆曲线密码体制的数学背景、相关概念和主要算法 研读现有的关于e c c 的草案、标准文档及相关文献资料，掌握椭圆曲线密码体 制的数学背景及相关概念，明确了它的关键算法和技术； ( 2 ) 对e c c 关键算法进行优化和改进 第一章概述 椭圆曲线密码体制的优化与设计 在椭圆曲线密码系统中，点乘运算是最关键、最耗时的运算，它决定着整个系统 的运行效率。本文对点乘运算和k p + ，q 运算算法进行优化，并从理论和实验两个方 面对优化算法进行分析； ( 3 ) 对协议的改进 分析e c c 三类基本协议：密钥交换协议、e c c 加密协议以及e c c 数字签名协议， 针对协议中存在的不足，提出改进方案； ( 4 ) 基于e c c 的密码方案的设计 要使椭圆曲线密码技术得以推广应用，就必须有基于该技术的密码方案的支持。 本文根据具体的应用需求和对现有方案的研究分析，设计了基于e c c 的多重数字签 名方案和签密方案； ( 5 ) 椭圆曲线密码系统的实现及应用 密码技术关系到国家和集团的切实利益，生产开发出具有自主产权的密码产品， 对国家和个人组织来说，都具有重要的现实意义。本文基于( 2 ) ( 3 ) 中对e c c 算法 的优化和协议的改进，设计实现了椭圆曲线密码系统，并将其应用于v p n 中。 1 3 2 本文研究意义 尽管欧美等发达国家在密码技术的理论和应用研究上都处于世界领先地位，并且 已经有了基于椭圆曲线公钥密码技术的密码类产品面世，但往往对我国采取禁运的政 策。并且由于我国在密码技术产品管理上实行专控，不能使用进口技术和产品。因此， 开展对椭圆曲线密码体制理论与应用的研究，开发出具有自主产权的密码产品，对我 们国家有着重要的现实意义。 椭圆曲线密码系统通常在两种有限域上实现：大素数域g f ( p ) 和二进制域 不同的 线密码 。因此， 椭圆曲线密码体制的优化与设计第一章概述 第二章：介绍椭圆曲线密码学的数学基础；给出二进制域上椭圆曲线的定义和表 示，并对椭圆曲线离散对数问题和椭圆曲线的安全攻击现状进行综述。 第三章：介绍了椭圆曲线密码体制的基本运算算法：域运算和椭圆曲线上点的运 算，并对点乘运算和舻+ 垃运算算法进行了优化，从理论和实验两方面对原算法和 优化算法进行对比分析。 第四章：对e c c 的协议进行优化设计。首先，分析现有协议的不足，对密钥协 商协议和数字签名协议进行优化改进；然后，根据具体应用需求，设计了两个基于 e c c 的密码方案：多重数字签名方案和签密方案。 第五章：基于优化的算法和协议，设计实现了椭圆曲线密码系统，并将其应用到 v p n 中，给出相应测试结果。 第六章：对本文所做工作进行总结，并对下一步工作进行展望。 7 第二章椭圆曲线密码学基础椭圆曲线密码体制的优化与设计 第二章椭圆曲线密码学基础 椭圆曲线理论是代数几何、数论和群论等多个数学分支的一个结合点，利用椭圆 曲线建立密码系统涉及到复杂的数学问题。本章将先对椭圆曲线密码学1 4 l 【5 】【6 】【7 1 的数学 基础进行介绍，然后根据椭圆曲线密码体制的攻击现状对其安全性进行分析。 2 1 群和域 2 1 1 群 群是由一个非空集合及一个二元运算构成的代数系统。 定义：设g 是一个非空集合，若在g 上定义一个二元运算满足以下条件： g 对运算0 是封闭的，即对任意4 ，b g ，有口o b g ； 结合律成立，即对任意口，b ，c g ，有0 0 b ) o c = 口o ( 6 0c ) ； 存在单位元e 使得对任意4 g ，有口。口= e o 口= 口； 对任意口g 有逆元口一，使得口- 1o 口= 口。口一= p ； 则称g 对运算0 构成群。 如果群g 对。符合交换律，即对任意a , b g ，有口0 b = b o 口，则称g 为交换 群或a b e l 群。 如果集合g 中只含有有限多个元素，则称 为有限群，此时，把集合g 中 元素的个数称为有限群 的阶。 设 是一个群，如果群g 中存在一个元素口，使得对群g 的任意元素b 都 存在一个整数i 使得b = 口，则称 是一个循环群，元素口称为g 的一个生成元。 2 1 2 域 定义：如果对于一个非空集合r ，对称为加法的代数运算0 和称为乘法的代数运 算圆满足： r 对加法运算。构成交换群( 加法的单位元称为零元) ； r 中至少含有一个非零元，r 对乘法运算圆封闭，对乘法0 满足结合律； 有乘法单位元e ，非零元有乘法逆元； 乘法交换律成立，左右分配律成立。 椭圆曲线密码体制的优化与设计 第二章椭圆曲线密码学基础 则称r 对该加法和乘法构成一个域。 如果集合f 中含有有限个元素，则称这时的域f 为有限域或g a l o i s 域，有限域 中元素的个数称为该有限域的阶。 通常在两种有限域上实现椭圆曲线密码算法：大素数域a f ( p ) 和二进制域 g f ( 2 “) ，由于本文选择二进制域的椭圆曲线密码体制进行研究，下面就二进制域的 椭圆曲线进行介绍。 2 2g f ( 2 ”) 有限域 有限域g f ( 2 ”) 包含2 ”个元素，g f ( 2 ”) 域上的元素是由一系列长度不大于m 的 多项式 口i s j - l x ”1 + 工”2 + a l x + ：q o ，1 ) ，组成的。对于有限域g f ( 2 ”) 的元素 通常有多种方法表示，一般常用的两种表示方法为：多项式基表示法和正规基表示法。 2 2 1 多项式基表示法 多项式基( p o l y n o m i a lb a s e ) 也称标准基( s t a n d a r db a s e ) ，是形如( 1 ，口，口2 ，口”1 ) 的 基，这里口是只上某个m 次不可约多项式的一个根。 多项式基是描述有限域g f ( 2 “) 最直观的方法。设： ，( x ) = x 8 + f m - i x ”_ + + 石x4 - f o ，z e ，f = o ，1 ，所一1 是e 上的1 1 1 次不可约多项式，那么有限域g f ( 2 ”) 可以看成是e 上所有次数小于m 的多项式的集合： f 2 舯= c k - i 工”_ 1 + 口。一2 工4 融+ + q x + a o ( a o ，1 ) ) 域中元素( d 。- l x “+ 口，一2 工”2 + - i - a i x - f a o ) 一般用长度为m 的二进制数串 ( 口“q ) 表示因此e 。= a m - i 工“+ a ，- 2 x ”2 + + 4 i x + a o ( a e o ，1 ) ) 就是所有 长度为n l 的二进制串的集合。其中不可约多项式，o ) 称为有限域g f ( 2 ”) 的定义多项 式。 在多项式基表示下的有限域g f ( 2 ”) 的算术运算定义如下： ( i ) 加法：( 口。- l t t l a o ) + ( 6 埘q b l b o ) = ( 气- i q c o ) ，其中q = q + 6 f 是按位异 或得到的。 ( 2 ) 乘法：( a 。- i a l a o ) ( k - l b l b o ) = ( ，厢_ l ，i ) ，其中( ，o ) 对应的多项 式。一l 工“+ + r l x + r o 是( 口。- 1 f 7 1 ) 对应的多项式乘以( k i b , b o ) 对应的多项式 9 第二章椭圆曲线密码学基础椭圆曲线密码体制的优化与设计 再除以不可约多项式，( d 所得的余式。即，胂一。x “+ + r ，x + r o 等于下式： ( a m - i x ”- 1 + + 口l x + 口o ) ( 6 卅一l x ”。1 + + 6 l x + b 0 ) r o o d f ( x ) 因此在多项式基表示下，域g f ( 2 ”) 的乘法可以看作是模不可约多项式厂( 功意义 下的多项式乘法。 ( 3 ) 求逆：在多项式基表示下，域乘法运算被看作是模f ( x ) 意义下的多项式乘 法。因为定义多项式f ( x ) 不可约，所以对任意一个元素e 只对应的多项式e ( x ) 都 有： g c d ( f ( x ) ，口( 力) = l g c d o 表示求最大公因式。由于存在多项式s ( 力和f ( 力，使得 ， ) s ( 功+ p ( 力f ( x ) = 1 所以 口( 功f ( 功zl ( m o d f ( x ) ) “x ) 对应的元素t = e 一，称为元素e 的逆。 从另一个角度看，g f ( 2 ”) 可以被看作是e 上的m 维向量空间。在多项式基表示 下，这个向量空间的基向量就是( 1 ，x ，工”1 ) ，工是f ( x ) 在g f ( 2 ”) 上的根，那么 g f ( 2 ”) 中任何一个元素都可以用这组基唯一表示。 2 - 2 2 正规基表示法 对于一个n 1 次不可约多项式g ( x ) ，如果g ( x ) 的m 个根，口，。在e 上是线 性无关，那么这m 个根构成了在e 上的一组基作为g ( x ) 的m 个共扼根，它们 可以写成某一个根a 的幂次，即口。= a ，= a 2 ，口2 = a ”口。- i = a 2 一。通常称形如 ( a ，0 2 , a 2 2 ，0 2 - ) 的基为正规基( n o n n a lb a s e ) ，对应的不可约多项式g c x ) 为正规多 项式，根a 为正规元确定了正规基后，g f ( 2 ”) 中任何一个元素a 都可以表示为该 正规基基向量的线性组合，即 a = a o o + a l a 2 + + 4 。1 a ”一， a l 0 ，1 ) ，0 i m - i ， 也就是说a 可以表示为正规基下的向量a = ( a m - 1 ，a i ，a o ) 。 对任意i , j ，0 s i , j 脚一1 ，4 ，a 是嘞，口l ，1 的线性组合。特别地， 也 1 0 椭圆曲线密码体制的优化与设计 第二章椭圆曲线密码学基础 其中，a 为e 上的m m 矩阵，称为关于a 的正规基的乘法表。乘法表与正规基表示 下的乘法密切相关。若对于只的元素a ，6 ，c 有c = a b ，记a 中第i 行j 列元素为五， 那么它们的坐标向量之间有如下关系： m 一- i m 一- 1 c k = a l + l t 屯+ i 乃0 k m l 乘法表中非零元素的个数称为正规基n 的复杂度，记为c n 。对所有所 一1 ，只至 少存在一个正规基。对e 在e 上的任意正规基，都有c 。 = 2 m 1 乘法表复杂度 最小的正规基被称为最优正规基( o p t i m a ln o r m a lb a s e ，缩写为o n b ) 。 尽管表示方法不同，但是无论是多项式基还是正规基，它们都可以表示同一有限 域。在这两种基表示下，两个集合的元素之间存在一个一一对应关系，利用这个一一 对应可以实现两种基之间的互相转换。 2 3w e i e r s t r a s s 方程 设c 是有限域，则其上的韦尔斯特拉斯( w e i e r s t r a s s ) 等式： 】，2 z + a , x y z + a 3 y z 2 = z 3 + 4 2 x 2 z + a 4 x z 2 + 口6 2 3口1 ，口2 ，口3 ，4 4 ，a 6ee 称为w e i e r s t r a s s 方程。 为方便起见，w e i e r s t r a s s 方程可写成仿射坐标的形式，令茗= x ir ，y = y z 则 w e i e r s t r a s s 方程可写成：y 3 + 口i x y + a 3 y = + 口2 工2 + a | i x + a 6 对任意域，w e i e r s t r a s s 方程的判别式是= 霹6 l 一8 酲一2 7 醪+ 9 b 2 b 4 b 6 ，其中 6 2 = 砰+ 4 a 2 ，b i = 口l 码+ 2 a 4 ，b 6 = q 2 + 4 a 6 ，6 l = 口? 一a l a 3 a 4 + 4 a 2 a 6 + 4 。q 2 一a ： 当a 事0 时，域上的点集e # ( x ，y ) ij ，2 + 口l x y + a 3 y = + 口2 x 2 + 吼x + 吼) u o ) ， 其中a l , a 2 ，口，a 。，a 。，d 为无穷远点，叫做域上的椭圆曲线。这时，j = a 叫做椭圆曲线e 的j 不变量，记作j ( e ) ，其中c 4 = 酲- 2 4 b 4 。 2 4 二进制域椭圆曲线 2 4 1 椭圆曲线的定义 椭圆曲线的研究来源于椭圆积分与茜，这里e ( 刁是x 的三次或四次多项式。 由于这样的积分不能用函数表示，为此引入椭圆曲线的概念。椭圆曲线指的是，在射 影平面上满足w e i e r s t r a s s 方程y 2 z + a i x y z + a 3 y z 2 = 肖3 + 口2 x 2 z + a 4 勉2 + 吼z 3 的 墨三兰堕堕些丝童塑兰茎堂堂旦些垡查塑堡型竺垡些皇堡生 所有点的集合，且曲线上的每个点都是非奇异( 或光滑) 的。所谓“非奇异”或“光滑” 是指曲线上任意一点的偏导数不能同时为0 ，即满足方程的任意一点都存在切线。满 足非奇异方程的所有点外加一个无穷远点0 ，就组成了椭圆曲线。 2 4 2 椭圆曲线域参数 有限域凹( 2 “) 上的椭圆曲线方程为：y 2 + 砂= x 3 + a 2 x 2 + 吒，椭圆曲线方程是 由参数a 2 ，a 6 确定。 椭圆曲线域参数是用以构造一个椭圆曲线密码系统所需的参数集，包括：有限域、 椭圆曲线、椭圆曲线的基点、基点的阶。当选择二迸制域上的椭圆曲线e ( 只。) 时， 它是由一个七元组：t = ( m ，( x ) ，a ，6 ，g ，矗) 构成的，其中厂( 并) 确定了有限域的定义 多项式，a 、b 确定了椭圆曲线e 的方程，g 是所定义椭圆曲线的基点( b a s ep o i n t ) ，n 是基点g 的阶，且要求n 为大素数，h 是n 关于撑e ( 只) 的协因子，即h 酬e ( c ) i n 。 椭圆曲线方程的所有解( x ，y ) ，y ，) ，连同“无穷远点”( 记为o ) 组 成的集合记为e ( 只) ，e ( 只) 即表示了二进制域上的一个椭圆曲线。其中椭圆曲线 e ( 只) 上的点数用榉e ( ) 来表示。其判别式= 一b 。椭圆曲线非奇异当且仅当b 0 a 2 4 3 椭圆曲线运算规则 设o 是椭圆曲线的无穷远点，椭圆曲线e ( 只。) 上所有的点对应下面的运算规则： 对于所有的p = ( ，y i ) e ( e ) ，有p + 0 = d + p = p ； 若p = ( 而，y 1 ) e ( ) ，则有( 而，朋) + ( 一，而+ y i ) = 0 ，则可得到点p ( 黾，乃) 的 逆元为：一p = ( x i 毛+ y 1 ) ； 点加运算：若p = ( 而，y 1 ) e ( e ) ，q = ( x 2 ，) ，2 ) e ( 0 ) ，p + q = ( x 3 ，乃) ，且 p q ，则有：r 而= 名+ a + 而+ x 2 + 口 ly 3 = 名( 而+ x 3 ) + x 3 + y l 其中，a = 执+ y 2 ) ( 而+ x ：) ，点加运算的几何意义如图2 1 所示。 倍点运算：若p = ( t ，m ) e ( ，_ ) ，p + p = 2 p = ( 南，儿) ，则可得到下式： l x ，2 尤一2 黾 l y , = 彤( 而一x 2 ) 一m 其中，a = + y i ，倍点运算的几何意义如图2 2 所示。 1 2 椭圆曲线密码体制的优化与设计 第二章椭圆曲线密码学基础 口= 屯叼- 。歹 一= v 。 、：二：一， r p = 章t ，1 ) 盂t 氛) 扑 图2 1g f ( 2 ”) 域椭圆曲线点加示意图 p 2 甑， 1 1。p - 。“n 八 | 7 i r = 炎 、 图2 2g f ( 2 ”) 域椭圆曲线倍点示意图 点乘运算：一般地，将，+ p + + p 记为k p ，称为椭圆曲线上的点乘运算， 即k p = p + 尸+ + p ，特别地，定义o p = 0 。 2 5 椭圆曲线离散对数问题 椭圆曲线离散对数问题( e c d l p ) 是椭圆曲线密码学的基础。设e 是定义在有限域 上的椭圆曲线，点乘k p = q ，其中p 、q 是椭圆曲线e 上的点，k 1 ，拧一1 】，n 是 椭圆曲线的阶，由给定的p 和q 求解k ，称为椭圆曲线上的离散对数问题。由椭圆曲 线的运算规则可知，根据k 、p 计算q 是相当简单的；反之，由q 、p 求出k 在计算 上则是非常困难的，这就是椭圆曲线离散对数问题的难解性。 椭圆曲线密码系统的安全性建立在e c d l p 的难解性上。其它常用的公钥密码系 统( p s a i ) s a ) 的安全性则是建立在分解两个大素数积的基础之上的，解这类问题现在 第二章椭圆曲线密码学基础 椭圆曲线密码体制的优化与设计 通用的方法，是用一般数域筛法进行因子分解，它是亚指数时间复杂度的算法。与整 数因子分解问题和一般离散对数问题( d l p ) 不同，目前已知的求解椭圆曲线离散对数 问题的最佳算法是p d 肌 订一p 因子分解算法，它是全指数时间复杂度的算法因此， 一般的用于离散对数的有效攻击不能应用到e c d l p 上来。从这种意义上讲，椭圆曲 线密码系统( e c c ) 是目前安全性最高的公钥密码系统a 2 6 椭圆曲线的安全攻击现状 对于椭圆曲线密码体制中的一些特殊椭圆曲线，如超奇异椭圆曲线和某些反常椭 圆曲线，其上的离散对数问题是相对容易求解的，因此应该尽量避免使用。在具体应 用时，可以通过简单的检测来确定所选择的椭圆曲线是否属于以上两种情况，从而避 免使用这些椭圆曲线。下面分别从特殊曲线和一般曲线两种情况对椭圆曲线的安全攻 击现状进行介绍。 2 6 1 对特殊曲线的攻击 由于一些特殊曲线的密码体制能够较快实现，过去它们曾经被建议用以构造密码 体制，近年来，由于对几类特殊曲线的攻击已有了比较有效的方法，如：m o v 方法 和s m a r t 方法。因此，在系统进行椭圆曲线选取时，已禁止使用这几类曲线。 1 m o v 方法 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 i s 提出了一种将e c d l p 归约为有限域上 离散对数问题的方法，这种方法可以采用指数计算法，但这种方法只适用于超奇异椭 圆曲线。对于超奇异椭圆曲线m o v 算法利用w e i l p a r i n g 方法，可建g f ( q ) 扩域上 椭圆曲线的加法群与g f ( q ) 的乘法群之间的联系，特别是把计算椭圆曲线的e c d l p 转化为计算有限域的乘法群的离散对数，这也证明了建立在e c d l p 上的椭圆曲线密 码体制比基于有限域上的离散对数密码体制更具优越性。 i e e ep 1 3 6 3 ，a n s ix 9 6 2 和a n s ix 9 6 3 在椭圆曲线系统有关标准中都己明确 禁用此类超奇异椭圆曲线。 2 s m a r t 方法 设q 是素数，对定义在e 上，当# e f g ) = g 时的椭圆曲线e 称为“畸形” ( a n a m a l o u s ) i 抽线。s m a r t p l 在1 9 9 8 年提出了一种删e o ( 1 n q ) 时间内求解的方法，同 1 4 椭圆曲线密码体制的优化与设计 第二章椭圆曲线密码学基础 时s e m a e v 0 0 1 也给出了一种在d ( 1 n g ) 时间内求解的方法。s m a r t 方法就是构造了e ( 疋) 到兄的加法群的一个同构映射，使得在多项式时间内可求解这类e c d l p ，因此对于 畸形椭圆曲线也应避免使用。 2 6 2 对一般曲线的攻击 对一般曲线的攻击主要有：大步小步法和p o l l a r dp 方法。 1 大步小步法 1 9 7 8 年以前求解e c d l p 的最好算法是s h a n k s 的大步小步( b a b ys t e pg i a n ts t e p ) 算法【1 1 l 。设群的阶为n ，令，= i ，取工= r f ，n l 可唯一表示成肌= a o l + b o ，也就 是q = m p = l p + b o p 。依次对b = 0 , 1 ，2 ，l 计算6 尸并列表；依次对a = 0 ，1 ，三计 算q a p ，并且在并列表查找，这样可以得到m 。这一算法的时间复杂度为d ( i ) ， 空间复杂度也为d ( 甩) 。用“穷搜索”方法求m 时，其时间复杂度为0 ( 功，空间复 杂度为，。因此这一算法是对“穷搜索方法在时间和空间上的一种折衷。 2 p o l l a r dp 方法 1 9 7 8 年p o l l a r d 提出了一种概率求解的方法【1 2 】，其时间复杂度大约是d ( 荔2 ) ， 与s h a n k s 的大步小步法相当，但由于其空间复杂度仅为o ( i ) ，所以一般认为p o l l a r d 的方法优于大步小步法。1 9 9 3 年，o r s c h o t 和w i e n e r 提出了分布式p o l l a r di d 算法， 时间复杂度约为o ( 4 - 磊( 2 r ) ) ，其中r 表示进程数。目前分布式p o l l a r dp 算法是已 知的对一般椭圆曲线离散对数最好的攻击方法。攻击者利用算法p o l l a r dp 攻击的途 径有硬件攻击( h a r d w a r ea t t a c k s ) 和软件攻击( s o f t w a r ea t t a c k s ) 。硬件攻击需要攻击者 有丰厚的经济实力来制造一种特殊用途的硬件用以并行计算。 c e l t i o d m 的e c c 2 k - 1 0 8 挑战是选择基于有限域的k o b l i t z 椭圆曲线，系统的主要 安全参数，即所选基点的阶是1 0 8 比特。2 0 0 0 年4 月r o b e r th a r l e y 等人利用大约9 5 0 0 台计算机联网经过四个月将其攻破，他们采用的就是并行的p o l l a r d 算法。e c c 2 k - 1 0 8 的攻破所做的工作相当于r s a - 1 5 5 分解( 5 1 2 位长的r s a 模数) 7 - 作的5 0 倍，据 c e r t i e o m 预测解决e c c 2 k - 1 6 3 挑战需要e c c 2 k 1 0 8 攻破工作的一亿倍。 图2 3 是加拿大c e r t i c o m 公司对不同的公钥密码算法进行攻击所得到的实验结 果。由此可以明显看出，与r s a d s a 相比，在相同的密钥尺寸下，椭圆曲线密码系 统的抗攻击性要强得多。 1 5 第二章椭圆曲线密码学基础 椭圆曲线密码体制的优化与设计 善 薹 船 墨露鲫阿( 姗融) 图2 3e c c 和r s a d s a 算法抗攻击比较图 c e r t i c o m 的实验结果使我们更加相信椭圆曲线离散对数问题的难解性和椭圆曲 线密码体制的安全性。 2 7 本章小结 本章主要介绍了椭圆曲线密码学的数学基础：群和域、w e i e r s t r a s s 方程、及二进 制域上椭圆曲线的相关定义；并介绍了椭圆曲线密码学的安全基础一椭圆曲线离散对 数问题；最后对椭圆曲线密码算法的攻击现状进行了综述。随后各章所要介绍的椭圆 曲线密码技术，是建立在本章密码学理论基础之上的。 l 椭圆曲线密码体制的优化与设计 第三章e c c 关键算法的研究和优化 第三章e c c 关键算法的研究和优化 椭圆曲线密码体制的运算主要包括域运算和椭圆曲线点运算两个层次。其中，域 运算与椭圆曲线点的运算相比，耗费时间较短，并且现有算法己较为成熟，而椭圆曲 线运算层中的点乘运算则是整个系统中最耗时、也是调用最为频繁的运算，它对整个 系统的运行效率起着决定性的作用。因此，对点乘算法的研究优化有着重要意义。本 章将对e c c 的主要运算包括：域运算、点乘运算的相关算法进行研究，在分析现有算 法的基础上，对e c c 的关键算法一点乘算法和应用层的核心运算舻+ 坦的算法进行 优化。 3 1 椭圆曲线上的运算 椭圆曲线密码系统的运算，可分成底层运算和高层运算两个层次。其中，底层运 算主要是域元素的相关运算；而高层运算则是椭圆曲线上点的相关运算。这两层所涉 及到的主要运算如图3 1 所示。 图3 1e c c 主要运算结构简图 由于点运算层中的点加运算和倍点运算规则在2 2 中已有介绍，因此在这里，将 1 7 第三章e c c 关键算法的研究和优化椭圆曲线密码体制的优化与设计 着重于对域元素的运算和点乘运算进行介绍。另外，由于在椭圆曲线数字签名和密钥 交换等多方协议中，都要用到k p + 坦的运算，因此，本章也将对该运算的算法进行 研究优化。 3 2 g f ( 2 ”) 域运算 g f ( 2 ”) 的域运算主要包括有限域加、模化约、平方、求逆和乘法运算。目前， 关于域运算的算法，研究已经比较成熟，相关成果也比较多5 】【1 3 1 1 4 1 。域运算与有限 域的定义多项式是直接相关的，设，( 功是有限域的定义多项式，下面分别对域元素 的相关运算算法进行介绍。 1 有限域加 有限域加是最直接、最容易实现的运算，其本质就是域元的异或运算。由于 a b z a + ( - b ) p - - - a + b ( m o d 2 ) ，因此，有限域的减法操作本质上跟加法操作是相同的。 算法3 2 1 给出了有限域加减的运算算法。 算法3 2 h 有限域加法运算 输入：域元素a = ( a 埘- i a 2 a l a o ) 、b = ( k i b 2 b l b o ) 输出：c = ( c 。- l c 2 c 1 c o ) = 口0 6 ( 1 ) 对i 从0 到m ，执行； 如果a l = 玩则c i = 0 否则= 1 ( 2 ) 返回c 2 模化约 设，( x ) = x ”+ ，一，并且域元素的表示形如a t x 当域元素经过运算最高 次数超过m - 1 时，就要对其进行模化约运算。模化约运算可以根据欧几里德算法的思 想来实现，当不可化约多项式八力是三项式或五项式时，模化约操作可以得以高效 实现。 算法3 2 2 模化约运算 输入：大整数口= ( q a l a 。) ，f = ( 厶厶i z 厶) ( f m 一1 ) 输出：c = a r o o d 厂 ( 1 ) 对i 从t 降到m ，执行： 椭圆曲线密码体制的优化与设计 第三章e c c 关键算法的研究和优化 如果口，0 则 对于j 从0 到m - 1 置a i 七- n 。+ i + ( 2 ) 置c 卜口 ( 3 ) 返回c 3 有限域乘 对于域元素a 乘以x ，若。= 0 ，则算法的结果实际上只是左移一位；若a 剃= l ， 则还需要对0 ) 进行模化约。根据以上分析a b m o c l f ( x ) 按下列步骤进行计算。 4 b m o d f ( x 、 = ( 口。一l x ”1 + + 口2 x 2 + 口1 x + a o ) b m o d f ( x ) = ( 口。一1 x ”一1 6 + + a 2 x 2 b + a l x b + 口o b ) m o d f ( x ) = ( d f f m _ l x ”1 b ) m o d f ( x ) + + ( q x b ) m o d f ( x ) + ( a o b ) m o d f ( x ) ( 3 - 1 ) 根据公式3 1 ，可得到有限域乘运算的算法3 2 3 。 算法3 2 3 ：有限域乘运算 输入：口= ( 。a , a o ) ，b = ( k ，岛) ，f = ( ，0 z 五) 输出：c = a b m o d f ( 1 ) 若a o = l 则c 4 - - - b ： 否则c4 - - 0 ( 2 ) 对于i 从l 到m 1 执行： b4 - - 6 x m o d f ( x ) i f 珥= lt h e n c4 - - c + b ( 3 ) 返回c 4 有限域平方 由于口， o 1 ) ，可得4 2 = q ，则口2 = ( 口，一) 2 = o q 2 毛矗= 口而“，由此 可得到有限域平方的算法3 2 4 。 算法3 2 4 ：有限域平方运算 输入：4 = ( 口“口2 q ) ，f = ( ，肼厶一i 石厶) 输出：c = ( c c 2 c i 白) = a 2 m o d f ( 1 ) 置c 卜0 1 9 第三章e c c 关键算法的研究和优化 椭圆曲线密码体制的优化与设计 ( 2 ) 对于i 从0 到m - i 执行： c 2 j 卜。q ( 3 ) c ( - - - c m o d f ( 4 ) 返回c 当采用正规基表示法来表示域元素时，则域平方运算只需要循环右移一位即： a 2 = ( 口m 一2 a o a m 1 ) 。 5 有限域求逆 域元素求逆方法主要基于扩展的欧几里德定理。算法3 2 5 一l 给出了基本的利用 扩展的欧几里德求域元素逆的算法。 算法3 2 5 一l ：求逆运算 输入：a f ，a 0 输出：a 。m o d f ( x ) ( 1 ) b 卜1 , c 卜o ，u 卜a ，v 卜， ( 2 ) w h i l ed e g ( u ) 0 d o j ( - - - d e g ( u ) 一d e g ( v ) i f ， 0t h e n 甜v , b 营v ，b c , j ( - - - ( 一d 却卜甜+ x j y ，6 扣b + x c ( 3 ) 返回b 其中d