Page 147 - 《软件学报》2025年第10期

4544 软件学报 2025 年第 36 卷第 10 期

表 1 符号说明

符号 含义
k 标量乘算法中的标量
P,Q 椭圆曲线上的点
[k]P 椭圆曲线上点 P 的 倍点
k
w 窗口宽度
NAF w (k) 标量 k 的wNAF表示
NAF rw (k) 标量 k 的RWNAF表示
NAF ow (k) 标量 k 的OWNAF表示
A 点加运算
D 倍点运算
sgn() 符号函数
MSB w (k) 取标量 k 的二进制表示的第 w 位
e λ e λ = λ−2 w−1 mod 2 w−1

k 的 wNAF 形式的算法如算法 1 所示.
计算数
算法 1. 标量 k 的 wNAF 编码算法 [3] .

输入: 标量 k, 窗口宽度 w;
输出: NAF w (k).

1. i ← 0;
2. while k ⩾ 0 do
3. if k 是奇数 then
w
4. k i ← k mod 2 ;
5. if k i ⩾ 2 w−1 then
w
6. k i = k i −2 ;
7. end if
8. k ← k −k i ;
9. else
10. k i ← 0;
11. end if
12. k ← k/2 i ← i+1;
,
13. end while
14. return NAF w (k) = (k i−1 ,k i−2 ,...,k 1 ,k 0 ).

由算法 1 计算得到的 NAF w (k) 的位数最大为 n+1 n 为 的二进制表示位数. 在宽度为 w 的 NAF w (k) 中非 0
,
k
数字的密度平均为 1/(w+1). 计算 wNAF 形式 k 的标量乘算法如算法 2 所示.
算法 2. wNAF 标量乘算法 [3] .

输入: 标量 k, 椭圆曲线上一点 P, 窗口宽度 w;
输出: [k]P.

len−1
∑
i
1. 计算 NAF w (k) = k i 2 ; /* 算法 1 */
i=0
{ w−1 }
,
2. 预计算 P i = [i]P i ∈ 1,3,...,2 −1 ;