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

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

( )
w
∧
7. T j [0] = T j [0] ((−((T j [0] == 0)&1))&(2 T j [0])); /* T j [0] = T j [0] == 0 ? 2 : T j [0] */
w∧
8. for j = 1,2 do
(
)
9. t j = T j [i] == 0 ;
)
(
)
(
(
)
,
w
10. T j [i−1]+ = 2 · sgn T j [i−1] ·t j T j [i] = 1−t j ·T j [i]− sgn T j [i−1] ·t j ; /* sgn 为符号函数 */
11. end for
12. end for
13. x ← (x−T 1 [i])/2 , y ← (y−T 1 [i])/2 ;
w
w
14. x ow [a+w−1] = 0, ..., x ow [a+1] = 0, x ow [a] = T 1 [i] y ow [a+w−1] = 0, ...,y ow [a+1] = 0,y ow [a] = T 2 [i];
;
,
15. a ← a+w i ← i+1;
16. end while
17. return NAF ow (K 1 ) = (x ow [n], x ow [n−1], ..., x ow [1], x ow [0]) NAF ow (K 2 ) = (y ow [n],y ow [n−1], ...,y ow [1],y ow [0]).
,
2.3 标量乘阶段
在算法 8 对密钥随机分割的基础上, 给出如算法 9 的标量乘算法.
算法 9. OWNAF 标量乘算法.
输入: 标量 k, 椭圆曲线上一点 P, 窗口 w;
输出: [k]P.
NAF ow (K 1 ) NAF ow (K 2 ); /* 算法 8 */
,
1. 计算
w
,
2. 预计算 P c = [c]P i ∈ {1,2,...,2 };
3. Q ← O;
4. for i = ⌈n/w⌉−1 down to 0 do
w
5. Q ← [2 ]Q;
c ← x ow [i·w]+y ow [i·w];
6.
7. Q ← Q+ sgn(c)P |c| ; /* sgn 为符号函数 */
8. end for
9. return Q.
2.4 算法分析

(1) 安全性分析
在 OWNAF 算法的第 4 步中的每次计算中点加和倍点运算都是 D...DA 的均匀运算, 攻击者无法通过 SPA

攻击获取任何信息; 并且由于随机地引入 r 来分割序列, 两序列的 NAF ow (k) 本身并不相关, 因此, 攻击者无法通过
DPA 获取任何信息; 攻击者不能在每次执行一个标量乘法时推断出 0 值的特殊点, 因此可以抵御 RPA 和 ZPA; 进
一步的, 由于算法 8 生成的序列 NAF ow K j ( j = 1,2) 中的非 0 元素由于有随机值混淆, 与 wNAF 算法对应的非 0
( )
元素不同, 会给文献 [8,9] 中的破解方法造成干扰, 能在一定程度上抵御这种针对 ECC 签名算法的攻击.
(2) 计算开销与存储开销分析
s
w
RWNAF 算法的计算开销分为 3 部分: 预计算随机掩码 R = −(2 −1)R, 预计算表 E 和标量乘法运算 , 它们
′
′
′
′
′
′
,
′
,
′
的计算开销分别为 t(R ) = wD+ A t(E ) = 2 w−1 A t(s ) = n D+⌈n /w⌉A, 其中 n 为 ′ RWNAF 算法生成的序列长度.
而 OWNAF 算法的计算开销分为两部分: 计算 NAF ow (k) 时的预计算表 E 和标量乘法运算 s, 它们的计算开销分别
w , n 为 OWNAF 算法生成的序列长度. 它们的计算开销比较如
为 t(E) = wD+(2 −1−w)A t(s) = nD+⌈n/w⌉A, 其中
表 2 所示.