基于二进制的相邻表示型多位生成算法研究

蒋洪波　孙宇　张鹏南　冯新宇　王明杰

摘要：信息安全一直是研究热点，而椭圆曲线加密在该領域占有举足轻重的作用，椭圆曲线的标量乘又是快速实现的关键点，其中二进制数的非相邻表示型（NAF）被应用在该点运算上，通常的NAF算法是一位一位的生成相应数位，而这在时间上产生极大的浪费.为了节省运算时间，分析NAF定义与性质，提出一种基于二进制的NAF多位生成算法，一次生成多位NAF值，减少了操作次数，替换了费时运算，从而节省了运行时间.经过分析及建模验证多位生成算法较原算法时间效率提高50%左右.

关键词：二进制;非相邻表示型;多位生成;标量乘

中图分类号：TN918.4  文献标识码：A  文章编号：1673-260X（2019）09-0086-04

1 引言

在过去，传统的通信是以信件为基础的，支付是通过支票或现金以及秘密文件都保存在密封的盒子里.今天一切都改变了，而且变化得非常快.每天都有人使用手机、电子邮件，越来越多的人通过互联网支付费用.这些变化正在使生活更便捷，但同时也会产生安全风险.信息安全问题在当前显得尤为重要.密码学是一种数学工具，安全工程师用来保护数据不受未经授权的访问或操作.密码学为负责安全的人提供所需的实用程序，它可以隐藏数据、控制对数据的访问、验证数据的完整性.椭圆曲线在密码应用中具有举足轻重的地位.然而计算标量乘法成为限制吞吐量的瓶颈.在标量乘中应用最多的是NAF表示型，[1]中的算法是一位一位生成的，这对长度为l的正整数k来说需要执行l次循环及其相关操作，为了节省时间，根据NAF定义和性质提出一种一次生成多位NAF值的算法，该算法还可优化模运算和除法运算，用运算效率更高的位运算和移位运算来代替它们.经初步分析预计可以提高至少30%的运算时间.

2 非相邻表示型（NAF）

Non-adjacent Form缩写为NAF，一个正整数k可以使用二进制表示，也可以使用带符号的二进制——1、0和-1来表示，如k=，其中ki∈{-1，0，1}，kl-1≠0，l为NAF的长度，且不存在非零的两个连续数字ki.

文献[1]的定理3.29给出了正整数k的NAF表示的如下性质：

（1）对于k的非相邻表示型是唯一的，记作NAF（k）;

（2）k的NAF（k）具有最少的非零数;

（3）L≤l≤L+1，L为k的二进制表示长度;

（4）2l/3<k<2l+1/3;

（5）NAF（k）的平均汉明密度约为1/3.

利用[1]中的算法3.30计算一个正整数k的NAF，从NAF（k）的最低位k0开始生成，需要先判断k的奇偶性，若k为奇数则用k对4取余，当前ki值为2减去余数的值，即ki=2-（kmod4），由于对奇数的k来说对4取余只有两种结果——1和3，因此ki的值也只有两种可能性，当余数小于2时ki=1，当余数大于2时ki=-1，计算完ki的值再用k减去ki得到新的k值，以便使得新k值为偶数，为后边的k=k/2做准备;若k为偶数，则ki=0，同样对k做折半处理，即k=k/2，与此同时i加1，为下一位ki的生成做准备.至此也看到ki的三种取值情况，算法3.30的流程图如图1所示.

基于此算法可以得到k=50、k=87和k=113的NAF表示见表1.

从表中可以看到三个NAF（k）的值都是由1、0和-1组成的，

3 基于二进制的NAF多位生成算法

从图1可以看到每次只生成1位的ki，生成步长为1，通过分析研究算法3.30可以看到NAF（k）没有相邻的两个非零值，也就是说1和-1的前后肯定是0，不会有非零数值存在，那么根据这个规律，可以考虑为什么不一起生成两位ki值呢？这样就会加快算法进度.此算法在文献[2]中已经给定，但是该算法对于k为偶数时是一位一位生成的，改进也只是在k为奇数时生成步长为2.

3.1 基于二进制的NAF两位生成算法

[1]中算法3.30和[2]中算法2对于k=113的计算过程如表2和表3所示.

为了进一步优化算法，本文在k为偶数时进行了优化.优化算法为基于二进制的NAF多位生成算法，优化的前提是k在计算机中是以二进制形式存放的，当然这也是我们无需特意转换的，因为正整数k在计算机中就是以二进制形式存放的.这里为了更好地阐述基于二进制的NAF多位生成算法假设正整数k=113，则k2=1 110 001，从表1可以看到NAF（113）=1 0 0 -1 0 0 0 1.

表3中由于将表2的第1次和第2次循环及第5次和第6次循环一起计算，所以循环次数要较算法3.30少两次，从执行速度看上有所提高，但是在算法3.30的第3次和第4次循环上我们发现对于连续的两个0来说，在NAF表示时也是两个0，因此在这种情况下就可以进一步优化算法得到算法1所示的基于二进制的NAF两位生成算法.

算法1 基于二进制的NAF两位生成算法

INPUT：正整数k.

OUTPUT：NAF（k）.

1.i=0;

2.k≥1时，重复执行

2.1t=k&0X3;

2.2switch（t）

case0：ki=0;ki+1=0;i=i+2;k=k>>2;

case1：ki=1;ki+1=0;i=i+2;k=k>>2;

case2：ki=0;i=i+1;k=k>>1;

case3：ki=-1;ki+1=0;i=i+2;k=k+1;k=k>>2;

3.返回（ki-1，ki-2，k0）.

用算法1计算NAF（113）的过程如表4所示.

算法1对表2中算法3.30的第3、4次循环一起计算，但是对第7次计算由于只有1个0，不能构成步长为2的两个0，因此只能单独计算该位ki值.

算法中无论k值是奇是偶，只要大于等于1，就取k的最后两位，其实就是k对4取余.因为k在计算机中以二进制形式存放，对4取余就等同于取k的最右两位，这样做也是因为位操作只需要一个指令周期，而取余运算需要调用子程序来完成，代码不仅长而且执行速度慢.同理算法3.30中的除法运算k=k/2也被替换成了位操作k=k>>1，k=k/4替换成k=k>>2.算法1中t有四种取值：

（1）t=（00）2，即t=（0）10，k为偶数，且即使右移一次后仍为偶数，对应的ki恰好是两个0，然后将k右移两位也即k除以4，达到当k为偶数时优化算法的目的;

（2）t=（01）2，即t=（1）10，k为奇数，ki=2-（kmod4）=1，根据NAF性质必有ki+1=0，步长加2，再右移两位;

（3）t=（10）2，即t=（2）10，k为偶数，但右移一位后为奇数，因此不能按照步长2去生成两个ki和ki+1的值，只能生成一位ki值，右移一位，将剩余的“1”与k的其他高位再次形成新t值，继续判断生成NAF（k）的其他位;

（4）t=（11）2，即t=（3）10，k为奇数，ki=2-（kmod4）=-1，根据NAF性质必有ki+1=0，步长加2，算法3.30中的k=k-ki，因为ki=-1，因此k=k+1，再右移两位.

对比表2和表3可以看到表3循环次数最少，原因是在第2次循环时将表2中算法3.30的第3、4次循环合并为一步完成，提高了执行速度.对于k值较大时这种速度提升更加明显.

3.2 基于二进制的窗口宽度w的NAF多位生成算法

文献[1]中给出了窗口宽度w的NAF算法，经过分析在本文算法1的基础上也对该算法进行了改进，基于二进制的窗口宽度w的NAF多位生成算法如算法2所示.

算法2 基于二進制的窗口宽度w的NAF多位生成算法

INPUT：正整数k，窗口宽度w.

OUTPUT：NAFw（k）

1.i=0;

2.k≥1时，重复执行

若k为奇数，则

（1）t=k&（2w-1）

（2）若t>2w-1，则

①ki=t-2w;

②k=k-ki;

否则，ki=t;

（3）ki+1=0;ki+2=0;…ki+w-1=0;

（4）k=k>>w;

（5）i=i+2;

否则，判断t的值，按值进行下列操作：

（1）末尾1个0：

ki=0;i=i+1;k=k>>1;

（2）末尾2个0：

ki=0;ki+1=0;i=i+2;k=k>>2;

……

（w）末尾w个0：

ki=0;ki+1=0;…;ki+w-1=0;

i=i+w;k=k>>w;

3.返回（ki-1，ki-2，…，k0）.

文献[1]的算法3.35中若k为奇数，则ki=kmod2w，由于计算机中的按位&比取余运算效率高得多，又由Hash散列原理可知

a%b=a-（a/b）*b

这里如果b=2w，就可以用位运算代替取余运算，即

a%b=a&（b-1）=a&（2w-1）

因此在本文算法2中将该步替换成t=k&（2w-1），为了保证-2w-1≤ki≤2w-1，需做t>2w-1的判断，若为真，则ki=t-2w，并将取得的负值加到k上，这样才能保证原k不变而进行后续的计算;否则ki直接取t值，这里将k减余数省略，因为先减后移位和不减后移位效果是相同的，而且不减又会提高运行效率，因此这里通过直接右移w达到最终目的.根据文献[1]定义3.32的任何连续w个数字中最多有1个非零值，则必有ki+1=0;ki+2=0;…;ki+w-1=0.

若k为偶数，这里根据t值的末尾有几个0来置几个ki的零值，然后k也跟着移动几位，这样能够提高k中多个0连续的处理效率.NAF（k）是w=2的MAFw（k）形式.

4 算法分析及验证

为了便于分析说明，设NAF（k）的长度为l，这里将文献[1]的算法3.30、文献[2]的算法2和本文的算法1就运算次数进行统计.

文献[1]的算法3.30由于是奇数时才进行模运算，根据NAF（k）的性质（5）有非零数值的密度约为l/3，因此该模运算进行约l/3次;减法进行约2l/3次;无论奇偶数k都要除2折半处理，因此除法进行l次;位运算&在这里主要是用来判断k的奇偶性，因此也进行l次;加法体现在变量i+1.

文献[2]的算法2除法次数由k为奇数时的l/3次k=k/4和k为偶数时的l/3次k=k/2组成，加法次数同理，其他运算次数与算法3.30相同.

算法1的模运算被替换成位运算&且不判断k的奇偶性，因此模运算次数为0;减法0次;除法替换成移位运算，所以除法运算0次;生成步长为2，所以位运算&约为l/2次;每次取末尾两位后都会进行移位操作，因此移位次数与位运算次数相同;加法次数为l/2次+case 3中k=k+1的次数（l/8）.

算法2没有模运算和除法;减法根据NAFw（k）的性质（iv）非零数值密度为1/（w+1）算得大约有l/（w+1）次;位运算包括奇偶判断和t值计算，因此有2l/（w+1）次;移位运算接近l/（w+1）;加法与位运算次数相同.运算次数统计表见表5.

当k为163位时，对表4中的几种算法进行C建模，运行于Linux平台，运行结果见表6.

从实验结果可以看到本文算法1较算法3.30的运算效率平均提高了50%左右.

5 结语

本文对[1]和[2]提出的NAF（k）算法进行了分析，在此基础上对其除法运算和模运算进行了替换改进，针对一次处理一位，提出了一次生成多位的NAF（k）算法，经理论分析和建模验证得出以下u語结论：

（1）本文NAF（k）算法不需模运算、减法和除法运算，位运算和移位运算均l/2次，加法次数也较前两种算法有减少.

（2）经建模验证效率提高50%左右，时间复杂度明显变小.

——————————

参考文献：

〔1〕Hankerson D， Menezes A， Vanstone S. Guide To Elliptic Curve Cryptography[M]. Springer， 2004： 98-100.

〔2〕蒋洪波，尚春雨，冯新宇.NAF算法的改进[J].科学技术与工程，2012，12（19）：4663-4666.

〔3〕J.López and R.Dahab. High-speed software multiplication in [C]//Progress in Cryptology —INDOCRYPT2000（LNCS1977） [393]. India ：Springer Verlag， 2000： 203-212.

〔4〕N. Koblitz. Elliptic curve cryptosystems[J]. Mathematics of Computation， 1987， 48： 203-209.

〔5〕李忠，张永华.整数的最佳带符号二进制表示的随机生成算法[J].计算机科学，2014，41（11A）：282-283.

〔6〕丁勇.椭圆曲线快速算法理论[M].北京：人民邮电出版社，2012.21-30.

〔7〕汪翔，鲍皖苏，吕诗飞.点乘运算中整数表示方法研究[J].微计算机信息，2006，22（3-3）：240-242.

〔8〕卢开澄，卢华明.椭圆曲线密码算法导引[M].北京：清华大学出版社，2008.101-102.

〔9〕MIIER B. Improved Techniques for Fast Exponentiation[C]. Information Security and Cryptology 2002 （LNCS 2587） [277]. Berlin： Springer Verlag， 2003： 298-312.

〔10〕MORAIN F， OLIVOS J. Speeding Up the Computations on An Elliptic Curve Using Addition-subtraction Chains[J]. Informatique Theorique et Applications， 1990， 24： 531-544.

〔11〕JEROME A. Efficient Arithmetic on Koblitz Curves[J]. Designs， Codes and Cryptography， 2000， 19：195-249.