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

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

3.4 wJRF 多标量乘算法方案
定理 2 证明了 wJRF 存在唯一, 这样从最小有效位出发的变换, 可以得到相应的 wJRF 格式, 算法过程只需要
,
,
计算 [±2 w−1 ]P [λ]P 和 [ e λ]P 这 4 个点 ( λ = k +l mod 2 w−1 e λ = λ−2 w−1 mod 2 w−1 ), wJRF 的生成算法如算法 12.
算法 12. wJRF 生成算法.

输入: 一对整数 (k,l) 满足 k mod 2 w−1 ≡ 0 且 l mod 2 w−1 / ≡ 0;
,
:
输出: wJRF (k,l) (k n−1 ,...,k 0 ) (l n−1 ,...,l 0 ).
,
,
1. i ← 0 s ← k t ← l;
2. while s > 0 and t > 0 do
3. k i = s mod 2 w−1 , l i = t mod 2 w−1 ;
,
,
4. a = sgn(k i ) b = sgn(l i ) c = ((−((a == b)&1))&1); /* c = (a == b)?1 : 0 */
w
5. k i ← c·(a·2 +(1−2a)·k i−1 )+(1−c)·k i k i−1 ← k i−1 ;
,
e
6. l i ← c·(b·2 +(1−2b)·l i−1 )+(1−c)·l i l i−1 ← l i−1 ;
,
w
e
( )/ ( )/
7. s ← s−(1−c−2a·c)·k i +a·c·2 w−1 2 t ← t −(1−c−2b·c)·k i +b·c·2 w−1 2;
,
8. i ← i+1;
9. end while
10. k i+1 = sgn(s), l i+1 = 1− sgn(s); /* sgn 为符号函数 */
11. n ← i+1;
,
12. return (k n−1 ,...,k 0 ) (l n−1 ,...,l 0 ).
由于多标量乘法对标量随机分割整体开销较大, 因此通过随机掩码的方式来抵抗 DPA 等攻击: 计算
:
,
[k]P+[l]Q+R, 其中 R 是椭圆曲线上的随机点, 先计算 wJRF (k,l) (k n−1 ,...,k 0 ) (l n−1 ,...,l 0 ), 此时对 R 做如下变换:

R = (111...1)R (9)
{ }
,
,
其中, 1 = −1, 令 P i = [i]P−R Q i = [i]Q−R i ∈ ±1,±2,...,±2 w−1 . 将每个窗口的标量信息提前预计算, 进而减少标
wJRF (k,l) 中第 个非 0 j k i , 0 时, j = 0,
i
量乘过程中的点加运算次数. 设 下标对应的标量乘法值为 T , 即当
i
0 , 1 , 令:
i i
T = P k i , 反之 j = 1 T = Q l i

j 2
j 1
T j 1 ,j 2 ,...,j w = [2 w−1 ]T +[2 w−2 ]T +...+T j w (10)
i 1 ,i 2 ,...,i w i 1 i 2 i w
其中, i 1 ,i 2 ,...,i w 对应窗口长度为 w 的窗口中每列的非 0 值, 此时可通过对应的下标找到对应窗口的标量值, 其中
非 0 值等于 ±2 w−1 , 因此预计算表需要的存储大小为 2 w+1 . 基于 wJRF 的抗 DPA 多标量乘算法如算法 13.
算法 13. 基于 wJRF 的抗 DPA 多标量乘算法.
输入: 椭圆曲线上两点 P,Q, 窗口宽度 w, 一对整数 (k,l);
输出: [k]P+[l]Q.
1. t ← 0;
2. while k mod 2 w−1 ≡ 0 and l mod 2 w−1 ≡ 0 do
,
3. l ← l+1 t ← t +1;
4. end while
5. R = RandomPoint();
{
1
0
,
6. T = [i]P−R T = [i]Q−R i ∈ ±1,±2,...,±2 w−1 } ;
,
i i
[
j 2
j w
j 1
7. 预计算 T j 1 ,j 2 ,..., j w = [2 w−1 ]T +[2 w−2 ]T +...+T , i s ∈ ±2 w−1 ] , j s ∈ [0,1], s ∈ [1,2,...,w];
i 1 ,i 2 ,...,i w i 1 i 2 i w