NAF算法介绍_IT分享知识网

大家好，欢迎来到IT知识分享网。

一、概述

最近研究SECP256K1曲线的相关运算时，在做ECDSA的验证时，需要计算aG + bP，其中a/b是标量,G/P是点，为了加速nP的运算，函数库中使用了w-NAF的算法，有些不甚理解，仔细研究了该算法的具体原理，并根据根据自己的理解进行如下的分析，w-NAF算法的核心就是NAF算法了。NAF算法的全称为非邻接形式（Non-Adjacent Form)表达。其核心思想是把标量b进行拆分，拆分为多项式表达式（1）：b = $k_{n-1}2^{n-1} +k_{n-2}2^{n-2}+k_{i}2^{i}+k_{2}2^{2}+k_{1}2^{1}+k_{0}$ ，其中 $k_{i} \exists \begin{Bmatrix}-1,0,1\end{Bmatrix} ,i=0,1,2,3...n-1$ ，n为最低位到最高位之间长度，

在解释NAF之前先看b值转化为2进制表述法

二、b*P转化二进制进行计算

b = $k_{n-1}2^{n-1} +k_{n-2}2^{n-2}+k_{i}2^{i}+k_{2}2^{2}+k_{1}2^{1}+k_{0}$ ，其中

$k_{i} \exists \begin{Bmatrix}0,1\end{Bmatrix} ,i=0,1,2,3...n-1$ ，n位转化为2进制数后的实际宽度，例如 5=b101,n为3，7=b111,n为3，对应b*P的计算方法可以转化为2进制方式进行。用2进制方式计算b*P时，有两种形式，一种形式时从多项式的右边向左进行累加方式，另外一种是从多项式的左边向右边进行倍乘。详见如下例子：

import ecdsa from ecdsa.ellipticcurve import Point,INFINITY #定义椭圆曲线的参数, 配置为secp256k1曲线 p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F 从右到左的计算方法-[6->110],先取0计算,在取1计算，在取最左边的1计算,计算k*P开始 def compute_bin_k_rtol(x, y, b): P: Point = Point(ecdsa.curves.SECP256k1.curve,x,y) Q: Point = INFINITY binstr = bin(b).replace("0b", "") binarray = list(binstr) bin_len = len(binarray) print('binarray=%s'%binarray,' len %d'%bin_len) # b->binarrary,[6->110]最低位是数组的最高位，故从右到左计算时，表现在数组上是从数组最高位向最低位运行 i = bin_len-1 while i>=0 : if binarray[i]=='1': Q = Q + P P = 2*P i-=1 q_x = Q.x() q_y = Q.y() print('q_x', q_x.to_bytes(32, byteorder='big').hex()) print('q_y', q_y.to_bytes(32, byteorder='big').hex()) None 从右到左的计算方法-[6->110],先取0计算,在取1计算，在取最左边的1计算,计算k*P结束 从左到右的计算方法-[6->110],先取1计算,在取1计算，最后右边的0计算,计算k*P开始 def compute_bin_k_ltor(x, y, b): P: Point = Point(ecdsa.curves.SECP256k1.curve,x,y) Q: Point = INFINITY binstr = bin(b).replace("0b", "") binarray = list(binstr) bin_len = len(binarray) print('binarray=%s'%binarray,' len %d'%bin_len) # b->binarrary,[5->110]最低位是数组的最高位，故从左到右计算时，表现在数组上是从数组最低位向最高位运行 i = bin_len-1 for i in range(0,bin_len): Q = 2 * Q if binarray[i]=='1': Q = Q + P q_x = Q.x() q_y = Q.y() print('q_x', q_x.to_bytes(32, byteorder='big').hex()) print('q_y', q_y.to_bytes(32, byteorder='big').hex()) None 从左到右的计算方法-[6->110],先取1计算,在取1计算，最后右边的0计算,计算k*P开始 #初始化P点 Px = 0x79fddb09f87acae42af3fe156d1b936a813cc368ff626bd Py = 0x316b1d0d025b5c76b87b42c6ddf879ec812bcf9eaeba6b2 print('right to left compute!!!') compute_bin_k_rtol(Px,Py,6) print('left to right compute!!!') compute_bin_k_ltor(Px,Py,6)

三、NAF系数计算

NAF的表示方式如：

b= $k_{n-1}2^{n-1} +k_{n-2}2^{n-2}+k_{i}2^{i}+k_{2}2^{2}+k_{1}2^{1}+k_{0}$

$k_{i} \exists \begin{Bmatrix}-1,0,1\end{Bmatrix} ,i=0,1,2,3...n-1$ ，Naf表示标量b与二进制表示法多了一个”-1″值，多项式形式是相同的，需要考虑“-1”值是怎么来的？看多项式的形式都是与2的幂乘有关，说明b是的多项式也是通过b/2这种方式产生，首先研究b转化为2进制的方法

7/2 = 3 余 1

3/2 = 1 余 1

1/2 = 0 余 1

可以看出来，余数的组合即为十进制7的二进制表示。在二进制的标量b*P算法中，如果b为7，需要反复执行如下代码：

if binarray[i]=='1': Q = Q + P

于是有天才思考通过NAF可以减少乘法的次数，NAF算法的目标就是每个相邻的值之间 $k_{i+1},k_{i}$ ,且不存在非零的两个连续数字，这样可以减少其乘法次数。考虑一下7的NAF表示。

7/2 = 3 余 1

3/2 = 1 余 1

7连续两次除2的余数均为1，根据NAF的设计，希望第一次除法有余数是可以的，但第2次除法希望余数为0，这样才能可能实现“且不存在非零的两个连续数字”的目标。要实现此目标就意味着第2次除2的时候，余数为0，第2次除2就相当于7/2/2=7/4余数为0，要余数为0，被除数7/2之后得商值为4,第2次除以2余数正好为0，考虑是否通过第一次7/2时通过变化，使得第2次除以2得时候余数为了0，于是有了如下操作：

第一次除以2

$k_{0}$ = 2-(7%4)=-1 商为k=k-k0=7-(-1)=8,此处需要考虑为啥是7%4，可以想想一下需要第2次除以2的余数为了0，也就是说7/4这次的余数应该为0。-1恰好是对第2次除以2进行补上值1，还需要注意除以2其实就是二进制的一位的值变化[0,1]，如果需要进位只能是1-(-1)，从此可以看出来涉及到一个概念是进位的宽度，NAF的进位宽度就是1位，也就是最大模为2，即2^1。当第2次相除时模是4，即2^2。如果设NAF的宽度为w，则下一次除以2的宽度为w+1。

NAF的核心思想就是w+1为0，需要从w执行时进行借值使之满足w+1执行时的余数为0。具体NAF系数 $k_{i} \exists \begin{Bmatrix}-1,0,1\end{Bmatrix} ,i=0,1,2,3...n-1$ $k_{i} \exists \begin{Bmatrix}-1,0,1\end{Bmatrix} ,i=0,1,2,3...n-1$ 算法实现如下：

#计算naf系数--开始 def comput_coeff_naf_2(b): k = b coeff_naf_val = [] i = 0 while k>=1: if k%2 : coeff_naf_val.append(2-k%4) k -= coeff_naf_val[i] else: coeff_naf_val.append(0) k = int(k / 2) i+=1 print('coeff_naf_val=',coeff_naf_val,' len %d'%(i) ) return coeff_naf_val naf-2进制函数--结束 b = 6 print('naf-2 compute-%d'%b) comput_coeff_naf_2(b)

四、使用NAF系数计算bP

使用naf2计算bP# def compute_naf2_k_ltor(x, y, b): P: Point = Point(ecdsa.curves.SECP256k1.curve,x,y) Q: Point = INFINITY binarray = comput_coeff_naf_2(b) bin_len = len(binarray) # print('binarray=%s' % binarray, ' len %d' % bin_len) for i in reversed(binarray): Q = 2 * Q if i==1: Q = Q + P if i==-1: Q = Q + P.__neg__() # 即 Q= Q -P q_x = Q.x() q_y = Q.y() print('q_x', q_x.to_bytes(32, byteorder='big').hex()) print('q_y', q_y.to_bytes(32, byteorder='big').hex()) None 从左到右的计算方法-[6->110],先取1计算,在取1计算，最后右边的0计算,计算k*P开始 #初始化P点 Px = 0x79fddb09f87acae42af3fe156d1b936a813cc368ff626bd Py = 0x316b1d0d025b5c76b87b42c6ddf879ec812bcf9eaeba6b2 print('naf-2 compute!!!') compute_naf2_k_ltor(Px,Py,b)

免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/151893.html

NAF算法介绍

一、概述

二、b*P转化二进制进行计算

三、NAF系数计算

四、使用NAF系数计算bP

相关推荐

发表回复