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

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

wJRF (k,l); /* 算法 12 */
8. 计算
9. T ← R;
10. for i = n−1 down to 0 by w do
w
11. T = [2 ]T ;
12. 根据窗口内的信息确定 i 1 ,i 2 ,...,i w 和 j 1 , j 2 ,..., j w 的取值;
13. T = T +T j 1 ,j 2 ,...,j w ;
i 1 ,i 2 ,...,i w
14. end for
15. return T −[t]Q−R.
( )
以 52 和 39, w = 2 为例, 此时它们的 wJRF 020201 , 此时的计算过程为:
表示为 (102020) 和
i 5 4 3 2 1 0
1 0 2 0 2 0
k i
0 2 0 2 0 −1
l i
T O [2]P+[2]Q+R O [12]P+[10]Q+R O [52]P+[39]Q+R
6D+3A 便完成了计算, 有效提
最终返回 T −[0]Q−R = [52]P+[39]Q, 与预期结果一致. 且通过窗口算法只需
高了多标量乘运算的效率.
3.5 wJRF 多标量乘算法分析
(1) 安全性分析
通过算法 12 生成了 k 和 l 的 wJRF 格式后, 计算多标量乘法 [k]P+[l]Q 时, 每次都只需要计算一次点加运算和
倍点运算, 实现了一致的点加-倍点标量乘算法, 达到了抗 SPA 攻击的效果. 除此之外, 由于每次算法中都引入了
R, 使得 DPA 攻击无法获取有效的能量曲线, 进而防御 DPA R 也使得多标量乘
一个随机掩码 攻击. 引入随机掩码
的计算过程中不存在坐标为 0 值的特殊点, 不使用零值寄存器, 进而防御 RPA 和 ZPA 攻击.
(2) 计算开销与存储开销分析
我们将算法 13 与已有的算法进行横向对比, 比对结果如表 5 所示, 算法 13 在与其他算法相比除了抗 SPA 攻
击的能力外, 还增加了对 DPA, RPA 和 ZPA 攻击的抵抗能力. 计算开销为 nD+⌈n/w⌉A, 相较已有算法的标量乘效
率有效提升, 有效提高了多标量乘运算的效率.

表 5 多标量乘算法横向对比

算法 预计算开销 多标量乘开销 抗SPA 抗DPA 抗RPA 抗ZPA
文献[13] 5 nD+nA √ × × ×
文献[14] 3 nD+nA √ × × ×
文献[15] 5 1.384nD+0.692nA √ × × ×
文献[17] 2 nD+nA √ × × ×
算法13 2 w+1 nD+⌈n/w⌉A √ √ √ √

4 总 结

本文研究了基于 wNAF 的标量乘算法 OWNAF, 基于 JRF 的标量乘算法和基于 wJRF 的多标量乘算法: OWNAF
算法相较于 RWNAF 算法在存储开销上有所增加, 但计算效率更高, 在抵御 SPA, DPA 等攻击的同时, 能够一定程
度抵御 Flush+Reload 攻击; 基于 wJRF 的多标量乘算法在付出一定预计算量的代价下能够有效提升多标量乘算法
的效率, 且能抵御 SPA, DPA 等攻击. 未来期待在这些算法的基础上更进一步地减少存储开销和提升计算效率, 推
动椭圆曲线标量乘和多标量乘算法的改进.