一种椭圆曲线参数生成的快速算法

一种椭圆曲线参数生成的快速算法 谷勇浩 刘勇 (北京邮电大学通信网络综合技术研究所) 摘要:椭圆曲线密码体制是公钥密码中的研究热点。该文介绍了椭圆曲线密码体制的基本概念及相关知识～讨论了目前基于离散对数问题的椭圆曲线密码的研究动态。本文的创新点是针对目前椭圆曲线研究重点之一——椭圆曲线参数生成算法～给出了一种生成参数a、b的快速算法。这种算法利用了Jacobi符号和二次剩余的理论～并且用matlab计算出利用这种算法生成一个椭圆曲线的平均时间～最后我们了今后椭圆曲线密码系统的研究方向和重点。 关键词:椭圆曲线,离散对数问题,Jacobi符号,二次剩余,阶 1976年Diffie和Hellman提出公钥密码思想以来，国际上提出了许多种公钥密码体制的实现。一些已经被攻破，一些被是不可行的。目前，只有3类公钥密码体制被认为是安全有效的，按照其所依据的难题划分为:基于大整数分解问题(IFP)，如RSA体制和Rabin体制;基于有限域离散对数问题(DLP)，如Diffie-Hellman体制和ElGamal体制;基于椭圆曲线离散对数问题(ECDLP)，如椭圆密码体制。椭圆曲线应用到密码学上最早是由Neal Koblitz和Victor Miller在1985年分别独立提出的。它是目前已知的公钥体制中，对每一比特所提供加密强度最高的一种体制。它具有安全性高、密钥量小、灵活性好的特点，受到了国际上的广泛关注。而SET(Secure Electronic Transaction)的制定者已把它作为下一代SET协议中缺省的公钥密码算法。深入研究基于椭圆曲线离散对数问题的公钥密码具有很大的现实意义。 1建立椭圆曲线公钥密码体制 1.1椭圆曲线域的参数 在基于椭圆曲线的加解密和数字签名的实现方案中，首先要给出椭圆曲线域的参数来确定一条椭圆曲线。在 IEEE P1363标准中，定义其参数为一个七元组:T=(q,FR,a,b,G,n,h)， m其中q代表有限域GF(q)，q为素数或;FR为域表示法，如f(x)为m域元素的不可约2F2 2m3多项式的表示法;曲线的方程，当q为素数时，方程为，当q为时，,，，axby2x 232方程为，a,b是方程中的系数;G为基点;n为大素数并且等于点G，,，，xyabyxx hEn,#()/的阶，h是小整数称为余因子且。主要的安全性参数是n，因此ECC密钥Fq 的长度就定义为n的长度。 1.2椭圆曲线密码的密钥 选取了基域和椭圆曲线后，得到了在有限域上的曲线E确定的具体形式，即FFqq 上述的椭圆曲线域参数的一个七元组。每个用户选取一个整数d(1?d?n-1) 作为其私钥，而以点Q=dG(G为基点)作其公钥，这样形成一个椭圆曲线公钥密码系统。在这个密码体制中，具体的曲线，基域，基点G及其阶n，以及每个用户的公钥都是该系统的公开参Fq 数，每个用户的私钥是保密的。 1.3基于椭圆曲线密码体制的加解密 假设用户A欲将明文m加密后发送给B，A执行以下操作: (1)查找B的公钥(E(，G，n，)); QFqB m,(2)将m表示成一个域元素，即; Fq (3)在区间[1，n-1]内选取一个随机数k; 4)计算点; (kG,(,)yx11 (5)依据B的公钥计算点，若,0，则返回到第(3)步; k,(,)Qyxx22B2 Cm,，(6)计算; x2 (7)传送加密数据给B。 (,,)Cyx11 B收到A的密文后，执行以下操作。 (,,)Cyx11 ,1(1)使用私钥，计算点，再计算中; (,)(,),yy()dFdxxqBxB12212 ,1(2)计算m=C，得到明文m。 ()x2 2 椭圆曲线密码的研究动态 2.1椭圆曲线密码的安全性 ECC的安全性是建立在离散对数问题计算难度基础之上，如果离散对数可以计算，从一个用户的公钥就可得到他的私钥，ECC就不安全了。对于一般的ECDLP，目前有两种较 [1]好的求解法:Pohlig-Hellman方法和Pollard-ρ方法。但是对于两类特殊的椭圆曲线，已经 [2]有了其他有效的求解方法。一类特殊的椭圆曲线——超奇异椭圆曲线(设的特征为p，Fq 的q阶Frobenius变换的迹t是p的倍数时，E称为超奇异的)，采用概率亚指数算EF/q 法——MOV算法和FR算法可以解决ECDLP。另一类特殊椭圆曲线是异常(anomalous)椭圆 m23[2]PE,()曲线(设，p?2,3为素数，由方程定义，q,,，，axbpyEF/Fqxq 的阶为p。当p=q时，异常曲线上的p阶Frobenius变换的迹t=1)，SSSA算法可以解决ECDLP。 2.2 椭圆曲线的选取 要保证椭圆曲线密码的安全性，就是要使所选取的曲线能抵抗上述的关于ECDLP 解决的方法和算法，所以选取一条安全的椭圆曲线，是一个深刻的数学难题，在此，仅提供几 [3]点椭圆曲线选取的安全准则: (1)为了抗击Pollard-ρ攻击，所选取EC的阶#E(GF(q))的分解式中应该包含一个大的素数因子，目前应不小于160bit; k(2)为了抗击Weil对和Tate对的攻击，对于1?k?30，n不能除(不宜选取超,1q 奇异椭圆曲线); (3)为了抗击Semaev-Smart-Satoh-Araki的攻击所选曲线的阶不能等于该曲线所定义的有限域的阶，即#E()?q(不宜选取异常椭圆曲线); Fq m(4)对于二进制域GF()的度m不宜为合数。Gaudry，Hess和Smart提出，若m有小2 约数l(l=4)，存在比Pollard's rho算法更快求解ECDLP的方法。 下面介绍3种选择适宜的椭圆曲线的方法: (1)仅限于有限域为上构造椭圆曲线。其原理是将定义在特征值比较小的有限域的mF2 椭圆曲线提升到该域的扩域上去，并且m能被小整数k?1整除。这种方法简单，但是得到的曲线较少。 (2)CM(Complex Multiplication)法，根据给定的阶来选取符合此阶的椭圆曲线。它的实现速度相对较快，但这种方法产生的椭圆曲线具有附带的结构特征。从安全性角度讲，这是一个潜在的威胁。 324270，,(3)随机选取曲线。随机选取曲线的参数a,b?如果q是素数，则满足;Fabq m如果q=，则b?0，然后计算u=#E(Fq)和大素数因子n，直到所选曲线满足安全需求。这2 种方法比较理想，选取的曲线安全级别高，它完全依赖于椭圆曲线阶的计算。 2.3椭圆曲线阶的计算 从上述椭圆曲线的安全性来看，如果曲线的阶充分大，平方根攻击如Shanks's baby-step gaint-step或Pollard's ρ方法就不太有效，要能抗击Pohlig-hellman攻击，一个好的策略是确保曲线的阶#E(Fq)中包含有大素数因子(该大素数作为所选取基点P的阶)使得 On()P,Pohlig-hellman算法的计算量不能实现。由此看来，计算#E(Fq)是研究定义在有限域上的椭圆曲线的一个核心问题。 对于#E(Fq)的计算是一个纯粹的数学问题。目前有两种方法可以采用: (1)随机选取一条定义于有限域的椭圆曲线，直接计算该曲线的阶，使其满足#E(Fq)Fq 中包含有大素数因子。在这方面，R. School做了开创性的工作，提出了著名的School算法，后经Atkin和Elkies的改进，提出了SEA(School Elkies Atkin)算法。后来，Morain,Lercier等人又对它作了一些优化，如今SEA算法已成为计算椭圆曲线阶的有效算法。另外，Satoh也提出了比较有效的算法及目前对于二进制域效率较高的Satoh-FGH算法。 mm(2)仅限于有限域为且它要求所定义的有限域中的m能分解为m=de，其FF22 ddde中d为一个小整数，通过计算子域上的#E()，从而计算出#E()。这种方法FFF222 d简单易实现，但是适用范围较小，不能计算出任意m或固定m的#E()。 F22.4 椭圆曲线的快速算法 在椭圆曲线密码体制应用中的大量运算是倍乘(数乘)，就是一串点的加法运算，即计算k*P=P+P+?+P共有k个P相加。椭圆曲线密码快速实现的关键就是快速实现kP的运算 (包括算法优化和程序优化、软件实现和硬件实现)。其中kP的运算主要基于两方面的运算:基域上域元素和曲线上点的运算。这些运算与我们所选取的有限域、采用的坐标系、基域中的元素表示方法、选取怎样的椭圆曲线和计算kP的方法有关。因为同一基域中的元素表示方法不一样(如中有多项式和通项表示法);不同的坐标系(如仿射坐标和射影mF2 坐标)下，都会影响kP的计算量。对于一些特殊的曲线，如Koblitz curves，已经有了较好的算法，但是对一般随机的椭圆曲线，如何快速计算kP仍是一个需要研究的问题。 3 椭圆曲线参数快速生成算法 3.1产生椭圆曲线的传统算法 通常情况下，从特定秩生成曲线组中随机选取一个作为椭圆曲线。下面的算法生成基于GF(p)域的椭圆曲线参数，而且能够生成足够的信息能使其他人验证这样的曲线的确是随机生成的。 [4] 选定如下参数: 素数模p;基点秩的上下界和;输出长为B比特的Hash函数H，其中rrmaxmin 1，，B,()LB,;以及Hash函数的输入比特长L，。 logrmin,,22,, 还要使用如下的符号: (1)v,,,，，p v = ;s = ;w = v -Bs -1 log,,2B,,，， 算法输入:p，，，(用于测试的除数的上限，满足<); llrrrminmaxminmaxmax 算法输出:比特串X;EC参数q=p，a，b，r，G (1) 选择长为L的比特串X; (2) 计算h=H(X); (3) 选取h的最右面的w比特串计为; W0 (4) 将字符串X转换为整数z; (5) I从1到s，作如下循环 L(5.1)将整数(z+i)mod()转化为长为L的比特串; X2i (5.2)计算,H(); WXii (6) 将所有的以如下形式合并成W: Wi W,||||...|| || 代表连接 WWW01s (7) 将长对为v-1的字符串W转换为整数c; (8) 如果c=0或4c+270(mod p)则返回到(1); , 23cp,(mod)(9) 选择整数a，bGF(p)，满足;(最简单的方式是选择a=c，,ba b=c。但是，出于性能的考虑，我们要选择其他的a,b) 23(10) 给定基于GF(p)的椭圆曲线E:，计算它的秩u; ,，，axbyx (11) 测试u的素性概率; (12) 如果u几乎不可能是素数，则返回(1);否则通过 ?? 的输出中含有k，r; (13) 生成秩为r的曲线E上的点G; (14) 输出X，a，b，r，G。 3.2 改进的a、b生成算法 23cp,(mod)为了计算(9)中，已经有很多中算法(例如，进化算法)，但是生ba 成参数a，b仍然需要花费很长时间。根据IEEE 1363中介绍的方法生成椭圆曲线参数的时 间大约为15s，所以，生成一个椭圆曲线需要的时间仍然是一个有待解决的问题。 为了解决椭圆曲线生成时间上的问题，本文将介绍一种新的方案，来解决23cp,(mod)计算上的问题。这种方法是基于雅可比符号(Jacobi Symbol)和二次剩ba 余(Quadratic Residue)理论。算法步骤如下: (1) 选定一个迭代数; (2) 随机生成参数c(长度为256比特); (3) 生成向量M(a，b，f)，其中a(长度为256比特)是随机的，b=0，f为一个 大整数; (4) 处理向量M的过程: ,1(4.1)计算(mod p); c ,13(4.2)计算((mod p))mod p = h; ,ca h(4.3)计算Jacobi符号; ()p h2,hpmod(4.4)如果,1，则; ()bp h(4.5)如果1，则随机生成新的a(长度为256比特)，返回(4.1); (),p 23cpp,,(mod)(mod)(5) 计算f = ;如果f = 0，则向量(a，b，c)就是生ba 成的结果; (6) 返回(4)，知道向量M中所有的EC都处理完; (7) 随机生成新的c(长度为256比特)，返回(3)。 以上算法通过Matlab运算，有如下结果: 向量中EC数目 生成所有EC的时间(s) 生成每个EC的时间(s) 1000 67 0.067 2000 128 0.064 5000 309 0.0618 有了这种算法，可以加快a、b的生成，再结合参考文献4中介绍的其他参数的生成算法，就可以快速生成安全而且有效的椭圆曲线，并且可以把它用于生成抗攻击的密码系统中。 4 结束语 椭圆曲线密码是一种能适应未来通信技术和信息安全技术发展的新型密码体制，它在运算速度和存储空间方面占有很大的优势，目前它已成为公钥密码体制中的研究热点。实际上 [5]椭圆曲线密码算法还有几个地方有待完算，今后主要的研究方向有3个方面: (1) 如何快速选取安全性高的椭圆曲线。 (2) 如何有效计算椭圆曲线的阶。因为选取安全椭圆曲线的核心步骤是对椭圆曲线阶 的计算，对计算椭圆曲线阶的有效算法的研究也是实现安全椭圆曲线密码体制的 一个极其重要的环节。 (3) 在椭圆曲线密码体制中，椭圆曲线群上点的倍乘占了整个运算的很大比例，它的 效率关系到整个体制的执行效率。对椭圆曲线中的kP倍乘计算仍需研究一种高 效快速的方法。 参考文献 [1] 李学俊,敬忠良等. 基于椭圆曲线离散对数问题的公钥密码. 计算机工程与应用. 2002,38(6):20-22. [2] 斐定一,祝跃飞. 算法数论. 北京:科学出版社,2002. [3] Lopez J, Dahab R. An Overview of Elliptic Curve Cryptography. Technical Report, Institute of Computing, State University of Campinas, Brazil, 2000-05-22. [4] IEEE Std 1363-2000: IEEE Standard Specifications for Public-Key Cryptography. 2000.1.30. P146-147. [5] 张雁，林英，郝林. 椭圆曲线公钥密码体制的研究热点综述. 计算机工程 第30卷 第3期 2004.2. 作者简介 谷勇浩 男，1980年8月生于山西省太原市，2002年7月获得杭州电子科技大学(原杭州电子工业学院)计算机科学与技术学士学位。目前正在攻读北京邮电大学通信与信息工程博士学位。主要研究方向:入侵检测、风险评估、密码学。 刘勇 男，教授，博士生导师。研究方向:下一代无线通信技术、网络及信息安全。