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

程石 等: 基于两种新标量表示的安全高效标量乘算法 4545

3. Q ← O;
4. for i = len−1 down to 0 do
5. Q ← [2]Q;
6. Q ← Q+[sgn(k i )]P k i ;
7. end for
8. return Q.

算法 2 中存在以下安全隐患: 当第 6 步中 k i = 0 时, 不进行点加运算; 而当 k i , 0 时, 进行一次点加运算, 这就
导致了 k i = 0 和 k i , 0 时运算出现了不同的分支, 耗时不同. 因此, 攻击者可以通过诸如 Flush+Reload 攻击等, 对时
k i 是否等于 D, 则对 wNAF 算法进行一次攻击后就可以获得类似
间进行检测, 判断 0. 记点加运算为 A, 倍点运算为
DADDADDDA... ”的点加和倍点信息链, 通过对这种不规则的信息链进行分析, 就能获取标量 的 k wNAF 表示
“
法中所有的非 0 元素 {k i } n 以及 k i 对应的原来角标值 i, 这样便可通过文献 [8,9] 中的格方法将其转换成 EHNP 问
i=1
题进行求解, 多次攻击后即可获取密钥相关的私密信息.
张涛等人 [10] 提出了一种基于改进 wNAF 的标量乘算法 RWNAF, 将原先 wNAF 算法生成的 NAF 序列变得规
则, 并借助随机掩码, 实现了抗 SPA, DPA 等攻击的安全标量乘算法, 其中 RWNAF 编码算法如算法 3 所示.
算法 3. 标量 k 的 RWNAF 编码算法 [10] .

输入: 标量 k, 窗口宽度 w;
输出: NAF rw (k).
1. r = 0 i = 0 r 0 = w;
,
,
2. if k 为偶数 then
3. k = k +1;
4. end if
5. while k > 1 do
( )
w
6. u[i] = k mod 2 w+1 −2 ;
r i
7. k = (k −u[i])/2 ;
8. k w [r +r i −1] = 0,...,k w [r +1] = 0,k w [r] = u[i];
9. r = r +r i ,i = i+1,r i = w;
10. end while
11. k w [n] = 0,...,k w [r +1] = 0,k w [r] = 1;
12. return k w [n],k w [n−1],...,k w [0].

R 可以构造其关于 RWNAF 标量表示的恒等式, 即:
注意到对于点

R = (0...1|0...b|...|0...b)R (1)
w
w
′
′
其中, b = −(2 −1), 因此令 R = [b]R = [−(2 −1)]R 用于预计算, 预计算开销为 t(R ) = wD+ A. 此时, 预计算表的内
w
容为 E = {P+R ,[3]P+R ,...,[(2 −1)]P+R }, 预计算开销为 t(E ) = 2 w−1 A, 标量乘算法如算法 4 所示.
′
′
′
′
′
算法 4. RWNAF 标量乘算法 [10] .
输入: NAF rw (k), 椭圆曲线上一点 P;
输出: [k]P.
1. R = RandomPoint();
2. Q = [k w [c]]P+R /* 其中 c 为 NAF rw (k) 序列中不为 0 的比特的最大序号 */