ECC

北京大学学报(自然科学版)，第44卷，第6期，2∞8年11月Acta Scientiarum Naturalium Universitatis Pekinensis, Vol.44, No. 6 (Nov. 2∞8) 椭圆曲线加密体制的双有限域算法及其FPGA实现王健T蒋安平盛世敏北京大学信息科学技术学院微电子学系，北京1∞871;咱-mail:wangjian8101ω@gmail.com 摘要提出一种支持椭圆曲线加密体制的双有限域算法。该算法可以同时完成素数域和二进制域上的运算，并且模数p和取模多项式可以任意选取。提出了椭圆曲线加密体制运算单元的设计方法，此运算单元可以同时完成素数域和二进制域上的所有运算，包括加法、减法、乘法、平方、求逆和除法。此外，描述了椭圆曲线加密体制的FPGA实现，最终的电路可以对任意长度密钥进行加密，并且支持素数域和二进制域上的任意椭圆曲线。关键词有限域:椭圆曲线加密算法;现场可编程门阵列实现中团分类号TN431; TN492 A Dual Finite Fields Algorithm for Elliptic Curve Cryptosystem and FPGA Implementation WANG Jiant , JIANG Anping, SHENG Shimin Department of Microelectronics, School of Electronics Engineering and Computer Science, Peking University, 8eijing 1∞871 ; t E-mail: wangjian810104@gmail.com Abstract A dua1 finite fields a1gorithm for elliptic curve cryptosystem ( ECC) is presented. It can be used in two kinds of finite fields, which are Ga10is fields GF ( p) and GF ( 2 m) for a出i国可primenumbers and irreducible polynomials respectively. An arithmetic unit, which can perform a11 dua1 Galois fields' arithmetic operations, including addition, subtraction, multiplication, squaring, inversion and division，也designedfor由eECC. Furthermore，也eauthors describes a FPGA implementation of ECC. It can efficienÙy handle reques恒fordifferent ECC key length and different cu凹esin GF(p) and GF(r). Key words finite fields; ECC; FPGA implementation 椭圆曲线加密算法(ECC)最早在1985年被Koblitz[l]和Miller[2]分别独立地提出来，至今已经发展了二十多年。在这期间，大量关于ECC的研究成者已经取代了RSA算法，成为主要的加密标准。目前，ECC的实现方案主要有两种:软件实现和硬件实现。软件实现成本低，适应性强，但运算速度慢;硬件实现成本高，设计周期长，但运算速度快。本设计既考虑到了软件实现的长处，也考虑到了硬件实现的优势，最终选择了硬件电路的FPGA实现果先后被发表出来，这些成果主要集中在两个方面，对于椭圆曲线加密算法本身的改进以及对该算法实现方案的改进。作为公钥密码体制的ECC算法和同样为公钥方案，这个实现方案和定制的硬件电路实现方案相比减少了设计戚本和时间。为了提高产品的适应密码体制的RSA[3]算法相比，突出的优点是ECC的加密强度更强[4]。通常认为当ECC的密钥长度达到163位时，其加密强度等同于RSA的密钥长度达到1024位的加密强度。正因为如此，目前ECC的应用越来越广泛，在很多领域(如快速加密、密钥交换、身份验证、数字签名、移动通信的安全保密)正在或收稿日朔:2∞7-11-01 ;修回日期:2∞8-06-03 性，本设计专门为ECC电路设计了可以支持素数域和二进制双有限域的运算单元，使得最后的产品可以满足更多情况下的加密工作，进一步降低了成本。在目前国内外已经发表的成果当中，可以同时完成两个有限域的ECC加密芯片并不多见。871 第6期域运算单元中两种有限域上的加、减法运算应该分别设计。有限域的乘法运算比加、减法运算要复杂，在很多文献中素数域和二进制域上的乘法运算差别很大[，]这样会增加有限域运算单元的设计成本。在本设计中将一种二进制域上乘法算法成功地应用到了素数域上，并且做了重要改进。既统一了两种有限域上的乘法算法，同时还提高了它们的运算效率。下面给出二进制域上乘法的具体算法:算法1二进制域乘法算法。输入:二进制域上的两个元素α，b。输出:c =αo b mod f(j是二进制域上的取模多项式)。1) c = 00 2)重复执行①若α。=1，则c= cEÐb。(b = (b << 1) EÐf。③α=α>> 10 ④若α=0，则执行步骤3。3)返回(c)(c=αob mod f)。算法1对二进制域上的乘法算法做出了两点重要改进:第一，步骤2)中①将变量C的移位运算与C的取模运算合并，这步运算在硬件实现上可以设计出与其相对应高效电路;第二，步骤2)中④增加了对元素α取值的判断，当元素α的值为零时将完成乘法运算。算法1和其他的二进制域乘法算法[7.8]相比，效率高，而且计算过程并不依赖取模多项式f，因此算法1的应用更加灵活。为了降低有限域运算芯片的成本，提高其运算效率，本设计将二进制域上的乘法算法1成功地应用到了素数域上，使得两种有限域上的乘法算法相统一。具体的算法如下:算法2素数域乘法算法。输入:素数域两个元素α，b。输出:c =αobmodp(p为素数域上的模数)。1) c = 00 2)重复执行①若α。=1，91Uc=c + bo ②若c~ p，则c= c -p。(b=b<< 1。④若b~ p，则b= b -p。⑤α=α>> 1。⑤若α=0，则执行步骤30王健等:椭圆曲线加密体制的双有限域算法及其FPGA实现3)返回(c)。算法2是算法1在素数域上的应用，和算法1唯一的不同是增加了步骤2)中③取模运算，可以说算法2继承了算法1的全部优点。在有限域运算单元的设计中由于算法1和2非常类似，因此它们的控制单元可以复用，节省了成本。同时，算法1和2也可以做平方运算。相对于有限域上的加法、减法、乘法和平方运算，有限域上的求逆运算则要更加复杂，很多文献['.9]专门研究有限域上的求逆运算，也提出了很多的算法。二进制域上的求逆算法通常有两种:多项式的扩展Euclidean算法[9]和Fennat定理求逆算法[1飞素数域上的求逆算法有扩展的整数Euclidean算法['J和Montgomery求逆算法[11]。在这里不去比较各种算法的优缺点，但是由于本设计是要完成双有限域上的运算，因此Euclidean算法是首选，因为Euclidean算法可以在二进制域和素数域上同时使用。算法3同时支持素数域和二进制域的统一求逆算法。输入:模p(素数域的模数p或二进制域的既约多项式f)、求逆元素α和有限域判断变量m(当m= 1时表示素数域，当m=0时表示二进制域)。输出:α-1mod p。1) u =α，V = p。2) X1 = 1,x2 =0。3)当U笋1和U并1时，重复执行①当U是偶数时，重复执行u = ul2; 若x1是偶数，则x1= x112; 否则，当m= 1时，x1= (x1 + p)l2; 当m=0时，x1= (x1 EÐp) >> 1。②当U是偶数时，重复执行v=vl2; 若X2是偶数，则问=x212; 否则，当m= 1时，问=(x2+p)l2;当m=O时，向=(x2EÐp)>>10③若u~v，则，当m= 1时，u=(u-v)l2;若x1>吨，则当x1和x2奇偶性相同时，x1= (x1 -x2)12; 当矶和x2奇偶性不同时，x1= (x1 -x2 + p)/2; 873 北京大学学报(自然科学版)否则，当X1和X2奇偶性相同时，X1=(X2-XI)I2+p; 当X1和向奇偶性不同时，XI=(X2-xl+p)1勾当m=0时，u = ( uG;) v) >> 1 ; 当X1和X2奇偶性相同时，X1= (X1G;)X2) >>1; 当X1和X2奇偶性不同时，X1= (X1G;)X2G;)P) >> 10 否则，当m= 1时，v = ( v -u) 12 ; 若X2>叭，当X1和X2奇偶性相同时，X2= (x2 -X1 )/2; 当X1和X2奇偶性不同时，问=(X2-X1+p)/2; 否则，当X1和X2奇偶性相同时，叫=(x1 -X2 )12 + p; 当X1和X2奇偶性不同时，X2 = (x1 -X2 + p)l2; 当m=0时，v = ( vG;) u) >> 1 ; 当XI和X2奇偶性相同时，X2= (X1G;)X2)>> 1; 当X1和X2奇偶性不同时，问=(X1G;)X2G;) p) >> 1。4)若u= 1，则返回(X1) ;否则，返回(X2)。算法3作为Euclidean算法的一种改进算法，成功地将两个有限域上的求逆算法统一起来。其中步骤3)中③做出的多处运算上的改进进一步提高了算法3的运算效率。3 点乘运算的硬件实现针对点乘运算分为3个层次的特点，本设计在硬件设计上也分为3个模块，它们和点乘运算的3级运算一一对应，如图2所示。在电路的总体结构确定之后，本设计的重点放在了开发有限域运算模块上。这个模块功能强大，其算法背景就是本文第2部分提到的3个算法，而它可以实现的运算如表1所示，可以完成素数域和二进制域上的所有运算。有限域运算模块的硬件结构如图3所示，在图3中控制单元通过\"mode\"信号来控制电路的具体运算。完成这么多的运算，只花费了4个寄存器，在算术逻辑运算单元中只由一个加法器和一个减法器组成。在这个模块的电路设计中实现了大量的硬件资874 第44卷固2点乘硬件结构图Fig.2 Hardware structure of point multiplication 襄1有限域运算模块所支持的运算Tahle 1 Operations supported by the finite fields' operatio咽circuit运算模式运算名称。初始化素数域加法2 素数域减法3 二进制域加减法4 素数域乘法和平方5 二进制域乘法和平方6 素数域求逆7 素数域除法8 二进制域求逆9 二进制域除法圈3有限域运算模块的硬件结构Fig.3 Hardware structure of the finite fields' operation circuit 源的复用，同时并没有降低每一种有限域运算的计算效率。4 FPGA实现和数据分析在FPGA实现中，本设计选用了Xilinx公司生产的Virtex2系列的xc2v3ωo芯片，封装标准为fg676。以设计好的ECC点乘运算verilog-HDL代码作为输入文件，通过专业软件来完成FPGA硬件电路的设计。主要流程为:1)对verilog代码进行综合设计;2)对综合后的结果进行实现设计，并完成电路的布局布线;3)生成编程文件;4)将编程文件写到北京大学学报(自然科学版)褒6T由le设计方法本设计文献[12]第44卷FPGA实现比较时钟频率计算时间Ims6 Comparison with related work on FPGA implementation 电路设计有限域GF(p)p为256位和GF(俨6)FPGA Xilinx Virtex-II FPGA Xilinx Virtex-II FPGA Altera EP1M350F780C5 FPGA Xilinx Virtex-II 49.5 MHz 66 MHz 素数域5.9;二进制域3.2GF(p) p为192位4.8 0.9368 1.9 文献[13J 文献[14]GF(2'63 ) GF(2'日)N/A N/A 5 总结本文在深入研究了椭圆曲线加密体制(ECC)的各种算法后提出了一种可以同时支持素数域和二进制域的有限域算法，并且在FPGA上完成了该算法的硬件实现。可支持双有限域的算法的提出是本设计的核心工作，这个算法整合了两种有限域上的所有算法，同时保证了每一种运算的高效运行。在硬件电路上采用了模块化的设计，高效地实现了改进后的算法。在FPGA测试中面积、速度和功耗这些电路参数都有很好的表现。对于这样一款ECC加密芯片，其应用性非常强大，它可以支持两种有限域上任意椭圆曲线任意位长的加密和解密运算。参考文献[ 1 J Koblitz N. Elliptic curve cryptosystems. Mathematics of Computation, 1987, 48(177): 203-2ω [2 J Miller V S. Use of eJliptic curve in cryptography 11 Advances in Cryptology CRYPfO 1985. New York: Springer-Verlag, 1985: 417-426 [3J Rivest R L, Shamir A, Adleman L. A me出odfor obtaining digital signatures and public-key cryptosystems. Com-munications of the ACM, 1987,21(2): 120-126 [4J Cil时oA, Coppolino L, Mazzocca N, et al. Elliptic curve cryptography engineering /1 Proceedings of the IEEE, Feb. 2侧，94(2): 395-4凶[5 J Hankerson D, Menezes A, Var回toneS. Guide to Elliptic 876 Curve Cryptography. New Y ork: Springer-Verlag, 2∞5 [6J 徐茂智，游林.信息安全与密码学.北京:清华大学出版社，2∞7[7J Satoh A, Takano K. A Scalable dual-field elliptic curve cryptographic processor. IEEE Transactions on Computer毡，2∞3，52(4): 449-4ω [ 8 J Crowe F, Daly A, Marnane W. A Scalable dual mode arithmetic unit for public key cryptosystems. IEEE Coding and Computing (口'CC'05)，2∞15， 1: 567-573 [9 J Burnner H, Curiger A, Hofstetter M. On computing ml刷plicativeinver回sin GF (2\"' ). IEEE Trans on Compute阻，1993，42(8):1010-1015 [ 10 J Dinh A V, Bolton R J, Mason R. A low latency architecture for computing multiplicative inverses and divisions in GF ( 2\"' ). IEEE Tr田国Analogand Digital Signal Processing, 2∞1， 48(8): 789-793 [ II J Savas E . A c町y-freearchitecture for montgomery inversion. IEEE Trans on Computers, 2∞15， 54 ( 12) : 1508-1519 [12剖J肌WuShu血JhuaωJa，Zhu阳uYue刷岛f凹e缸i.A 肥盹酬u陀rce描efficie阻len削It酣a陀时础胁h山盹IÌ让i怡阳te回ec讪for RSA and elliptic curve cηP严>toωsy严st怡ems.Communications, Ci配uitsand Systems Proceedings, 2创施，4: 2356-2360 [ 13 J Dupont L, Roy S, Chouinard J Y. A FPGA implementation of an elliptic curve cryptosystem 11 ISCAS 2α后，May 2∞6. Island of Kos, Greece, 2创滔[ 14 J Liu Sining, Bowen F, King B, et al. Elliptic curve C可ptosystemimplementation ba回don a look-up table sharing scheme 11 ISCAS 2饭后，May 2∞6. Island of Kos, Greece, 2α后