 Computer Science and Application 计算机科学与应用, 2012, 2, 26-31 http://dx.doi.org/10.12677/csa.2012.21006 Published Online March 2012 (http://www.hanspub.org/journal/csa) Research on Fast Algorithms of Elliptic Curve over 3n GF * Jingjing Liu, Meng Zhou School of Mathematics and System Science, LMIB, Beihang University, Beijing Email: jingjingliu1988@163.com, zm1613@sina.com Received: Nov. 24th, 2011; revised: Dec. 16th, 2011; accepted: Jan. 2nd, 2012 Abstract: 3n GF , as a more special type field of n GF p, the e lliptic curv e cryptos ystem based on which has thei r own advantages. As we know, reducing the operation of inverse is an important method in elliptic curve cryptography fast calculation. It requires 2k times inversions on elliptic curves over 3n GF 3kP to compute scalar multiplication by individual computation. This paper deduces a formula of calculating directly based upon the idea of recursive induction and trading inversions for multiplication, which reduces the inversion to once. The proposed algorithm is prior to multiple tripling point algorithms when the speed ratio of field inversion to field multiplication is high. And the bigger the ratio is, the more the efficiency improves. 3kP Keywords: Elliptic Curves; Scalar Multiplication; Field Inversion; Recursive Induction 3n GF 椭圆曲线快速算法研究* 刘景景，周 梦 北京航空航天大学数学与系统科学学院 LMIB，北京 Email: jingjingliu1988@163.com, zm1613@sina.com 收稿日期：2011 年11 月24日；修回日期：2011 年12 月16 日；录用日期：2012 年1月2日 摘 要： 3n GF 作为 更加特殊的一种类型，定义于其上的椭圆曲线密码算法有自己的优越性。快速计 算椭圆曲线密码标量乘的方法之一是牺牲乘法或平方减少求逆次数，若采用逐次累加的方法计算 n GF p 3n GF 3k 上椭圆 曲线标量乘，需要 次求逆运算。本文根据递推归纳、转换求逆为乘法的思想，推导了直接计算 的公 式，使求逆运算降至一次。在逆乘率 I/M 较高时，其效率要优于逐次三倍点算法，并且逆乘率越大，其效率提 高的越多。 3kP2k P 关键词：椭圆曲线；标量乘；求逆；递推归纳 1. 引言 自1985 年Koblitz[1]和Miller[2]各自分别提出椭圆 曲线密码体制(ECC，Elliptic Curve Cryptography)， ECC 就一直得到众多密码学家及密码学研究者的关 注。 ECC 体制的安全性是基于椭圆曲线上离散对数问 题求解的困难性[2]，目前还没有找到解决此问题的亚 *基金项目：国家自然科学基金资助项目(10871017)；北京市自然科 学基金资助项目(102026)。 指数时间算法，因而与另一著名的公钥密码 RSA 相 Copyright © 2012 Hanspub 26  3n GF 椭圆曲线快速算法研究 比，ECC密钥短，安全性高，速度快，存储空间占用 少和带宽要求低。它的这些特点使得业内人士普遍认 为ECC 将成为下一代最通用的公钥加密算法标准。 目前，二元域 2ECC n GF 和大素数域 ECCp是最为常用的两个有限域，对于 体制研究的也比较充分。相比而言， 3ECC n GF 的研究工作还很少开展。随着 Weil 对 究的不断进步以及基于此而设计的各 种安全协议的广泛应用，使得小素数扩域椭圆曲线 ECC n GF p能够比传统有限域提供更多、更加灵 案。由于针对 ECC n GF p的攻击 算法相对来说比较少，因而其安 较高。 3n GF 作为 n GF p更加特殊的一种类型，定义于其 曲线 更加优越。 3ECC n GF 有类 似于 2ECC n GF 计算速度快的某 有自 己的特 得其上算术运算效率非常高，极 适合作为安全密码算法的载体。 椭圆曲线标量乘是 ECC中最 GF 椭圆曲线密码 和Tate 对理论 活的密码选择 上的椭圆 密 其上的 殊性质，这使 核心的运算，而求 逆又 2. 背景知识简介 椭圆曲线的定义 定义 1 定义在域K上的 Weierstrass 方程： 6 (1) 所确定的平面曲线称为椭圆曲线：其中 域， 研 方 全 算法 性相比之下比 些特性，但 码 也 是标量乘运算中最耗时的运算，所以很多学者采 用牺牲乘法来减少逆运算的次数，我们延续这一思 想，着重讨论在特征为3的椭圆曲线上直接计算 3kP 的算法。文章首先介绍了ECC 中相关的知识，之 提出了一种直接计算 3kP的递推算法。 后 2.1. 232 :Eyaxy ayxaxax a 13 24 K为有限 12346 ,,,, ,aaaaa K。满足(1)式的 , x y称为域 K 上的点还定义一个特 无穷远点 o；即域 K上的点集和一个无穷远点 o组成域K上的 椭圆曲线 EK。 椭圆曲 的群 ；此外，椭圆曲线 殊的 线E运算是按照椭圆曲线群运算法则 完成的，其中所涉及的运算有加、减、乘、求逆和平 方五种基本运算，用 ,, M SI分别表示域K上的乘法、 平方和求逆运算， I M逆和乘法运算的复杂度 比，也称逆乘率。 基本运算中，加法和减法相对 其他运算来说，所用时间可以忽略不计。求逆运算则 是最耗时的，对于平方和 乘法 ，一般设定 表示求 五种 1S 0.8 M 。 2.2. 椭圆曲线上点的运算 EK表示定义在域 K上的椭圆曲线 E的所有点 及一个无穷远点(称为零点)的集合。设 11 ,Pxy， 22 ,Qxy是 EK上的任意两个非零点，且 PQ 公式 ，仿射坐 点加公式 33 ,PQ xy 和标下 倍点 44 ,x y分别由(2)、(3)给 1) 2P 出： 点加 2 3121 313131 2 3 x aaxx yxxaxy a , 21 2 yy 1 x x (2) 2) 倍点 3 2 4121 414141 2xaax y xx axya , 2 12121 1113 32 24 x ax aya yaxa K的特征等于3且满足 时， (3) 容许的如果 变量 2 12 aa 变换 13 ,, x yxyaxa 可以 变成： 将E 23 y xaxb (4) 其中 ,abK ，上述曲线是非超奇异的，且 3 3a，文献]指出若 [3 3 L F 上的椭圆曲线E由 23 y xaxb (,, 3 L ab F但 1b )决定，则存 E 在 正整数 l，使 得为3 L F 上一类良好的椭圆曲线。下面 给出当椭圆曲线E为形式(4)时，点加和倍点的公式： 1) 点加 2 31 313 2 1 x xx y xx y , 其中 21 2 yy x 1 x 倍点 (5) 2) 2 41 3 41 + x x yy , 其中 1 a y 加的运算量为 (6) 其中点 11 2 I SM ，倍点的 运算量为 11 2 I SM 。 3. 算法改进 由于求逆运算的运算量一般是乘法运算的 10 倍 左右[4]，因此标量乘的计算可以将求逆运算转化为适 Copyright © 2012 Hanspub 27  3n GF 椭圆曲线快速算法研究 量的乘法运算从而提高运算效率。基于这一思想，Ciet 等在文献[5]中给出了 3,4,2,3,4PPPQPQPQ的 快速算法。选取特征3若 根据(5)、(6)式逐次计算，计算量为 上的椭圆曲线(4)计算 3kP， 22kI S k 4kM。下面推导直接计算 3kP的一般 的直接计算公式 算法公式。 3.1. 3P 需从 3P开始。计算3kP直接计算公式的推导 33 ,y ，一般先计算3Px 22 2,Px y，然 后将 11 ,Pxy ，这样 32PP通过式(6 计算 2P和3P，即 加到 2P上P，分别 )、式(5) ： 23 121121 1 +1 a x xy y y ，， (7) 2 21 232123213 21 , yy 1 x xxyxx y xx , (8) 如果按照上面的公式计算3P，则需要两次求逆， 总运算量为 224 I SM 。为了减少求逆运算， 把(7)式中的 22 , x y代入(8)式中的 2 则 3 211 2 y a令 21 1 I ay，从而 3P可以按照如 下公式计算： 23 4 211 , , 11 ,1 I a y 1 Ia Iy 2 21132 +, 2 123 132 x xx xxyxxy , 。其总 运算量为 15 5 I SM ，虽 逐次计算 次平方运 然比 增加了 1次乘法运 算，但是减少了一次求逆 运算。当 算和 3 5.2IM时，该算法优于直接计算。 下面推一般形式，令 11 , 导3P的 A aB y，则 111 A B ，将(7)式中的 2 y代入(8)式中的2 ： 34 311 11 1 21 222 1111 A B yy AB (9) 不需要计算 ，令 和 2 y 23 1111 11 ,dABC AB 4 1 D 11 Bd ，则 211 dC ，将(7)式中的 2 x 代入(8)式中的 3 x ： 11 11 1 11 11 2 1 2 2 11 2 32121 1 11 11 11 1111 11 11 11 11 11 1 CACA x dB dB x xD xx BC Ad BC AdBd Bd BC Ad BC Ad D (10) 令1 ，则 2 1111111111 EBCAdBCAdxD 1 32 1 =E xD 11 3213 11 2 11 23 11 11111 3 1 =CE yxxyx1 dD BC xD EBD D B (11) 令 23 111111 11 F BC xDEBD，则 3 311 = y FD。 为了推导直接计算 的一般算法，这里我们引 一些中间变量： 1 3P k 入了 2 11 1 43 111 111 2 1111111111 23 111111 11 ; ; ; ; . dA B CBA DBd EBCAdBCAdxD FBCxDE BD 1 11 ;; Aa By 则 33 3,Px y可以由以下式子计算得到： 11 33 23 11 == DD ， EF xy (12) 计算复杂度为 1413 I S 法在保证求逆操作不增 式计算 M(一次求逆是计 算 的逆)，此算 加的情况下， 与 3 1 D 以上不使用推导公 31PI 5 5 S M相 比， 加了一些乘法操作，这样牺牲乘法的目的是为 了接下来推导 3kP的一般算法。 3.2. 9P的直接计算公式 增 假设已知 33 3,Px y，下面来计算 ，这 里我们利用 99 9,Px y 33 3,Px y的计算公式，直接计算[6] 99 , 3x y 。 依然令 33 3,Px y9P 2 A a ,3 311 By FD ，则令 2 B 1 F ，从而 3 321 BD； 22 322 ayABD3 1 ， y d 令22 AB； 22 d 4312 4221 43 3 2 32 12 12 11 BAD B a A DD ，令 Cy 4312 2221 CBAD ; 2 2222 22 3332 66 11 BBd Dyay 2 yA DD ，令 2 a 22 DBd ；则 3 1321 ayADB 2 (13) 4312 221 329 C 21 22 9 22121 1 BAD y A BD dD (14) Copyright © 2012 Hanspub 28  3n GF 椭圆曲线快速算法研究 从而： 921213 33 221221 1 992 22 21 211 12 12 22 22122 2211 99 2121 1 1212162 2222122221121 9 21 xx CADCADE BB dD dDD BC AdDBC AdDE DDDD D BCAdDBCAdDD DE DD 2 (15) 令1 则 1212162 2222212222112 ,EBCAdDBCAdDDDE 2 92 9 12 =E xDD 。 3239 3 22 122 92 23 9 12 11 12 16 224 3 221 212212 3 9 12 yxxy BC EEB DD DD DD BCDDEEBDD DD (16) 令2 16 224 3 3221212 21 F BCDDEEBDD ，则 2 93 9 12 =F yDD ； 综上，引 下中间变量： 1 则 可以由以下式子计算得到： 入以 2 2 222 43 222 222 121216 2 12222122221 12 16 224 3 2221212 212 ; ; ; ; ; . Aa B dAB CBA DBd EBCAdDBCAdD DDE FBCDDEEBDD 1 2;F 99 9,Px y 22 9 =,= EF xy (17) 其计算复杂度为 9 23 99 12 12 DD DD 112 30 I SM 。 算的复杂度 与逐次计 ( 448 I SM )相比，该算 法操作，但是减少 法牺牲了 8 次平方操作和22次乘了 3次求逆 操作，当 9.47IM 运算转化为适量的乘 3.3. 27P的直接计算公式 同样按照 3P计算9P的方法，由 9P计算 时，将求逆 法运算能够提高运算效率。 上面由 ，即由 和 2727 27 ,Pxy22 ,EF2 D 找 计算 27P，同时保证 出计算 的一般算 法，得到以下的过程： 3 中间过程和上面累死，便于 3kP 32 2 33 3 12 439 3 33312 333 12 12 99 333 331233 3312 16 92 12 32 16 24 92 9 33312323 3123 ;; ; ; ; ; . Aa BF dAB CBADD DBd EBC AdDDBC AdDD DD DE FBCDD DEEBDDD 2727 27 ,Px y可以由以下式子得到： 33 27 27 23 99 99 12 312 3 , EF xy DD DDD D (18) 其计算复杂度为 12046 I SM 。与逐次计 算的复杂度( 66 12 I SM )相比，该算 次乘法操作，但是 法 14 次平方操减少了 5次求 逆操作，当 牺牲了 作和 34 9.04 时，将求逆运算IM转化为适量的 乘法运算 效率。 能够提高运算 3.4. 3k P 的直接计算公式 根据前面 P和27P的计算，以此类推可 以得到 3kP的递推公式： 对3P，9 2 12 43 ; ; A B CBAM 1 9 9 9 12 31 12 12 16 21 16 224 3 1 ;; ; ; . k kk kkk kkkk kk kkk kkkkkk kkkkk kkk kkkkkkk kkk BF d MD DDD DBd EBCAdM BCAdM MDE FBCMDEE BMD Aa 其中 23 33 11 ,; kk kk kk EF xy MM (19) Copyright © 2012 Hanspub 29  3n GF 椭圆曲线快速算法研究 下面给出在仿射坐标下直接计算 的算法： 输入：基点 输出：椭圆曲线上的点 ; Step 1: 计算 1 Step 2: for i from 2 to k do Step 3: compute: 3kP 11 ,;Px y;ka 33 3, kk kPxy 2 111111 43 111111 2 1111111111 23 111111 11 ;; ; ;; ; . AaByd AB CBADBd EBCAdBCAdxD FBCxDE BD 2 19 9 9 12 43 12 12 16 21 16 224 3 1 ;;; ;; ; . iiiiii iii iii iiiiiiiiii iii iiiiiii iii AaBFd AB MDDDD BAM DBd BCAdM DE FBCMDEE BMD i EB CAdM 12 3 1ii i C M 23 33 11 ;; kk kk kk EF xy MM Step 4: 输出 线上点 P计算 ，其计 算复杂性为 ,; kk xy 33 在此算法中，由椭圆曲 3kP 184162 I kS kM ：第一步中须计算 242 111 ,, ，具体计 算过程如下 A BD 2 1111111111 共4 1 , 次平方， 323 11 111 A B AD，， , 11 1 BC Ad乘法； 第二步中当 i Bd BCAd BCxD ，， ， 23 1 11 11111 BC AdxDD，，，共 2i时，需要 7次平法，14 次 E B 10 次 乘法，从3 开始往后的 法，最后 2k项，每步均需要8次平法 一步还需要计算 ，16 次乘 2, 1kk xEM 3k 3 1 3kkk yFM k 次乘法： 8 ，它需要计算 , 1次平方： 2 1;6M K k M M9, K k M D 2 11 , kk MM 31, kk FM 21, kk EM 2 11 ,1 kk k EM M 次求逆： 3 1k M1 ，其中 9 1, kkk M MD 8 (k M 在上一步中计算k 16 M 时已 且存储98 k 经用到 kk M MM)。综上，计算 3kP共需要的计 算量为： 184162410 71428 1 16 16 I kS kMSM SMk S I M SM . 3.5. 算法性能比较 量的比较，假设1 S = 0.8 1。 ，与逐次计，虽然 了乘法或平方运算 同时也减少 了一些求 根据域中运算 M，列表 通过表 1比较可以发现 算相比 直接计算增加 一些，但 逆运算。而 I M的值一般大10，将求逆 运算转化为 于 适量的乘法运算之后，由上表可以看出， 随着 k的增大，直接计算方法比逐次计算方法更有效。 上面的临界点是 116.85.22 1IkMk ,当k 趋于无穷大时，8.4IM 。故当k比较大且 8.4IM 时，本文介绍的直接计算方法均优于逐次计算方法。 本文根据递归思想及最小公倍数方法究了特 的有限域上的椭圆曲线在仿射坐标下直接计算 ，虽 4. 结束语 ，研 征为 3 3的算法。本质上将耗时的域中求逆运算替换成了 较快的平方或乘法运算 然牺牲了一些乘法或平方 操作，但同时也减少了求逆操作，当逆乘率 kP I M比较 大时，这种替换能加快计算速度，提高运算效率。具 体地，当k很大时， 至少提高：1) 5. 与逐次计算相比，此算法的效率 08%，当9IM时；2) 12.50%，当 10IM时；3) 18.84%，当 11IM时。综上， I M 值越大，将求逆运算转化为适量的乘法运算越有效。 曲线标量乘中，当因此，在椭圆 I M比较大时，该算 法是一种 比较 计算的值 S M 有效的改进方法。 5. 致谢 在此，非常感谢我的导师周梦教授在论文构思和 书写的过程中给予指导，感谢国家自然科学基金 (1087101 7)、北京市自然科学基金(102026)的资助和 Table 1. The cost of different operations 表1. 不同运算的 计算方法 I I/M 逐次计算 2 2 4 3P 10.6 逐次计算 4 4 9P 直接计算 1 1 直接计算 1 4 13 8 2 30 9.47 逐次计算 6 6 12 直接计算 1 20 46 9.04 3 直接计算 1 8k – 4 16k 27P 逐次计算 8 8 16 4P 直接计算1 28 62 8.86 逐次计算 2k 2k 4k 3kP – 2 (16.8k – 5.2)/(2k – 1) Copyright © 2012 Hanspub 30  3n GF 椭圆曲线快速算法研究 Copyright © 2012 Hanspub 31 支持，同时 给予转载 和引用权的资料、文献、研究思想和设想的所有者谨 致谢意。 参考文献 (References) [1] N. Koblitz. Ellipticurethematics of Com- tion, 1987)20 [2] Mif etic es yptograph s, Ed., CRYPTO 1985. LNCS, Vol. 218. Heidelberg: r, 1986: 417-428. [3] 李超. 特征为 3的有限域上用于密码体制的椭圆曲线[J]. 通 信保密, 1994, 58(2): 46-49. , et al. Field inversion and point on Computers, 2004, 53(8): 对所有提供给我指导和帮助者、 c 7, 48(17ve cryptosyst : 203-ms. Ma puta V. S. 9. ller. Uses ollipcurvin cry. In: H. C. 算机 William Springe [4] K. Fong, D. Hankerson, J. Lopez halving revisited. IEEE Transactions 1047-1059. [5] M. Ciet, K. Lauter, M. Joye and P. L. Montgomery. Trading inversions for multiplications in elliptic curve cryptography. De- signs, Codes and Cryptography, 2006, 39(2): 189-206. [6] 殷新春, 候红祥, 谢立. 基于双基数的快速标量乘算法[J]. 计 3科学, 2008, 5(6): 186-189, 195. |