改进的基于整数拆分形式标量乘快速算法

张 亮

(郑州工业应用技术学院，河南 郑州 451150)

基础理论 doi:10.3969/j.issn.1673-5692.2016.05.007

改进的基于整数拆分形式标量乘快速算法

张 亮

(郑州工业应用技术学院，河南 郑州 451150)

标量乘运算是椭圆曲线密码的关键运算。为有效提高椭圆曲线密码标量乘法的运算效率，给出了一种改进的带符号整数拆分形式标量乘快速算法。首先通过对标量进行带符号的整数拆分形式编码，然后将标量乘运算转化为由一组椭圆曲线上的点累加和形式进行计算，同时在预计算阶段采用更为高效的折半运算代替倍点运算。算法性能分析的结果表明：与已有的基于整数拆分形式标量乘快速算法相比，新算法的能够大幅提升运算效率，在应用椭圆曲线密码的各种系统中具有较好的实际应用价值。

椭圆曲线密码；标量乘法；折半运算；整数拆分形式

0 引 言

椭圆曲线密码体制(Elliptic Curve Cryptogram, ECC)是于1985年Koblitz N与Miller V最早提出来的。ECC是将离散对数有限循环群替换成有限域上的椭圆曲线有限群所构造的密码体制，算法的安全性是建立在椭圆曲线对数问题的难解性之上的，同其余传统的密码算法相比，具备所需密钥长度更短，存储空间更小等优点[1-2]。其核心运算主要是计算在椭圆曲线群上的标量乘法运算，它的运算速度决定着密码系统整体执行效率的关键。国内外的研究学者在椭圆曲线密码的标量乘法运算方面做出了许多建设性的工作，为逐步提高椭圆曲线密码的运算效率，加快推进椭圆曲线密码实际应用做了大量贡献。采用m_ary算法是椭圆曲线密码标量乘法运算的传统运算方式，主要是通过多次使用点加操作与倍点操作来计算[3]。近年来，其它一些标量乘快速算法也被较多的提出来[4-5]。其中，文献[6]中石润华等人提出了一种基于整数拆分的标量乘快速算法，并结合预计算的方法，能有效提升标量乘法的计算效率。文献[7]中Kundsen E等人则提出了一种基于折半运算的椭圆曲线密码的快速标量乘算法，其中所提算法采用的折半运算比倍点操作能够提升大约一倍的效率。

通过分析基于整数拆分形式快速标量乘法的特性，可以将整数拆分形式转换成带符号的形式，从而能有效减少拆分次数。同时由于折半运算的效率要优于倍点运算，因而在标量乘算法的预计算阶段，可以用更加高效折半运算操作替代标量乘法运算中的倍点操作来进行计算，从而给出一种改进的基于带符号整数拆分形式标量乘快速算法(Improved fast scalar multiplication based on Signed Integer Splitting form，ISIS)，该算法可以有效提升椭圆曲线密码标量乘的计算效率。同传统的基于整数拆分形式标量乘算法相比，给出的改进算法能有效提升标量乘法的运算效率。

1 背景知识介绍

1.1 带符号整数拆分形式表示

对于任一正整数都可以由一组长度有限的数列(f(1),f(2),…,f(n))表示，只需满足这个数列的和不大于这个整数。文献[8]从具体的数学模型中抽象出了数列f(n)的定义，并采用归纳法给出了该定理正确性的证明。假设存在一组无穷数列{f(1),f(2),…,f(n),…}，则有：

(1)

其中，n可以为任意的正整数。则称式(1)为拆分数列。

(2)

其中，ai表示拆分系数，则称式(2)正整数k的整数拆分形式，记为SIS(k)。

整数k基于带符号整数拆分形式的编码算法过程如下面算法1所示：

算法1 整数k带符号整数拆分形式的编码算法

输入：n,k；

输出：SIS(k)。

1.对于i从1到n，重复执行：ai=0；

2.令s=1；

3.如果k>0，则执行：

3.1 如果k=1，则ai=s,k=0；

3.2 否则i=2；

3.3 如果(!(f(i-1)

3.3.1 如果k>((f(i)-1)/2)，则执行k=f(i)-k，ai=s，s=-s；

3.3.2 否则k=k-f(i-1),ai-1=s；

4.返回SIS(k)=(an,an-1,…,a1)。

1.2 折半运算

假定在二进制域F2m上定义了一个椭圆曲线E，如式(3)所示：

E:y2+xy=x3+ax+b,a,b∈F2m,b≠0

(3)

在椭圆曲线E上定义一个点P=(x1,y1)，而且这个点满足P∈E(F2m)，并且有P≠-P。则在仿射坐标系下计算倍点操作运算2P=(x3,y3)，其中坐标值如式(4)所示：

(4)

由文献[9]所给定理可以看出，在一个椭圆曲线上能够定义倍点运算的一种逆操作运算，如以下定理1所示：

定理1(折半运算)假定在椭圆曲线E上有一个n阶子群{G}(n是奇数)，倍点操作和折半操作在子群{G}上自同构。则对任一点Q∈{G}，都将存在一个点P∈{G}，满足Q=2P。

椭圆曲线上定义倍点运算的逆操作运算称为折半运算，其是表示在二进制域F2m中，当Q=(x3,y3)为定点时，可计算出定义在椭圆曲线E上的点P=(x1,y1)。即根据式(4)计算出μ,x1,y1，计算公式如式(5)所示：

(5)

椭圆曲线上的折半运算操作如算法2所示[10]：

算法2 椭圆曲线折半运算操作算法

输入：Q=(x3,y3)；

输出：P=1/2Q=(x1,y1)。

1.根据式μ2+μ+a=x3求解μ；

2.计算η=y3-(μ+1)x3；

4.返回值(x1,y1)。

2 新算法设计

所给的基于折半运算和带符号整数拆分形式的标量乘快速算法，其基本思想是：首先通过将一个正整数标量拆分成以类基(f(1),f(2),…,f(n))相加的表示形式，且拆分系数为{-1,0,1}中之一，然后标量乘中的倍点运算用更高效的折半运算代替，同时结合预计算的方法，将标量乘法运算转化成为计算椭圆曲线上一组点的累加和的形式。则基于ISIS标量乘法运算如式(6)所示：

=a1·f(1)P+a2·f(2)P+…+an·f(n)P

=a1·PH1+a2·PH2+…+an·PHn

(6)

其中，mi为拆分数列的折半运算编码长度，mmax为最大长度。如果拆分数列f(i)的折半运算编码长度不足mmax位时，可将剩余的(ji-m)位全部补充为0。PHi为采用折半运算的预计算表。下面给出基于折半运算和带符号整数拆分形式标量乘快速算法的具体执行过程：

第一步：计算出已知标量k的带符号整数拆分编码SIS(k)=(an,an-1,…,a1)；

第二步：将折半运算应用在拆分数列f(i)的预计算构造中，得到预计算表PHi；

第三步：根据查找预计算表，将标量乘法运算kP转化为计算一组椭圆曲线上的点的累加和的形式，则可得返回结果。

则基于折半运算和带符号整数拆分形式的标量乘快速算法如算法3所示：

算法3 基于ISIS的标量乘快速算法

输入：k,P；

输出：Q=kP。

1.计算出已知标量k的带符号整数拆分表示形式SIS(k)=(an,an-1,…,a1)；

2.构造预计算表PHi；

3.令Q=O，其中O无穷远点；

4.对于i从1到n，重复执行：

4.1 如果ai=1，则Q=Q+PHi；

4.2 如果ai=-1，则Q=Q-PHi；

5.返回Q。

其中，预计算表PHi固定且可预先存储在应用系统中。则构造预计算表的具体过程如算法4所示：

算法4 预计算表PHi的构造算法

输入：n,P；

输出：预计算表PHi。

1.令Q=O；

2.对于i从1到mi，重复执行：

2.1R=Q/2；

2.2PHi=R+P；

2.3Q=PHi+Q；

3.返回PHi。

3 算法性能分析

算法3中，步骤2采用算法4中基于折半运算的预计算表构造算法，其运算量为mavg(H+2A)，其中mavg为拆分数列f(i)基于折半运算的平均编码长度。步骤4的主循环运算中，令navg为平均执行循环操作的次数，且有navg≈2/3·n，则主循环运算所需运算量为navgA。因此算法3所需总的运算量为mavgH+(navg+2mavg)A。令p为传统的整数拆分编码长度，pavg为传统基于整数拆分标量乘算法平均执行循环操作次数，lavg为拆分数列的平均二进制编码长度，则传统基于整数拆分形式的标量乘算法所需总运算量为lavgD+(pavg+2lavg)A。令t为传统的整数拆分编码长度，tavg为带符号的基于整数拆分标量乘算法平均执行循环操作次数，savg为带符号拆分数列的平均二进制编码长度，则带符号的基于整数拆分形式的标量乘算法所需总运算量为savgD+(tavg+2savg)A。其中，H表示折半运算，D表示倍点运算，A表示点加运算。表1给出了算法3与传统基于整数拆分形式标量乘算法(ISF)以及基于带符号的整数拆分形式标量乘算法(SISF)的运算量比较。

表1 算法3与传统ISF算法及SISF算法运算量比较

由表2可知，与传统基于整数拆分表示形式标量乘算法相比，预计算的运算效率提升了约39.65%～46.89%，主循环的运算效率提升了约29.04%。与基于带符号的整数拆分表示形式标量乘算法相比，预计算的运算效率提升了约30.83%～39.13%，主循环的运算效率保持不变，这事因为算法3采用的是带符号整数拆分形式编码，与基于带符号的整数拆分表示形式标量乘算法的编码长度相同，且类基拆分数列及符号相同，则有相同的拆分数列二进制编码长度。综上所述，则可知算法3总的计算效率与已有的基于整数拆分表示形式标量乘相比提升了大约22.24%～41.76%。这是因为通过将标量采用带符号的整数拆分形式表示，可以相对减少标量的编码长度，从而可以提升预计算阶段和主循环阶段的运算效率，同时在预计算阶段通过采用折半运算替代倍点运算，可以进一步提高标量乘法的运算效率，而由于主循环运算阶段只包含点加操作运算，不需应用折半运算。因此所给算法3能有效提升标量乘运算的效率，可以很好地满足各种椭圆曲线密码系统的需求，特别是对存储空间和时间都比较高但资源却受限的模块或系统之中。

表2 不同坐标系下算法3与传统ISF算法及SISF算法的执行效率比较

4 结 语

椭圆曲线密码中的标量乘运算主要是反复进行点加运算和倍点运算，是提升椭圆曲线密码算法效率的关键。通过分析标量的整数拆分表示形式可知，采用带符号的整数拆分编码方法和折半运算，利用折半运算替代倍点运算，通过计算基于折半运算的预计算表，因为折半运算同倍点运算相比，其运算效率较高，因而可以有效提高标量乘的运算效率，所给算法在椭圆曲线密码标量乘算法中能够大幅提高运算效率。由算法性能分析可知，所给算法能够较好地用于各类密码应用模块中，有较好的研究意义与实际应用价值。

[1] Antao S, Bajard J, Sousa L.Elliptic curve point multiplication on gpus [C]//Proceedings of the 21th IEEE Int.Conf.on Application-Specific Systems, Architectures and Processors, 2010:192-199.

[2] 艾树峰．二元域乘法器的研究[J]．中国电子科学研究院学报，2009，4(3)：320-322．

[3] Purohit G N, Rawat S A.Fast scalar multiplication in ECC using the multi base number system [J].International Journal of Computer Science Issues, 2011, 8(1):131-137.

[4] 王正义，赵俊阁．ECC抗功率分析攻击的等功耗编码算法[J]．计算机工程，2012，38(10)：111-113．

[5] WU Tao, LIU Li-tian.Elliptic curve point multiplication by generalized mersenne numbers[J].Journal of Electronic Science and Technology, 2012, 10(3):199-208.

[6] 石润华，钟诚．基于整数拆分的椭圆曲线密码体制上的快速点乘算法[J]．计算机工程与科学，2005，27(5)：66-67.

[7] Knudsen E.Elliptic scalar multiplication using point halving [C]//Advances in Cryptology-ASIACRYPT’99.New Youk:Springer-Verlag, 1999, 1716(274):135-149.

[8] Morain F, Olivos J.Speeding up the computations on an elliptic curve using addition-subtraction chains [J].Theoretical Informatics and Applications, 1990, 24(6):120-126.

[9] Purohit G N, Rawat S A, Kumar M.Elliptic curve point multiplication using MBNR and point halving [J].International Journal of Advanced Networking and Applications, 2012, 3(5):1329-1337．

[10]王玉玺，张串绒，张柄虹．一种改进的固定基点标量乘快速算法[J]．计算机科学，2013，40(10)：135-138.

[11]Fong K, Hankerson D, Lopez J, et al.Field inversion and point halving revisited[J].IEEE Transactions on Computers, 2004, 53(8):1047-1059．

[12]Barua R, Pandey S K, Pankaj R.Efficient window-based scalar multiplication on elliptic curves using double- base number system [C]//Lecture Notes in Computer Science, Berlin:Springer-Verlag, 2007:351-360．

张 亮(1983—)，男，河南人，讲师，主要研究方向为计算机网络及安全。

E-mail:wangzy7134@163.com

Improved Fast Scalar Multiplication Algorithm Based on Signed Integer Splitting Form

ZHANG Liang

(Zhengzhou University of industrial technology, Henan Zhengzhou 451150, China)

The scalar multiplication is the key operation in elliptic curve cryptography.To improve the efficiency of scalar multiplication effectively, a novel improved fast scalar multiplication algorithm based on signed integer splitting algorithm for elliptic curve cryptography is proposed.Firstly, the scalar is coded by signed integer splitting form, and then the scalar multiplication is transformed into a accumulate sum form by a group of points in elliptic curve.Meanwhile, point halving which higher efficient is used to replace point doubling on the stage of pre-computation.The results of performance analysis show that the proposed scheme could improve the operation efficient of scalar multiplication greatly for elliptic curve cryptography by comparing with existed scalar multiplication algorithm based on integer splitting.Hence the proposed scheme could has better practical value in different systems which applying the elliptic curve cryptography.

ellipse curve cryptography；scalar multiplication；point halving；integer splitting form

2015-12-01

2016-03-01

河南省基础与前沿技术研究计划项目(142300410283)；河南省软科学研究计划项目(142400410179)；河南省教育厅科学技术研究重点项目(12B520063，14B520065)；河南省高等学校青年骨干教师资助计划项目(2013GGJS-230)

：A

1673-5692(2016)05-490-05