NAF点乘算法的并行计算研究*

赵前进 ，李西萍，戴紫彬，张永福

(1.解放军信息工程大学 电子技术学院，河南 郑州450004；2.第四军医大学，陕西 西安710023)

椭圆曲线密码算法(ECC)是目前公认最有效的公钥密码算法，1985年由MILLER V和KOBLITZ N独立提出的[1-2]。在ECC密码算法中，点乘运算是最主要运算，决定着ECC密码算法的实现效率。如果将定义在椭圆曲线上的点p自相加k次，把计算结果记作kp，则称根据k计算kp的运算为点乘运算。在对常用点乘算法研究的基础上，本文对NAF点乘算法(二进制NAF和窗口NAF点乘算法)进行了改进，改进后的NAF点乘算法具备了并行调度点加和点倍的特点,与原算法相比效率有明显提高。

1 二进制NAF点乘算法的并行计算

减少k的二进制表示时,非0元素的个数可以提高点乘算法的效率。对k进行重新编码，即k=(km-1,km-2,…,k0)2，其中 ki∈{0,±1}，最高位 km-1≠0，且没有相邻的非 0元素，称该式为非相邻有符号二进制表示方式NAF(Non-Adjacent Form)，并记作 NAF(k)。 用 NAF(k)代替了k的二进制表示就是二进制NAF点乘算法[3,5-6]。对k进行NAF编码的算法和二进制NAF点乘算法见参考文献[3]、[6]。把 k进行 NAF编码后，ki≠0的概率为 1/3。点加用ECADD表示，点倍用ECDBL表示，则二进制NAF点乘算法的期望计算时间为:m/3 ECADD+m ECDBL。

[4]通过增加输入的方式对Double-and-Add点乘算法进行了改进，改进后的算法具有并行运算的特点。在二进制NAF点乘算法中，假设i轮迭代的输入值为 Q，根据对 ki值的判断，返回值 Q′可能是 2Q-P、2Q、2Q+P。根据这个特点，本文对二进制NAF点乘算法进行了并行改进:每轮迭代输入增加为Q-P、Q和Q+P、返回值 Q′为 Q[1]-P、Q[1]、Q[1]+P作为下一轮迭代的输入，其中 Q[1]的值可能是 2Q-P、2Q和 2Q+P作为结果输出。改进后的算法如图1所示。

首先用归纳法证明Q[0]=Q[1]-P，Q[2]=Q[1]+P。当m取最小值2时：

因此m=2时,Q[0]=Q[1]-P,Q[2]=Q[1]+P成立。设当 m=k时，Q[0]=Q[1]-P,Q[2]=Q[1]+P成立，则当 m=k+1时：

因此 Q[0]=Q[1]-P，Q[2]=Q[1]+P。

而且,若 ki=-1，则 Q[1]′=2Q[1]-P;若 ki=0，则 Q[1]′=2Q[1]；若 ki=1，则 Q[1]′=2Q[1]+P。 因此 Q[1]与二进制NAF点乘算法[3,6]的输出值是等价的。由此证明了图1所示算法的正确性。

图2是依据图1算法给出的并行二进制NAF点乘算法的运算流程。

通过图2可以看出，图1所示算法可以使用2个点加和1个点倍运算单元并行运算完成一轮迭代，共需要进行m-1轮迭代。而一般点倍运算略快于点加运算，所以图1所示算法期望计算时间为(m-1)ECADD。

2 窗口NAF点乘算法的并行计算

窗口NAF点乘算法与二进制NAF点乘算法具有相同的运算流程,同样可以对窗口NAF点乘算法作并行改进：每轮迭代增加 2w-1个输入,使输入为 Q-(2w-1-1)P、...、Q-3P、QP、Q、Q+P、Q+3P、…、Q+(2w-1-1)P，根据 ki的值选择相应Q+kiP做点倍运算，并依次与其他输入做点加运算，将运算结果按升序排列为 Q[1]-(2w-1-1)P、...、Q[1]-3P、Q[1]-P、Q[1]、Q[1]+P、Q[1]+3P、… 、Q[1]+(2w-1-1)P 作为 下 一 轮迭代的输入，其中 Q[1]的值可能是 2Q-|ki|P、2Q、2Q+|ki|P，作为结果输出。改进后的算法如图3所示。

以窗口值 w=3为例，返回值为 Q2，给出了如图 4所示的并行的窗口NAF点乘算法的运算流程。当窗口值时，图3所示算法可以使用4个点加和1个点倍运算单元并行运算完成一轮迭代，共需要(m-w)轮迭代，所以图3所示算法的期望计算时间为(m-w)ECADD。

3 分析验证

改进后的二进制NAF点乘算法和窗口NAF点乘算法增加了迭代时输入值的个数，点加和点倍可以并行计算，从而提高了效率，但资源消耗随之增加。原始NAF点乘算法串行调度点加和点倍，只需要1个点倍和1个点加运算单元。改进后的二进制NAF点乘算法需要2个点加和1个点倍运算单元并行计算。而改进后的窗口NAF点乘算法，随着窗口宽度的增加，需要的点加运算单元数量呈指数增加。表1为算法改进前后的期望计算时间和资源消耗对比。

本文以NIST推荐的二进制域上的163位随机椭圆曲线，在ALTERA公司的EP2S90F1508C3器件上进行了实验，表2给出了实验结果的比较。窗口NAF点乘算法取窗口值w=3。由于随着窗口宽度的增加，非0元素个数减少，效率随之降低。本文对常用的NAF点乘算法进行了分析和改进，对点乘算法进行并行化处理，使得点乘算法可以并行调度点倍和点加运算，使改进后的算法具有并行运算的特点，该算法是提高点乘运算效率的一种重要途径，同时提高了算法的安全性[4]。经过实验，本文提出的并行算法与原算法相比，在实现效率上有明显提高。

表1 期望计算时间和资源消耗对比

表2 算法改进前后计算时间比较

参考文献

[1]MILLER V S.Use of elliptic curves in cryptography[C].CRYPTO′85,1986:417-426.

[2]KOBLITZ N.Elliptic curve cryptosystems[J].Mathematics of computation,1987,48(4):203-209.

[3]HANKERSON D.椭圆曲线密码学引导译[M].张焕国,译.北京：电子工业出版社,2005.

[4]IZU T,TAKAGI T.A fast parallel EC multiplication resistant against side channel attacks[R].CACR University of Waterloo.2002.

[5]刘双根,李 萍.胡予濮.椭圆曲线密码中标量乘算法的改进方案[J].计算机工程,2006,32(17):28-29.

[6]陶 然,陈丽燕.椭圆曲线密码体制中点乘的快速算法[J].北京理工大学学报,2005,25(8):701-704.