基于模糊控制器的w2MOF快速标量乘算法

李超群 吴向前

基于模糊控制器的w2MOF快速标量乘算法

李超群 吴向前

(新疆大学电气工程学院 新疆 乌鲁木齐 830000)

椭圆曲线密码体制中基点的标量乘是最耗时的一种操作，通过预计算的方式可以有效地提高其效率。借助于更灵活且高效的2MOF表示形式，在此基础上利用滑动窗口技术，结合混合坐标下直接计算2kQ+P的计算方式，对w2MOF算法进行改进。对于滑动窗口技术下最优窗口宽度的选择，采用预先设计好的模糊控制器做出决策。根据目前常用的两种模糊推理系统，模糊控制器选择了Mamdani模型。实验结果分析，结合模糊控制器与优化的w2MOF算法，平均效率大约提高11.7%，而且比基于wNAF算法的文献[1]中在曲线NIST-B163上，最优窗口w=5下减少了19次点加运算量。

椭圆曲线密码体制 w2MOF 混合坐标 滑动窗口 模糊控制器

0 引 言

自1985年Koblitz[1]和Miller[2]各自提出椭圆曲线密码体制(ECC) 以来，与其他目前常用的公钥密码系统比较起来，比如RSA密码系统，基于离散对数的密码系统等，ECC具有更快的密钥交换与签名速度。此外，在同等安全强度下，ECC需要更小的宽带，密钥尺寸以及更快的运算速度。椭圆曲线密码最基本的运算是基于倍运算与加运算的，而这两种运算又构成了域运算中的平方，加法与求逆。kP是椭圆曲线密码体制中最主要的运算，而提高标量乘效率的方法主要从两个方面去着手，一是研究k的有效表示，二是研究椭圆曲线标量乘的底乘域快速算法[3]。

提高k的有效表示，主要是围绕减小其表示长度，平均汉明权重去优化的。k的最古老的表现形式是不带符号的二进制串以及带符号的NAF。文献[4]提出带符号二进制串另一种表现形式2MOF，它具有与NAF相同的长度与平均汉明权重，但是它比NAF更具有灵活性，既可以从右向左扫描，也可以从左向右扫描二进制串，而且它在转换过程中不需要求余与除法，文献[5]提出了补数编码的形式，但比文献[4]提出的2MOF形式平均汉明权重大，适合于硬件坏境。在存储空间容许的范围内，利用滑动窗口技术，通过预计算的方式可以提高标量乘效率，而最优窗口宽度的选择决定了预计算量与点加运算量。文献[6]提出了基于wNAF带预计算的标量乘法，文献[7]提出了利用模糊控制器的思想，通过预先设计的模糊推理系统决定最优的窗口宽度，并在补数编码的表示形式上实行窗口技术。文献[8]中通过优化其规则库，在NAF上实行窗口技术。另一种提高标量乘效率的方式就是在底层域结合坐标变换，文献[9]中给出了混合坐标系下的2kQ+P算法，效率比传统的倍乘与点加更高。

本文结合文献[8]所提出的模糊控制器的思想，通过优化规则库得到其最优窗口宽度，再在滑动窗口技术上的w2MOF上结合文献[9]所提出的快速2kQ+P标量乘进行运算。实验结果表明，标量乘效率得到了较大提高。

1 椭圆曲线介绍

1.1 椭圆曲线定义

定义1 定义在域K上的 Weierstrass 方程为[10]：

E:y2+a1xy+a3y=x3+a2x2+a4x+a6

(1)

其中：a1,a2,a3,a4,a6∈K,K为有限域，称E是域K上的椭圆曲线。在实际中，式(1)可以利用相容性变换进行简化。当char(K)=2时，若a1≠0 ，则E可以简化为：

y2+xy=x3+ax2+b

(2)

其中：a,b∈K,Δ=b≠0 。

当char(K)≠2,3时，E可以简化为：

y2=x3+ax+b

(3)

其中：a,b∈K,Δ=-16(4a3+27b4)≠0 。本文基于式(3)的情形进行讨论。

1.2 椭圆曲线的运算法则

E(K)表示满足于式(3)E上的点P=(x,y)∈K2的集合(外加无穷远点O)。令P1=(x1,y1),P2=(x2,y2)为仿射坐标系下的点，-P1=(x1,-y1),则：

当P1≠±P2时：

x3= λ12-x1-x2

(4)

y3=(x1-x3)λ1-y1

(5)

当P1=P2时：

x3= λ22-2x1

(6)

y3=(x1-x3)λ2-y1

(7)

其中P3=P1+P2=(x3,y3)为上述两点的点加或点倍，λ1=(y2-y1)/(x2-x1),λ2= (3x12+ a)/2y1。

1.3 椭圆曲线的标量乘

标量乘可以被定义为重复的加法获得：

式中，P是椭圆曲线上的一个点，k∈[1,N-1]为正整数，N为点P的阶。在整个ECC体系中，标量乘的效率高低决定了能否将其应用到实际场合中去。对标量乘中所涉及到点加与倍点运算，用M、I、S分别表示域K上的乘法、求逆、平方运算，A、J、Jm分别代表仿射坐标、雅可比坐标、优化的雅可比坐标，不同坐标下点加与倍点的时间消耗如表1所示。由表1可知，对于求逆运算时间消耗大的解决方法可以转化为其他坐标系下去运算，同一坐标系下的点加与倍点运算量也有差异，比如在仿射坐标下点加运算就快于倍点运算，而在其他坐标系下倍点快于点加。平均情况下，采用J+A=J进行点加运算，2J=J进行倍点运算是提升标量乘法效率的较佳组合。

表1 点加、倍点运算时间消耗[11]

提高标量乘的效率的关键因素首先在k的表示上，如果只是对kP进行重复的点加，那么我们需要(k-1)次点加运算。如果将k表示为如下二进制形式：

其中ki∈{0,1}， 假设k=39=(100111)2，那么运算量在仿射坐标下由38S+76M+38I降为13S+16M+8I。由上例可知，将k表示成二进制串结合倍点与点加效率更高，并且串l的长度决定倍点的运算量，串l中非‘0’位决定点加的运算量。

2 优化的w2MOF标量乘算法

2.1 k的有效表示

由于标量乘运算中加法与减法具有同等的运算量[6]，所以近年来对k的带符号二进制表示成为研究的热点之一，旨在减少k的二进制表示中的非零位数量。

算法1 二进制串转变为NAF[8]

输入：(el-1,el-2,…,e0)2

输出：(sl,sl-1,…,s0)NAF

1: k0←0;

2: for i=0 to (l-1) do

3: k(i+1)←[(ei+ki+e(i+1))/2];

4: si←ei+ki-2ki+1;

5: end for;

6： return(sl,sl-1,…,s0)

由NAF表示的二进制形式平均汉明权重可以减少为(l/3)，但是倍乘数量还是与二进制形式相同。

2MOF表示法更具有灵活性[4]，使得标量的转换既可以从右向左进行，也可以从左向右进行，并且它的表示与NAF具有相同的平均汉明重量和表示长度，其转换过程算法2所示。

算法2 二进制串转变为2MOF[4]

输入：(el-1,el-2,…,e0)2

输出：(sl,sl-1,…,s0)2MOF

1: e-1←0;

2: i←c+1 for the 1 argest c with dc≠0;

3: sl←0;sl-1←0;…;s0←0;

4: while i≥1 do

5: if ei-1=eithen

6： si←0;i←i-1;

7: else{ei-1≠ei}

8: si←-ei+ei-2;si-1←-ei-2+ei-1;i←i-2;

9: if i=0 then

10: s0←-e0;

11: return(sl,sl-1,…,s0)

2MOF方法相对于NAF方法来说更优越，不仅转换过程不需要求模、除法运算，而且平均移动次数也比NAF少。

2.2 基于滑动窗口技术的w2MOF标量乘算法

算法3 基于滑动窗口技术的w2MOF标量乘

输入：基点P，整数k，窗口宽度-w

输出：Q=kP

1. Q=O,计算k=(el-1,el-2,…,e0)2;

2. 利用算法2计算2MOF(k);

3. 计算[n]P,n=(1，3，5，…,(2(2w-(-1)w)/3-1));

4. j=l-1;

5. while j≥0 do

6. if(sj==0)

7. Q←2Q,N←0,j←j-1;end if;

8. else

9. i←maximum(j-w+1,0);

10. while si==0 do

11. i←i+1;

12. end while;

13. for c=1 to (j-i+1) do

14. c=c+1 and Q←2Q;

15. end for;

16. N←(sj…si)2MOF;j←i-1;

17. end else;

18. if(N≥0) Q←Q+[N]P; end if;

19. else Q←Q-[N]P;end else;

20. end while;

21. return (Q)

算法3中期望的运行时间包括预计算时间和在线主计算时间，分别近似为[6]：

1D+((2w-(-1)w)/3-1)A

(8)

(l-1)D+(l/(w+v(w))-1)A

(9)

式中v(w)=4/3-(-1)w/(3·2w-2)代表‘0’在窗口之间移动的平均长度；A表示点加运算，D表示倍点运算。

2.3 优化的滑动窗口w2MOF标量乘算法

根据算法3可以对其进行改进，也就是在扫描到连续个零位的时候对其进行统计，然后借助文献[9]给出的混合坐标下直接计算2kQ+P的算法进行优化。

算法4 优化的滑动窗口w2MOF标量乘算法

输入： 基点P，整数k，窗口宽度-w

输出： Q=kP

1. 算法3步骤1～步骤4；

2. while j≥0 do

3. n=0;

4. while(sj==0 and j≥0)

5. n←n+1,N←0,j←j-1;

6. end while;

7. if j≥0 then

8. i←maximum(j-w+1,0);

9. while si==0 do

10. i←i+1;

11. end while;

12. N←(sj…si)2MOF;

13. end if;

14. if(N≥0)Q←2n+j-i+1Q+[N]P;end if;

15. else Q←2n+j-i+1Q-[N]P;end else;

16. j←i-1;

17. end while;

18. return (Q)

算法4中在线主运算时间的标量乘法可以采用文献[9]直接给出的2kQ+P算法优化，一次计算2kQ+P的时间消耗为(7.2k+11.4)M,平均情况下算法4的时间消耗近似为[9]：

33.6M+32.8((2w-(-1)w)/3-1)M+(l/(w+

v(w))-1)[7.2(w+v(w)-1)+11.4]M

(10)

2.4 基于模糊控制器的最佳窗口宽度

由式(8)可以发现滑动窗口技术运算量的花费依赖于窗口的大小w，而窗口宽度最优的选择既可以减少ECC运算当中的点加操作，也可以减轻系统预计算的负担。根据表2可以推出随着窗口宽度的加大，预计算量也在逐增，点加和倍乘运算量在减少，变化率最大的是预计算量与点加量，所以需要在预计算量与点加量之间有一个折中点，也就是需要根据自身的环境选择一个最佳窗口。文献[8]提出了利用模糊控制器的思想根据规则库自动地选择最优的窗口宽度，本文在此基础上进行扩展。

表2 基于滑动窗口方法的不同窗口宽度比较

对于一个模糊控制器而言，主要由输入、模糊推理系统、输出三部分组成。在本文中，输入由预计算量和点加量组成，并且它们都具有三种状态(低，中，高)，输出为窗口大小变化趋势，也包含三种状态(减小，保持，增大)。模糊推理系统是一系列将输入转变为输出的规则库的集合，主要有Mamdani和Takagi-Sugeno两种常用模型，本文中选择前者。推理系统的规则如表3所示，规则前可以赋予一定的权重，默认为1。

表3 模糊控制器的规则库

整个模糊控制系统的流程方框图由图1所示。根据图所示，首先需要为窗口设置个初始值，根据标量k的2MOF编码利用窗口技术扫描得到所需的预计算量和点加运算量。将获得的两变量输入到双输入单输出的模糊推理系统，模糊推理系统首先将输入量模糊化，再将模糊化量通过规则库获得模糊输出，最后通过去模糊获得窗口变化的趋势。

图1 模糊控制系统工作流程

3 实验结果与分析

为了将改进的基于滑动窗口技术的w2MOF算法与模糊控制器结合起来，本文通过在eclipse环境下利用Java语言随机生成NIST推荐的椭圆曲线分别在k为160、233、283、384 bit下的2MOF表示形式，并将其存入txt文档。在Matlab环境下，通过自带的工具箱函数读入txt文档，经过相应地处理输入到设计好的规则库的模糊推理系统，最后得到该环境下最优的窗口宽度。表4列出了不同标量k下的最优窗口宽度及相应的预计算数与点加数。

表4 不同标量k下的最优窗口宽度

为便于比较，可按文献[9]的假设：1S=0.8 M，1I=30 M。由表4可知，根据所设计的模糊推理系统计算出k=160 bit下的最优窗口宽度为5，点加运算量为20，预计算量为10，与文献[8]进行比较，在同样的标量k下，基于wNAF算法在窗口宽度为5时，所需的点加运算量为39，本文提出的算法减少了19次点加运算量，假设在仿射坐标下，那么由表1可知减少的运算量为623.2 M。基于滑动窗口技术的算法3与算法4中的预计算阶段都采用仿射坐标下的倍乘与点加运算，而在主计算阶段算法3中倍乘与点加采用混合坐标下的最优计算方式如表1所示，算法4采用混合坐标下直接计算2kQ+P方式。将算法3、算法4应用于表4不同标量k下的最优窗口宽度中，其时间消耗如表5所示。

表5 算法3与算法4的运算量比较

根据表5可知，随着k值的增大，两种算法的运算量都明显增加。在曲线NIST B-163上，算法4比算法3效率提高约12%，在曲线NIST B-233上，算法4比算法3效率提高12.2%,在曲线NIST B-283上，算法4比算法3效率提高12.3%,在曲线NIST B-384上，算法4比算法3效率提高10.6%。

4 结 语

本文首先分析了标量k的有效表示中具有相同长度和平均汉明权重的主流NAF和2MOF算法，将更有灵活性的2MOF算法与带预计算的滑动窗口技术结合，并利用混合坐标下直接计算2kQ+P的方式提高标量乘的效率。带预计算的滑动窗口技术需要根据自身环境首先确定最优的窗口宽度，提出了利用模糊控制器通过预先设计的规则库来确定窗口宽度的大小。将模糊控制器与优化的w2MOF算法结合，实验结果表明，算法4比算法3平均效率提高11.7%，并且与文献[8]基于wNAF算法的滑动窗口技术在同样的窗口下减少了19次点加运算量。

[1] Koblitz N.Elliptic curve cryptosystems[J].Mathematics of computation,1987,48(177):203-209.

[2] Miller V S.Use of elliptic curves in cryptography[C]//Advances in Cryptology—CRYPTO’85 Proceedings. Springer Berlin Heidelberg,1986:417-426.

[3] 赖忠喜,张占军,陶东娅.椭圆曲线底层域快速算法的研究[J].计算机工程与应用,2014,50(3):67-70.

[4] Okeya K,Schmidt-Samoa K,Spahn C,et al.Signed binary representations revisited[C]//Advances in Cryptology-CRYPTO 2004.Springer Berlin Heidelberg,2004:123-139.

[5] Balasubramaniam P,Karthikeyan E.Elliptic curve scalar multiplication algorithm using complementary recoding[J].Applied mathematics and computation,2007,190(1):51-56.

[6] Hankerson D,Vanstone S,Menezes A J.Guide to elliptic curve cryptography[M].Springer,2004.

[7] Huang X,Sharma D.Fuzzy controlling window for elliptic curve cryptography in wireless networks[C]//Computer Sciences and Convergence Information Technology (ICCIT),2010 5th International Conference on.IEEE,2010:521-526.

[8] Kodali R K,Budwal H S,Patel K,et al.Fuzzy controlled scalar multiplication for ECC[C]//TENCON Spring Conference,2013 IEEE.IEEE,2013:352-356.

[9] 李忠,彭代渊.基于滑动窗口技术的快速标量乘法[J].计算机科学,2012,39(6A):54-56,64.

[10] 周梦,周海波.椭圆曲线快速点乘算法优化[J].计算机应用研究,2012,29(8):3056-3058.

[11] Mahdavi R,Saiadian A.Efficient scalar multiplications for elliptic curve cryptosystems using mixed coordinates strategy and direct computations[M].Cryptology and Network Security.Springer Berlin Heidelberg,2010:184-198.

FAST W2MOF SCALAR MULTIPLICATION BASED ON FUZZY CONTROLLER

Li Chaoqun Wu Xiangqian

(SchoolofElectricalEngineering,XinjiangUniversity,Urumqi830000,Xinjiang,China)

Scalar multiplication of basis points in elliptic curve cryptosystems is one of the most time-consuming operations, but the efficiency can be improved by the way of pre-computation. By means of more flexible and efficient form of 2MOF representation, and using sliding window technology on this basis, we modified the w2MOF algorithm in combination with the computation mode of directly calculating 2kQ+P on mixed coordinates. For the selection of optimal window width using sliding window technology, we used the pre-designed fuzzy controller to make decision. According to commonly used two kinds of fuzzy inference system, the fuzzy controller chose Mamdani model. Analysis of experimental results showed that with the combination of fuzzy controller and optimised w2MOF algorithm, the average efficiency improved about 11.7%, and compared with the wNAF algorithm-based literature[1], on elliptic curve NIST-B163 and under the optimal window w=5, the amount of point adding operation reduced 19 times.

Elliptic curve cryptosystem w2MOF Mixed coordinates Sliding window Fuzzy controller

2014-12-06。李超群，硕士生，主研领域：公钥密码学。吴向前，教授。

TP309.7

A

10.3969/j.issn.1000-386x.2016.04.075