一种低复杂度的改进wNAF标量乘算法

赵石磊，杨晓秋，刘志伟，于 斌，黄 海

（哈尔滨理工大学计算机科学与技术学院，黑龙江哈尔滨 150080）

1 引言

椭圆曲线密码体制的核心运算主要是椭圆曲线群上的标量乘法，它的运算速度决定着密码系统整体执行效率［1］. 一般来说，标量乘算法可分为两种：无预计算算法和有预计算算法. 无预计算算法包括二进制算法（Double and Add，D&A）［2］、非邻接表示算法（Non-Adjacent Form，NAF）［3］、多基链表算法（Double-Base Chain，DBC）［4］和相反形式算法（Mutual Opposite Form，MOF）［5］等，这些算法大都存在着计算复杂度过高的问题. 为降低计算复杂度，学者们提出了有预计算算法，如滑动窗口算法［6］、窗口非相邻算法（window width-Non-Adjacent Form，wNAF）［7］、加法链算法［8］、利用素数代替奇数进行预计算并通过构建多基链来弥补素数与奇数之间的差值算法［9］、带门限的动态窗口的NAF 标量乘法［10］等. 文献［8］所提加法链算法相比较其他加法链算法计算复杂度降低了4%～18%. 文献［9］的计算复杂度相比于wNAF 优化了28.37%. 在文献［10］中，带门限的动态窗口的NAF 标量乘法的预计算量仅为基于Moller 碎片窗口技术的标量乘法的30%、基于固定窗口改进后的NAF 标量乘法的25%，其预计算利用率比基于Moller 碎片窗口技术的标量乘法提高了15%左右，比基于固定窗口改进后的NAF标量乘法提高了12%左右. 文献［11］则提出了Alternate-Zeckendorf 表示算法，可以用加法链序列表示任何标量k，此算法比其他算法的成本至少降低12.7%. 文献［12］提出了基于窗口的NAF 算法，当n={192，224，256，384}时，预计算效率提高了26.35%，当n=521时，预计算效率提高33.59%.

以上算法虽然取得了较好的结果，能够有效降低标量k的汉明重量，减少点加操作的次数，降低标量乘的计算复杂度，但是仍然存在着不适用于窗口宽度较大、使用寄存器较多、预计算量过大等问题. 针对以上问题，本文设计了一种低复杂度的改进wNAF 算法，首先在预计算阶段用2nP替换(2h-1)P（wNAF 算法中奇数与基点P的乘积），再用2nP构造加法链来补偿2nP与(2h-1)P之间的差值. 然后，为解决随着窗口宽度的增大，2nP与(2h-1)P之间差值过大的问题，采用有符号的wNAF 算法将标量k的二进制链转换成有符号的wNAF 链，能将该差值范围缩小为原来的50%，极大地减少了点加次数. 最后，实验结果证明，所设计的算法具有所需寄存器数量少以及计算复杂度低等优点.

2 椭圆曲线标量乘算法分析

2.1 窗口非相邻（wNAF）标量乘

椭圆曲线标量乘法是椭圆曲线密码系统中最关键（也是消耗资源和能量最多）的步骤，是椭圆曲线上一个点P与一个随机的整数k的乘积，即Q=kP=P+P+…+P. 由于在雅可比坐标下，倍点的运算消耗小于点加，因此通常做法是将k进行转换以减少其中点加次数，如wNAF 标量乘算法［13］. wNAF 标量乘算法通过将二进制形式的标量k转化为wNAF 形式，构建一条wNAF 链，即其中ki∈{±1，±3，…，±(2w-1)}，m表示wNAF 链中的非零数字个数，λi是wNAF 链中每个非零数ki所在的位置. 实现标量乘时，通过调用已预计算并存储的点{±P，±3P，…，±(2w-1)P}，其中w是窗口宽度，可极大地减少运算时的计算量.wNAF 的具体实现如算法1所示.

该算法整个过程分成3 个阶段：wNAF 序列生成阶段（步骤1 到步骤12）、预计算阶段（步骤13）和算数运算阶段（算数运算包括点加运算和倍点运算，步骤14到步骤20）.wNAF 是通过降低标量k的汉明权重、减少点加运算来降低算法的复杂度. 假设在wNAF 链{ki}中有非零数字m个，第i个非零数字是ki，λi是wNAF 链中每个ki所在的位置，则有λi-λi-1≥w+1，显然，wNAF 的非零概率为1( )w+1，预计算阶段和算数运算阶段的成本分别为2w-1A+D 和，所以标量乘计算量为，其中A 是点加运算，D 是倍点运算，且有1A=12M+4S，1D=4M+6S［14］以及0.8M=1S［15］（M 是模乘运算，S 是模平方运算）. 然而，wNAF 标量乘算法也存在一定的问题：当窗口宽度增大的时候，预计算点的个数呈指数增长，大大增加了预计算量和所需的寄存器数量.

算法1 带符号的wNAF标量乘算法输入:标量k,基点P,窗口宽度w输出:标量乘结果Q 1)i=0 2) While k ＞0 do 3) If k mod 2=1 then ei=k mod 2w+1;4) If ei ≥2w then ei ⇐ei-2w+1;5) End if 6) k ⇐k-ei;7) Else 8) ei=0;9) End if 10) k ⇐k/2; i ⇐i+1;11)End while 12)return{ki-1，ki-2，…，k1，k0}13)预计算:Pi=iP，i ∈{1，3，5，…，2w-1}14)for i from b-1 to 0 do 15) Q ⇐2Q;16) If ki ≠0 then 17) If ki ＞0 then Q ⇐Q+Pki;18) If ki ＜0 then Q ⇐Q-Pki;19) End 20)End

2.2 加法链标量乘算法

文献［16］进行加法链标量乘运算时，首先构造一条加法链，定义为一个序列v=(v1，v2，…，vl)，其中，v1=1，v2=2，vi=vi-1+vi-2(3 ≤i≤l)，l是加法链的长度，标量k由加法链序列中若干个vi组成，表示成其次，将vi与基点P相乘并存储；最后，只需点加操作即可得到标量乘的最终结果. 加法链标量乘算法如算法2所示.

算法2 加法链标量乘算法输入:标量k,基点P输出:标量乘结果Q 1)通过贪心算法得到k的加法链(v1，v2，…，vl)2)Q ⇐0;3)for i from 1 to l do 4) Q ⇐Q+vi;5)end 6)return Q

如算法2所示，步骤1是得到k的加法链的过程，贪心算法用于每次在加法链中寻找最接近ki的元素vi，然后再利用ki和vi的差值在加法链中找到最接近该差值的vi，进而可以得到标量k的加法链；步骤2～6是计算标量乘的过程，这部分只需要进行点加操作而不需要进行倍点操作即可得到标量乘的结果. 此外，由于生成k的加法链需要用到贪心算法，随着k位数的增加，创建加法链所用的时间也会越长.

3 低计算复杂度的wNAF算法设计

3.1 基于2n p预计算

众所周知，wNAF 算法在预计算阶段将{±P，±3P，…， ±(2w- 1)P}存储起来用于加速标量乘的计算，但随着窗口宽度w的增大，预计算点的个数呈指数增长，使得该算法不适用于窗口宽度较大的情况. 本部分针对该问题，对wNAF 算法进行改进，减少预计算点以降低wNAF算法的标量乘计算复杂度.

由于倍点运算相较于点加运算、3 倍点运算和5 倍点运算需要较少的模乘次数，同时由于2n构成的集合中元素比3n，5n构成的集合中元素更加密集，2n与奇数之间的差值更小，有利于构造差值的加法链. 此外，考虑到在进行算数运算时也需要进行倍点运算，倍点运算结构可以通过控制器控制，反复利用，节省资源. 本文的思路是：在预计算阶段用2n代替生成的wNAF链中的奇数，只预计算并存储2nP. 这种替换的优势在于能够大大减少预计算点的个数且预计算点只需要通过倍点运算即可得到. 例如：当窗口为5时，wNAF 算法需要存储{P，3P，…，31P}，共计16 个点；而本文算法只需要存储{20P，21P，…，25P}，共计6个点. 表1列出了在不同窗口宽度下所需预计算的点及个数.

表1 预计算点及个数

3.2 基于2n p的加法链的差值补偿

由3.1 节 中 可 知，用{20P，21P，…，2nP} 代 替{P，3P，…，(2w-1)P}会产生差值. 例如当窗口宽度为w=5 时，本文预计算点为{20P，21P，…，25P}，wNAF 算法预计算点为{P，3P，…，31P}，若wNAF 链中存在非零数17时，24P与17P最接近，但存在差值P；当wNAF链中存在非零数21 时，24P与21P最接近，存在差值5P；当wNAF链中存在非零数23时，24P与23P最接近，存在差值7P.不同窗口宽度下的预计算点与wNAF 预计算点之间可能存在的差值如表2所示.

由表2 可知，本文预计算与wNAF 预计算之间的差值为奇数，且随着窗口宽度的增加，该差值的最大值也不断增加，当窗口宽度在5～11范围内时，差值的最大值为511P.

表2 本文预计算点与wNAF预计算点之间的差值

由于任意一个标量k都可以用二进制表示并且在预计算阶段已经完成了对2nP的计算和存储，因此2nP与(2h-1)P之间的差值Δ可以通过构造2nP加法链来补偿. 由第2.2 节可知，加法链是将一个大数拆分成若干个小数，在计算时，通过若干个小数相加减得到结果.因此，差值Δ 可以基于加法链的思想由多个2nP相加减得到，即Δ=∑2nP. 例如：在窗口宽度为w=5 时，已知wNAF 链中存在非零数13，且已有预计算点{20P，21P，22P，23P，24P，25P}找到与13P最接近的24P，24P与13P之间的差值为3P，3P则可以表示为22P-20P，最终13P=24P-22P+20P. 此外，根据表2，当窗口宽度为11 时，构造的加法链最长，需要4 次点加运算，例如：差值为299P时，299P的加法链可以构造为299P=28P+25P+23P+21P+20P.

3.3 改进的wNAF标量乘算法

根据第3.1 节和第3.2 节，可以总结出本文的算法：通过算法1生成wNAF链，用2n代替wNAF链中的奇数，在预计算阶段，将2nP预计算出来，在算数运算阶段，通过搜索k链中的非零数值ki，2nP与kiP之间的差值通过构建微小的2nP加法链来实现，最后再通过一系列的点加运算和倍点运算，得到标量乘的最终结果. 改进的wNAF标量乘算法如算法3所示.

算法3 中，步骤1～2 是预计算部分，根据窗口的大小预计算2nP；步骤3～37 是算数运算阶段. 步骤8～10用于寻找与wNAF 链中非零数值最接近的2nP，此时，在查找k链时会分成两种情况，一种是k链中的非零数值小于0 的情况，执行步骤11～22；另一种是k链中的非零数值大于0 的情况，执行步骤23～34. 此外，步骤11～12 以及步骤23～24 用于得到2nP和(2h-1)P之间的差值Δ；步骤14～19 以及步骤26～31 是构造差值Δ 的加法链的过程，先找到与Δ 接近的2nP，计算它们的差值，再找到与该差值接近的2nP，以此类推，迭代找到构成Δ的2nP加法链add1，最终得到标量乘结果.

算法3 改进的wNAF的标量乘算法输入:标量k,基点P,窗口宽度w输出:标量乘结果Q 1)预计算:2) Pi=2iP，i ∈{0，1，2，…，w}3)标量乘计算:4) Q ⇐0;add1 ⇐0;5) for i from b-1 to 0 do 6) Q ⇐2Q;7) add1 ⇐0;8) If ki ≠0 then 9) s ⇐Findnearst(|kiP|) //找到最接近|kiP|的2nP;10) add ⇐Findnearst(|kiP|);11) If ki ＜0 12) a ⇐kiP+s;13) j ⇐0;14) While(a ≠0)15) tj ⇐Findnearst(|a|);16) a ⇐|a|-tj 17) j ⇐j+1;18) End 19) add1 ⇐∑tj;20) If a ≥0 then add ⇐add1-add;21) Else add ⇐-add-add1;22) End 23) If ki ＞0 24) a ⇐kiP-s;25) j ⇐0;26) While(a ≠0)27) tj ⇐Findnearst(|a|);28) a ⇐|a|-tj 29) j ⇐j+1;30) End 31) add1 ⇐∑tj;32) If a ≥0 then add ⇐add-add1;33) Else add ⇐-add-add1 34) End 35) Q ⇐Q+add;36) End 37) End

3.4 算法计算复杂度分析

结合第3.1 节、第3.2 节、第3.3 节得到的本文算法，下面对算法的复杂度进行分析.

预计算部分：计算2nP时，窗口宽度为w，则需要进行w次倍点，例如，当w=5时，预计算点为{20P，21P，…，25P}，需要进行5次倍点，所以预计算的成本为

算数运算部分：设wNAF 链长为n，则需要进行n次倍点操作，由文献［12］可知wNAF 的汉明重量为则k链中一共有个非零数字，需要进行次点加，当窗口宽度w=5 时，在构建2nP与(2h-1)P差值的加法链时，需要额外进行一次点加运算的点的个数占k链中非零数字的1/4，需要额外进行两次点加运算的点的个数占k链中非零数字的3/4，因此需要额外进行次点加运算，一共需要进行次点加运算，并且窗口宽度每增加1，点加次数多增加，算数运算阶段一共所需的成本为

标量乘部分：标量乘成本=预计算成本+算数运算成本，即

通过将1A=12M+4S，1D=4M+6S［14］以及0.8M=1S［15］代入到式（1）、式（2）和式（3）可以得到以模乘次数为标准的预计算计算复杂度、算数运算计算复杂度和标量乘计算复杂度，结果如图1所示.

图1 表示了以模乘次数为标准的本文算法在不同窗口宽度、不同曲线下的计算复杂度曲线. 计算复杂度包括预计算计算复杂度、算数运算计算复杂度和标量乘计算复杂度；曲线包括P256，P384和P521，窗口宽度范围为2～12. 由图1可以看出，对于所有曲线，窗口宽度为11时，标量乘计算复杂度最小；窗口宽度小于5时，标量乘计算复杂度要高于窗口宽度为5时. 而当窗口宽度大于11时，由于2nP与(2h-1)P之间的差值过大，不利于构建基于2nP的加法链. 根据以上结果，本文后面对算法的比较与分析都将窗口宽度限制在5～11的范围内.

图1 低复杂度的改进wNAF标量乘算法在不同窗口下的计算复杂度分析

4 算法计算复杂度比较

4.1 预计算计算复杂度比较

为了更直观、更清晰地观察本文算法在预计算方面有优势，将提出的算法与目前研究比较多的wNAF 算法［17］、滑动窗口非相邻形式算法（swNAF算法）［18］和基于素数预计算的算法［9］进行了比较，比较结果如表3所示.

由表3 可以看出，相较于wNAF 算法、swNAF 算法和基于素数预计算的算法，本文算法在窗口宽度为5～11 时预计算点的个数减少，而在窗口宽度为11 时预计算点个数减少最多，分别减少了1 013 个、330 个和204个，减少的百分比分别为98.83%，96.49%和94.42%. 此外，当窗口宽度增加时，本文算法的预计算点的数量减少的百分比也随之增加，说明本算法比其他算法更适用于窗口宽度较大的情况.

表3 预计算点比较

表4 显示了当窗口宽度为5～11 时预计算点所需的模乘次数的比较，其中，倍点运算（用D 表示）根据1D=4M+6S 以及0.8M=1S 进行转换. 从表4 可以看出，相较于wNAF 算法、swNAF 算法和基于素数预计算的算法，在窗口宽度为5 时，本文算法在预计算的模乘次数分别减少了81.95%，70.19%和74.19%，在窗口宽度为11 时，预计算的模乘次数分别减少了99.38%，99.07%和97.83%. 由此可知，在窗口宽度5～11 时，本文算法的预计算复杂度最低. 此外，随着窗口宽度的增加，本文算法预计算所需模乘次数减少的百分比也随之增加，也说明了本文算法更适用于较大窗口.

表4 预计算点所需的模乘次数比较

4.2 标量乘计算复杂度比较

标量乘计算复杂度包括了预计算计算复杂度以及算数运算计算复杂度两部分，在第4.1节已经对预计算计算复杂度进行了对比，表5 显示了当n为256，384，521 时，4 种算法的算数运算计算复杂度和标量乘计算复杂度对比. 由表5 可以看出，本文算法在算数运算部分的计算复杂度与其他3种算法相当，但窗口宽度增加时，本文算法的预计算优势越明显. 并且随着窗口宽度增大，在相同位数下，有符号wNAF 链中非零个数相比无符号wNAF 链中更少，这也进一步减少点加次数，从而降低标量乘的计算复杂度. 此外，在窗口宽度较大时w=11 时，本文算法的标量乘计算复杂度相较于wNAF算法、swNAF 算法和基于素数预计算算法降低了最多，分别为78.23%，68.94%和43.63%.

表5 4种算法总体计算复杂度对比

5 结论

本文提出了在有符号wNAF算法的基础上，在预计算阶段采用2nP替换(2h-1)P，替换后的差值采用2nP构造的加法链进行补偿，该方法有效降低了预计算复杂度，并且只需要少量的寄存器即可完成预计算点的存储，进而解决了有预计算算法不适用于窗口很大的问题. 与现有的算法相比，预计算所需模乘数相较于wNAF 算法、swNAF 算法和基于素数预计算算法最多减少了99.38%，99.07%和97.83%，标量乘的计算复杂度分别降低了78.23%，68.94%和43.63%.