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

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

表 2 NAF 标量乘算法计算开销比较

算法 预计算开销 t(E) 标量乘开销 t(s) 总开销
⌉
⌈
′
′
RWNAF [10] wD+(2 w−1 +1)A n D+ n /w A
t(E)+t(s)
w
OWNAF (本文) wD+(2 −1−w)A nD+⌈n/w⌉A

可以看出, 在预计算阶段 OWNAF 算法无需额外对随机掩码进行处理, 但由于需要对 k 进行分割, 需要额外的
预计算点用于后续计算. 在标量乘开销方面, 由于 OWNAF 算法生成的 NAF 序列的平均长度 n 小于 RWNAF 算
法生成的 NAF 序列的平均长度 n , 因此在标量乘方面的开销有了一定的优势.
′
为了进一步验证本文算法的性能, 本文在 64 位 Windows 11 操作系统上使用 C++语言和 OpenSSL 库实现上
述算法, 实验环境中处理器型号为 Intel(R) Core(TM) i9-13900H 处理器, 主频为 2.60 GHz. 实验环境如表 3 所示.

表 3 实验环境

实验环境 配置
操作系统 Windows 11
CPU型号 i9-13900H (2.60 GHz)
使用语言 C++
运行内存 16 GB
代码库版本 OpenSSL 3.2.0

我们使用随机生成器生成 128, 256 和 512 位的随机整数, OpenSSL 中椭圆曲线的参数分别设置为 NID_
secp128r1, NID_sm2 和 NID_secp521r1 (3 类不同安全级别的椭圆曲线). 针对不同的窗口长度, 分别使用 RWNAF
和 OWNAF 算法进行 10 次标量乘运算, 最终标量乘效率比对结果如表 4 所示. 数值实验结果表明, 基于 OWNAF 的
6
标量乘法相较基于 RWNAF 的标量乘法实现效率提升了 2%–5% 左右, 在保证安全的基础上提升了标量乘算法的
效率.

表 4 NAF 标量乘算法效率比较

大数长度 (bit) 窗口宽度 RWNAF算法耗时 (ms) OWNAF算法耗时 (ms) 加速比 (%)
128 2 0.332 667 0.315 723 5.09
128 3 0.287 894 0.276 295 4.03
128 4 0.264 948 0.254 496 3.95
128 5 0.259 858 0.247 743 4.66
128 6 0.240 851 0.228 241 5.24
256 2 0.668 457 0.645 516 3.43
256 3 0.572 802 0.553 764 3.32
256 4 0.524 114 0.509 962 2.70
256 5 0.496 005 0.479 385 3.35
256 6 0.486 888 0.468 379 3.80
512 2 1.376 3 1.334 23 3.06
512 3 1.151 38 1.127 11 2.11
512 4 1.059 36 1.029 46 2.82
512 5 0.995 034 0.968 719 2.64
512 6 0.945 202 0.921 907 2.46

3 基于 wJRF 的多标量乘算法方案

3.1 JRF 标量乘算法方案
n−1 n−1
∑ ∑
k = k +1 = 2 + i k 和 的 l JRF 格式将非常简单, 此时
n
注意到当 l = k +1 时, 假设 k i, 有 (k i −1)2 , 计算
i=0 i=0
有算法 10.