《椭圆曲线密码快速算法理论-丁勇 著-人民邮电出版社2012.10-ISBN 9787115289438.pdf》由会员分享，可在线阅读，更多相关《椭圆曲线密码快速算法理论-丁勇 著-人民邮电出版社2012.10-ISBN 9787115289438.pdf（298页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、目录封面扉页版权前言第1章 椭圆曲线密码简介1.1 无穷远点1.2 数论相关概念1.2.1 同余和剩余类的概念1.2.2 Euler定理和中国剩余定理1.3 有限域简介1.4 椭圆曲线简介1.4.1 椭圆曲线的概念1.4.2 GF(p)上的椭圆曲线群1.4.3 GF(2m)上的椭圆曲线1.4.4 ECC的困难问题1.4.5 ECDSA算法1.5 ECC的安全性分析1.6 总结第2章 ECC上的点计算及几种常见的算法2.1 点计算算法即计算量分析2.2 射影坐标2.3 总结第3章 基于非邻接形式（NAF）的快速算法3.1 w-NNAF表示3.1.1 引言3.1.2 NAF和NAFw3.1.3 w
2、-NNAF表示3.1.4 w-NNAF分析3.1.5 总结3.2 Koblitz曲线上的多比特组合方法3.2.1 引言3.2.2 Solinas方法3.2.3 多比特组合方法3.2.4 总结3.3 RTSNAF方法3.3.1 引言3.3.2 RTSNAF方法3.3.3 总结3.4 -NAFw窗口技术3.4.1 引言3.4.2 自同态3.4.3 -NAF分解3.4.4 -NAFw窗口技术3.4.5 总结3.5 窗口3NAF的联合稀疏形式3.5.1 引言3.5.2 JSF表示3.5.3 WT-JSF3.5.4 总结3.6 通用的-NAF分解方法3.6.1 引言3.6.2 通用-NAF分解3.6.3
3、 总结第4章 JSF与Frobenius映射的结合4.1 引言4.2 Lee等的方法4.2.1 Frobenius表示4.2.2 方法14.2.3 方法24.3 与JSF的结合4.4 总结第5章 基于GCD算法的高速带模除法5.1 引言5.2 常规GCD算法5.3 改进的GCD算法5.4 GCD算法的扩展5.4.1 A.Zadeh的扩展5.4.2 新算法的扩展5.5 数值运算结果5.6 总结第6章 基于双基表示的快速算法6.1 引言6.2 半点运算6.3 双基数字系统（DBNS）6.4 改进的双基表示与半点方法6.4.1 Extend DBNS方法6.4.2 双基链和半点方法796.4.3 提
4、出的算法6.4.4 数值运算结果6.4.5 总结6.5 基于半点与多基表示的快速标量乘算法6.5.1 多基表示6.5.2 新的标量表示及标量乘算法6.5.3 数值运算结果6.5.4 总结第7章 基于双基数链的Tate对优化算法7.1 引言7.2 双线性对7.2.1 扭转点7.2.2 有理函数7.2.3 零点和极点7.2.4 除子7.2.5 Tate对7.2.6 Tate对的Miller算法7.2.7 Tate对的计算实例7.3 基于双基数链的Tate对优化算法7.4 算法7.3的复杂度分析7.4.1 TDBL的计算7.4.2 TTRL的计算7.4.3 TDBL_ADD的计算7.4.4 TDBL
5、_SUB的计算7.4.5 TTRL_ADD的计算7.4.6 TTRL_SUB的计算7.5 算法之间复杂度比较7.6 结论附录参考文献桂林电子科技大学学术著作出版基金资助出版ELLIPTIC CURVE椭圆曲线密码快速算法理论丁勇著人民邮电出版社北京图书在版编目（CIP）数据椭圆曲线密码快速算法理论/丁勇著.-北京：人民邮电出版社，2012.10ISBN978-7-115-28943-8.椭.丁.椭圆曲线算法理论.0187.1中国版本图书馆CIP数据核字（2012）第169133号内容提要本书以作者及其研究组多年的研究成果为主体，结合国内外专家及学者在椭圆曲线密码快速算法方面的代表性成果，系统论
6、述了这一领域的主要研究内容。本书分为两个部分，共7章。第一部分（第1、2章）讲述了研究椭圆曲线密码体制所需的基础知识及椭圆曲线上点的计算；第二部分（第37章）讲述了椭圆曲线密码的快速算法及其分析，主要包括非邻接形式（NAF）的改进形式，基于最大公约数（GCD）算法的高速带模除法，基于多基表示的快速算法，基于双基数链的Tate对优化算法。本书既可以作为密码学、信息安全、计算机科学等相关专业的研究生教学参考书，也可作为教师和相关科研人员的参考书。椭圆曲线密码快速算法理论著丁勇责任编辑王建军执行编辑代晓丽人民邮电出版社出版发行北京市崇文区夕照寺街14号邮编100061电子邮件网址http:/三河市海
7、波印务有限公司印刷开本：78710921/16印张：112012年10月第1版字数：245千字2012年10月河北第1次印刷ISBN978-7-115-28943-8定价：45.00元读者服务热线：(010)67119329印装质量热线：(010)67129223反盗版热线：(010)67171154广告经营许可证：京崇工商广字第0021号前言自从W.Hellman和M.E.Hellman于1976年提出公钥密码思想以来，由于其良好的性质以及现代通信网络的发展对信息安全技术需求的强烈增长，公钥密码体系得到了广泛的应用和发展。目前使用较为广泛的公钥密码体系是RSA，但是它也有其局限性，由于存在着
8、亚指数攻击，随着计算能力的不断增强，RSA不得不提高密钥长度来保证其安全强度。1985年提出的椭圆曲线密码体系（ECC，Elliptic CurveCrypto System）是一种基于椭圆曲线群上的新的公钥体系，相对 RSA而言，它具有安全强度高、密钥长度短、计算速度快、节约通信带宽、节省存储空间等优点，逐渐成为理论研究的热点和实际应用的首选。而对于ECC的快速实现来说，最为关键的因素就是标量乘法kP的计算，因此研究标量乘法的快速算法具有很好的应用前景和迫切的实际需求。1948年 Shannon发表了划时代的“通信的数学理论”1，宣告了信息论的诞生。60多年后的今天，通信、计算机和网络技术的
9、发展已将人类社会推进了一个崭新的信息时代。随着计算机及通信技术的快速发展，数字化、信息化、网络化正冲击、影响并改变着我们生活的方方面面。自古以来，通信安全保密就成为各国军队和政府高度关注和把持的领域。孙子兵法云：“知己知彼，百战不殆”。因此，如何保证己方信息不被敌方知道就成了战场上的一个决定胜负的因素。历史上的战争，特别是在两次世界大战中，谁能在通信保密、密码分析上占据优势，往往就能在战争中取得主动，有些时候甚至成为扭转战局的关键。因此，早期密码的主要应用就是使用对称加密体制对通信的信息进行加密，以保证自己的情报不被敌方获悉。在信息社会中，信息是一种重要的战略资源，因特网已经成为世界各国获取经
10、济、军事和科技情报的极其重要的战场。信息高速公路为跨国搜集各种战略信息提供了新的机会，国际上围绕信息的获取、使用及控制的斗争亦愈演愈烈。“谁掌握了信息，控制了网络，谁就将拥有整个世界”（托夫勒）。一个国家的信息获取能力及在社会生产生活领域中“制信息权”的大小，成为了这个国家在生存与发展的竞争中能否占据主动的关键。信息安全已成为信息社会亟需解决的重要问题之一。在 21 世纪，保障信息安全是综合国力、经济竞争能力和生存能力的重要组成部分，是当前世界各国奋力攀登的制高点。自从20世纪70年代中期Diffie和Hellman提出了公钥密码体系的思想2以来，密码学中爆发了一场革命。从那时起，密码学理论和
11、技术已不再是被少数人掌握并服务于政府、军事、外交等神秘领域，而是“飞入寻常百姓家”。基于文献2思想的公钥密码体系以及1977年美国NBS制定的公开的数据加密标准DES（Data EncryptStandard）3成为了现代密码学诞生的两个标志。公钥体制的最大特点就是采用两个密钥将加密和解密功能分开：一个公开作为公钥（它的名称由此而来）；一个为用户专用，作为私钥。通信双方无需事先交换密钥就可以进行保密通信，而要从用户公开的公钥以及可得的明文和密文中分析出私钥在计算上是不可行的。若以公钥作为加密密钥，以私钥作为解密密钥，可实现多个用户加密的消息只能由一个用户解读。反之，如果使用私钥作为加密密钥而将
12、公钥作为解密密钥，则可实现一个用户加密，多个用户解读。公钥体制的出现，标志着保密学理论与技术划时代的革命的爆发，主要体现在以下几方面：第一，传统的对称加密体制主要功能是信息保密，而公钥体制则还可以实现消息的认证；第二，公钥体制无需实现交换密钥，大大简化了密钥分配的工作量，尤其适用于当前的大型动态网络；第三，公钥体制实现了密码学和数学（如数论、抽象代数、复杂性理论、组合数学、概率论等）、信息论、计算机科学以及微电子、量子理论等学科的交叉，大大丰富了密码学的内容，为密码学的研究提供了强有力的理论工具和应用领域。基于 Diffie-Hellman 的思想，公钥密码算法的设计成为了密码学家研究的重点。
13、许多密码学家提出了各种不同的公钥密码算法，有的是成功的，而有的是失败的。包括背包体制47、Willamas体制8，9、ELGamal体制10，11、RSA体制1214、椭圆曲线密码15，16以及新兴的辫群公钥密码体系1720和NTRU21等。由于公钥密码体系良好而特殊的性质，当前信息技术的高度发达导致的信息安全需求的多样性和爆发性，它被广泛地应用于信息安全的各个领域，用于构造各种密码应用和安全保护，如消息加密、认证和密钥协商、身份认证、数字签名、数据完整性保护、特殊数字签名、电子选举、电子商务等，特别是以CA和证书为支撑的PKI更是成为构建大型动态安全网络必需的基础设施。在公开密码体制中，密钥
14、对的选择要保证从公钥求出私钥等价于要求解一个困难的计算问题。公开密钥方案要求参与通信的双方知道一对密钥：私钥不能被其他参与方知道；公钥则以公开的方式保存起来，以便在同一安全方案下的参与方都知道。私钥和公钥通过单项函数联系起来：知道私钥可以很容易地得到公钥，但是知道公钥却很难得到私钥。通常情况下，公钥连同公钥算法一起保存在软件中，而私钥则以硬件的形式保存起来，避免对私钥的截取和篡改。对于N个通信方的网络来说，一方若需要跟网络中任何一方进行安全通信，则只需要保存自身的一个私钥，与其他参与方通信的时候查找相应的公钥即可。很明显，这种方案很好地解决了对称密钥方案的密钥管理问题，更主要的是，有些公开密钥
15、算法可进行数字签名。构成常用公钥密码基础的困难问题是如下的数论问题。1.整数的因子分解问题，其困难性是RSA公钥密码安全性的基础。2.离散对数问题，其困难性是 EIGamal 公钥密码及其变体（如数字签名算法）安全性的基础。3.椭圆曲线离散对数问题，其困难性是椭圆曲线公钥密码安全性的基础。目前广泛应用于实际系统的公钥密码算法是RSA体制。它的困难性问题是基于大整数的因式分解问题，而大整数的因式分解问题是数学上的著名难题，至今没有有效的方法予以解决，因此可以确保RSA算法的安全性。该体制简述如下：独立地选取两个大素数p、q，计算n=pq，其欧拉函数(n)=(p1)(q1)；随机选择一个整数1e(
16、n)，计算d=e1(mod (n)，取公钥为n、e，私钥为d。对于明文m，加密算法为c=mx mod n，其中x为e（公钥加密）或者d（私钥加密）。椭圆曲线作为代数几何中的一个重要问题，已经有100多年的研究历史，积累了大量的研究文献。直到 1985 年，Kolitz 以及 Miller 才分别独立将其引入密码学领域，构造了ECC（椭圆曲线密码体系）。相对RSA而言，椭圆曲线密码的优势和好处为：第一，安全强度更高。RSA中存在着一般数域筛（NFS）方法攻击，使得其安全强度为亚指数级，而ECC 的安全强度为指数级22，即使使用目前国际上公认的有效攻击方法Pollard orhd方法也很难将其破解
17、。第二，密钥短。在同等安全强度下，椭圆曲线密码的密钥尺寸比RSA体制和ElGamal类体制要小得多，椭圆曲线密码所具有的短密钥这一优势，将适合在存储受限的条件下（如 IC 卡技术等）使用。第三，椭圆曲线密码所需的存储空间小，宽带要求低。由于其存储少、宽带要求低的特点，使得椭圆曲线密码在许多条件受限的领域内具有很优越的发展前景。第四，椭圆曲线密码的计算速度快。在现代分布式网络中，由于服务器的瓶颈效应，使得快速的认证成为了一种迫切的需求。比如一个Web服务器，如果认证速度太慢，就会影响用户访问的热情，导致服务效率降低。由于 ECC 最底层的有限域规模较小，以及相关研究的不断深入，已使得其计算速度大
18、大高于RSA的计算速度。而相对后来的辫群公钥系统以及 NTRU 的新兴公钥系统，ECC 已经得到了广泛而长期的研究和攻击，能提供更可靠的安全性。推动ECC实际应用的一个里程碑事件就是椭圆曲线数字签名标准（ECDSA）23（ ANSI X9.62）的公布。之后其他国际组织也纷纷将其标准化，例如 IEEE P1363、ISO、IEC CD14888-3等24，而相应的各种协议也将ECC应用到其中，如IPSec/IKE25，26、WAPI27等。其中，由Visa和Mastercard两大信用卡公司于1997年推出的SET（安全电子交易）协议更是将其默认的公钥密码算法置为 ECC。ECC 的加密技术产
19、品已经被广泛应用到各种安全产品中，如VPN网关、防火墙，安全网关、安全路由器、Web服务器、基于ECC的移动终端、SIM卡数字签名模块、无线POS机、CA以及基于ECC的企业级安全解决方案等。可以说ECC已经逐步并将最终取代RSA的主流应用公钥密码算法的地位，将拥有非常广阔的市场。尽管现有的ECC的计算速度已经比RSA快了很多，但是由于信息技术飞速发展造成的信息膨胀，因此对ECC的计算速度也提出了更高的要求。ECC的快速实现算法将在很长一段时间内成为安全专家研究的重点。在对椭圆曲线密码的研究中，椭圆曲线密码的构造、分析和快速实现是目前研究的 3个主要方向。由于椭圆曲线密码快速实现直接影响了整个
20、椭圆曲线密码体系的性能，所以快速计算的实现已成为椭圆曲线密码体制能否快速实现的关键，本书主要对椭圆曲线密码快速算法进行了较深入的研究。经过10多年来的努力研究，密码学家们在ECC标量乘法的快速计算方面取得了令人瞩目的成就。Knuth提出了标量k从右到左的二进制方法。1997年，J.Solinas在二进制方法的基础上，提出了k的非邻接形式（NAF）和窗口 NAF 方法，此后不久又有学者在此基础上提出了滑动窗口方法，这种方法利用额外的存储器，扩大了可能的系数集，降低了标量k的非零密度。目前基于 NAF 的研究有很多，其中主要的研究是与底层域上的快速算法相结合提出新算法。目前研究最热的是由V.S.D
21、imitrov等人率先提出的双基数字系统（DBNS，Double-base Number System），此系统的思想是将标量k分解成2与3的幂指数和的形式，减少点加操作的次数。在双基数字系统的基础上，C.Doche和L.Imbert提出了Extended DBNS方法，这种方法扩大了可能的系数集，有效地降低了椭圆曲线密码系统的计算复杂度。K.W.Wong等人在双基表示的基础上，结合半点运算提出了一种新的双基表示，进一步提高了标量乘法的运算效率。近年来，Dimitrov等人对双基数字系统进行了扩展，提出了多基的思想，基于多基思想的研究也是最近几年的研究热点。不少专著和文献对标量k的表示形式进行
22、了更加深入的研究，在标量k的表示方面技术已愈趋成熟。基于双基系统的快速算法的相关研究可参考文献2830。近年来底层运算有了新的发展，Guajardo等人应用中间变量，用乘法运算来代换求逆运算，提出了二进制域上4P、8P、16P的直接计算方法，减少了算法的运算量。目前底层运算已经发展到了3P、2kP等。二进制域上的特殊曲线Koblitz曲线上的标量乘法由于可以不用使用倍点算法，而且其计算相对比较容易，所以，Koblitz曲线的研究也是目前标量乘法研究的主要内容。另外，Sakai等人于2000年提出了基于双线性对的身份认证协议，最近几年，双线性对获得了广泛的密码应用，涌现出了各种基于双线性对的密码
23、协议。实现这些应用的效率，取决于双线性对的计算速度，而实现这些协议的瓶颈在于能否快速计算双线性对，Miller算法成功地运用倍点加和切割线组合来完成这一计算过程。在ECC的标量乘法的快速计算方面的理论已愈趋成熟，而在ECC的快速实现中，最关键的因素就是标量乘法kP的快速算法研究问题。因此，研究这个问题有着较深的理论意义，更具有迫切的实际意义和广阔的市场前景。本书的内容安排如下。第1章介绍椭圆曲线密码的基本概念和研究椭圆曲线密码所需的基础知识。第2章介绍椭圆曲线上重要的点的计算公式。第3章讲述了基于NAF分解，提出几种新的标量乘快速算法，如w-NNAF方法、RTSNAF方法等。这些方法使得标量乘
24、的计算复杂性可以进一步降低，最后定量分析了这些方法降低的计算复杂度。第3章是本书的重点。第4章讲述了联合稀疏形（JSF）与Frobenius映射结合的快速算法，该方法以少量的存储为代价获得了一定的运算加速。第5章介绍基于最大公约数（GCD）的高速带模除法，主要对常规 GCD 算法进行了深入分析，改进了算法的判断标准和体系结构，从根本上加快了GCD算法的效率。第6章扩展了基于半点与双基表示的ECC快速标量算法，分析并比较了提出的快速算法的计算复杂度相比于其他算法的优势。第7章提出了一种优化算法，将双基数链与Miller算法相结合，从而缩短了链长，减少了算法中的迭代次数，并将“倍点加”的过程进行优
25、化，提出新的除子表达式，在迭代过程中优化了除子计算，提高了运算速度。第1章 椭圆曲线密码简介椭圆曲线是代数几何中一类重要的曲线，至今已有 100 多年的研究历史。而应用于密码学中的椭圆曲线是基于有限域上的，通过引入无穷远点，将椭圆曲线上的所有点和无穷远点组成一个集合，并在该集合上定义一个运算，从而该集合和运算构成了群。在有限域上的椭圆曲线群有两种，分别基于GF(p)以及GF(2m)，它们各自有不同的群元素和群运算，然而对于群上的 ECDLP 问题，都认为是一个指数级的困难问题。基于这个困难问题，构建了ECC算法，包括公钥加密、私钥解密、数字签名、签名验证、DH交换等。1.1 无穷远点在平面上，
26、任意两条不同的直线只有相交和平行两种关系，为了将这两种关系统一，引入了无穷远点的概念，无穷远点就是两条平行直线的交点。有了这个概念，我们就认为平面任意两条不同的直线都是相交的，对于平行的直线，它们的交点为无穷远点。任何一条直线有且只有一个无穷远点，平面上不平行的两条直线有不同的无穷远点。平面上所有的无穷远点组成一条直线，成为无穷远直线。为了从坐标上把普通点和无穷远点表示出来，我们使用齐次坐标（X，Y，Z）（X，Y，Z不能全为0）来表示平面上普通坐标为（x，y）的点。二者之间的转化关系为x=X/Z，y=Y/Z，之所以称为齐次坐标，是因为（pX，pY，pZ）表示同一个点。而无穷远点的齐次坐标表示形
27、式为（X，Y，0），无穷远直线的方程为Z0。假设在普通的坐标系下一条直线L的方程为：ax+by=c，则在齐次坐标下L的方程为aX+bY=cZ。任何曲线都可以实现方程之间的转化，而且任何曲线都包括无穷远点。1.2 数论相关概念1.2.1 同余和剩余类的概念这一节我们将给出同余系统的一些结果。定理 1.2.1 对整数n1，同余关系（模n）具有自反性、对称性和传递性，即对任意的a,b,c Z有1.a a(mod n)；2.如果ab(modn)，则ba(modn)；3.如果ab(modn)，bc(modn)，则ac(modn)。满足定理1.2.1中3条性质的关系被称为等价关系。大家都知道，一个集合上的
28、等价关系把这个集合分为若干个等价类。令“n”表示模n同余的等价关系。这个关系定义在集合Z上，因此它把Z恰好分成n个等价类，每个类包含于某整数模n同余的所有整数。把这n个类表示成其中，=xZ|x(modn)a。我们将上面每一个集合均称为一个模 n 剩余类，显然，我们可以将 Z 看做是。定理1.2.2 对任意的a,bZ定义剩余类和 之间的加法和乘法运算为则对任意的n1，由“(modn)”定义的映射f:ZZn是从Z到Zn的一个同态映射。定理1.2.3 对任意整数n1，如果ab(modn)和cd(modn)，则acbd(modn)，acbd(modn)。1.2.2 Euler定理和中国剩余定理定义1.
29、2.1 Euler函数。在有限域Fq上，q1，在1,2,n中与n互素的元素的个数叫做Euler函数，记作(n)。引理1.2.1 设(n)是定义1.2.1中定义了的欧拉函数。则1.(1)=1；2.如果p是素数，则(p)=p 1；3.欧拉函数是积性函数。即如果gcd(m,n)=1，则(m,n)=(m)(n)。4.如果是n的素分解，则定理1.2.4 对于整数n0，有。证明 假设Sd=x|1xn,gcd(x,n)=d，显然，对于每个d|n，集合S=1,2,n被分割成不相交的子集Sd，所以注意到对任意的d|n，有，于是然而，对任意的d|n，我们有(d/n)|n，所以证毕。例1.1 对于n=12，d |1
30、2可能的值是1，2，3，4，6和12。我们有(1)+(2)+(3)+(4)+(6)+(12)=1+1+2+2+2+4=12。定理1.2.5 Fermat定理。若p是素数，a是正整数且不能被p整除，则ap11mod pFermat定理的另一种有用的表示形式是若p是素数且a是正整数，则app mod p。定理1.2.6 Euler定理。令=a|aFq,gcd(a,q)=1，则(q2)中元素a满足a(q)1modq其中，表示有限域中所有的非零元素的集合。定理1.2.7 中国剩余定理（CRT)。令r个整数m1,m2,mr两两互素，a1,a2,ar是任意r个整数，则同余方程xai mod mi，1ir（
31、1-1）有如下唯一解其中，Mi=M/mi，M=m1m2mr，yi=modmi，1ir。算法1.1 中国剩余算法输入：整数多元组(m1,m2,mr)两两互素；整数多元组(a1(modm1),a2(modm2),ar(modmr)输出：整数xM=m1,m2,mr满足方程（1-1）1.Mm1m2mr2.对于i=1,2,r重复执行（1）yi(M/mi)1(modmi)（2）yiM/mi3.返回中国剩余定理是数论中最有用的定理之一，它说明了某一范围内的整数可通过它对两两互素的整数取模所得的余数来重构。1.3 有限域简介有限域的具体相关知识请参看文献31。我们这里仅列出一些重要的概念和定理。定义1.3.1
32、 任意给定一非空集合G和其上的二元运算“”，如果满足：1.封闭性：对任意a,bG，存在cG，使得ab=c；2.结合律：对于任意a,bcG，都有(ab)c=a(bc)；3.单位元e存在：即存在eG，对于任意aG，都有ea=ae；4.逆元存在：对于任意aG，存在bG，使得ba=ab=e，b称为a的逆元。则称集合G关于二元运算“”构成群，记为：。在群中，如果对于任意a,bG，都有ba=ab，则称群是交换群，也称为阿贝尔（Abel）群。定义1.3.2 设“+”，“”是G上的二元运算，集合的基数|G|1，如果满足：1.是一个交换群，其单位元记为0；2.是交换群，其单位元记为1；3.运算“*”对“+”可分
33、配，即对任意a,b,cG，都有a(b+c)=(ab)+(ac)(a+b)c=(ac)+(bc)则称是域。例如：是自然数集上关于“+”所做成的群，是非零有理数集关于“”所做成的群，而则是有理数集上关于“+”和“”所做成的域。定义1.3.3 有限域，又称伽罗华（Galois)域，顾名思义，就是指域G元素个数为有限的域。其中，G中的元素个数称为有限域G的阶，记为|G|。定义1.3.4 设G是任意域，1是G的单位元。如果对于任何正整数n，有则称域G的特征为0；如果存在正整数n，满足则称满足上式的最小正整数n为G的特征，记为ChG=n。定理1.3.1 若G是域，则G的特征为0或者是一个素数p。定理1.3
34、.2 从同构意义上来说，则只存在两种有限域。一种有限域元素个数为p（p为正素数），记做GF(p)；另一种元素个数为pm（p为正素数，m为正整数），记做GF(pm)。定义1.3.5 有限域的全体非零元素都可以用域中某一个元素的幂次来表示，我们称这个元素为域的本原元。定义1.3.6 对于有限域上的一个元素x，满足xl1的最小的正整数l称作元素x的阶。有限域GF(p)可以用区间0，p1上的全体整数来表示，并且满足如下条件。1.乘法中的幺元为整数1。2.加法中的零元为整数0。3.域中的加法为模p加法，即任取a,bGF(p)，有ab=(a+b)modp。4.域中的乘法为模p乘法，即任取a,bGF(p)，
35、有ab=(ab)modp。对于有限域 GF(pm)，由于主流的 ECC 算法中只用到 GF(2m)，因此我们这里只介绍GF(2m)，GF(pm)的表示方式也和GF(2m)类似。GF(2m)可以看做是GF(2)上的一个m维向量空间，只要确定了空间上的基，GF(2m)上的任何一个元素都可以用这些基的线性组合来表示。若用多项式基表示，首先确定一个 GF(2)上的 m 次不可约多项式f(x)，则多项式xi(0i0，则；若k0，则kP=(k)( P)。我们知道所有公钥密码体系都是要基于一个困难问题来保证其安全性的，比如 RSA是基于大数分解、DSA是基于GF(p)上的离散对数、辫群是基于共轭搜索问题等。
36、ECC的困难问题就是ECDLP问题，定义如1.4.3。定义1.4.3 ECDLP问题就是对于一个大整数k和非奇异椭圆曲线上的一个基点P，已知它们的标量乘法kP的值和基点P，求k的值。无论对于GF(p)上的还是GF(2m)上的ECC系统，在椭圆曲线为非奇异曲线的前提下，ECDLP 问题是一个困难问题，且求解它的计算复杂度是需要指数时间的。ECC 公钥密码体系正是建立在ECDLP问题上的。1.4.5 ECDSA算法ECDSA 算法是目前使用最为广泛的标准算法，它是以 ECDLP困难问题为基础，采用ELGamal体制构建的一个签名算法，它包含一个签名算法和一个验证算法。ECDSA算法如下：首先选择好
37、系统参数，如有限域类型和表示方法，曲线参数a，b，以及一个曲线上的基点G以及G的阶n，要求n必须为一个大素数（相关的系统参数的选择可见文献23）。参数确定以后，ECDSA算法分为如下 3 个模块分别执行不同的功能，即密钥产生模块、数字签名模块以及签名验证模块。另外介绍一个基于ECC的DiffieHellman交换型算法以及公钥加密算法。密钥产生：1.在区间1,n1上随机产生一个整数d（当然d不能太小）。2.计算标量乘法Q=dG。3.公开Q为私钥，保留d为私钥。数字签名：1.使用安全散列函数H对需要签名的消息M进行杂凑计算e=H(M)。2.随机生成一个区间1,n1上的本地秘密随机数k，并计算kG
38、=(x1,y1)。3.计算r=x1 mod n。4.计算s=k1(e+dr)mod n。5.则数据r|s即为ECDSA算法下对消息M的签名（其中|表示两个比特串的串接）。签名验证：1.使用与签名一样的散列算法H计算e=H(M)。2.计算c=s1 mod n。3.计算u1=ec mod n，u2=rc mod n。4.计算(x1,y1)u1G+uQ2。5.计算v=x1mod n。若v=r，则为一个合法签名，否则验证不通过。DH交换：1.A随机生成一个区间1,n1上的本地秘密随机数k，计算并发送kG到B。2.B随机生成一个区间1,n1上的本地秘密随机数l，计算并发送lG到A。3.最后A计算k(lG
39、)同时B计算l(kG)作为双方的共享密钥。公钥加密算法：1.公钥加密：随机生成一个区间1,n1上的本地秘密随机数k，并计算，对需要加密的消息M。计算的密文C=kG|kQ+M（其中+为XOR运算）。2.私钥解密：M=(kQ+M)d(kG)。1.5 ECC的安全性分析使用椭圆曲线作为公钥密码体制的基础是，定义在有限域上的椭圆曲线的点集可以构成一个 Abel 加法群。对于一般群的离散对数问题，当该群的阶较小时，有许多算法可以对其求解。目前较有效的解决离散对数问题的算法，有 Shanks 的 Baby Step-Giant Step （BSGS)算法和任意循环群上的指数计算法。BSGS算法是一个不依赖
40、于基本群形式的有效算法，但是它需要群中阶的最大素因子的安全指数时间为O(l1/2)。其中l是群E(Fq)的阶的最大素因子。为了防止Shanks算法的攻击，l的长度至少应为40 bit的十进制数。指数计算法是一个亚指数时间算法。椭圆曲线密码体制的安全性取决于椭圆曲线离散对数问题（LCDLP）的难解性。对于公钥密码体制的安全性要求一般都是针对密文的特性而言的，就是说，密文应该满足某种安全特性。目前被国际密码界广泛接受的密文的安全性要求主要有单向性、不可区分性和不可扩展性。单向性就是说攻击者在没有拥有私钥的前提下，无法计算出任何密文m所对应的明文信息m。不可区分性就是说对已知给定的两个明文，加密者随
41、机一致的选择其中一个进行加密，攻击者无法从密文中知道是对哪个明文的加密。不可扩展性就是说攻击者无法构造与已给密文相关的新密文。在公钥密码体制中，攻击者拥有公钥，它可以随便选择明文进行加密，攻击者还有机会获得密文，而且还可能利用各种途径来进行解密，为此，公钥密码体制应该不会泄露其他密文的明文信息，这就要求该密码体制能抗选择密文攻击。对于椭圆曲线离散对数问题（ECDLP），目前还没有有效的快速算法来解决这一难题，它有指数级的算法，这也是椭圆曲线密码体制的安全基础。ECDLP问题上一节我们提过，给定椭圆曲线E，以及其上的基点P和P的一个标量乘Q，来确定一个正整数k，满足Q=kP。从目前的研究来看，E
42、CDLP比有限域上离散对数问题（DLP)更加难以处理。已经知道的对椭圆曲线密码体制的攻击方法主要有以下几种，设椭圆曲线上的基点P，P的阶为n。1.穷举搜索法计算2P，3P，4P，直到找到满足Q=kP的k为止，这种算法最多需要n步椭圆曲线上的点加运算。2.大步小步（BSGS）算法这种算法的思想在于测试P的倍点运算是否等于Q，具体思路如下。问题：设G是一个阶为N的有限群，P,QG,m0,N，由P，Q求出关系式Q=mP中的m的值。解题步骤如下。（1）令N1=，则对任何x0,N，x可唯一表示为：x=aN1+b（a,b0,N1）。（2）对于Q=mP一定有：m=a0N1+b0其中，a0,b00,N1。（3
43、）将上式代入Q=mP得出：Qa0(N1P)=b0P。（4）算出N1P后，在区间0,N1行采用穷举搜索方法查找出a0,b0。由表达式m=a0N1+b0的唯一性即可求出m。该算法的时间复杂度为O(N1)=O()。3.SPH攻击法该算法实质上是一种演化算法，它的最大功能是将阶为N的群上的离散对数问题化为阶为N的一个素因子的循环子群上的离散对数问题。算法的主要思路：用n表示P点的阶，并设n的标准素因子分解式为假如对于每一个(i=1,2,r)，已经求出了mmod ，则由中国剩余定理可立即求出m。4.MOV攻击MOV 攻击的核心思想就是将椭圆曲线离散对数问题转化为某个有限域的乘法群上的离散对数问题，此类攻
44、击只对超奇异椭圆曲线有效，该算法导致出现了亚指数的 ECDLP求解算法，所以在对椭圆曲线的参数进行选择的时候，应避免这一情况的出现。5.Weil descent攻击这种方法只适合于特征值为2的复合域，在椭圆曲线密码体制的实际应用中，我们可以选择m为素数的GF(2m)来避免此类攻击。6.Pollards rho算法从目前来看，对ECDLP最有效的攻击就是并行Pollards rho算法攻击，这种算法是小步大步算法的随机版本，它的运行时间和小步大步算法差不多，只是需要很小的存储空间，该算法可以在几种处理器上并行。Pollards rho算法具体的思路如下。假设有限群G的阶N是素数。该攻击方法首先将
45、群G划分成3个包含的元素个数大致相等的子集M1、M2、M3，然后在这3个子集上定义一个迭代函数f(X)(XG)随机选取整数a,b1,N，计算迭代函数fX0=aP+bQX1=f(X0)X2=f(X1)Xl=f(Xl1)其中，每个Xl有Xl=alP+blQ，且alal+1，blbl+1，将迭代中的(Xl,al,bl)记录下来，若在第k次迭代中的Xk等于第j次迭代中的Xj，即Xk=Xj，则有ajP+bjQ=akP+bkQ由此可以推导出m的值。有学者指出，如果m2 120，花费1 000万美元建立具有325 000并行处理的Pollards rho算法来解决ECDLP需要32天左右，而在实际的工作中，
46、我们一般采用的都是m160，因此可以说椭圆曲线密码体制是比较安全的。Certicom 是 ECC 的主要商业支持者，拥有超过130项专利，并且已经以2 500万美元的交易获得了国家安全机构（NSA）的技术许可。他们也已经发起了许多对ECC算法的挑战，已经被解决的最复杂的是109bit的密钥，是在 2003 年年初由一个研究团队破解的。破解密钥的这个团队使用了基于生日攻击的大块并行攻击用超过10 000台奔腾级的PC机连续运行了540天以上。对于ECC推荐的最小密钥长度163bit来说，当前估计需要的计算资源是109bit问题的108倍。1.6 总结本章介绍了有限域的有关概念，包括GF(p)和G
47、F(2m)，并对它们上面的运算进行了定义。通过引入无穷点的定义，我们把椭圆曲线上的点和无穷点构成一个结合，并通过定义一个群运算，使其构成椭圆曲线群。并且特别给出了用于 ECC 上的基于 GF(p)和 GF(2m)的椭圆曲线群的定义。在这个群上，基于一个定义的困难问题ECDLP，介绍了ECC算法包括数字签名、签名验证、公钥加密、私钥解密和DH交换。第2章 ECC上的点计算及几种常见的算法ECC上的计算共分为4层：有限域上运算、点运算、标量乘法、应用ECC算法。本章将给出GF(p)以及GF(2m)上的点运算2P+Q,3P,3P+Q,4P的优化算法，并以有限域上的计算为单位量化其计算复杂度。2.1
48、点计算算法即计算量分析第2章我们将对整个ECC做一个整体上的简单介绍，从其中我们可以看到ECC的计算一共分为4层，最底层为最基础的有限域上的运算，之上的为椭圆曲线群运算（由于该群运算的群元素为曲线上的点，因此我们称其为 ECC 上的点计算），次高层为标量乘法kP，最高层为应用的ECC算法。对于有限域上的算法，有很多的相关研究资料3338，本章将不再做介绍。点的标量乘的结果主要是由椭圆曲线上点的加法和倍法产生的，点加和倍乘运算需要用到域上的除法和乘法。到目前为止，还没有很理想的坐标系统能同时降低点加法和点倍乘的运行速度。因此，加快点的加法和倍乘的运行速度就直接影响到了点的标量乘的运行速度。点的加
49、法和倍乘可以用域上的操作来实现。这些操作是域乘法、域加法、域除法等。在这些域操作中，域除法是最费时的运算，域乘法运算相比之下简单快速，而相比域乘法运算，域上的加法运算和平方运算则更加简单，几乎可以忽略它们的运算时间。可见要提高椭圆曲线密码算法的执行速度就要尽量地减少域除法和域乘法的运算次数。若域GF(2m)上的除法比乘法更加耗时，所以便应用了使用其他坐标系统来表示椭圆曲线上的点以减少域除法的次数。我们这里重点介绍几个 ECC 上的点算法。包括 GF(p)以及GF(2m)上的如下点计算：2P+Q,3P,3P+Q,4P。算法2.1(2P+Q on GF(p)INPUTP=(x1,y1)0,Q=(x
50、2,y2)0OUTPUT2P+Q=(x4,y4)PROCESS1.If(x1=x2)then（1）If(y1=y2)then return3P（2）Else return P2.X=(x2 x1)2; Y=(y2y1)23.d=X(2x1+x2)Y4.if(d=0)then return(0)5.D=d(x2 x1); I=D16.1=dI(y2y1)7.2=2y1X(x2 x1)I18.x4=(21)(1+1)+x29.y4=( x1 x4)2 y1END算法2.2(3P on GF(p)INPUTP=(x1,y1)0OUTPUT3P=(x4,y4)PROCESS1.If(y1=0)then