ECC中计算倍点的两种方法

最近在看ECC的加密算法，该算法的安全性基于“求离散对数”的困难。下面主要介绍一下ECC在实现倍点过程中的算法，分为两部分：一是基于二进数的计算方法，二是基于ＮＡＦ序列的计算方法。

基于二进数的计算方法中，分为两种遍历方式，一是从左向右遍历，二是从右向左遍历，该算法类似模幂运算中对于其指数的处理方式。具体算法如下。

ECC中计算倍乘的算法：现计算kP,k=(k_t-1,k_t-2,.....,k₁,k₀),PE(F_q)

算法1：从左向右遍历

输入：k=(k_t-1,k_t-2,.....,k₁,k₀),PE(F_q)

输出：Q=k P

Q←０（这里０指的是群运算中的单位元）

for i=0 to t-1

begin

  if ki=1 Q=Q+P

  P=2P

end

return Q

算法2：从右向左遍历

输入：k=(k_t-1,k_t-2,.....,k₁,k₀),PE(F_q)

输出：Q=k P

Q←０（这里０指的是群运算中的单位元）

for i=t-1 to 0

begin

  Q=2Q

  if ki=1 Q=Q+P

end

return Q

基于NAF序列计算点乘运算中也分为两种情况，一种是基于NAF2，一种是基于ＮＡＦｗ，下面先介绍一下ＮＡＦ的定义，然后再介绍一下基于ＮＡＦ计算点乘的算法。

标量的非相邻表示称为NAF

定义：一个正整数k的非相邻表示型是表达式,其中,并且没有两个连续的数字k_i是非零的,NAF的长度是l.

NAF的性质：

1 k有唯一的NAF,并记作NAF(k)。

2 NAF(k)在k 的所有带符号表示中具有最少的非零位。

3 NAF(k)的长度最多比k的二进制表示的长度大1.

4 若NAF(k)的长度是l,则2^l/3(l+1)/3.

5 所有长度为l的NAF中非零数字的平均密度约为1/3.

计算一个正整数的NAF，算法如下：

输入：一个正整数k

输出：NAF序列

1. i←0

2. while (k≥1)

3.   if(k mod 2==1) ki←2-(k mod 4),k ←k-ki

4.   else ki=0

5.   k ←k/2,i ←i+1

6. return (ki-1,ki-2,....,k0)

用二进制NAF的方法计算点乘

输入：一个正整数k, PE(F_q)

输出：kP

1. NAF(k)=

2. Q←０（这里０指的是群运算中的单位元）

3. for i=l-1 to 0

4. begin

5.    Q←2Q

6.    if ki=1 Q ←Q+P

7.    if ki=-1 Q ←Q-P

8. return Q

窗口方法：即基于ＮＡＦｗ的计算方法。

可以利用额外的存储器，采用一次处理k的w位的窗口方法，可以将算法的运行时间减小。

定义：令w≥2是正整数。正整数k的宽度为w的NAF是表达式，其中每一个非零系数k_i都是奇数，，，并且任何连续w个数字中最多1位非零。宽度为w的NAF的长度是l。

宽度为w的NAF的性质：

1. k有唯一的宽度NAF，记作NAF_w(k)

2. NAF₂(k)=NAF

3. NAF_w(k)的长度最多比k的二进制表示的长度大1。

4. 在所有长度为l的宽度w的NAF中，平均非零数字的密度近似为1/w+1

 

计算一个正整数的窗口宽度w的NAF

输入：窗口宽度为w，一个正整数k

输出：NAF_w(k)

1. i←0

2. 当k≥1时，重复执行

3.    if(k mod 2 ==1) then ki ←k mod 2^w,k ←k- ki

4.    else ki ←0

5.    k← k/2,i ←i+1

6. return (k_i-1,k_i-2,.....,k1,k0)

 

计算点乘的窗口NAF方法

输入：窗口宽度w,一个正整数k, PE(F_q)

输出：kP

1. 计算NAF_w(k)

2. 对于，计算Pi=i P

3. Q←０（这里０指的是群运算中的单位元）

4. for i=l-1 to 0

5. Q ←2Q

6.  if ki≠0

7.    if ki>0 Q ←Q+Pi

8.    else Q← Q-Pi

9. return Q