椭圆曲线密码体制的研究与实现

椭圆曲线密码体制的研究与实现

姓名：李德庆申请学位级别：硕士专业：电路与系统指导教师：李小平

20080101

摘要摘要加密算法是网络信息安全的核心，根据已有资料分析，利用ＦＰＧＡ实现的最优正规基表示下的二进制有限域上的椭圆曲线密码体制具有最高的安全强度和较快的处理速度，而椭圆曲线密码体制的ＦＰＧＡ实现，主要面临以下几个问题：１．最优正规基下的有限域元素乘法矩阵的构造，以及乘法运算的快速实现。２．最优正规基下的有限域元素求逆运算算法的优化与实现。３．在椭圆曲线运算层，如何减少或者避免有限域元素上的求逆运算。４．针对椭圆曲线运算层上的标量乘运算，如何减少点加运算和倍点运算的次数。从以上四个问题出发，本文在分析和研究椭圆曲线密码体制的最新研究成果的基础上，主要对基于ＦＰＧＡ的椭圆曲线加密算法的实现以及优化设计进行了研究，作者取得的主要研究成果有：１．给出Ｉ型和Ⅱ型最优正规基下的并行输出结构的乘法矩阵的运算定理，完成了串并结合结构的通用乘法器的设计。２．在分析有限域求逆运算和正规基性质的基础上，给出了一种简化的求逆运算算法及实现，其具有和ＯＩＡ（优化求逆算法）同样的运算复杂度。３．在椭圆曲线运算层的标量乘运算运行过程中，对椭圆曲线上的点进行坐标变换，只需要在运算开始的时候做简单的坐标转换，计算结束后用１次求逆和２次乘法还原成仿射坐标即可，虽然增加了乘法运算的次数，但是大大减少了运算中的求逆运算次数。４．在椭圆曲线运算层，对标量乘运算的参数进行有符号非相邻表示型（ＮＡＦ）编码，使标量乘运算具有最少的点加运算。在对有限域运算和椭圆曲线标量乘运算优化的基础上，本设计达到了预期的目标，测试结果表明，当研＝１９１的时候，在５０Ｍ的工作频率下，平均每次标量乘运算的时间为１１Ｉ璐。该设计可以支持册＜２３２的ＧＦ（２”）上任意可变曲线的椭圆曲线加密算法，是一种数据位宽度可调的快速椭圆曲线密码运算核的ＦＰＧＡ实现。关键词：椭圆曲线密码体制有限域最优正规基乘法器标量乘ＡｂｓｔｒａｃｔＡ６ｓ臼ａｃｆＷｉｍｔｌｌｅｒａｐｉｄｄｅＶｅｌ叩ｍｅｍＴｈｅｏｆｔｌｌｅｉⅡｔｅｍｅｔ，ｉＩｌｆ．０衄ａｔｉｏｎｅｘｃｌｌａｎｇｅｂｅｃｏｍｅｓｓｅｃｕｄｔｙｉｓｇｉｖｅｎｍｏｒｅｉｓａ趾ｄｍｏ陀ａｔｔ蜘ｔｉｏｌＬｄｉ伍ｃｕｎｐｍｂｌｅｍｍｅｔＩｌｏｄ，ｔｏｉｎ｜’ｏ加ａ吐ｏｎｌａ唱ｅｒ锄ｄｌａ唱ｅｒ．Ｉｔｍｅｅｔｔｈｅｄｅｍａｎｄｗｉｔｌｌｔｈｅ仃ａｄｉｔｉｏＩｌａｌｓｏｆｔｗａｒｅｃＩｌｃｒｙｐｔｉｏｎ∞ｔｈｅｈａｒｄｗａ∞ｉｌＩｌｐｌｅｍｅｎｔａｔｉｏｎ印ｐｅａｒｅｄ．Ａｓｃｕｎｒｅｍｗｐｕｂｌｉｃ－ｋｃｙｃｒｙｐｔｏｇｒａｐｈｙ，ｅｌｌｉ讲ｉｃｌｅｎｇｍｏｆｔｈｅｃｒｙｐｔｏ鲫１１ｙｈ船ｓｏｍｅｅｘｃｅＩｌｅｎｔ砌ｂｕｔｃｓ：ｓｈｏｒｔｃｒｙｐｔｏｇｒａｐｈｙ．ｋｅ）ｒ，ｆ弧ｓｐｅｅｄｏｆ虹坨ｐｒｏｃｅ鼹，ｈｉ出ｌｅｖｅｌｏｆ也ｅｓｅｃｕｒｉ劬Ａｎｏｆ也ｅｓｅｔｈｅｐｕｂｌｉｃ－ｋｅｙｏｎｍａｋｅｉｔ觚ｉｄｅａｌｃｈｏｉｃｅ南ｒｔｈｅａｐｐｌｉｃａｔｉｏｎ．ｍ自ｃｔ，ｉｔｉｓｏｎｅｏｆ纯ｍ‘ｌａｒｄｓｏｆｎ坞北斌ｇｅｍｒａ矗ｏｎｔｏＩｎｍｅｐａｐｅｒ，ｂａＳｅｄｒｅｓｅａｒｃｈｏｆｔｌｌｅｔｈｅｇｅｎｅ删硫ｉ∞觚ｄａｎａｌ”ｉｃａｌｓｔＩｌｄｙｔｏｔｈｅｐｒｅ矧１ｔＥＣＣｉｓＥｌｌｉ砸ｃＣｕｒ、，ｅＣｒｙ舯）ｇｒａｐｈｙ（ＥＣＣ），Ⅱ地ｂｌｕｅｍ印ｏｆｔｈｅｓｔｌｌｄｙｔｌｌｅａｒ主ｔ｝ｌｍｅ６ｃｉｎｆｅｒｅｎｃｅｓ季Ｖｅｎｔｏｃｏｍｐｌｅｔｅ趾抽ｄｅｐ曲ｄ鼬ｔｓｙｓｔｅｍ．Ｆｉｆｓｔ＇ｗｅｉｎｔｌｌｅｆｉｎｉｔｅｆｉｅｌｄ．ｉＩｌｗｈｉｃｈ辩ｖｅｍｌｔｌｌｃｏｒｅＩ璐锄ｄｕｓｅｆＩｌｌｏｐ啪ｔｉｏｎｏｆｔｌ岵ＥＣＣ戤ｅｌｌｉ—ｃｃｕⅣｅ晔蚴ｌｅｄ．Ｓｃｃｏｎｄｌｙ’缸ｔｈａ妇Ｈ饿ｅｉｎｌｐｌ髓黝ｔａｔｉｏｎｏｆｔｈｅｃｒ），ｐｔ０铲ａｐｈｙａｒｉｔｌｌｍｅｔｉｃｉｓｔｌｌｅｈｏｔｓｐｌｏｔｄｉｒｅｃｔｉｏｎｉｎｔｈｅＥＣＣｒｃ∞ａｒｃｌｌ，∞ｔｈｅｌｌａｆｄｗａｒｅｉｍｐ】ｅｍｅｎｔａｔｉｏｎｓｏｆｔｌｌｅ蠡啦ｔｃｆｉｅｌｄｏｌ，ｃｒａｔｉｏｎｓａ犯西ｖｅｎｗｉｔｌｌｏｐｔｉｌｌｌａｌ∞姗ａｌｂ猫ｉｓ，ｍｅｄｅｓｉｇｌｌｏｆ岫ＥＣＣｃｏｒｃｍＯｄｍｅｓ∽ｃｏｍｐＩｅｔ甜，ｗｌｌｉｃｈｍｌｌｌｄｅｓｗｈｉｃｈⅡｌｅｏｎｔｌ惦ｄｌｉｐｔｉｃｃ哪ｅｓｃａｌａｒｍｕｌｔｉｐｌｉｃａｔｉｏｎ枷ｃｈｃｏ脚【ｂｉｎｅｓＮＡＦｃｏｄｅ、ｖｉｍａｍｅｎｄｅｄｒｅｓｕｌｔａｒｉｔｈＩＩｌｃｔｉｃ．Ｆｉｎａｌｌｙ，ｔｈｅｏｆｓｉＩＩｌｕｌａｌｉｏｎ锄ｄａｐｐｌｉｃａｔｉｏｎａｒｅ西ｖｃｎ，ｉｎｃｏｎｃｌｕｓｊ∞ｓ啪ｍａｒｉｚｅｓｍａｔＥＣＣ∞ａｌ盯ｍｕｌｔｉｐｌｉｃａｔｉｏｎｍｏｄｌｌｌｅｓｂａｓｅｄａＩＩｏｐｔ砌∞ｍｌａｌＫｅｙｗｏｒｄ：ｅｌｌｉｐｔｉｃｓｃａｌａｒｂ嬲ｅｓｃｏｍｐｌｅｔｅｓｃｏｍｐｕｔｉｎｇｎｏｅｄｓ矗ｍｅｌｌｍｓａｔ５０ＭＨＺ肌ｑｕｃＩｌｃｙｏｆ血ｃｗｏｒｋｉｎ舒（２州）．ｃｕｒｙｅｃｒｙｐｔｏｇｒａｐｈｙＧａｌｏｉｓ６ｅ埘ｏｐｔｉｍｍ舯瑚村ｂａｓｉｓｍｕｌｔｉｐｈｃａｔｉ蛐ｍａｔ血ｏｆｍｕｌｔｉｐＨｃａｔｉｏｎ西安电子科技大学学位论文独创性（或创新性）声明秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中做了明确的说明并表示了谢意。申请学位论文与资料若有不实之处，本人承担一切的法律责任。本人签名：公逸度日期型：！：兰西安电子科技大学关于论文使用授权的说明本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后结合学位论文研究课题再撰写的文章一律署名单位为西安电子科技大学。（保密的论文在解密后遵守此规定）本学位论文属于保密，在一年解密后适用本授权书。本人签名：盔丝丞导师签名：日期ｗｇ一／・Ⅵ蕉止垒日期主！墨：ｆ：丝第一章绪论第一章绪论椭圆曲线密码体制的研究由来已久，各种算法和实现方式也层出不穷，本文立足于最优正规基表示下的二进制有限域，利用ＦＰＧＡ来实现其运算算法。在整个椭圆曲线密码体制的硬件实现中，我们均采用硬件描述语言Ⅵ：ｆｉｌｏｇ翔）Ｌ语言作为算法实现描述语言，整个设计过程均运行在Ａｌｔｅｍ公司开发的ＱｕａｒｔＩｌｓⅡ７．１平台上，设计选用的是Ａｌｔｅｒａ公司的ＣｙｃＩｏ∞Ⅱ系列器件ＥＰ２Ｃ３５Ｆ４８４ｃ８Ｎ。１．１选题的意义在网络传输中，加密技术是一种效率高而又灵活的安全手段，随着通讯网络的发展和信息交换的需要，为了达到一定的安全要求，大多数的公钥密码体制的密钥也越来越大，传统利用软件来实现的加密／解密方式已经很难满足要求，随着硬件集成电路的发展和新理论的出现，采用硬件实现的运算模块随之诞生。目前，椭圆曲线密码体制由于其抗攻击能力强，计算量小，处理速度快等优势，有望成为下一代公钥密码体制的标准，采用ＦＰＧＡ快速实现椭圆曲线密码体制是当前的研究热点之一。针对素域和多项式表示下的二进制有限域上的椭圆曲线密码体制芯片，成都三Ｏ集团和清华微电子研究所已经有成熟的解决方案。近年来，最优正规基得到了大量的研究，其具有高效的乘法运算算法，具体可见参考文献【ｌ】，为了紧跟世界的趋势，缩短与国外先进技术的差距，把正规基下的二进制有限域作为椭圆曲线密码体制的实现的有限域，构造我们的椭圆曲线密码芯片产权核，并在此基础上建立高效，参数控制数据宽度的椭圆曲线密码体制，对于我国经济和国防事业的发展具有很重要的意义。１．２ＥＣＣ研究现状在１９８５年，ＫＤｂｌｉｔｚ口】和Ｍｉｌｌｅ一３Ｊ分别提出了椭圆曲线密码体制之后，由于在已知的公钥密码体制中，椭圆曲线密码体制具有每ｂｉｔ最高强度的安全性，最快的处理速度和最低的开销，目前已成为信息传输中安全性研究的热点方向１４】。第六届国际密码学会议对应用于公钥密码系统的加密算法推荐了两种：基于大整数因子分解问题（ＩＦＰ）的ＲＳＡ算法和基于椭圆曲线上离散对数计算问题（ＥＣＤＬＰ）的ＥＣＣ算法。ＲＳＡ算法的特点之一是数学原理简单、在工程应用中比椭圆曲线密码体制的研究与实现较易于实现，但它的单位安全强度相对较低。目前用国际上公认的对于ＲＳＡ算法最有效的攻击方法一般数域筛０婚ｓ）方法去破译和攻击ＲＳＡ算法，它的破译或求解难度是亚指数级别的。Ｅｃｃ算法的数学理论非常深奥和复杂，在工程应用中比较难于实现，但它的单位安全强度相对较高。用国际上公认的对于Ｅｃｃ算法最有效的攻击方法Ｐｏｌｌａｒｄｒｈｏ方法去破译和攻击ＥＣＣ算法，它的破译或求解难度基本上是指数级别的。正是由于ＲｓＡ算法和ＥｃＣ算法这一明显不同，使得ＥＣｃ算法的单位安全强度高于ＲｓＡ算法，也就是说，要达到同样的安全强度，ＥｃＣ算法所需的密钥长度远比ＲＳＡ算法低（见表１）。这就有效地解决了为了提高安全强度必须增加密钥长度所带来的工程实现难度的问题。（见表２）表１．ＲｓＡ和Ｅｃｃ安全密钥长度的比较攻破时间ＲＳ＾／ＤＳＡⅢ口婢ｌ酽１０搴１０１ｌ窑钥长度５１２７石８１０２４２０４８２１０００Ｅｃｃ密钥长度１０６１３２１６０２１０６００ＲＳＡ／ＥＣＣ窑钥长度比５：ｌ６：ｌＴ：ｌ１０：ｌ３５：ｌｉ庐１０７Ｂ表２．ＲＳＡ和ＥｃＣ速度的比较功能密钥对生成签名认证Ｄｉｆｆｉｅ一一Ｈｅｌｌ孤２ｍＳｅｃｕｒｉｔｙＢｕｉｌｄｅｒ１．２丑Ｓ舡咂３．Ｄｉ６３位Ｅ０ｃ（ＩＬ５）３．８ｌ，０２４位ＲｓＡ（Ｍ，４，ＴＤ８．３２２Ｂ．４２．１（ＥＣＮＲＡ）３．Ｏ（ＥＣＤＳＡ）９．９（ＥＣＮＲＡ）１０．Ｔ（ＥＣＤＳＡ）７．３ｌ，６５哇．０１２．Ｔ密钥交换显然，ＥＣＣ具有很大的技术优势：●抗攻击能力强ＥＣＣ和其它几种公钥系统相比，其抗攻击性具有绝对的优势，具有单位比特最高强度的安全性。如１６０ｂｉｔＥＣＣ与１０２４ｂｉｔＲＳＡ、ＤＳＡ有相同的安全强度。而２ｌＯｂｉｔＥＣＣ则与２０４８ｂｉｔＲｓＡ、ＤＳＡ具有相同的安全强度・计算量小，处理速度快虽然在ＲＳＡ中可以通过选取较小的公钥（可以小到３）的方法提高公钥处理速度，即提高加密和签名验证的速度，使其在加密和签名验证速度上与ＥＣＣ有可第一章绪论比性，但在私钥的处理速度上（解密和签名），ＥＣＣ远比ＲＳＡ、ＤＳＡ快得多。因此ＥｃＣ总的速度比ＲＳＡ、ＤＳＡ要快得多，在相同的安全强度下，我们用１６０ｂｉｔＥＣＣ进行加解密或数字签名要比用１０２４ｂｉｔＲｓＡ、ＤＳＡ要快大约１０倍。●密钥尺寸小和系统参数小Ｅｃｃ的密钥尺寸和系统参数与ＲＳＡ、ＤｓＡ相比要小得多，意味着它所占的存贮空间要小得多。●带宽要求低当对长消息进行加解密时，三类密码系统有相同的带宽要求，但应用于短消息时ＥｃＣ带宽要求却低得多。而公钥加密系统多用于短消息，例如用于数字签名和用于对对称系统的会话密钥传递。ＥｃＣ的特性使它在快速加密、密钥交换、身份认证、数字签名、移动通信、智能卡的安全保密等领域，具有广阔的市场前景。在椭圆曲线密码体制的标准化方面，ＩＥＥＥ、ＡＮｓＩ、Ｉｓ０、ＩＥＴＦ、ＡＴＭ等都做了大量的工作，他们所开发的有关椭圆曲线密码体制标准的文档有：ＩＥＥＥＰ１３６３ａ、ＡＮＳＩＸ９．６２Ｘ９．６３、Ｐ１３６３ＩＳｏ／ＩＥＣｌ４８８８等。２００３年５月１２日中国颁布的无线局域网国家标准ＧＢｌ５６２９．１１中，包含了全新的ｗＡＰＩ（ｗＬＡＮＡｕｍｃｌｌｄｃａｌｉ∞锄ｄＰｒｉｖａｃｙＩｎ觚加ｌｍ鹏）安全机制，能为用户的ＷＬＡＮ系统提供全面可靠的安全保护。这种安全机制由ＷＡＩ和、）ｌ，ＰＩ两部分组成，分别实现对用户身份的鉴别和对传输的数据加密。ｗＡＩ采用了公开密钥密码体制，利用认证证书来对ｗＬＡＮ系统中的用户和Ａ＿Ｐ进行认证。证书里面包含有证书颁发者（ＡＳＵ）的公钥和签名以及证书持有者的公钥和签名，这里的签名系统采用的就是椭圆曲线密码体制算法。从实现的角度来看椭圆曲线密码体制，则无论硬件实现还是软件实现，其总体设计的差异性不大。椭圆曲线密码体制的ＦＰＧＡ技术实现可以分为五个层次，见图１．１：有限域运算层、椭圆曲线运算层、密码运算层、接口层和密码体制应用层。其中有限域运算层是最基础的，而接口层和应用层是最接近用户的。４椭圆曲线密码体制的研究与实现图１．１．椭圆曲线密码系统结构层次图有限域的运算层主要提供根据数论提供的有限域运算法则进行的计算，根据我们设计的需要，由于选择的是基于ｏＮＢ的有限域，所以主要包括有限域元素的加法运算、平方运算、乘法运算、求逆运算。在某些特殊的情况下，因为求逆运算是复杂的运算，为了避免求逆运算，在一些特殊的地方还加入了坐标平面的映射转换。运算层的实现效率将对整个椭圆曲线密码体制的运行效率起决定性作用，提供了所有上层运算的基本模块。因此有限域运算层的编程工作是算法实现的核心部分，也是基础部分，同时也是最艰巨的部分。椭圆曲线运算层在本设计中主要包括三个基本的运算模块：第一是椭圆曲线上不同点的加运算，即点加；第二是椭圆曲线上的倍点运算：第三部分是舻运算的优化。舻的直接关系着整个椭圆曲线的运行效率，所以对舻运算的优化将是我们工作的重点。密码运算层是为了支持公钥密码系统，通常提供的五种操作：生成密钥对、加密、解密、签名和验证签名。接口层的主要负责控制数据的输入输出，比如３２位的输入数据转化为可以直接处理的所位数据，把处理好的ｍ位数据并行串出，存储加密系统的基本参数，包括基点、私钥、椭圆曲线、对方的公钥、以及选择椭圆曲线密码系统的工作方式，控制群运算等。应用层的主要功能是根据接口层提供的下层服务，可以是软件模块，也可以是硬件模块，但是在通常的情况下，一般采用软件来实现。考虑到本项目的主要目标是为了最大可能的优化和提升椭圆曲线密码体制核心算法的性能，所以接口层和应用层并不是本设计的重点所在，这里只是简单做一个说明。椭圆曲线密码体制特别适合于硬件的实现，最早采用硬件实现椭圆曲线密码体制的报道见于文献【５１。文献【５】构造了一个基于ＧＦ（２”’）的乘法运算的ＶＬＳＩ芯片，第一章绪论在此基础上利用一个可编程控制器实现了椭圆曲线密码体制芯片。利用该芯片，加密速度可以达到４０ｋｂ，Ｓ，换算为签名的速度大约为１３０次每秒。２０００年，文献１６】介绍了一个定义在ＧＦ（２“３）上的ＫＤｂｌｉｔｚ曲线，采用了ＦＰＧＡ和ＡＳＩＣ两种实现方式，并给出了其仿真结果。在Ｏ．２５啪的ＣＭＯＳ工艺下，ＡＳＩＣ芯片的规模为１６万门电路，工作频率可以达到６６ＭＨＺ。利用这样的一个芯片，完成一次标量乘运算大概需要１．１ｍｓ。２０００年，文献【７】介绍了对定义在ＧＦ（２１”）上的椭圆曲线采用Ｘｉｌｉ舣ｘＣＶ４００ＥＦＰＧＡ芯片实现的结果，在这个实现中，芯片的主要工作频率可以到达７６．７ＭＨｚ，在最高工作频率下，完成一次标量乘运算需要Ｏ．２ｌＩｍ。２００１年，Ｍｏｔｏｒｏｌａ公司推出了一款多功能的安全处理器，型号为ＭＰｃｌ８０。这是一款功能上几乎做到了包罗万象的芯片，只要是为了实现网络安全芯片而设计的。该芯片具有实现ＤＥＳ、３ＤＥＳ、ＲＣ４、ＤＭ４、ＭＤ５、Ｓ姒．１、ＲＳＡ、ＥＣＣ等算法功能。关于椭圆曲线密码体制部分，ＭＰＣＩ８０芯片可以同时兼容素数域曲线和特征值为２的域的曲线。对于素域的情况下，芯片只要求定义曲线的素域内元素的是一个规模在“比特到５１２比特之间的素数即可。对于特征值为２的域的情况，也只要求定义曲线的有限域的长度在６４比特到５１２比特之间。对于以上两种情况下的椭圆曲线，芯片没有提供任何完整的算法功能或者密码协议的实现，只是提供了标量乘所必须的两种椭圆曲线运算层上的运算，即计算椭圆曲线上点加和计算倍点的功能嘲。２００３年文献【１】介绍了定义在ＧＦ（２“），ｍ≤２５６上的任意椭圆曲线密码体制的ＦＰＧＡ实现。其采用微处理器模式，消耗了２０，０６８个ＡＬｕＴ和６，３２１个ＦＦ，工作时钟频率为６６．４ＭＨＺ，当正常工作的时候，对于采用定义在ＧＦ（２懈）上的ＮｌｓＴ所推荐的椭圆曲线，每秒可以完成６９５５次点乘运算，在一般曲线的情况下，每秒可以完成３３０８个点乘运算。我国的密码芯片的设计和生产还远远滞后于网络发展的需求，特别是在高速密码芯片方面与国外先进水平还有十分明显的差距。国内对椭圆曲线密码体制的芯片集成的研究起步较晚，但是发展十分迅速，目前已经有正式的产品面世。２００４年，上海微科集成电路有限公司宣布开发成功的Ｒｓ～ＥＣＣ二合一密码算法协处理器芯片，该芯片最多可以完成２５６比特的椭圆曲线密码体制运算，每秒至少可以完成１００次点乘运算。２００６年，清华大学微电子研究所召开了“高速椭圆曲线密码ＴＨＥｃｃ／２３３・１００”专用：签片技术成果鉴定会。ＴＨＥＣＣ／２３３一ｌｏｏ芯片实现ＧＦ（２２”）的基于Ｋ一２３３曲线的椭圆曲线密码（ＥＣＣ）算法，具有ＥＣＣ数字签名的产生、验证、密钥对生成和多倍点运算等四种功能。该芯片采用Ｏ．１８微米ＣＭｏＳ工艺制造，电路规模１２万等效门，面积２．３５ｍｍ＋２．３５ｍｍ．经测试表明，芯片最高工作频率可达１４０ＭＨｚ，在６椭圆曲线密码体制的研究与实现ｌＯＯＭＨｚ工作频率条件下，每秒能够完成数字签名２９５０次、签名验证１６８０次，基本达到同类国际先进水平。２００７年，成都三。嘉微电子有限责任公司的ＥＣＣ数字签名验证芯片投放市场。该芯片采用Ｏ．１８啪工艺ＡｓＩＣ实现，支持１９２位到３２０位素域椭圆曲线算法，２５６位签名速度达到每秒１３００次，验证速度为６５０次每秒，基本代表国内素域上椭圆曲线密码体制的最高水平。在椭圆曲线密码体制的ＦＰＧＡ实现中，有限域的选择是一个关键的问题，从上面已经出现在市场上的芯片来看，基于素域和多项式基下的二进制域的实现是比较多的。由于其数据表示固有的性质，素域结构简单，元素的表达也比较方便，在其上也有很多比较成熟的算法，比较适合软件实现。在这样的域中，主要问题通常是模素数的大数运算，对于非特殊形式的素数Ｐ，求ｚｍｏｄＰ的计算是基本运算单元中最费时的部分，人们以原始Ｍｏｎｔｇ涨ｒｙ模乘的算法为基础研究了多种不同的改进算法。而在有限域６Ｆ（２”）中，元素都是一定长度的Ｏ和ｌ的比特串，特别符合硬件中对元素的表示，并且其运算只涉及移位和按位的模２运算，所以从方便硬件实现的角度来看，二进制域ＧＦ（２”）是最有吸引力的。多项式基下的二进制域，域元素平方运算极其复杂，但是在系统的实现中，域元素的平方运算又是最频繁的运算，这在一定程度上降低了椭圆曲线密码体制运行的效率。对于正整数所，有限域ＧＦ（２”）就像上面所说的，和多项式基一样，可以根据算法２．１进行判断是否存在着最优正规基【９】【１０ｌ【１１】（ｏＮＢ），如果存在，则当采用最优正规基来表示域元素的时候，虽然不如多项式基那么直观，但是在实际工作中，可以充分地利用移位运算。基于０ＮＢ表示法的域元素在执行平方运算时高效，仅需对表示元素的矢量进行循环移位。在幂运算方面，ｍ懵表示法也比多项式表示法更加有效，其求逆运算存在优化算法，虽然其乘法运算比多项式表示法复杂，但是如果我们先计算出其乘法矩阵，则问题也迎刃而解了。因此，我们采用基于最优正规基（０ＮＢ）的二进制有限域来实现椭圆曲线密码体制，使用正规基表示上元素的相应运算算法较好的综述文章，请参见文献【１２１。在椭圆曲线运算层，根据椭圆曲线运算法则，不管是点加运算还是倍点运算，都需要至少一个求逆运算，而在正规基表示下的域元素，虽然存在优化求逆算法，求逆运算仍然是比较消耗时间资源的运算，因此避免求逆运算或者减少求逆运算的次数也是我们要考虑的一个问题。在椭圆曲线密码系统中，最耗时和最频繁的操作就是计算护，椭圆曲线标量乘的运算可以分解为点加运算和倍点运算，在参数一定的情况下，减少倍点运算或者点加运算的次数，也可以提高整个系统的运行效率。第一章绪论７可见，在最优正规基表示下的二进制有限域上，构建一个优化的椭圆曲线密码体制系统，主要存在以下几个问题：１．最优正规基下的有限域元素乘法矩阵的构造，以及域元素乘法运算的快速实现。２．最优正规基下的有限域元素求逆运算的优化域实现。３．在椭圆曲线运算层，如何减少或者避免有限域元素上的求逆运算。４．针对椭圆曲线运算层上的标量乘运算，如何减少点加运算和倍点运算的次数。针对以上几个问题，也有相关的一些资料出现，但是据目前得到的资料分析，国内还没有单位实现完整的基于正规基下的椭圆曲线密码体制的报道。文献【４ｌ】提供了基于正规基的一种乘法器的实现方式，此方法虽然额外占用了很多逻辑单元和寄存器单元，但是相比较ＲＲＭ０乘法器来说，仍然具有最小的空间复杂度。文献ｍ】【４３１给出了降低乘法器的空间复杂度的一种方法，并在此基础上给出了正规基上的有限域的运算的基本运算方法，并给出了Ｉ型最优正规基的乘法矩阵的一种构造方法。文献Ｄ４１给出了有限域上元素的一种求逆运算方法，即优化求逆算法，并把求逆运算转换为乘法运算，使其具有最少的乘法次数。文献Ⅲ】针对椭圆曲线运算层提出了一种优化的算法，在预先计算倍点的情况下，通过降低点加运算的次数来提高运行的效率，在这种算法下，可以比直接运算快９０％。尽管如此，但是从实现的角度上来讲，并没有唯一确定的最优算法可以实现系统，我们只能从运算层次上分别对其进行优化，以求获取我们预期的性能。１．３论文的主要工作和论文结构本论文在着眼于椭圆曲线密码体制的ＦＰＧＡ实现，在吸取前人经验的基础上，提出一个可行的完整的实现方案，根据提出的方案，进行系统的理论分析，应用设计，并采用ＦＰＧＡ实现，可以为椭圆曲线密码体制的实现提供有效的方案模板。本论文针对最优正规基表示的ＧＦ（２”）上的椭圆曲线密码体制做了以下研究工作：第一，针对第一类型和第二类型最优正规基表示的域元素，给出了乘法矩阵的几种计算方法。第二，对基于最优正规基表示的域元素进行研究，设计了一种通用的，串并结构皆可的乘法器，能够完成不同带宽下的乘法运算。第三，针对求逆运算器，比较分析了两种不同的设计结构，并给出了其理论分８椭圆曲线密码体制的研究与实现析与性能比较。第四，针对椭圆曲线上的点，采用不同的坐标系，在计算点加运算和倍点运算中，减少了求逆运算的次数。第五，对定义在ＧＦ（２”）上的椭圆曲线密码体制，采用修正算法对标量参数进行有符号的ＮＡＦ编码，使之拥有最少的非零位，在一定程度上减少了点加运算的次数，从而提高整个系统的运行效率。论文是按照以下顺序组织的：第一章绪论。给出了进行椭圆曲线密码研究的意义，以及对椭圆曲线密码体制研究现状做了简要的说明，给出了椭圆曲线密码体制的总体设计，以及在设计中面临的问题，最后针对问题给出了可行的解决方案。第二章介绍了实现椭圆曲线密码体制的理论基础，包括有限域运算的基本知识和运算法财，椭圆曲线层的基本概念和基于三种不同的域上的运算法则。第三章详细阐述了有限域运算的四种基本运算，给出了优化的算法，硬件模块的结构以及性能分析。第四章对椭圆曲线运算层进行分析，把椭圆曲线上的点映射到ＬＤ仿射坐标下，进行运算以减少求逆运算的次数，在点加运算和倍点运算的基础上，采用ＮＡＦ编码来标量乘运算过程中点加运算的次数来提高标量乘运算的效率。第五章对设计的模块进行仿真验证，给出了一个应用实例。第六章对本文进行总结，并对今后的工作进行了展望。第二章ＥＣＣ理论基础９第二章Ｅｃｃ理论基础有限域的运算和椭圆曲线上点的运算是椭圆曲线密码体制实现的数学基础。为了论文的完整性，本章介绍了群、域、有限域、椭圆曲线的概念，给出其相应的运算法则，并对椭圆曲线加密体制进行必要的说明。２．１有限域２．１．１有限域定义２．１设Ｇ是一个具有代数运算“・”的非空集合，并且满足：（１）结合律。即对任意口，６，ｃ∈Ｇ，有（口・厶）・ｃ＝４・（６・０；（２）Ｇ中有元素Ｐ，使得对任意４∈Ｇ，有口・ｅ＝Ｐ・口；（３）对Ｇ中的任意口∈Ｇ，有元素６∈Ｇ，使得口．６＝６．口＝Ｐ，则称Ｇ关于运算“・”构成一个群，记作（Ｇ，．）。在不致引起歧义的情况下，也称Ｇ为群。如果群Ｇ的元素的个数有限，则称为有限群，否则称为无限群。当群Ｇ为有限群的时，如果群Ｇ含有疗个元素，则称刀为群Ｇ的阶，记作ＩＧＩ＝刀。定义２．２定义２．３如果群Ｇ的运算“・”还满足交换律，即对任意口，６∈Ｇ，有口・６＝６・口，则称Ｇ为一个交换群，或阿贝尔（Ａｂｅｌ）群。域由一个集合Ｆ和两种运算共同组成，这两种运算分别为加法（用。表示）和乘法（用固表示），并且满足下列算术特性：ｉ（Ｆ，ｏ）对于加法运算构成加法交换群，单位元用Ｏ表示。ｉｉ（Ｆ、｛Ｏ），ｏ）对于乘法运算构成乘法交换群，单位元用ｌ表示。ｉｉｉ分配率成立：对于所有的口，６，ｃ∈Ｆ，都有（口０６）ｏｃ＝００ｃ）ｏ（６圆ｃ）。若集合Ｆ是有限集合，则称Ｆ为有限域，由于它首先由Ｅ．伽罗华所发现，因而又被称为伽罗华域（ＧａｌｏｉｓＦｉｅｌｄ）。有限域ＧＦ（矿）可以看作域ＧＦ（口）上的一个向量空间。其向量是域ＧＦ（ｇ”）的元素，标量是域ＧＦ（ｇ）的元素，在向量的加法运算就是域ＧＦ（ｇ卅）的加法运算，标量域向量的乘法是域ＧＦ（ｇ）的元素与域凹（ｇ”）的元素在域卯（ｇ”）上的乘法运算。这个向量空间的维数是所，并有很多基底（简称为基）。１０椭圆曲线密码体制的研究与实现２．１．２素域有限域的元素的个数称为有限域的阶。存在一个ｑ阶的有限域Ｆ，当且仅当ｇ是一个素数ｐ的幂，即口＝矿，其中ｐ是一个素数并称之为域Ｆ的特征，一是一个正整数。当疗＝１时，则域Ｆ就称为素域，否则称为扩域。定义２．４设Ｐ是一个素数，以Ｐ为模，则模Ｐ的全体余数的集合｛Ｏ，１，２，…，尸一１）Ｐ表示Ｐ除ｘ所得到的余数，，Ｏ≤，≤Ｐ—ｌ，并关于模Ｐ的加法和乘法构成一个Ｐ阶有限域，并用符号砟表示。我们称Ｐ为耳的模。对于任意的整数ｘ，ｘｍｏｄ称这样的运算为求模尸的剩余。例２．１（素域％）昂的元素｛Ｏ，１，…，２８｝。下面是域％的算术运算的例子【ｌ”。２９＝８。ｍｏｄ２９＝２６。１．加法运算：１７＋２０＝８，因为３７ｍｏｄ２．减法运算：１７—２０＝２６，因为一３３．乘法运算：１７×２０＝２ｌ，因为３４０４．求逆运算：１７一＝１２，因为１７×１２ｍｏｄ２９＝２ｌ。ｍｏｄ２９＝ｌ。２．１．３基于多项式基的二进制有限域定义２．５阶为２”的有限域称为二进制域或特征为２的有限域，其中雄≥２。在采用多项式基表示二进制有限域的时候，有限域ＧＦ（２”）的元素是次数最多为ｎ—１次的二进制多项式（多项式的系数取自Ｅ＝｛ｏ，１｝），即对于任意口∈ＧＦ（２”）：口＝｛ｃｈｘ”＿１＋％＿２矿－２＋…＋口２ｘ２＋ｑｘ＋４０：ｑ∈｛Ｏ，１））可以将口∈ＧＦ（２”）表示为长度为”的比特串（％－１吒一２…啦印％）。选择一个二进制域上的欲既约多项式厂（工）（对于任意的胁这样的多项式一定存在，并且可以有效产生）。，（ｘ）的既约性意味着，（∞不可以被分解为次数低于月的二进制域上的多项式的乘积。例如：工２＋ｘ＋１是２次既约多项式，ｘ４＋ｘ＋１是４次既约多项式。对于ＧＦ（２）上的任意ｍ次既约多项式，都能够除尽ｘ，。＋ｌ，例如２次既约多项式能够除尽矿＋ｌ，３次既约多项式能够除尽，＋１等等。假设口＝（口。巳一：…啦ｑ口０）和６＝（％一。阮一：…６２６１６０），则下面给出使用多项式基表示的域元素的运算法则。加法运算ｃ＝口０６＝（巳－１矗一２…岛ｑｃｏ），ｑ＝（ｑ＋６ｊ）ｍｏｄ即域元素的加法即为按对应位进行异或运算。乘法运算ｃ＝口固６＝（６一Ｉ厶一２…乞ｑｃｏ），其中２，ｆ＝Ｏ，１，…，玎一ｌ。第二章ＥＣｃ理论基础ｃ（力＝厶一ｌ，一１＋ｑ一２，一２＋・・・＋乞工２＋ｃｌｘ＋ｃｏ是（％－ｌ】广１＋％－２ｘ’卜２＋…＋呸Ｊ２＋ｑｘ＋％）（％一Ｉ工”一１＋ｑ一２ｘ”一２＋…＋口２ｘ２＋ｑｘ＋％）模既约多项式／（力的余式。求逆运算因为二进制有限域构成了一个循环乘法群，所以域内一定存在非零的生成元ｇ，有限域内其他的元素均可以表示为ｇ的幂的形式，４∈ＧＦ（２”），存在某个正整数膏，满足口＝ｇｔ，则口－ｌ＝ｇ（４）血ｏｄ（ｒ“。（２．１）例２．２下面给出ＧＦ（２４）运算的例子【１４ｌＧＦ（２４）共有１６个元素：（ｏｏｏＯ），（ｏ００１），（００１０），（００１１），（０ｌｏｏ），（０１０１），（０１１０），（０１１１），（１０００），（１００１），（１０１０），（１０１１），（１１００），（１１０１），（１１１０），（１１１１）。其既约多项式为，（ｘ）＝，＋ｘ＋ｌ。１．加法运算：（０１１０）＋（０１０１）＝（００１１）。２．乘法运算：（１１０１）（１００１）＝（ｘ３＋ｘ２＋１）（Ｘ３＋１）ｒ∞ｄ取ｘ）＝ｘ３＋ｘ２＋ｘ＋ｌ＝（１１１１）。３．求逆运算：显然ｇ＝（００ｌＯ）是有限域的一个生成元，则有ｇｏ＝（Ｏ００１），９１＝（００１０），９２＝（０１００），９３＝（１０００），９４＝（００ｌ１），９５＝（０１１０），９６＝（１ｌＯＯ），９７＝（１０ｌ１），ｇ。＝（０１０１），９９＝（１０１０），９１０＝（０１ｌ１），Ｆ１＝（１１ｌｏ），９１２＝（１１ｌ１），９１３＝（１１０１），９１４＝（１００１），９１５＝（０００１）。则ｇ－７＝ｇ‘－７’血０ｄ‘ｒ．１’＝９８。要验证这个公式，可以采用乘法：占７固９８＝（１０１１）（０１０１）＝（∥＋工＋１）（工２＋１）ｍｏｄ，（功＝１＝（ｏ００１），可见结果是完全正确的。在二进制有限域上，可以充分移位运算，比较适合硬件实现。在二进制有限域上进行乘法运算的时候，多项式基相对于正规基来说表示简单，但是运算的速度慢，并且在该域上进行乘方运算很复杂。而采用正规基可以显著提高有限域运椭圆曲线密码体制的研究与实现算的效率。２．１．４基于正规基的二进制有限域对于一个ＧＦ（２）上的脚阶不可约多项式厂＠）。如果在模厂（力的条件下，由向量（，～，广－２，…，，２，，，矿）到向量（ｙ∥，，∥，…，广２，，２‘，，２。）的转移矩阵是可逆的，那么称，（ｘ）为正规多项式（ＮｏｍｌａｌＰｏｌｙｎｏｎｌｉａｌ）。对于，∈ＧＦ（２”），如果它有如下形式的基：（，，∥，，∥，…，广２，广‘，尸），则６Ｆ（２“）在ＧＦ（２）上的基被称为正规基。对于每个有限域ＧＦ（２”），都存在正规基，但是不一定存在ｏＮＢ。当所＞ｌ，且埘不能被８整除时，可令ｒ＝１（Ｉ型）或者丁＝２（ＩＩ型），根据Ｉ髓Ｅ１３６３可以得到检验有限域ＧＦ（２４）是否存在ｏＮＢ的算法２．１【“，表２．１列出了１０００以内，所有存在Ｉ型或者Ⅱ型的ＯＮＢ的域。算法２．１：正规基是否存在检验算法１．Ｐ＝砌＋ｌ２．若尸不是素数，在不存在ＯＮＢ３．求七，使２‘；ｌｍｏｄＰ４．｜ｌｌ＝砌／ｊ｝５．计算ｄ＝ＧＣＤ（而，ｍ）表２．１６．若ｄ＝１，则存在０ＮＢ，否则不存在０ＮＢ。肌≤ｌＯＯＯ时，存在∞旧的珊值第二章ＥｃＣ理论基础定理２．１㈣假设ｍ＋１是一个素数，２是模聊＋１的一个元根，则ＧＦ（２）上的历个非单位元的（ｍ＋１）次单位根是线性无关的，且组成ＧＦ（２“）到ＧＦ（２）的一组最优正规基，记Ⅳ＝｛∥Ｉ扛ｏ，ｌ，…，聊一１｝＝｛∥Ｉ＿，＝ｌ，２，…，肌｝，其中口是一个（肌＋１）次本原单位根，称Ⅳ是ＧＦ（２”）到ＧＦ（２）的一组Ｉ型最优正规基。定理２．２【１６ｌ如果２埘＋ｌ＝ｐ是一个素数，且下面两个条件之一成立：・２是模＿ｐ原根；・ｐ；３（ｍｏｄ４），且２模ｐ的次数为肌，则ｙ＝∥＋∥－１生成一个ＧＦ（２”）到ＧＦ（２）的一组最优正规基，其中∥是（２研＋１）次本原单位根。记作Ⅳ＝｛，一，…，，，’，尸｝＝｛∥＋∥一，…，∥２＋∥“，∥＋∥一，｝，称Ⅳ是ＧＦ（２”）到６Ｆ（２）的一组ＩＩ型最优正规基。设有限域ＧＦ（２”）的ｏＮＢ为（ｙ∥，…，ｙ’，尸），，，∈ＧＦ（２“），域元素口＝（％－ｌ，％。…，ｑ，口ｏ）和域元素６＝（吒。，ｋ－２，…，６ｌ，６０）・则口的ｏＮＢ表示式：口＝∑ｎ，尸，６的ｏＮＢ表示式：６＝∑岛ｙ，ｊ＝Ｏｆ＝ｏ■—１加法运算ｃ＝口＋６＝∑（ｑ＋包）２７，其中ｑ＋包为取异或运算。ｌＩＯ平方运算在正规基下，平方运算为域元素对应的比特串循环左移一位的结果，开方运算为循环右移一位的结果。即：口２＝（４，２，％－３，…，ｑ，口０，％－１）。乘法运算对于乘法法则由一个坍×埘的矩阵Ｍ来表征的。乘法矩阵的定义：”∥∥∥Ｍ＝山‰‰‰蜘‰‰‰蜘‰‰‰蜘‰‰‰…∥竹矿矿户ｐ”廖群英在论文中指出：在有限域的乘法运算中，计算正规基的乘法表Ｔ是快速实现有限域上的椭圆曲线密码体制重要的一环，可以根据乘法表唯一地确定乘法矩阵。下面分别给出求取Ｉ型０ＮＢ和ＩＩ型ｏＮＢ乘法表的运算定理：定理２．３【１６】：设Ⅳ＝｛∥ｆｆ－Ｏ，１，…，小一１）＝｛口，口２，…，矿）（其中口是ｍ＋１次本原单位根）为Ｆ到Ｅ上的一组Ｉ型ｏＮＢ，ｒ＝（ｆ。）为其乘法表，则当，＝０，１，…，加一１时，有１４椭圆曲线密码体制的研究与实现ｆ。＝一ｌ；ｉ√（２－２）当ｆ＝ｏ，ｌ，…，册一１，且ｆ≠罢时，有铲怯翻名舞¨Ｄ’定理２．４‘１６１型最优正规基，ｒ＝纯．，）为其乘法表，则弦，，：设Ⅳ＝｛，＋厂１，，２＋，－２，…，广＋ｙ一”）为ＧＦ（２”）到ＧＦ（２）上的一组ＩＩ幻＝怯毓：’ｈ，：｛：，萄硼‘１或者！二妇（删２ｍ＋１）＇ｋ－１。一１０，否则；侩４，（２＿５）ｕ’）’础＝ｌ，２，…炉２时，她，＝｛Ｌ靴ｋ《２’嚣∽斛耽（２－６）根据求出的乘法表，我们可以轻易获取基于ＯＮＢ下的乘法矩阵【１７１。对于口＝（％一，％：，…，吒，ｑ，％），ｃ＝（？。＿ｌ，％一２，％－３，…，巳，ｑ，ｃｏ）。６＝蛾．．，ｋ：，…，％，岛，钆）∈叩（２”）结果为在实际的运算中，把口循环右移七比特：ｑ＝（ｑ十吼－２，…，４０，％％－２…，吒），６循环右移七比特：丸＝＠．．，瓯。…，６０，吒一．屯。…，瓯），计算：ｑ＝吒慨７从而得到乘法的结果。（２．Ｊ７）求逆运算域中的任何一个元素（Ｏ除外）有且只有一个逆元。给定域中的一个元素口，那么一定存在一个元素６，满足口０６＝ｌ，那么６就是４的逆元。由于口＝口ｒ，所以一：口Ｆ：什一：矿：，“＋一一＝庐＝兀一＝口２＋２～２’一一可见乘法是制约求逆运算的主要因素。（２．８）２．１．５多项式基与正规基的关系Ⅲ一】设／（ｘ）＝，＋∑，一是ＧＦ（２）上次数为所的既约多项式，把厂（ｘ）作为约减多项式的有限域ＧＦ（砂）可以表述为：第二章Ｅｃｃ理论基础ＧＦ（２”）＝∑ｑ一，其中ｑ∈ＧＦ（２）Ｊｌｏ设Ｓ＝｛‰－ｌ，‰－２，…，＾，％｝是ＧＦ（２”）在ＧＦ（２）上的一组基，如果存在∥∈Ｇ．Ｆ（２”），满足量＝∥。，ｏ≤ｆ≤肌一ｌ，则称ｓ为一组多项式基。设Ⅳ＝｛乃＿ｌ，厶－２，…，＾，凡）是ＧＦ（２“）在ＧＦ（２）上的一组基，如果存在，∈ＧＦ（２”），满足＾＝ｙ２，Ｏ≤，ｓ所一ｌ，则称Ⅳ为一组正规基。根据定理２．２，ＩＩ型最优正规基与多项式基有如下的转换形式。因为，＝芦＋矿１，且∥是（２Ｊ，ｌ＋１）次本原单位根，有，ｒ＝（∥＋∥一１）ｒ＝∥ｒ＋∥掣＝∥’＋∥一，Ｏ＜ｒ＜ｐ＝２研＋１，２’＝ｆ（ｍｏｄｐ）当ｍ＋１≤ｒｓ２ｍ，可以用（ｐ—ｆ）代替ｆ，从而，得到下面的定理。定理２．５【１引【１９１两个基集合朋’＝｛∥＋∥一，∥２＋∥＿２，…，∥∥＋∥－２“）和Ⅳ＝｛∥＋∥１，∥２＋∥－２，…，夕“＋∥”）是等价的。假设口关于基Ｍ和Ⅳ的表示分别为（％。，…，呸，ｑ，嘞）和（吒－．，…，岛，岛，％），则根据定理２．５和∥２”１＝ｌ，可以得到口，和岛之间的关系口，＝６ｉ，其中口０１：。Ｉ七（七∈【ｌ，ｍ】）【（２埘＋１）一七｜｜｝∈［所＋１，２，＂】（２－９）后＝２”１（ｎ１０ｄ２ｍ＋１）Ｏ＝ｌ，２，…，ｍ）利用式（２－９）可以实现ＩＩ型ＯＮＢ域元素在正规基和多项式基之间的相互转换。２．２椭圆曲线理论基础椭圆曲线口１１∞】１２３】【２４】【２５１的研究来自于椭圆积分：的求解，其中Ｅ（功是ｘ的三次多项式或者四次多项式，这样的积分不能用初等函数来表达，从而引出了椭圆曲线函数。２．２．１基本概念如果每个系数在Ｋ上的玎阶多项式恰有打个Ｋ中的根，则称域Ｋ是代数封闭的。对于每一个域Ｋ，都存在一个代数封闭的域乏，使Ｋ包含于ｉ中。１６椭圆曲线密码体制的研究与实现定义２．６设Ｋ是一个给定的域，ｉ是它的代数闭域，Ｋ上的三元齐次方程ｏ一’（爿，ｙ，ｚ）＝ＯＥ：），２Ｚ＋口１习Ｚ＋鸭）Ｚ２＝ｘ３＋吒ｘ２Ｚ＋吼】．Ｚ２＋％Ｚ３，其中ｑ，啦，吩，嗍，％∈Ｋ，称为代数封闭域上的ｗｂｉｅｒｓ廿舾ｓ方程。令ｘ＝考，】，＝三，则ｗｅｉｃｒｓ缸ａｓｓ方程在仿射坐标系下表示为，（ｘ，．ｙ）＝ｏ：Ｅ：ｙ２＋ｑ砂＋吩岁＝，＋啦ｘ２＋嘞ｘ＋％，（２・９）且判别式△≠Ｏ，△是保证Ｅ是“光滑”的判别式，满足方程的＠，ｙ）称为域置上椭圆曲线Ｅ的点，除了椭圆曲线上的所有点，还需要加一个特殊的无穷远点。。定义２．７若域Ｋ的特征是２，则通过变量的相容性变换，得到曲线），２＋砂＝ｘ３＋印产＋６其中口，６∈足。这样的曲线称为非超奇异椭圆曲线，且判别式△＝６，记为：Ｅ，６Ｆ（２“）：．，，２＋砂＝ｘ３＋饿２＋６（２－１０）２．２．２椭圆曲线上的运算法则现在我们开始讨论式（２．１０）所确定的椭圆曲线，特别地，当６＝１的时候，我们把式（２．１０）称为Ｋｏｂｌ池曲线（Ｋｏｂｌ池ＣＩｌｎ，ｃ）。此类曲线在实现椭圆曲线密码体制的时候速度比较快。椭圆曲线上的三个点如果在同一条直线上，则我们说它们的和为ｍ（无穷远点），“弦和切线”法则如下：①ｏｏ＝—∞，对于椭圆曲线上任意一点Ｐ＝（ｘ，ｙ），Ｐ＋∞＝Ｐ。②设椭圆曲线上两点Ｐ＝Ｏ，ｙ），Ｑ＝（ｘ，一ｙ），它们的连线是一条垂直线，且与椭圆曲线相交于无穷远点ｍ，所以Ｐ＝—Ｑ。③点加运算：设椭圆曲线上的两个具有不同ｘ坐标的点Ｐ＝（而，Ｍ），Ｑ＝（而，儿），它们的连线与椭圆曲线相交于第三点Ｒ’，则Ｐ＋Ｑ＋Ｒ’＝ｍ，所以Ｐ＋Ｑ＝一Ｒ’，示意图见图２．１。④倍点运算：点Ｐ＝（而，Ｍ）是椭圆曲线上的任意一点，过点Ｐ画切线与椭圆曲线相交于点Ｑ，即２Ｐ＋Ｑ＝∞，２Ｐ＝一Ｑ，示意图见图２－２。图２・ｌ椭圆曲线点加运算示意图而＝彳２＋五＋五＋为＋４（２．ＩＩ）乃２五“＋弓）＋毛＋一其中名２瓴＋儿）“＋屯）－Ｉ（２．１２）１８椭圆曲线密码体制的研究与实现４．倍点。令Ｐ＝（而，Ｍ）∈Ｅ／ＧＦ（２”），Ｐ≠一Ｐ，Ｒ＝２Ｐ＝（屯，乃）那么而＝五２＋２＋口＝葺２＋６（葺２）－１（２－１３）（２－１４）儿＝毛２＋他＋而其中五＝五＋咒（而）。定义２．８其中．｜｝是一个整数，尸是定义在ＧＦ（２”）上的椭圆曲线Ｅ上的一个点，则血Ｐ称之为点乘或标量乘，它决定着椭圆曲线密码体制的运算速度。在一般的密码系统中，Ｐ是固定的，可以通过预计算数据，提高其运算效率。定义２．９设Ｐ是定义在ＧＦ（２”）上的椭圆曲线Ｅ上的一个点，若存在最小的正整数疗，使得，护＝。ｏ（ｍ为无穷远点），则称一是点Ｐ的阶。２．２．３椭圆曲线密码体制自从Ｄｉｆｆｉｅ－Ｈｅｌｌｍ蛆提出公钥密码体制以来，我们提出了很多密码的算法问题，设计了各种各样的密码体制。对于这些密码体制的安全性，一般认为能够经得起各种攻击，就可以认为他们是安全的，如果出现某些攻击有效的情况，可以通过修改密码体制的设计方案来完善，但是随着攻击手段的多样化和新的理论、新的算法的出现，以前认为很安全的密码体制，现在也被认为是不安全的，如Ｃｈｏｒ．黜ｖｅｓｔ密码体制，因此设计新的密码体制在一种程度上可以加强系统的安全性，但是事实上，我们很难确认某种密码体制的安全性。公钥密码体制是以单向陷门函数作为支撑点的，对于单向陷门函数Ｚ（ｘ）：Ｄ专尺，对于任意的ｘ∈Ｄ，很容易计算Ｚ（∞，而对于几乎所有的ｙ∈Ｒ，求出ｘ是非常苦难的。但是如果知道陷门信息ｒ，则对于所有的ｙ∈Ｒ，很容易计算满足ｙ＝Ｚ（ｘ）的工。常见的单向陷门函数主要有ＲｓＡ问题、离散对数问题和Ｄｉ伍ｅ．Ｈｅｌｌｍ锄问题，下面就开始介绍椭圆曲线上的离散对数问题。令Ｅ是定义在ＧＦ（２”）上的椭圆曲线，Ｐ是Ｅ／ＧＦ（２”）上的点，设Ｐ的阶为月，则集合｛ｏｏ，尸，２Ｐ，…，∽一１）日是由Ｐ生成的椭圆曲线循环子群。椭圆曲线方程Ｅ，点Ｐ和阶胛构成公开参数组。私钥是在区间【ｌ，门一１】内随机选择的正整数ｄ，相应的公第二章ＥＣＣ理论基础１９钥是Ｑ＝卯。２．２．４椭圆曲线密码体制的安全性分析对于公钥密码体制的安全性要求一般都是针对密文的特性而言的，就是说，密文应该满足某种安全特性。目前被国际密码界广泛接受的密文的安全性要求主要有以下几种：单向性，不可区分性和不可扩展性。单向性就是说攻击者在没有拥有私钥的前提下，无法计算出任何密文所所对应的明文信息加。不可区分性就是说对己知给定的两个明文，加密者随机一致的选择其中一个进行加密，攻击者无法从密文中知道是对哪个明文的加密。不可扩展性就是说攻击者无法构造与已给密文相关的新密文。在公钥密码体制中，攻击者拥有公钥，他可以随便选择明文进行加密，攻击者还有机会获得密文，而且还可能利用各种途径来获得解密，为此，公钥密码体制应该不会泄露其他密文的明文信息，这就要求该密码体制能抗选择密文攻击。椭圆益线密码体制的安全性基于椭圆曲线离散对数问题（ＥＣＤＬＰ）的难解性。目前还没有有效的快速算法来解决这一难题，它只有指数级的算法。这也是椭圆曲线密码体制的安全基础。ＥＣＤＬＰ问题就是，给定椭圆曲线Ｅ，基点Ｐ和Ｐ的一个标量乘Ｑ，来确定一个正整数七。满足Ｑ＝舻。从目前的研究来看，ＥＣＤＬＰ比有限域上离散对数问题（ＤＬＰ）更加难以处理。已经知道的对椭圆曲线的攻击方法主要有以下几种，设椭圆曲线上的基点Ｐ，Ｐ的阶为胛。１．穷举搜索法计算２Ｐ，３Ｐ，４Ｐ，…直到找到Ｑ，这种算法最多需要胛步椭圆曲线的点加。２．大步小步法这种算法的思想在于测试Ｐ的倍点运算是否等于Ｑ，利用一种数据结构，具体的做法是，预先计算并存储一些Ｐ的某些倍点（小步）运算的结果，然后对于某个整数，，计算Ｑ一护，Ｑ一２护，…（大步），直到Ｑ—ｆ，户在预存表中出现。３．ＭＯＶ攻击其核心思想是将椭圆曲线离散对数问题转化为某个有限域的乘法群上的离散对数问题，此类攻击只对超奇异椭圆曲线有效，该算法导致出现了亚指数的ＥｃＤＬＰ求解算法，所以在对椭圆曲线的参数进行选择的时候，避免出现这一情况的出现。４．ｗｅｉｌｄｅｓｃｅｎｔ攻击这种方法只适合于特征值为２的复合域，在椭圆曲线密码体制的实际应用种，我椭圆曲线密码体制的研究与实现们可以选择所为素数的ＧＦ（２”）来避免此类攻击。５．Ｐｏｌｌａｒｄ’ｓｒｈｏ算法从目前来看，对ＥｃＤＬＰ最有效的攻击就是并行Ｐｏｌｌａｒｄ’ｓｒｈｏ算法攻击，这种算法是小步大步算法的随机版本，它的运行时间和小步大步算法差不多，只是需要很小的存储空间，该算法可以在几种处理器上并行，其运行时间为√丌ｍ步点加运算。有学者指出，如果肌＊２。，花费ｌｏｏＯ万美元建立具有３２５０００并行处理的Ｐｏｌｌａｒｄ’ｓｒｌｌｏ算法来解决ＥｃＤＬＰ需要３２天左右，而在实际的工作中，我们一般采用的都是珊≥１６０，因此可以说椭圆曲线密码体制是比较安全的。ｃｅｎｉｃｏｍ是ＥＣＣ的主要商业支持者，拥有超过１３０项专利，并且已经以２５００万美元的交易获得了国家安全机构（ＮｓＡ）的技术许可。他们也已经发起了许多对ＥＣＣ算法的挑战。已经被解决的最复杂的是１０９位的密钥，是在２００３年初由一个研究团队破解的。破解密钥的这个团队使用了基于生日攻击的大块并行攻击用超过１０。ｏｏＯ台奔腾级的ＰＣ机连续运行了５４０天以上。对于ＥＣＣ推荐的最小密钥长度１６３位来说，当前估计需要的计算资源是１０９位问题的１０８倍。２．２．５椭圆曲线上域参数的选择在椭圆曲线密码体制的硬件实现中，有限域ＧＦ（２”）上相对于ＧＦ（ｐ）的运算快很多，用最优正规基表示下的有限域ＧＦ（２”）元素运算相当高效。最优正规基分为Ｉ型和ＩＩ型，一般认为最优正规基的类型值越小，其运算速度越快，但是在实现中，由于ＩＩ型最优正规基的存在个数大约是Ｉ型的３倍，所以对ＩＩ型ｏＮＢ的研究也是我们工作的重点。根据我们上面对椭圆曲线密码体制安全性的探讨，存在着对某些特殊类型的椭圆曲线的亚指数攻击，所以，在对椭圆曲线以及它的基点的选择上，必须避免以下几种情况：１．满足撑Ｅ（ＧＦ（２”））＝２”的椭圆曲线。２．椭圆曲线的基点的阶不是素数。３．椭圆曲线不可以是超奇异椭圆曲线。２．３小结有限域的运算和椭圆曲线上点的运算是椭圆曲线密码体制实现的基础。椭圆曲线加密系统一般是建立在有限域ＧＦ（ｐ）和有限域ＧＦ（２”），其中对于ＧＦ（２“），第二章Ｅｃｃ理论基础２ｌ根据基的不同，又分为多项式基和正规基。本章主要论述了基于ＧＦ（２“）的运算定理，重点在于基于正规基的构造，正规基的运算，以及椭圆曲线的基本性质和一类特殊的椭圆曲线（非超奇异椭圆曲线），给出了其运算法则。第三章有限域算法的实现第三章有限域算法的实现素域结构简单，元素的表达也比较方便，在其上也有很多比较成熟的算法，比较适合软件实现。在这样的域中，主要问题通常是模素数的大数运算。而在有限域ＧＦ（２”）中，元素都是一定长度的Ｏ和１的比特串，特别符合硬件中对元素的表示，而当采用最优正规基来表示域元素的时候，可以充分地利用移位运算，元素的运算是十分高效的，所以，我们这里采用基于最优正规基的二进制有限域来实现椭圆曲线密码体制。３．１加法运算有限域ＧＦ（２”）的加法运算，就是对元素的二进制表示序列按位进行异或运算。输入数据：口，６ＥＧＦ（２”），输出数据为ｃ∈ＧＦ（２４），利用异或门来实现，利用ＶｃｒｉｌｏｇＨＤＬ描述就是简单的语句，ｎ船ｉ｛弘ｃ＝口“６；，生成运算模块如图３．１所示，其运算几乎不占用时钟周期。因为对于域元素来讲，其加法逆元为其自身，所以减法运算等同于加法运算。图３．１加法运算模块３．２平方运算用正规基来表述的域元素，最大的运算优势就是平方运算，这个在多项式基下比较费时和消耗资源的运算，转变为一个简单的循环移位操作。输入数据：口∈ＧＦ（２“），输出数据为口２∈ＧＦ（２”），利用控制信号ｒｌＲｏＲ来控制循环移位，在实际工作中，一个时钟周期内完成运算，并稳定输出，生成运算模块见图３．２．２４椭圆曲线密码体制的研究与实现图３．２平方运算模块３．３乘法运算有限域的乘法运算具有无进位，无误差的特点，在纠错码、密码学、数字信号处理领域有着广泛的应用，本节在分析各种算法原理和硬件结构的基础上，给出了乘法矩阵的几种运算方法，并设计了满足所有基于Ｉ型或者Ⅱ型最优正规基的串并皆可的乘法器。３．３．１乘法矩阵的构造根据式（２－７），乘法运算的核心部件为乘法矩阵，在最优正规基的情况下，该矩阵是一个稀疏矩阵，除第ｌ列只有一个ｌ外，其余各列都只有两个ｌ。对于存在ｏＮＢ的正整数州，根据算法３．１，可以确定其是Ｉ型或者ＩＩ最优正规基，对ＧＦ（２“）为Ｉ型最优正规基，其既约多项式厂（工）＝，＋ｘ“＋…＋ｘ２＋ｘ＋ｌ，对ＧＦ（２”）为Ⅱ最优正规基，其既约多项式，（工）＝厶（ｘ）有下面递归的形式啪】：五（ｘ）＝１，』（ｘ）＝工＋ｌ，Ｚ（ｘ）＝】兀ｌ（石）＋丘２（工）ｆ＝０，１，…，掰一１。在这里需要注意的是，在每一步运行的时候，多项式的系数，进行模２操作，Ⅳ＝｛ｘ∥，ｘ∥，…，ｘ７，工’，ｘ２。）即为ＧＦ（２“）在ＧＦ（２）上的正规基。算法３．１【２７】：乘法矩阵的获取输入：正整数ｍ。输出：正规基乘法矩阵，。１．构造运算矩阵４：把一ｍｏｄ厂（ｘ），ｆ∈【Ｏ，ｍ—ｌ】，构成的向量作为矩阵的第行亍。２．在ＧＦ（２）上对矩阵Ａ求逆，得到４一。３．构造运算矩阵７’’：把就７ｍｏｄ，（ｘ），ｆ∈【Ｏ，所一ｌ】，构成的向量作为矩阵笙三皇童堡堡簦鲨塑壅堡的第＿ｉ彳＝亍。４，在Ｇ＿Ｆ（２）上计算乘法表ｒ＝７’’爿一。．————．竺５．计算乘法矩阵，，满足Ｌ＝五Ｊ．ｊ。－ｊ）（五∽表示ｒ内元素（ｇ，矗）位置进行模脚运算），其中ｆ，，∈【ｏ，＿Ｉ，ｌ一１】。例３．１求取ＧＦ（２４）的乘法矩阵口刀１．当拼：４的时候，其存在Ｉ型最优正规基，则既约多项，（力＝≯＋≯＋ｘ２＋ｘ＋ｌ，正规基Ⅳ：｛，，，，一，，＇。２．矩阵４由以下的结构组成：第Ｏ行：工ｍｏｄ，（ｘ）＝工＝（ＯＯｌＯ），第ｌ行：ｘ２ｍｏｄ，（ｘ）＝，＝（ＯｌＯＯ），ｌ１第２行：一ｍｏｄ，（ｘ）＝矿＋ｘ２＋工＋１＝（１第３行：，ｍｏｄ，（ｘ）＝矿＝（１因此，可以得到ＯＯ彳＝１ｌｌＯｌ０ＯＯ１），０）。ＯｌｌＯＯＯｌＯ１．在ＧＦ（２）上，可以得到ＯＡ一ＯｌＯｌＯＯＯｌＯ＝１１２．矩阵ｒ’类似矩阵■得到１Ｏｒ’＝０ｌＯ１１１ＯＯＯＯ３．计算乘法表ｒＯＯ？＝１ＯｌＯｌｌｌ０１ＯＯ０Ｏ１４．计算乘法矩阵，椭圆曲线密码体制的研究与实现Ｏ０，＝１Ｏ００１ｌｌ１ＯＯＯｌＯｌ算法３．１虽然有其运算普遍性，但是由于需要计算矩阵的逆，而矩阵的求逆是复杂耗时的运算，其优化算法的效率也比较低下，因此在实际的应用中，我们采用下面的两个算法来分别计算Ｉ型最优正规基和Ⅱ型最优正规的乘法矩阵。根据定理２．１，在基于Ｉ型ｏＮＢ的情况下，我们可以得到算法３．２．算法３．２：基于Ｉ型ｏＮＢ的乘法矩阵输入：正整数册。输出；正规基乘法矩阵，。１．求出（ｆ，ｓ（ｊ））满足２‘；ｓ（ｆ）＋１（ｍｏｄｍ＋１），Ｖｆ＝ｏ，１，２，…，脚一１。２．显然Ｊ（Ｏ）＝０，把ｓ（ｆ）Ｏ＝ｏ，ｌ，…，ｍ—１）按从小到大的顺序排列得到循序对：（Ｏ，ｏ），（＾，１），（＾，２），…，（厶。，所一１），其中Ｊ“）＝ｆ，Ｚ＝１，２，…，ｍ一１・３．写出满足条件Ｖ七＝Ｏ，１，…，ｍ一１，ｓＵ）＝ｓ（七）＋１的（Ｊｊ｝，，）对为：（Ｏ，＾），（＾，止），…，（＾ｔ，＾。）。４．在乘法表ｒ＝“．，）中，有：Ｖ七＝０，ｌ，…，坍一ｌ，七≠册／２，钿＝１：ｆ。＝１，Ｗ＝Ｏ，１，…，ｍ—ｌ；而其余的‘，取值为Ｏ。５．根据算法３．１的第５步计算出乘法矩阵，。例３．２ＧＦ（２４）乘法矩阵２埘＝４，则为Ｉ型ｏＮＢ，根据算法３．２，编制的Ｃ程序直接给出了其乘法矩阵，见图３１３。图３．３坍＝４时，求出的乘法矩阵可见，其结果和算法３．１一致，并给出了其非零元素的个数Ｃ。＝２ｍ一１＝７。算法３．３：基于ＩＩ型ｏＮＢ的乘法矩阵输入：正整数所。输出：正规基乘法矩阵，。１．求出（ｆ，ｓ（ｆ））满足２‘；±（Ｊ（ｆ）＋１）（ｎｌｏｄ２ｍ＋１），Ｖｆ＝ｏ，１，２，…，胁一１。２，显然ｓ（ｏ）＝Ｏ，把ｓ（ｆ）（扛ｏ，ｌ，…，ｍ一１）按从小到大的顺序排列得到循序对：（０，０），（＾，１），（＾，２），…，（厶一Ｉ，肌一１），喜ｅ中ｓ（Ｚ）＝ｆ，Ｚ＝１，２，…，脚一１。３．写出满足条件Ｖ七＝Ｏ，１，…，ｍ一１，Ｊ（，）＝Ｊ＠）＋１的（七，Ｄ对为：第三章有限域算法的实现（Ｏ，＾），（＾，五），…，（＾－２，Ｌ．，）。写出满足条件Ｖ七＝Ｏ，１，…，肌一１，ｓ（ｆ）＝ｓ（七）一１的（．｜｝，ｆ）对为：（＾，ｏ），（五，石），…，（五－－，．，，ｚ）・４．求出＿，＝Ｏ，１，２，…，掰一１，使得２”１；±３（ｍｏｄ２研＋１）。１．在乘法表ｒ＝辑，，）中，有：Ｖ七＝ｌ，…，ｍ一２，‘Ｊ＝ｌ；ｆ０’１＝１；‘－１．，＝ｌ，若，＝以一ｌ或者２’“ｉ±３（ｍｏｄ２脚＋１）；余的ｆ。，取值为Ｏ。６．根据算法４．１的第５步计算出乘法矩阵，。计算有限域上Ｉ型和ＩＩ型最优正规基的乘法矩阵，当有限域ＧＦ（２”）的ｍ小时，根据算法４．２和算法４．３，计算十分简单。在有限域上椭圆曲线密码体制中，一般ｍ取三位数，即使取到四位数，计算也不复杂，因此，上述的两个算法对计算椭圆曲线密码体制中的有限域运算的乘法矩阵是十分有效的。３．３．２乘法模块的实现乘法运算的优劣直接关系着整个密码体制的运行效率，因此，乘法运算在整个系统的运行中，起着举足轻重的作用，我们在这里就乘法运算的实现进行详细的探讨，下面先给出串行乘法器的算法３．４。算法３．４【２８１：串行乘法器输入：口＝（％一ｐ％－２，…，ｑ，口ｏ），６＝（％－１，％－２，…，６Ｉ，％）输出：ｃ＝（％．１，％．２，…，ｑ，吒）１初始化：ｘ＝口，Ｊ，＝６，ｄ＝ＯＦＯｒｉ＝Ｏｔｏｍ２．１２ｄ＝ｄ＞＞１，ｄ［肌一ｌ】＝Ｆ（并，力ｘ＝ｘ＞＞ｌ，ｙ＝），＞＞ｌ２．２其中，（口，６）为乘法矩阵。３返回ｃ＝ｄ利用上面的算法，珊＝１６２的时候，我们可以得到乘法器的电路图见图３．４。椭圆曲线密码体制的研究与实现Ｋ直－●：ｊ舞存矗＾—仆１广习—一习巴透鼙舔。ｌ—‘’■＆ｔ————————ＪｌｔＨ———一ｊＥ絮１ｒ宙Ｅ墨醪司｝＝￡’ｉ＾ｊ马霹嚣瑟一吵。‘’ｂ＆ｔ————————．ＪＩ燧到ｌＩ哥睁蝴嚣娃ｔ图３．４．乘法器内部电路图硬件乘法器主要由循环移位寄存器Ａ和循环移位寄存器Ｂ、运算矩阵、移位寄存器Ｃ、控制状态机、计数器构成。当系统接收到来自上层调用的复位信号ｎＲＥｓＥＴ，乘法器在状态机（运行状态图见图３．Ｓ）的控制下进入ＭＴＩＤＬＥ状态，当ｎＥＮ没有下降沿的时候，ｔｏＲＩＪＮ信号为０，乘法器处于等待状态，乘法器为空闲状态ＢｕｓＹ＝ｏ，ｎＤｏＮＥ＝ｌ，并不断复位其他的模块，当ｎＥＮ有效的时候，ｔｏＲＵＮ＝ｌ，进入ｈ仃Ｓ１＇ＡＲＴ状态，设置乘法器为繁忙状态ＢｕＳＹ＝ｌ，设置所需要的参数如第一次进入，设置寄存器Ａ，寄存器Ｂ为数据加载模式，查询计数器的状态，当ｃｏｌｌＩｌ＿研的数值在计算最后一个比特位（这里为１６１）之前，进入ＭＴＲｕＮ状态，等待来自运算矩阵的信号，当运算正常结束的时候，ｔｏＰＩ的Ｃ＝ｌ，把运算结果送入寄存器Ｃ，并使寄存器Ｃ移位，同时重新进入ｍＳＴ觚ｒ状态，当不是第一次进入的时候，设置寄存器Ａ和寄存器Ｂ为自动循环移位，判断状态循环，当循环次数为１６ｌ的时候，进入最后一位的数据处理状态ＭＴＤｓＰ，等待运算矩阵正常运算结束的信号，输出最后的结果ｄｏｍ，并输出一个负脉冲ｌｌ【＇ｏＮＥ，同时复位计数器，判断是不是下一个运算许可ｔｏＲｕＮ，如果许可直接进入Ｍ丌ＳＴＡＲＴ开始新的计算循环，否则进入ＭＴＩＤＬＥ，继续等待。乘法器完成后，寄存器Ｃ存储的数据ｒｅｇｃｏｕｔ就是ｄｉＩＩａ和ｄｉｌｌｂ两个有限域元素的乘积。第三章有限域算法的实现ｔｏＲＵＮ＝口图３．５串行乘法器控制状态机运行图上面给出的串行乘法器虽然硬件上实现简单，消耗资源也不大，但是其太低的运行效率使得在实际的工作中应用很少，所以需要开发新的乘法器来满足现实的需求，根据式（２—７），我们可以得到以下的形式：ｑ＝（‰４，２，…，口¨，％）Ｍ（６Ｈ，６＿．２，…，６¨，九）７，在这里针对不同的字长ｗ，我们得到修正ｗ一蹴护Ｑ伫９１ｐ０１Ｄｕ口２１后的算法３．５。算法３．５：修正ｗ一肌俨％算法输入：口＝（％。，％－２，…，啦，ｑ，口ｏ），６＝（６卅。，ｋ。，…，６２，６ｌ，‰）。输出：ｃ＝（％－ｌ，ｃ埘－２，…，乞，ｑ，岛）＝口０６。１．初始化数据：ｘ＝（口州，％一…，色，ｑ，‰），ｙ＝（６卅＋吒－２，…，６２，６ｌ，６０），Ｄ＝（靠Ｈ，‰－２，…，吐，吐，磊）＝Ｏ，（七＝ｉ１１ｔ（脚／ｗ）＋１）；２．对于ｆ＜七，执行循环２．１Ｄ＝Ｄ２’＋（ＸＷ）；２．２工＝ｘ”，ｙ＝】，”；３．ｃ＝（如。，办。，吐，吐，巩）。ＶｅｒｉｌｏｇＨＤＬ具有很强的行为描述能力，主要用于描述数字系统的结构、行为、椭圆曲线密码体制的研究与实现功能和接口，根据算法３．５，下面以所＝１９ｌ为例给出乘法器的接口描述。ｍｏｄｕｌｅｍｕｌ“ｃ此ｎＲＳＴ．ｎＬＯＡＤ－－Ｂ，ｎＬＯＡＤＡ，ｎＭｌⅡ，Ｓ１ＡＲＴ，ＲＥＧＡ．ＭＵＬ，ＲＥＧＢ－－ＭＵＬ，ｎＭＵＩ，ＤＯＮＥ，ＤＯＵＴ－－ＭＵＬ）；ｐ盯锄ｅｔｅｒ、丽ｄｕｌ－１９１；呻ｌｌｔｉｎｐｕｔｃ邺Ｔ，ＩｌＬＯＡＤＭｄ“ｌ：Ｏ】ＲＥＧＡＡ，ｎＩ，ＯＡＤＢ，ｎＭＩⅡ，ｓＴＡＲＴ；ＭＩⅡ。ＲＥＧＢＭＩⅡ‘叫ｔｐｕｔｎＭ【ＪＩ—ＤＯＮＥ；ｏｕｔｐｕｔ【讲ｄｔｌｌ－１：Ｏ］ＤＯＵＴ＿．ＭＵＬ；ｅｎｄｎｌｏｄｕｌｅ其中ｃｎ（为时钟，ｎＲＳＴ为复位信号，ｎＬ０√虹）ＬＡ，ＩｌＬＯＡＤ．－Ｂ分别把Ｉ也ＧＡＭＩⅡ，，ＲＥＧＢ』虱几装载到循环移位寄存器Ａ和循环移位寄存器Ｂ，ＤｏＵＴＭＩⅡ。为输出结果，ｎＭＩⅡ，ＤｏＮＥ为运行结束标志。下面给出乘法器的硬件实现系统结构，见图３．６。图３．６乘法器硬件结构图从图３．６可以清楚的看出，乘法器主要有循环移位寄存器Ａ和循环移位寄存器Ｂ，运算矩阵（乘法矩阵），移位寄存器Ｃ，计数器和有限状态机构成。其中循环移位寄存器的移位位数可以利用参数来设定，使之满足算法３．５的要求，乘法矩阵是根第三章有限域算法的实现３ｌ据算法３．２或者算法３．３确定的与异或运算阵列，一次输出的位数由ｗ一蹴铲Ｄ，，的ｗ决定，移位寄存器Ｃ是存储运算中的临时结果，并在运算完成后，在状态机的控制下，输出ｍ位结果。下面乘法状杰机的状态转换图，见图３．７。图３．７．乘法状态机转换图从图３．７可以看出，当数据处于就绪状态，乘法开始运算信号有效，就由ＩＤＬＥ状态进入ＳＴＡＲＴ状态，然后进入ｗＡＩＴ状态等待乘法矩阵输出ｗ位数据，然后进入ＲＵＮ状态，发送信号给计数器，表示完成一次计算，返回ＷＡＩＴ状态，判断移位次数是不是已经是七，如果是，进入ＥＮＤ状态，否则仍然等待，进入ＲｕＮ循环，在ＥＮＤ状态，输出结果，运行结束，进入下一个开始运算状态或者进入ＩＤＬＥ状态。３．３．３性能分析根据实际的情况，适当选择ｗ的数值，当ｗ＝１的时候，称为串行乘法器，当ｗ＝所的时候，称为并行乘法器，当１＜ｗ＜ｍ的时候，称为串并结合结构的乘法器。图４．６设计的乘法器，只要预置合适的参数，更换乘法矩阵，就可以完成Ｉ型最优正规基或者ＩＩ型最优正规基的运算，所以这里不再对最优正规基的类型做专门的说明，从某种意义上来讲，它是通用的，只是根据硬件条件和运算速率的要求，选择合适的ｗ值，来寻求资源消耗和运行速度之间的平衡。下面以ＩＩ型最优正规基为例，当小＝１９ｌ的时候，对ｗ＝８，ｗ＝１６，ｗ＝３２的时候的运行速率和资源消耗做简要的分析，对比见表３．１。表３．１．字长消耗ＡＬｕＴｓ乘法矩阵ｗ＝８１３９６不同字长的乘法器性能比较消耗ＡＬＭｓ消耗逻辑寄存器运行时钟周期乘法矩阵其他单元１０３ｌ７９ｌ１２９６２５１８９２其他单元总计乘法矩阵１４２０３２７４总计乘法矩阵椭圆曲线密码体制的研究与实现其他单元３２９８６４０３ｗ＝１６其他单元总计乘法矩阵７９９２６８３４７３２８１５４８７４５０总计乘法矩阵其他单元ｗ＝３２其他单元总计６４２７２６总计在功能仿真真确的基础上，分别对三种不同的字长做了性能的综合分析，通过分析（详细见表３．１）可以看出，随着字长ｗ值的增加，占用的逻辑资源逐步增大，特别是完成乘法必须的乘法矩阵逻辑阵列，基本成线性增长趋势，而完成运算的时钟个数成比例下降，在实际的设计中，为了实现速度和消耗资源之间的平衡，以及为了对后面所要设计的椭圆曲线密码体制的其他模块进行分析，在以后设计和分析中，均取＇‘，＝１６的乘法器作为最终的处理核的部件，此时完成一次有限域的乘法运算，需要５０个时钟周期。３．４求逆运算求逆算法在编码理论和密码学中具有广泛的应用，应用求逆算法还可以降低指数运算的复杂性【３３１，当有限域的元素用正规基来表示时，根据式（２．８），我们可以看出有限域的求逆算法可以转换为域元素的平方运算和乘法运算，而平方运算可以通过一个循环移位来实现，所以降低乘法运算的次数就成为设计求逆运算的关键。３．４．１优化求逆算法设工是ＧＦ（２”）上的任意的非零元素，那么ｘ２＿－１＝ｌ，所以ｘ～＝ｘ２一一２＝（ｘ２。４－１）２。显然求逆运算是一种特殊的指数运算，设６：ｘ∥一，则ｒ１：６２。把ｍ一１表示为二进制的形式（口０ｑ…吼）２，其中％＝ｌ，为数据最高位。定义递推关系式啊＋ｌ＝２ｑ＋ｑ＋ｌ，Ｏ≤ｆ≤Ｊｊ｝一ｌ，‰＝ｌ（３－１）第三章有限域算法的实现工＝ｘｐ－１（３—２）显然从式（３－２）得到％＝ｘ，６＝黾，根据式（３・１）和式（３－２），可以得到下面的递推关系：＂｛ｘ嘉，：拦根据以上的推理分析，我们可以得到算法４．６。算法３．６：简化求逆算法输入：正整数所，非零任意域元素ｘ∈ＧＦ（２”）。输出：域元素ｒ１。１．初始化数据：令疗＝脚一１，根据七确定珥，喝。设置，＝１；２．根据递推关系式（４．３）计算置；３．ｆ－ｆ＋ｌ，如果ｆ＜七，则转向第２步：＠ｓ，４．一＝黾２，则求逆运算结束。算法３．６可以大大提高了求逆运算的运行效率，在设计前预计算相关数据，进行ＡＳＩＣ的设计是其应用的方向。ＳａｌｌｇＨｏ０ｂ和Ｃｈ锄ｇＨ锄砌ｍ【３４１提出了一种算法，该算法在乘法数量上可以和ｎｏｈ【３５１算法相等，但是其更适合硬件实现，该算法的描述见算法３．７，流程图见图３．８。算法３．７：优化求逆算法（ｏＩＡ－ｏｐｔｉｍａＩＩｎｖｅ玮ｅＡｌｇｏｒｉｔｈｍ）输入：正整数ｍ，口∈ＧＦ（２”）输出：口。１．初始化数据：，＝肼一１，Ｊ＝ｌ，甜＝口２：２．当ｆ＞Ｏ，执行下面的循环２．１如果ｆ０＝Ｏ，且ｒ＞１执行下面的操作２．１．１把ｆ向右移动一位；２．１．２甜＝甜．材，：如果“≠０则执行下面的操作２．２ｚ＝ｚ・Ⅳ：２．３如果ｆ＝１，则运算完成；２．４女Ⅱ果ｆ≠１，“＝甜２，“＝Ｏ；３．返回逆元（ｘ）。注意：令ｆ＝（‘一。‘一：…‘％）：，ｆ的向右移位为（Ｏ，‘一。‘一２…‘ｆ０）：。椭圆曲线密码体制的研究与实现图３．８．ｏＩＡ算法流程图可见ｏＩＡ算法对数据的位数没有特殊的要求，在乘法器固定的情况下，可以通过适当的控制器参数设计，就能满足设计中通用的要求，因此在本论文中，求逆运算模块的硬件设计采用０ｎ算法来完成。３．４．２求逆模块的实现根据算法３．７，我们利用Ｖｅ！ｒｉｌｏｇＨＤＬ语言对域元素求逆模块进行描述实现，接口描述为：ｍｏｄｕｌｅｉＩⅣ（ｃｌｋｎＲＳＴ－删蛰吣弧。ｄｉｎ＿ｘ，ｎＩＮＶ＿－ＤｏＮＥ，ｄｏｕｔｉｎｖ）；ｐａｒ锄ｅｔｃｒ晰ｄｔｌＦｌ９ｌ；ｉｔｌｐｕｔｉｎｐｕｔｃｌｋ；ｎＲＳＴ．ｎＩＮＶ—ＳＴＡＲＴ．ｉ印ｕｔｉｌｌｐｕｔｏｕｔｐｕｔＭｄｔＩｌ－ｌ：Ｏ】ｄｉｎ＿ｘ；ＩｌＩＮＶ—ＤＯＮＥ；ｏｕｔｐｕｔ【埘ｄｍ－１：Ｏ】ｄｏｌｌｔｊｎｖ；第三章有限域算法的实现ｅｎｄｍｏｄｕＩｅ下面给出其实现的数据通道硬件结构图３．９和控制通道硬件结构图３．１０。翩，Ｈ９潮，Ｉ强—’ｍ●ｄ科嚣Ｉ越４嘲，疆裎棚｛Ｖ＿图３．９当ｍ＝１９１时，域元素求逆模块数据通路硬件实现结构图可见在有限域元素求逆运算的过程，其实是对乘法运算器进行控制来完成的，域元素求逆控制单元其实就是对求逆控制器的优化管理单元，下面给出对域元素求逆模块控制通路硬件实现结构图（图３．１０）的文件描述。求逆运算控制单元主要有计数器ＲＥＧＴ和求逆运算状态机组成。ＲＥＧＴ用来存储ｍ一１，并且具有右移和末尾清零的功能，它的数值用来控制状态机的循环次数，循环单元的循环左移次数，以及运算中的跳转条件，当ＲＥＧＴ的值为１的时候，运算结束。循环单元用来对寄存器ＲＥａ，的数据进行循环左移，以获取运算所需要的∥。求逆状态机的主要输入信号有：求逆运算器开始信号ｌｌＩＮＶｓＴＡＲＴ，循环单元完成标志ｎＬＯＯＰＤｏＮＥ，乘法器运行结束标志ｎＭＩ『Ｉ．ＤＯＮＥ，以及Ｉ汪ＧＴ的数据ＲＥＧＴ。输出信号主要有：寄存器ＲＥＧＵ的写有效信号ｎⅪ！ＧＵ、ⅣＥ、循环左移信号ｎＩ也ＧｕＲＯＲ、数据来源选择信号ｎｓＥＬＵ，寄存器砌粥Ｘ的写有效信号ｎＲＥＧＸｗＥ、数据来源选择信号ｎｓＥＬｘ，乘法器运算因子的选择信号ｌｌｓＥＬ和完成信号小ⅣＸ。瓜麟Ｊ鐾Ｉ一～一～旭娜ｏ图３．１０当所＝１９１时，域元素求逆模块控制通路硬件实现结构图求逆运算控制模块单元的有限状态机的转换图如图４．１１所示。这个状态机共有１４个状态，ｎＩＮｖＳＴＡＲＴ为求逆运算开始信号，Ｉ也ＧＴ的数据对应算法４．７的，值，在状态图中，ＬＯＯＰ是当第一次进入数据处理的时候，判断ＲＥＧＴ的数据是椭圆曲线密码体制的研究与实现否符合运算的条件，在ＴｓＨＲ中，对ＲＥＧＴ进行移位操作，因为数据操作的完成需要一个时钟周期，所以在下一个时钟周期，即状态ｗＴＴＳ，把数据送入循环寄存器，并对ＲＥＧＵ的数据进行ｆ次移位操作，这是一个比较浪费时间资源的操作，以肌＝１９０为例子，当第一次进行操作的时候，至少需要９５个时钟周期，进入等待状态ＵＴ、ⅣＴ，当移位操作完成信号输出的时候，就可以调用乘法模块开始Ⅳｏ∥运算，运算结束后吧数据存入寄存器Ｉ也ＧＵ，并根据判断条件ＲＥＧＴ＞ｌ＆＆ＲＥＧ【０】一１，来执行算法３．７的第２步，当不符合条件的时候，进入ＲＥＧｘ状态，来执行甜ｏｘ运算，在状态ＬＡｓＴ中判断是否符合模块运行结束的条件Ｉ也ＧＴ！一１，如果符合则继续进行算法３．７的第２步继续循环执行，否则在状态ＥＮＤＰ输出结果，模块进入ＩＤＬＥ状态等待下次运行的开始。图３．１１求逆状态机的有限状态图３．４．３性能分析根据算法４．６，我们可以得到求逆算法的运算过程。设ｍ＝１９１，工是ＧＦ（２”）上任意非零域元素，由坍一ｌ＝１９０，可以得到％＝吒＝呜＝啊＝如＝‰＝１，口ｌ＝唧＝Ｏ；％＝１，啊＝２，也＝５，，玛＝１ｌ，一＝２３，，传＝４７，魄＝９５，嘞＝１９０。根据式（３－３）的迭代得而２麒２＝ｘ２２一，而＝Ｈ五而２２）２＝ｘ２。１，而＝ｘ（屯屯２５）２＝工２”一，毛＝ｘ（而毛２“）２＝ｘ２”一，弓＝ｘ（矗矗２”）２＝Ｊ２”一，第三章有限域算法的实现３７％＝颤％毛２卅）２＝ｘ护一，而＝％％２＝工２”～，ｒ１＝Ｌ２＝ｘ妒－’。显然完成运算需要１３次乘法和１９０次平方运算，因为乘法运算是具有运算复杂度较高的运算，平方运算可以用一个循环移位来实现，所以可以记简化求逆算法的运算复杂度为１３Ｍ（Ｍ为乘法运算次数，后面不再说明）。而对于优化求逆算法（０ＩＡ），Ｉｔｏｈ【４】指出，完成一次求逆运算所需要的乘法次数最少为，（ｍ）＝【ｌｏｇ：（ｍ一１）】＋似脚一１）一ｌ，其中似棚一１）表示域ＧＦ（２”）中（聊一１）的二进制表示式中１的个数。所以可以记优化求逆算法的运算复杂度为１３Ｍ。根据上面的理论分析我们可以清楚的得到，简化求逆算法和优化求逆算法具有相同的算法复杂度，但是就本论文来讲，根据设计的需要，我们采用了算法３．７，但是算法３．６在某些情况下更具有优势，简单的来讲，在算法３．７中，额外用到了一个临时寄存器ＲＥＧｕ，而算法３．６则没有，算法３．６的迭代很有规律性，并且在设计的前期可以轻易获取模块的运算规则，选择一个针对特殊数据的有限状态机，可以大大加速其运算效率，因此在一些特殊埘值的场合，设计专门的移位寄存器，可以大大减少运算所需要的时钟周期，而算法３．７中“２‘的运算最少需要ｆ个时钟周期，但是算法３．７有更多的灵活性，因此算法３．６适合ＡＳＩＣ设计，而算法３．７适合设计灵活的ＦＰＧＡ设计。下面给出了根据算法３．７，我们对基于ｏＩＡ算法的求逆运算模块的资源消耗和运行时间见表３．２，从表中我们可以清楚的得到一个信息，由于控制和多次调用乘法模块，求逆运算消耗的时钟资源很高，而对于运算本身来讲，节本做到了最小的运算量，所以一般情况下，建议避免求逆运算以提高系统的运行效率。表３．２．消耗ＡＬＵＴｓ乘法器单元３４８５２８８２４７３８５１６４１７１研＝１９１时，求逆运算器的资源性能分析表消耗ＡＬＭｓ乘法器单元控制状态机计数器寄存器临时存储单元寄存器ｘ其他总计２５１８１６６１９３２３８１３４３２１３１５９９９００逻辑寄存器运行时钟周期控制状态机计数器寄存器临时存储单元寄存器Ｘ其他总计３．５小结有限域运算的硬件实现是整个系统实现的基石，由于上层的运算模块是对有限椭圆曲线密码体制的研究与实现域运算模块的控制来来实现的，所以有限域运算的效率极其重要。在本章中，我们从理论出发，针对硬件发展的现状，给出了有限域的加法运算设计和平方运算设计，并重点分析了乘法运算的整个过程，给出了有限域基于正规基下的乘法矩阵的计算方法，给出了一个具有普遍适用性的基于ＩＩ型ＯＮＢ的设计模型，并针对不同字长ｗ下的模块性能进行理论探讨，实际分析。在优化乘法器的基础上，给出了两个优化的求逆算法，并比较他们之间的性能差异，最后给出了ＧＦ（２”１）的优化求逆模块的硬件实现。第四章椭圆曲线标量乘法器第四章椭圆曲线标量乘法器在椭圆曲线密码系统中，最耗时和最频繁的操作就是计算舻，标量乘运算把点加运算（椭圆曲线上两点不同，且Ｐ≠一Ｐ）和倍点运算（即２Ｐ）作为运算的基础，为了优化运算，在这里我们也提出了关于护的相关的优化算法。为了减少运算中的求逆运算，我们这里引入了三种射影坐标系：标准投影坐标，雅克比坐标和ＬＤ投影坐标。如果在仿射坐标下点Ｐ的坐标表示为∽ｙ），在射影坐标系下点Ｐ的坐标表示为（ｘ，ｙ，ｚ），则三种情况下的对应关系为‘３６】：（１）标准射影坐标系ＸＹ舻ｉ’＿ｙ２三（２）雅克比坐标系ＸＹ舻可’Ｊ，２可（３）ＬＤ投影坐标ＸＹ垆亍’ｙ２可９在这里，我们采用一条特殊的椭圆曲线作为我们实现加密算法的曲线Ｈ５１，令式（２．１０）的口＝０，６＝ｌ，则得非奇异Ｋ０ｂｌ娩曲线ｖ２＋】印＝矿＋饿２＋６（４．１）４．１倍点、点加运算的模块设计４．１．１倍点、点加基本运算在ＧＦ（２”）上采用式（３．１）方程的倍点、点加运算公式为Ｄ６１：令Ｐ＝（五，乃），Ｒ＝２尸＝（为，乃），则屯＝Ａ２＋五＋口（４．２）（４．３）乃＝＃＋鸽＋墨式中五＝一十丛。而令Ｐ＝（玉，Ｍ），Ｑ＝（％，儿），Ｒ＝（屯，乃）＝Ｐ＋Ｑ，则４０椭圆曲线密码体制的研究与实现玛＝口２＋口＋五＋屯＋口（４．４）（４．５）乃＝口（而＋而）＋而＋Ｍ式中口：型丝。‘＋屯４．１．２射影坐标系下的运算这里选用的影射坐标系是ＬＤ投影坐标系，椭圆曲线的投影方程是ｙ２＋．腕＝Ｘ３Ｚ＋．ｒ２２２＋Ｚ４。无穷远点ｏｏ对应于（１：０：ｏ），而点（ｘ：Ｙ：ｚ）的负点是（ｘ：ｘ＋】，：ｚ）。计算点Ｐ＝（五：Ｘ：ｚ１）的倍点２Ｐ＝（玛：巧：ｚ３）的算法见算法４．１。计算点Ｐ＝（五：Ｋ：ＺＩ）与点Ｑ＝％：五：１）的和胄＝Ｐ＋Ｑ＝（五：Ｅ：互）的算法见算法４．２。算法４．１【３６】：倍点运算算法输入：椭圆曲线Ｅ／Ｋ：），２＋砂＝，＋ｚ２＋１，ＬＤ投射坐标中的点Ｐ＝（五，Ｋ，ＺＩ）。输出：ＬＤ投射坐标系下的点２Ｐ＝（墨，五，ｚ３）。１．如果Ｐ＝ｏｏ，返回。；２．五＝Ｚ１２，五＝五２；３．ｚ３＝五・乏，墨＝正２；４．写＝写２；ｓ．瓦＝五；６．五＝五＋正；７．五＝Ｘ２；８．五＝正＋ｚｊ；９．五＝五＋瓦；ｌＯ．墨＝五・五；第四章椭圆曲线标量乘法器４１１１．正＝五・ｚ３；１２．Ｅ＝五＋五；１３．返回（玛：Ｅ：ｚ３）。算法４．２口６】；点加运算算法输入：椭圆曲线Ｅ／Ｋ：ｙ２＋砂＝，＋ｚ２＋１，ＬＤ投射坐标中的点Ｐ＝（墨，Ｉ，ｚＩ），仿射坐标系下的点Ｑ＝（而，儿）。输出：ＬＤ坐标系下的点尸＋Ｑ＝（五：五：ｚ３）。１．若Ｑ＝∞，返回Ｐ。２．若Ｐ＝∞，返回Ｑ＝（恐：致：１）。３．写＝ｚ１‘屯；４．互＝ｚ１２：５．爿ｊ＝．蜀＋五：６．五＝ｚ１‘墨；７．乃＝五‘％；；８．巧＝墨＋乃；９．如果墨＝Ｏ，则・若巧＝ｏ，则调用倍点算法计算（墨：写：ｚ３）＝２（而：咒：１），并返回（墨：Ｅ：ｚ３）。●否则返回ｏｏ。ｌｏ．ｚ３＝彳；１１．五＝五‘Ｅ；１２．写＝石＋瓦；１３．瓦＝墨２；４２椭圆曲线密码体制的研究与实现１４．五＝瓦・五；１５．正＝Ｅ２；１６．墨＝玛＋五；１７．玛＝蜀＋五；１８．五＝而・ｚ３；１９．五＝五＋五；２０．五＝ｚ３２；２１．巧＝五＋ｚ３；２２．Ｅ＝正・正；２３．五＝而＋弘；２４．五＝五・正；２５．Ｅ＝Ｅ＋五；２６．返回（玛：Ｅ：乙）。采用混合坐标系计算后，还原成仿射坐标需要１次求逆和２次乘法。４．１．３倍点、点加运算模块设计实现椭圆曲线倍点和点加运算的时候，把其分别设计为一个独立的运算模块，接口电路如图４．１和图４．２所示。图４．１倍点运算电路接口图第四章椭圆曲线标量乘法器４３嚏ｎＲＳＴ咖－ｘ１”∞脚咖—ｙ１¨∞皿ｄｈ』剐叩．田由■＿ｙ剐∞．卸ｎＹ３』吲屹由幢Ｊ钟蚰一０ｌｎ）１３．ｐ。怔啪－ｙ却∞．埘ｎＳＴ＾ＲＴ图４．２点加运算电路接口图在某种意义上来说，倍点和点加运算都是通过对有限域的乘法器和求逆运算模块的控制来实现的。４．２标量乘运算模块设计椭圆曲线加密的实质就是实现椭圆曲线上的标量乘运算【３”，从算法２．３和算法２．３中可以清楚地看到，在计算公钥、加密明文和解密密文的过程中，其实都是椭圆曲线标量乘运算。椭圆曲线的群运算的算法特点决定了要把椭圆曲线上的标量乘运算转化为椭圆曲线上的点加运算和倍点运算。椭圆曲线上任意两点相加的结果还是椭圆曲线上的点，所以标量乘的运算结果还是椭圆曲线上的某一点。舻运算就是基于基点Ｐ自加七一１次，但是这样的算法特别消耗时间资源，在实际的工作中并不推荐使用，下面我们给出标量乘几种常用的优化算法。４．２．１标量乘运算的快速算法椭圆曲线密码系统是建立在椭圆曲线的一个子群基础上的，首先在椭圆曲线上选取基点Ｐ，我们假设撑Ｅ（ＧＦ（２”））＝砌，其中Ｈ是素数，厅是一个小整数，且Ｐ的阶为行，对于乘数七，可以随机地从区间［１，胛一１］内选择，我们这里把Ｊｊ｝的位二进制表示为（ｔ．ｐ电。…，岛，与，‰）。算法４．３计算标量乘的从右向左的二进制方法【３８】输入：后＝（ｔ．。，毛一：，…，岛，毛，‰），Ｐ∈Ｅ（ＧＦ（２”））。输出：舻。１．Ｑ＝∞。２．对于ｆ从Ｏ到ｆ一１，重复执行２．１如果ｔ＝１，贝０Ｑ＝Ｑ＋Ｐ。２．２Ｐ＝２Ｐ。３．返回（Ｑ）。椭圆曲线密码体制的研究与实现在这里七∈ＧＦ（２”），所以可以假设各位的Ｏ和１是分布均匀的，这样算法４．３平均需要：圭个点加运算，ｆ个倍点运算・最坏的时候需要ｆ个点加运算，ｆ个倍点运算。由于点加运算只有在毛＝１的时候需要，所以减少七的编码中的ｌ的个数，可以降低点加运算的次数，从而提高系统的运行效率，设尸＝＠，力∈Ｅ（ＧＦ（２”）），则—Ｐ＝Ｏ，工＋力，因此椭圆曲线上的点加和点减具有几乎一样的运算效率，这样我们可以使用带有符号的数字来表示后＝∑ｔ２。，其中ｔ∈（ｏ，±１｝。下面介绍特别的表示方式：非相邻表示型（ＮＡＦ）。，－ｌ定义５．１一个正整数七的非相邻表示型的表达式是表达式七＝∑ｔ２。，其中１１０毛∈｛０，±１），且岛－．≠Ｏ，并且没有两个连续的数字置是非零的。ＮＡＦ的长度是，。定理４．２【３ｑ令七是一个正整数。◆．ｉ｝具有唯一的ＮＡＦ，并记为＾“以后）。◆批伊（Ｄ在七的所有带符号表示式中具有最少的非零位。◆删Ｆ（Ｊｊ｝）的长度最多比．｜｝的二进制表示的长度大１．夺若Ｍ，（七）的长度是，，则％＜七＜２７彳。夺所有长度为，的ＮＡＦ的非零数字的平均密度大概为％－算法４．４计算一个正整数的ＮＡＦ输入：～个正整数豇。输出：＾ＷＦ（七）。１．ｉ＝Ｏ。２．当七≥１时候，循环执行２．１如若七是奇数，则七，＝２一（七ｍｏｄ４），七＝＿｜｝一毛．２．２２．３否则，ｔ＝Ｏ。女向右移位一位，ｆ＿ｆ＋１。第四章椭圆曲线标量乘法器３．返回（屯，置一２，…，岛，毛，‰）．下面给出根据ＮＡＦ编码方式得到的修正标量乘算法。算法４．５修正标量乘算法【３羽输入：七＝（毛。，毛一：，－．．，屯，与，‰），Ｐ∈Ｅ（ＧＦ（２”））。输出：舻。１．得到冗余编码七＝（吒。，吒－２，…，如，向，‰）。２．初始化：Ｑ＝ｍ。３．对于ｆ从疗一ｌ到ｏ，重复执行ａ）执行倍点运算：Ｑ＝２Ｑ。ｂ）如果七ｆ＝１，执行Ｑ＝Ｑ＋Ｐ。ｃ）如果ｔ＝一ｌ，执行Ｑ＝Ｑ—Ｐ。４．返回（Ｑ）。ＮＡＦ编码后计算标量乘运算平均需要的％次点加运算，一次倍点运算，显然，可以显著降低点加运算的次数，来提升系统的运行效率。如果点Ｐ是固定的，并且有存储器可以利用，那么可以通过预先计算某些数据，来提升舻的运算速度。例如如果预先计算出所有的２Ｐ，２Ｐ，２２Ｐ＇…，２“Ｐ，可以省去所有的倍点运算。４．２．２标量乘运算的模块设计根据算法４．５，显然对于置有三种状态，Ｏ、ｌ和・１，我们采用编码对其进行处理，在这里根据定理４．２的第３条，显然对七进行编码后的位数为３８４比特，即００代表正整数的Ｏ，Ｏｌ代表１，ｌｌ代表．１。下面给出其控制状态机。见图４．３。图４．３标量乘运算控制状态机在状态机的外部还有一个计数器，用来控制标量乘运算的结束，一次移动数据位椭圆曲线密码体制的研究与实现两位，计数器加ｌ，根据前两位数据位的数值来对调用点加（点减）运算和倍点运算，从而完成舻运算，其接口见图４．４。ｄｋＤＯＵＴｌ伊埘１∞埘晌ＳＴｎＳＴ＾ＲＴＤＯｕＴＪ伊二”∞，埘ｎｃＨ０ＰＫＥＹｌｌ舳ａＩ帕。畦Ｐｘ’【１９０．０】Ｐ．”【１９口埘图４．４标量乘运算模块电路图４．３小结椭圆曲线的群运算是完成椭圆曲线密码体制的最基本的运算，在有限域运算的基础上，我们在这里给出了椭圆曲线的群运算，并给出了相应的三个模块的设计。椭圆曲线的舻运算是建立在点乘和倍点运算基础上的，是椭圆曲线加密体制的核心运算模块。它的运行效率其实就是椭圆曲线密码体制的运行效率，我们在这里给出了一种基于重新对后进行编码的优化算法，在优化设计的基础上完成了肼＝１９ｌ情况下的椭圆曲线标量乘模块。第五章仿真与应用第五章仿真与应用目前越来越多的系统采用ＦＰＧＡ进行硬件设计，而ＦＰＧＡ设计中非常重要而频繁进行的一环是仿真。仿真过程是计算机软件模拟芯片对测试输入的逻辑处理，通常计算时间消耗很大。但是仿真能将硬件设计中的逻辑和时序问题及早暴露出来，以便工程师改进设计或调整方案。仿真是硬件设计流程中较为耗时和烦琐的一环，主要原因有：第一，仿真的激励波形必须由设计者自行创建；第二，测试波形必须人工输入；第三，仿真的结果正确与否必须由设计者自行判断，很难自动化；第四，时序仿真前必须对整个设计做耗时的全编译。５．１仿真验证５．１．１有限域乘法运算模块有限域乘法模块可以说是整个椭圆曲线密码体制运算的基石，在这里我们采用ＩＩ型ｏＮＢ的１９１作为我们测试的例子，见图５．１和图５．２。测试向量：因子Ａ：（３５８ＤＦｌＥＡ９ＥＢＣ２Ｅ４２２ＦＢＥＣ０６９ＤＤＥ７３Ｄ２Ｃ２５５９７ＣＣＣＤ２Ａ３Ｅ２４４）１６因子Ｂ：（００００００００００００００２３４７７７８２３４ＦＦＥＥＡＡ２３６３７２３１２３１２３２１３１２）１６’结果Ｄ：（１Ｅ９９３ＤＤ４５Ｅ３Ｅ１１７５９ＢＥ４ＢＣ３７ＦＤＤＣ５５Ｅ６ＥＣ７６１ＡＣ００５４２Ｃ４Ｃ７）１６图５．１埘＝１９１，乘法器运行图（待续）验证乘法器的时候，选择两个１９１比特位的数据作为乘法因子输入，因为乘法器内有寄存器，当ＩｌＬＯＡＤＡ为低电平的时候，把数据ＲＥＧＡＭＵＬ装载到乘法器中，同理，当当ｌｌＬＯＡＤＢ为低电平的时候，把数据ＲＥＧＢ—ＭＩⅡ，装载到乘法器中，一个时钟周期完成内部数据的更新后，ｎＭＩⅡ，ＳＴＡＲＴ信号为低电平的时候，乘法器开始运算，等待给出结果，并输出一个负脉冲信号。高模块占用了３２９８个逻辑单元，完成运算大约５０个时钟周期。对于正规基表示下的有限域的元素，其与单位元的乘积为其自身，单位元是每个比特位均为１的特殊的数据，则从一定程度上验证乘法器的有效性和准确度。椭圆曲线密码体制的研究与实现图５．２ｍ＝１９１，乘法器运行图（续图５．１）５．１．２有限域求逆运算模块测试向量：域元素：（３５８ＤＦｌＥＡ９ＥＢＣ２Ｅ４２２ＦＢＥＣ０６９ＤＤＥ７３Ｄ２Ｃ２５５９７ＣＣＣＤ２Ａ３Ｅ２“）１６结果：（５６１４９ＥＡＦＢ２Ｆ４８１ＡＥ３２９７０２３５ＥＯＯＥＡ９０６３ＤＦｌＤＣ４８５１３９Ｆ８８０）１６图５．３ｍ＝１９ｌ，求逆运算器运行图（待续）有限域的求逆运算，在一定程度上是通过对乘法器的调度来实现的，但是由于其对时序的要求，在设计中出现不少的问题，首先是乘法器调度过程中，乘法因子的存储问题，所以在乘法器中加入两个数据加载信号ＩｌＬＯＡＤＡ和ｎＬＯＡＤＢ，虽然在一定程度上解决了数据的问题，但是不可避免的引入了一个时钟的延迟。其次是求∥，虽然设计上等待延迟就可以了，但是由于其移位占用的时钟周期比较长，大大增加了运算时间，降低了运算的效率，如果采用简化求逆算法，针对特定的肌值，构造一个时钟周期的移位，则可大大增加运算效率。当数据和求逆运算开始信号ｎＩＮＶＳ１ｍ盯有效（低电平）的时候，根据输入的数据，开始对内部的寄存器进行初始化，并调度乘法器，内部寄存器进行求逆运算，当运算完成后，输出结构数据和运算有效信号ｎＩＮ、ｒＤ伪厄（也可以作为模块忙状态信号）。本模块占用４１７１个逻辑单元，运行时间为９００个时钟周期，其中求“７占用１９１个时钟周期。第五章仿真与应用图５．４研＝１９１，求逆运算器运行图（续图５．３）因为在正规基表示下的二进制有限域，则乘法单位元为１９１位数据位均为ｌ的数据，根据数据求逆的结果，进行乘法运算，元素与其逆乘积为１，则可从侧面验证乘法器和求逆运算器。５．１．３点加运算模块点加运算是椭圆曲线层运算的基本模块，由于其运算的特殊性，基本可以认定其为顺序运算，就算法而言，几乎没有优化的余地，这里给出其输入参数和输出结果。设输入参数点Ｐ＝（而，弗），Ｑ＝（而，奶），输出参数Ｒ＝Ｐ＋Ｑ＝（为，乃）。输入参数：而＝（３５８ＤＦｌＥＡ９ＥＢＣ２Ｅ４２２ＦＢＥＣ０６９ＤＤＥ７３Ｄ２Ｃ２５５９７ＣＣＣＤ２Ａ３Ｅ２４４）１６Ｍ＝（０５ＤＤＤ４５０６０１４ＣＡ３Ｅ６０６０７６Ｅ２ＢＤ７５２１６４３Ｆ６８２Ｃ８０５ＢＥ０５４４Ｃ）１６艺＝（４９８９６９８Ｄ４８３４３７８４ｃ１３６Ｅ５ＤＢ６ＥＤＥ５ＤｃＡＥ２９Ｆ３８ｃ６Ａ７２０Ｄ７９Ｂ）１６弘＝（５Ｅ３５９ＤＢｌＯＦ７３ＤＥ３Ｅ６Ａ４２ＦＢ４Ｃ９ＦＦｌ９１３８Ｆ１２０３Ｄ２８ＢＦＤ３２８０Ａ）１６输出参数：而＝（３ｌＤ８Ｄ４１ＤＥｌＢＢ３３２５ＢＤ７６５６８３ＡＡ４４９Ｄ２Ｅ０８Ｄ０３ＡＢ７Ｅ５６８３７６Ｄ）１６乃＝（ＯＦＦＤＢＦ４ＣＯＦ３６８０２ＡＯＣ９ＥＥ５７Ａ９Ｅ３８３８８１５８７９６Ｆ３０ＤＣ６４８４９Ｂ）１６图５．５点加运算器５０椭圆曲线密码体制的研究与实现５．１．４倍点运算模块Ｋｏｂｌ池曲线的主要优点是可以不使用倍点运算，但是在我们的设计中，没有采用Ｋｏｂｌ沱曲线。与点加运算模块类似，从算法上来讲，优化的空间同样很小，下面给出其验证结果，见图５．６，设Ｐ＝（五，Ｍ），２Ｐ＝（而，乃）。输入参数：而＝（３５８ＤＦｌＥＡ９ＥＢＣ２Ｅ４２２ＦＢＥＣ０６９ＤＤＥ７３Ｄ２Ｃ２５５９７ＣＣＣＤ２Ａ３Ｅ２４４）１６Ｍ＝（０５ＤＤＤ４５０６０１４ＣＡ３Ｅ６０６０７６Ｅ２ＢＤ７５２１６４３Ｆ６８２Ｃ８０５腿０５４４Ｃ）１６输出参数：毛＝（４９８９６９８Ｄ４８３４３７８４Ｃ１３６Ｅ５ＤＢ６ＥＤＥ５ＤＣＡＥ２９Ｆ３８Ｃ６Ａ７２０Ｄ７９Ｂ）１６弘＝（５Ｅ３５９ＤＢｌｏＦ７３ＤＥ３Ｅ６Ａ４２ＦＢ４Ｃ９ＦＦｌ９１３８Ｆ１２０３Ｄ２８ＢＦＤ３２ＢＯＡ）１６图５．６倍点运算５．１．４标量乘运算模块舻运算是椭圆曲线密码体制中最重要的运算，我们这里给出椭圆曲线的基点Ｐ＝（而，Ｍ），以及标量七。测试向量：输入参数：而＝（３５８ＤＦｌＥＡ９ＥＢＣ２Ｅ４２２ＦＢＥＣ０６９ＤＤＥ７３Ｄ２Ｃ２５５９７ＣＣＣＤ２Ａ３Ｅ２４４）１６弘＝（０５ＤＤＤ４５０６０１４ＣＡ３Ｅ６０６０７６Ｅ２ＢＤ７５２１６４３Ｆ６８２Ｃ８０５ＢＥ０５４４Ｃ）１６七＝（４ＣＥ７４０１４５８ＥＯＥ９６１８２０爿，ＣＤＦＣ５４，ｊＤｌ９７９９９Ｄ６５９Ｅ８３４２８爿５Ｄ爿）１６输出参数：第五章仿真与应用毛＝（２Ｆ４４船０４９Ｃ７２３２４８船２Ｆ７Ｄ８６５１Ｃ３４Ｃ４４Ｃ４４５Ｄ９爿４９２２胱８）１６乃＝（７０８２口４４７６Ｆ５６ＤＥＢ７６Ｅ６４２２３１９８５０７４９１０８０４１４５２Ｆ９９Ｅ０彳１Ｄ１６在５０Ｍ时钟频率下，完成一次倍点运算大约需要２０Ｉｌｓ的时间，完成一次点加运算需要的时间大约是２ｌｌｌｓ，平均完成一次标量乘运算大约需要１１ｍｓ，一秒钟大约可以标量乘运算９０次。５．２标量乘模块应用实例椭圆曲线实现加密方案的解密和解密算法分别由算法５．１【３９】和算法５．２【３９】给出。首先把明文辨表示为椭圆曲线上的一个点髟，然后再加上素Ｑ进行加密。发方把密文ｃＩ＝船和ｃ２＝盯＋坦发给接收方。接收方利用自己的私钥ｄ计算弼＝ｄ（舻）＝七（卯）＝坦，进而可以恢复出明文肠＝ｃ２一地。算法５．１：基本椭圆曲线加密输入：Ｄ＝（Ｅ，Ｐ，玎），公钥Ｑ，明文脚。输出：密文（ｃＩ，ｃ２）。１．将明文所表示为Ｅ（ＧＦ（２”））上的点Ｍ。２．选择任意Ｊｉ｝￡【ｌ，胛一１】。３．计算Ｃ＝舻。４．计算ｃ２＝Ｍ＋坦。５．返回（ｃｌ，ｃ２）。算法５．２：基本椭圆曲线解密输入：Ｄ＝（层，只力，私钥ｄ，密文（ｃｌ，ｃ２）。输出：明文棚。１．计算Ｍ＝ｃ２一鹅。２．从点取出明文ｍ，返回ｍ。根据算法５．１和算法５．２可以清楚的看出，无论加密运算或者解密运算都可以归结为椭圆曲线在有限域上的舻运算。其中设公钥Ｑ＝（ｘ，ｙ），椭圆曲线运算基点Ｐ＝（‘，Ｍ），明文Ｍ和随机数ｋ，输出点Ｒ＝（屯，乃）即为加密后的数据。５２椭圆曲线密码体制的研究与实现输入参数：五＝（３５８ＤＦｌＥＡ９ＥＢＣ２Ｅ４２２ＦＢＥＣ０６９ＤＤＥ７３Ｄ２Ｃ２５５９７ＣＣＣＤ２Ａ３Ｅ２４４）ＭＭ＝（０５ＤＤＤ４５０６０１４ＣＡ３Ｅ６０６０７６Ｅ２ＢＤ７５２１６４３Ｆ６８２Ｃ８０５ＢＥ０５４４Ｃ）Ｍ肘＝（６８３４７９９２９９Ｅ２３１Ｄ４８１ＢＦＡ４３Ｃ２Ｆ０４７４１９６ＢＥ６Ｆ２６７４４Ｄ２Ｄ８２３）１６七＝（１３８８ＡＥ４６９７５８２２５９Ａ５４９３Ｅ３４５Ｃ９３７ＥＢｌＤ８Ａ１Ｅ３ＥＤ８４Ａ４５８Ｄ５）１６ｘ＝（２Ｆ４ＡＦＢ０４９Ｃ７２３２４８ＦＣＥ２Ｆ７Ｄ８６５２Ｃ３４ＣＡ４Ｃ４Ａ５Ｄ９Ａ４９２２ＢＦＣ８）１６ｙ＝（７０８２８４Ａ７６Ｆ５６ＤＥＢ７６Ｅ６Ａ２２３１９８５０７４９１０８０４１４５２Ｆ９９ＥｏＡｌＥ）１６输出参数：毛＝（１ＡＢＣ６Ｆ５１５７７ＤＢＦＢｌ５１８１２７８４Ｄ０４ｌＥ７Ｆ９２９ｌＥ６Ｆ０９４９８６ＦＤ７１）１６乃＝（２０舡Ｄ３Ｆ６５８Ｄ８９３２１２ｌＡ４８５Ａ９１０２ｃ３Ｄ９Ｄ２６３１ｓＣＢＢ４ＥＡ９Ｅ４５９）１６椭圆曲线的解密模块，设点Ｃ＝（ｃｌ，ｃ２）为密文，私钥吒。则直接通过算法５．２获取明文。５．３小结椭圆曲线密码体制的有效性和可靠性是我们关注的重点，本章利用舢ｔｅｍ公司的Ｑｕａｎ：ＩｌｓＩＩ７．１平台对椭圆曲线密码体制的核心模块进了软件仿真，基本符合我们的设计期望，和理论分析保持高度一致。从仿真中我们可以看到，椭圆曲线密码系统的优化重点在两个方面，一个是有限域乘法运算的优化，一个是标量乘运算的优化，两者都存在很多优化算法，其中的核心在于在消耗硬件资源和消耗时间资源获取平衡，虽然随着硬件的发展，可以在一定程度上满足我们的需求，但是如何在性能和资源之间获得最佳，仍然是个重要的需要研究的问题。第六章结束语第六章结束语论文从有限域的基本表示方法和有限域的基本运算着手，分析了正规基表示下的二进制有限域的性质，运算法则，给出了通用的计算有限域乘法矩阵的简单方法，本文实现的对最优正规基表示下的有限域乘法矩阵的构造方法，在很大的范围了解决了有限域运算模块无法通用的问题。通过理论分析和试验数据的比较与分析，以及对算法正确性的验证，充分说明了这种算法的优越性和可靠性。因为有限域层的运算是整个运算的基础，所以对有限域运算的优化可以大大提高整个系统的运算效率。以１９ｌ位为例，其有限域元素乘法运算周期优化后为１５个时钟周期，仅相当于通常方法计算用的最少１９２个时钟周期的×，，这在一定程度上大大提高了整个系统的运行效率。，１Ｊ椭圆曲线层的运算的重点在于其标量乘运算，它直接关系到椭圆曲线密码体制的运行效率，根据椭圆曲线上点的表示和标量乘运算舻中正整数七的ＮＡＦ编码，提出了一种优化的舻算法。本文采用ＮＡＦ编码，因为它具有最少的非零位，而这在一定程度上可以大大减少点加运算的次数，从而实现提高运算效率的目的。以１９１位为例，椭圆曲线运算层上的点加运算是比较消耗时间资源的运算，对标量乘参数采用ＮＡＦ编码，可以减少大约总量坛次的点加运算。，Ｖ通过两个最主要的优化，整个系统可以在ｌｓ内实现９０次舻运算，相对于其消耗的硬件资源来讲，其运算比较高效。椭圆曲线密码体制【４０】的标量乘运算的硬件实现具有重要的工程应用，作为椭圆曲线密码体制的最重要的ＩＰ核，再集成其他简单的辅助模块后，就可以独立地实现椭圆曲线加密体制，也可以作为一个整体嵌入到其他的运算模块。本文采用ｖｅｒｉｌｏｇ｝Ⅱ）Ｌ描述了整个系统，按照层次化设计的思想把设计分为三个运算层次：第一，有限域上的运算；第二，椭圆曲线上的运算，第三，密码层的运算。对每一层的功能和接口有明确的划分，完成每一个模块的设计、仿真和综合后，利用这些模块实现了椭圆曲线加密解密模块的设计，这里采用的域的大小为１９１比特，实际中可以根据需要，只要简单修改域参数和更换乘法矩阵模块，就可以实现不同的域的大小，这在工程中将大大增强系统的灵活性和实用性。本文主要对椭圆曲线密码体制的ＦＰＧＡ实现做了初步的探索，虽然采用ｖｅｒｉｌｏｇＨＤＬ实现了椭圆曲线密码体制的描述和仿真，但是功能并不完善，还有很多方面值得改进和进一步的研究，主要包括以下几点：椭圆曲线密码体制的研究与实现１．对有限域的运算可以采用流水线的形式大大加速其基本运算，这对整个系统的运算效率会有很大的提升。２．这里实现的椭圆曲线密码运算模块，考虑到其设计的通用性，所有的模块都是采用器件的逻辑单元来实现的，所以其资源的占用是一个很大的问题，如果采用特定的芯片，考虑其固定的嵌入式单元，则可以大大节省器件的资源。３．我们这里对数据的加密是假设已经为椭圆曲线上的一点，而把明文信息映射到椭圆曲线上的点，则需要设计合适的ＨＡｓＨ函数模块，这也是下一步工作的重点。４．针对多项式基和正规基下的椭圆曲线，其运行期间若可以彼此相互转换，则在一定程度上可以加速椭圆曲线的运算，而基转换矩阵的建立和实现则是一个难题，也是下一步工作的重点。致谢致谢首先要感谢我的导师李小平教授。在读研究生期间，李老师对我的培养花费了巨大的心血，给我提供了良好的学习环境和许多实践的机会，使我的学习和工作能力都得到了很大的提高。在论文课题方面给与的方向指导，使我少走了很多弯路，能顺利完成论文的各项工作。李老师严谨的治学态度，孜孜不倦的钻研精神，求实的工作作风和渊博的学识给我极大的教育，使我终身受益，谨此表示崇高的敬意和衷心的感谢！感谢刘彦明副教授，在我三年的学习期间给与我的理解和支持，感谢刘老师在我做论文期间给与我的帮助和精神的鼓励，在论文期间，刘老师更是在百忙之中多次抽出宝贵的时间对我的论文进行仔细的审阅和指导，提出了很多宝贵的意见和建议。感谢董庆宽老师，孙小平老师和王海老师对我的关心和帮助，在做算法设计的时候有了他们的指导，使我有了很多后来证明有效的设计思想；感谢杨一展、李亚娟、吴琼、田晓明、孙威、柯资颖同学，与他们在一起工作和学习很愉快；感谢宋斌、郭晓江师弟在我完成论文期间对我的帮助。最后，我要感谢我的父亲、母亲和妻子，没有他们三年来的理解和支持，我走到这一步是不可能的，在这里，我衷心的感谢他们！参考文献参考文献【１】Ａ．ＲＭ啪ｌｅｈ．Ｅ仿ｃｉｅｎｔａｌｇｏｒｉ恤璐锄ｄ盯ｃｈｉｔｅｃｎ鹏ｓ蠡ｗｆｉｅｌｄｍｌｌｌｔｉｐｌｉｃａｔｉｏｎ１１ｓｉｎｇＧ羽瑚ｉａｎｎｏ】咖Ｉａｌｂ刮；嚣．ＩＥＥＥＴ瑚ｓａｃｔｉｏｎｓｏｎｃｏｍｐｕｔｅｒｓ，２００６，５５（１）：３４－４７．【２】Ｋｏｂｌｉ乜，Ｎ．．Ｅｌｌｉｐｔｉｃｐｐ．２０４—２０９，１９８７．ｃｕｎ，ｅｃｒｙｐｔｏｓｙｓｃｅ娜，Ｍａ吐Ｉｅｍａｌｉｃｓｏｆｃｏｍｌ，ｕｔａｔｉｏｎｖ０１．４８，【３】Ｍｉｌｌ盯，Ｖ—ｕ∞ｓｏｆｅｌｌｉｐｔｉｃＣｏｍｐｕｔｃｒｃｕｎ，ｅｉＩｌｃｒｙｐｔｏＦａｐｈｙ，ＩｎｃＲⅥ’１Ｄ’８５，Ｌｅｃｔｕ佗ＮｏｔｅｓｉｎＳｃｉｅｎｃｅ，ＬＮｃｓ２１８，ｐｐ．４１７．４２６，Ｓｐｒｉｎｇ＊Ｖｅｒｈｇ，１９８６．【４】信息科技领域研发热点及发展态势的文献计量分析研究．中国科学院成都文献【５】Ａ娜ＧＢ，ＦＭＵＬｌｉｌｌ．Ｒ．ｃ，ｖ锄Ｓｔ∞ｅ．Ｓ．Ａ。ＡｎＩｍｐｌｅｍ叫ｔ芒Ｌｔｉ∞ｏｆＥｌｌｉｐｔｉｃＣｒｙｐｔｏｓｙｓｔｅｍｓｏｖｅｒＧＦ（２嘲）叨．ＩＥＥＥＪｏｎＳｅｌｅｃｔｅｄＡ陀嬲ｉＩｌ情报中心战略情报研究小组．ＣｕⅣｅＣ咖姗ｍｊｃａｔｉｏＩｌｓ，ｃＤ傅ｏｇｍｐＩｌｉｃ１９９３，１ｌ（５）：８０４－８１３．【６】０ｋａｄａｓ，ＴｏｒｉｉＮ，ＫｏｕｉｃｌｌｉＩ．Ｉｎｌｐｌｅｍｅｎｔａｔｉ∞ｏｆＥｌｌｉ砸ｃｃｕｒｖｅＣｏ眦ｅｓｓｏｒｏＶ盯６Ｆ（２“）∞ＦＰＧＡ［Ｃ】．ｗｏｒｋｓｈｏｐ∞ＣｒｙｐｔｏｇｍｐｌｌｉｃＨａｒｄｗａ聆觚ｄＥｍｂｅｄｄｅｄＳｙｓｔｅｍ－ＣＨＥＳ’２０００．ＳｐｒｉｒＩｇ－ｖｅｄａｇ，ＬＮＣＳ１９６５，２０００：２５—４０．【７】ｏｒｌ她ｄｏＧａｐｃｒＣ．Ａｌｌｉ曲－ｐｅ响ｒＩＩｌａｎｃｅＲｅｃｏ曲ｇｕｍｂｌｅＥｌｌｉｐｔｉｃ１９６５，２０００：４１－５６．向Ｇ联２”）【Ｃ】．ｗｏｒｋｓｈ叩∞ＣｒｙｐｔｏｇｍｐｈｉｃＨ盯ｄ聊嘴ａｎｄＣＨＥＳ’２０００．Ｓ面ｎｇ－ｖｅｄａｇ，ＬＮＣＳ【９】ＩＥＥＥＰ１３６３．ＳｔａＩｌｄａｒｄＥｍ妣ｄＣｌ删ｅ№ｅｓ蚶Ｓｙｓｔｅｍ【８】白国强，陈弘毅．椭圆曲线密码的芯片集成。中兴通讯技术，２００４．４：２７—２９．Ｓｐｃｃｉｆｉｃａｔｉｏ璐ｆｏｒＰｕｂｌｉｃＫｅｙＣｒｙｐｔｏ笋ａｐｈｙＤｒａＲⅥ臌ｏｎ１３，１９９９【１０】Ｒ．Ｃ．ＭｌｌｌｌｉＩｌ，Ｉ．Ｍ．０】哕ｓｚｃｈｕｋ，Ｓ．Ａ．Ⅵｍｓｔｏｎｅ，姐ｄＲＭ．Ｗｉｌ∞ｎ．Ｏｐ血ｎａｌＮｏｍｌａｌ．Ｂ嬲ｅｓｉｌｌＧＦ（矿），ＤｉｓｃｒｅｔｅＡｐｐｌｉｅｄＭａｔｈｅｍａｔｉｃｓ，２２：１４９＿１６ｌ，１９８８—８９．【１ｌ】Ｒ．Ｃ．Ｍｌｌｌｌｉｌｌ．Ａｃｈａ船ｃ涮２ａｔｉｏｎＨａｌｌｏｆ恤ｅｘ呦ｅｄｉ矧ｂｕｔｉｏ船ｏｆｏｐ缸ａｌｎｏ咖ａｌＣｏｎｆ．盯ｃｎｃｅ，Ｂｕｄｉｎ鲫，ｖｅ姗。她１９９０，ｏｆｅｌｌｉｐ石ｃｃｕｎ，ｅｔｏｂａｓｅｓ，Ｐｒｏｃ．Ｍ掷ｌｌａｌｌ印ｐｅ配［１２】Ｎ．Ｋｏｂｌｉｔｚ，Ａ．ＭｅｎｅｚｅｓＤｅｓｉｇｌｌｓ，ＣｏｄｅｓａｎｄＭｅｍｏｒｉａｌａＩｌｄＳ．Ｖ锄ｓｔｏｎｅ．１１忙ｓ诅ｔｅｃｒｙ舯）黟ａｐｈｙ．ｃｒｙｐｔｏｇｒａｐｈｙ，２０００，１９：１７３一１９３．Ｍｅｎｅｚｅｓ，ＳｃｏｔｔＶｈｎｓｔｏｎｅ．Ｇｕｉｄｅｔｏ【１３】ＤａＨ℃ｌＨａｎｋｅｒｓｏｎ，Ａｌ舶ｄＥｌｌｉｐｔｉｃＣｕｒｖｅＣｒｙｐｔｏｇｒａｐｈｙ，２００３：２６．［１４】ｈ仕ｐ：，／ｗｗｗｃｅｒｔｉｃｏｍ．ｃｏＩｌｌ／ｉｎｄｅｘ．ｐｈｐ？ａｃｔｉｏｎ＝ｅｃｃ，ｍａｍ９．【１５】ＩＥＥＥＰ１３６３ａ．ｉｎｃｌｕｄｅｄＥＣＤＳＡ，ＥＣＮＲ，ＥＣＮＲ２，ＥＣＰＶ：ＥＣＤＨａｎｄＥＣＭＱＶ：５８椭圆曲线密码体制的研究与实现Ｉ）Ｉ曩ｆｔＶｅｒｓｉｏｎＤ９（２００１．６．１３）．【１６】廖群英，孙琦．有限域上最优正规基的乘法表，数学学报，、，０１．４８，Ｎｏ．５，（２００５），９４７—９５４．【１７】ｃｅｎｉｃｏｍＲｅｓｅａｒｃｈ．ＥＩｌｉｐｔｉｃ【１８】ＡＮＳＩＸ９．６２．ＰｕｂｌｉｃＫｅｙＣｕｒ、，ｅＣｕｒｖｅＣｒｙｐｔｏｇｍｐｈｙ，ｖ１．Ｏ（２０００，９，２０）．ｆｏｒⅡｌｅＦｉＩｌａｎｃｉａｌＳｅｒｖｉｃｅｓＣｒｙｌ）ｔｏｇｒａｐｈｙＩｎｄｕｓ仃ｙ：ｍ１９９９．Ｅｌｌｉ面ｃ【１９】ＡＮＳＩＤｉｇ砌ｓｉｇＩｌａｎ鹏趟ｇｏｄⅡｌＩｎ（ＥＣＤＳＡ），ａｐｐｒｏｖｅｄＪａｎｕａｒｙＣｒ），ｐｔｏｇｒ印ｂｙＫｅｙＴＩ孤ｌｓｌ＇ｏｎＵｓｉＩｌｇＥｌｌｉｐｃｉｃＣｕｒｖｃＡ铲涨ｎｔ锄ｄｖｅｒ．１９９９，ｌ，８．Ｘ９．６３．ＰｕｂｌｉｃＫｅｙＦｏｒ１１嵋ＦｉＩｌａＩｎｃｉａｌＳｅｎ，ｉｃｅｓＩｎｄｕｓｎｙ：ＫｃｙＣｒｙｐｔｏ掣ａｐｌｌｙ，ＷｂｆｋｉｎｇＤｍＲ【２０】王庆先．有限域运算和椭圆曲线数乘运算研究：【博士学位论文】．成都：电子科技大学，２００６．【２１】Ｎ．Ｋｏｂｌ池．Ｅｌｌｉｐ如Ｃｌ】ｎ，ｅＣｒｙｐｔｏｓｙｓｔｅ娜Ｍａ也Ｃ伽叩Ｖ０１．４８．１９８７．口２】Ｌｅｏｎａｒｄ２００１．Ｊａｃｏｂｓ．Ｅｌｌｉｐ虹ｃＣｕｎ，ｃＣｒｙｐｔｏｓｙｓｔｅｍｓＡｎ０№ｒｖｉｅｗ，ＳＡＮＳ，Ｍ鲫ｃｈｉｎ２４，【２３】Ｖ．Ｓ．Ｍｉｌｌ既Ｕ辩ｏｆＥｌｌｉ砸ｃＣｒ），１）ｔｏ’８５．ＬｅｃｔＩ鹏Ｎｏｔｅｓ１９８５．４１７．４２６．ＣｕｒｖｅｓｉｎｉｎＣｒｙｐｔｏ铲ａｐ量ｌｙ．Ａｄｖ趾ｃｅｓＣｒｙｐｔｏｌｏ舒Ｂｅｄｉｎ．Ｃ蚰ｌｐｕｔｅｒＳｃｉｅｎｃｃＮｏ．２１８．Ｓｐｒｉｌｌｇ－Ｖｅｄａｇ【２４】ＨｅｇｃＩ乙Ｆｒｉｕｍ．码ｅＧｒｏｕｐＬａｗ∞ＥｌＩｉ砸ｃＣｕｎ，ｃｓ∞ＨｅｓｓｅｎｆｏｒＩｎ，ＣＡｃＲ（ｕｎｉｖ．ｃｕｒｖｅｏｆＷｈ制ｏｏ）ＴｃｃｈｌｌｉｃａｌＲｃｐｏｎ，ＣＯＩ汛２００ｌ—０９，２００１．【２５】Ｔ．Ｓａｔｏｈ，Ｋ．Ａ∞ｋｉａｎｄｓ．Ｍｉｕｍ．０ｌｖｅｒｖｉｅｗｏｆｅｌｌｉｐｔｉｃｃｒ）ｆｐｔｏ掣ａｐｌｌｙ，Ｐｒｏｃ．ｏｆＰＫＣ’９８，ｓ面ｎｇ洲打ｌａｇ，ＬＮｃＳ１４３１，ｐｐ．２９－４９，１９９８．［２６】冯克勤，余红兵．整数与多项式，１９９９：（１３４—１４８）．【２７】ｈｔＩｐ：伽ｎ删ｃｅｍｃｏｍ肋ｎ仉ｎｄｅｘ．ｐｈｐ？ａｃｔｉｏｎ＝ｃｃｃ，ＩＩｌａｍ９－１．【２８】Ａ．ＲｅｙｌｌａＩｌｉ－ＭａｓｏｌｅｈＭｕｍｐｌｉｅ体ｏｖｅｒａｎｄＭ．Ａ．ＨａｓａＩＬＥ伍ｃｉｅｎｔＤｉ百ｔ－ＳｅｒｉａｌＮｏｍｌａｌＢ勰ｉｓＧＦ（２”）ＡＣＭＴｈ璐．ＥｍｂｅｄｄｅｄＣｏｎｌｐｕｔｉｎｇＳｙｓｔｃｎｌｓ（ＴＥＣＳ），ｓｐｅｃｉａＩｉｓ乳ｌｅ∞ｅｍｂｅｄｄｅｄｓｙ毗ｍｓ雒ｄ∞ｃ嘶％ｖ０１．３，∞．３，ｐｐ．５７５—５９２，Ａｕｇ．２００４．口９】Ａｒ鹊ｈＲｅｙｌｌａＩｌｉ—Ｍａｓｏｌｃ】１，ＭｅｍｂｅｒＩＥＥＥ．ＬｏｗＩＥＥＥ，ａｎｄＳｅｑｕｅｎｔｉａｌＭ．Ａｎｗ盯Ｈａ舶ｌｌ，ＳｅＩｌｉｏｒＭｅＩｎｂｅｒＣｏｍｐｌｅｘ毋ｗｏｒｄ・ＬｅｖｅｌａｎｄＣ．Ｋ．Ｋｏｃ．ＡｎＮｏｍａｌＢａｓｉｓＭＩｌｌ虹ｐｌｉ哪．ＮｏｎｎａｌＢ嬲ｉｓ【３０】Ｂ．ＳｕｍｒＥ衢ｃｉｅｎｔ研Ｉ恤ｌａｌＴｙｐｃＩｌＦＭＵＬｔｉｐｌｉｃｒ，ＩＥＥＥＴｒ趾ｓ．Ｃｏｍｐｕ觚，、，０１．５０，ｎｏ．１，ｐｐ．８３－８８，Ｊ锄．２００１．【３ｌ】Ａ．Ｒｅｙｈａｎｉ－ＭａｓｏｌｅｈａｎｄＭ．Ａ．Ｈａｓ姐．ＦａｓｔＮｏｍｌａｌＢａｓｉｓＭｕｌｔｉｐｌｉｃａｌｊｏｎ啦啦ＧｅｎｅｒａｌＰｕｒｌ）ｏ∞Ｐｒｏｃｅｓｓｏｒｓ，ＴｏａｐｐｃａｒａｔＴｅｃｌｌＩｌｉｃａｌＲｃｐｏｎ，ＣＯＲＲ２００ｌ一２５，２００１．ＳＡＣ’２００１．－ＣＡＣ取ＵＩｌｉｖ．ｏｆＷｒａｔｅｒＩｏｏ）［３２】Ｓ．Ｍ．Ｙｅｌｌ＇ＩｍｐｒｏｖｅｄｎｏｎＩｌａｌｂ髂ｉｓｉｎｖｅｒｓｉｏｎｉｎＧ，（２“），ＩＥＥＥｌｅｃ仃ｏｌｌｉｃｓＬｅｔｔｅ岱，参考文献Ｖｏｌｌ３３，Ｎｏ．３，ｐｐ．１９６—１９７，Ｊ锄．１９９７．【３３】ＢｒｉｃｋｄｌＦＦ．Ａ融ｍｏｄｕｌａｒｍｕｌｔｉｐｌｉｃａｔｉｏｎｉｎａｌｇｏｄｔｈｍ谢ｔｈ。ａｐｐｌｉｃａｔｉｏｎＰｒｏｃｅｅｄｉｎｇＳｔｏ似ｏｋｅｙｃｒｙｐｔｏ擎ａｐｈｙ，ａｄｖａｎｃｃｓｃｒｙｐｔ０酉ａｐｈｙｏｆＣ呻ｔｏ－８２，ＮｅｗＹ－ｏｒｋ：Ｐ１ｃｎ啪Ｐｒｅｓｓ，１９８３，５１・６０。口４】Ｓａｌｌｇ【３５】Ｔ．Ｉｔｏｈｈｏ也ｃｈａＩｌｇＨ锄硒ｍ．舢ｇｏ删恤ｏｆａｎｄｉＩｌｖｅｆｓｃｏｐｅｒａｔｉ∞ｉＩＩ叨．ＩＥＥＥＴｒ锄啦ｃｄＯ船∞Ｉｎｆｏｍｍｔｉ∞ｎｃ０职１９９８．ｓ．Ｔｓｕｊｉｉ．Ａ触ａ１９０Ｉｉｔｌｍｆｏｒｃｏ唧ｕｔｉｎｇＧＦ（２“）ｌｌｓｉｎｇｎｏｍｌａｌｂａ∞ｓ，Ｉｎｆｏｍｌａｔｉ∞粕ｄ１９８８．ｃ伽删ｏｎ，ｖｏｌＩＩｌｍ６ｐｌｉｃａｉｉｖｅｉｎｖｅｒｓｅｓｉｎ７８，ｐｐ．１７ｌ－１７７，【３６】Ｄａｎ℃ｌＨａｌｌｌ【ｅｒｓｏｎ，Ａｌ舭ｄＭｅＩｌｅｚｅｓ，ｓｃＤｔｔＶａ哪瞳。鹏．（ｈｉｄｅｔｏＥｌｌｉｐｔｉｃｃ咖ｃｕⅣｅＣｒｙｐｔｏ鲫ｈｙ，２００３：（８１・９０）．【３７】ＪｕｌｉｏＬ０ｐｅｚ．ＡｎｏｖｅｎｒｉｅｗｏｆＥｌｌｉｐｔｉｃＣｕ“ｅＣｒｙｐｔｏｇｒａｐｈｙ，ｅｔａｌ，２０００．ｔ０【３８】Ｄａｎ．ｃｌＨ锄ｋｃｒｓ‘砜Ａｌ舶ｄＭｅｍｚｅｓ，ｓｃｏｔｔＶａＩＩｌｓ胁∞．（＇ｍｉｄｅＣｒｙｐｔｏ掣ａｐｈｙ，２００３：（９１．９５），【３９】Ｄａｎ．ｅｌＨ孤ｋ盯ｓｏｎＡｌ矗ｅｄＭ∞ｅｚｅｓ，ＳｃｏｔｔＶ缸ｌｓｔ０船．ＧｕｉｄｅＣｒｙｐｔｏｇｒａｐｈｙ，２００３：（１０一１３），【４０】Ａ．Ｍｅｎｅｚｅｓ，Ｔ．０ｋａｒＩｌｏｔ０．ＲｅｄｕｃｉｎｇｄｌｉｐｔｉｃｆｉｎｉｔｅｃｕｒｖｅＥｌｌｉｐｔｉｃｔｏＥｌｌｉｐｔｉｃＣｕⅣｅ１０９ａｒｉｔｈｍｓｔｏｌｏｇａｒｉ岫ｓｉｎａｆｉｅｌｄ．ｈｔｔｐ：／＾＾九＾几ｖｃａｃ邶ｎａｍ．圳吼ｅｄｏｏ．ｃａ，２００３．Ｌｏｗ【４１１Ｆ强．Ｈ，Ｄａｉ．Ｙｃｏｍｐｌｃｘ酊ｂｉｔ－ｐ撕ｌｌｅｌ∞册ａｌＩｓｓｕｅｌ，８ＶＬｓＩｂ勰ｅｓｍｕｌｔｉｐｌｉ粥ｆｏｒａｎｄｉｎｖｅ礴ｂｎＧＦ（２”），Ｅｌｅｃ仃ｏｎｉｃｓＬｅｔｌ髓ｓＶｏｌ啪ｅ４０，【４２】ＬｉｊｕｎＧａ０，ｓｏｂｅｌＩｎａｎ．ＧＥ．Ｉ删瑚ｗｄｉｎＪ雒．２００４Ｐａｇｅ（ｓ）：２４—２６．ｄｅｓｉ弘ｓｆｏｒ删小岫ｌｋａｔｉｏｎＧＦ（矽）ｏｖｅｒｎｏｍｌｂａ∞ｓＡＳＩＣ，ｓＯＣＣｏｎｆｈｅｎｃｅ，２０００．Ｐｒｏｃｃｃｄｉｎｇｓ．１３ｔｈＡｎｎＩｌａｌＩＥＥＥＩｎｔｅｍａｌｉｏｌｌａｌ１３－１６Ｓ印ｔ．２０００Ｐａｇｅ（ｓ）：９７—１０１．【４３】ＲｅｙｈａＩｌｉ—ＭａＳｏｌｅｈ，气Ｈａｓ锄．Ｍ，Ａ．．Ｅｍｃｉｅｍｍｕｌｔｉｐｌｉｃａｔｉｏｎｂｅｙｏｎｄｏｐｔｉｎｌａｌｎｏｍ“ｂａｓｅｓ，Ｃｏｍｐｕｔｅ塔，ＩＥＥＥ１ｈｍ∞ｔｉｏ船叩ＶｒｏＩｕｍｅ５２，Ｉｓｓｕｅ４，Ａｐｒｉｌ２００３Ｐａｇｅ（ｓ）：４２８～４３９．ｓｃａＩａｒ［４４】Ａｎ谢，Ｂ．，ＨｌｌａｌｐｃｎｇＷｕ．Ｐａｒ击ＩｅｌｍｌｌＩｔｉｐｌｉｃａｔｉ∞内ｒｅｌＩｉ砸ｃｃｕｒｖｅｃｒｙｐｔｏｓｙｓｔｅ栅ＣｏＩ衄ｕＩｌｉｃａｔｉｏｎｓ，Ｃｉｒｃｕ砥ａｎｄＳｙＳｔｅ脚，２００５．Ｐｒｏｃｅｅｄｉｎｇｓ．２００５ＩｎｔｅｍａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅｏｎⅥ）ｌｕＩｎｅｌ，２７．３０Ｍ匆２００５Ｐａｇｅ（ｓ）：７１－７３ｖｏＬ１．研究成果６ｌ研究成果【ｌ】李德庆，宋斌．Ｒｓ４２２瓜Ｓ４８５分析模型及其应用．电子元器件应用：２００８・Ｏｌ