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

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

算法 7. 标量 k 的 OWNAF(k) 生成算法.

输入: 标量 k;
输出: NAF ow (k).

,
1. a ← 0 i ← 0;
2. while k ⩾ 1 do
(
3. T [i] = k mod 2 w+1 ) ;
w
w
4. T [i] = (T [i]−2 ·MSB w (T [i])) mod 2 ; /* MSB w (k) 表示取标量 k 的二进制表示的第 w 位 */
w∧
w
5. T [0] = T [0] ((−((T[0] == 0)&1))&(2 T[0])); /* T [0] = (T [0] == 0) ? 2 : T [0] */
∧
6. t = (T [i] == 0);
w
,
7. T [i−1]+ = 2 · sgn(T [i−1])·t T [i] = (1−t)·T [i]− sgn(T [i−1])·t; /* sgn 为符号函数 */
8. k ← (k −T [i])/2 ;
w
,
9. k ow [a+w−1] = 0, ...,k ow [a+1] = 0 k ow [a] = T [i];
,
10. a ← a+w i ← i+1;
11. end while
12. return (k ow [a+w−1],...,k ow [1],k ow [0]).
通过 OWNAF 算法得到了标量 k 的 NAF ow (k) 表示, 在每个宽度为 w 的子序列中都有形如 0...0a 的形式, 其中
w
0 < |a| ⩽ 2 , 假设生成的序列长度为 n, 最终得到的序列形如:

⌈n/w⌉个子序列
z }| {
0...0a|0...0a|...|0...0a (2)
由于在 RWNAF 算法的基础上调整了 T [i] 的取值范围, OWNAF 算法相较 RWNAF 算法的预计算开销差值
( w−1 )
为 2 −1−w A, 预计算开销有所增加. OWNAF 算法则规避了 RWNAF 在循环结束后补充一个 0...01 的子序列
OWNAF(k) 的平均长度小于同样窗口大小的 RWNAF RWNAF (k) 的平
的处理, 因而生成的序列 算法生成的序列
均长度. 下面给出数学证明.
定理 1. OWNAF 生成的序列长度小于等于 RWNAF.
证明: 不失一般性, 设标量 k > 0, 如果 OWNAF 生成的序列长度大于 RWNAF 生成的序列长度, 由算法结构,
假设 OWNAF 的序列多一个窗口长度, 即:
OWNAF 生成的序列 NAF ow (k) = (0... x[n+1]|0... x[n]|...|0... x[0]).
RWNAF 生成的序列 NAF rw (k) = (0...y[n]|0...y[n−1]|...|0...y[0]).
对于 k 的两种标量表示, 显然可以互相转换.
w
0
nw
w
w
(1) 假设 x[n+1] = 1, 由 1·2 (n+1)w = (2 −1)2 +(2 −1)2 (n−1)w +...+(2 −1)2 +1, 有:

n ∑ n ∑
w
w
iw
k = (x[i]+(2 −1))·2 +(x[0]+2 ) = (y[i])·2 iw (3)
i=1 i=0
由于 RWNAF 算法构造的序列唯一, 转换后有 x[i]+(2 −1) = y[i],1 ⩽ i ⩽ n 且 x[0]+2 = y[0], 由 RWNAF 序
w
w
w
w
列中 y[n] = 1, 因此 x[n] = −2 , 此时 OWNAF 序列中有 x[n+1] = 1 和 x[n] = −2 , 显然可以将第 n+1 个窗口和第
OWNAF(k) = (0... x[n−1]|...|0... x[0]), 此时 OWNAF 生成的序列长度显然小于
n 个窗口的子序列合并缩短, 即
RWNAF 序列生成的长度, 矛盾; x[n+1] = −1 同理.
w w y[i] 的取值范围显然超过了
(2) 假设 1 < |x[n+1]| ⩽ 2 , 在相互转换时, 有 x[i]+ x[n+1]·(2 −1) = y[i], 此时
w
w
RWNAF 算法的取值范围 [−(2 −1),2 −1], 矛盾.
综上, 可知假设错误, 因此 OWNAF 生成的序列长度小于等于 RWNAF. 证毕.
我们基于 OpenSSL 实现了 OWNAF 和 RWNAF 序列生成算法, 针对不同的大数长度和窗口宽度进行 10 次
6