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

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

6. else
7. R = R+[l i ]Q;
8. end if
9. end for
10. return R.

从算法 6 可知, 生成 k 和 l 的 JRF 格式后, 计算多标量乘法时, 可始终保证 k i 和 l i 其中一个为 ±1 而另一个为 0,
这样在第 2 步后的每轮迭代中都必然要计算一次点加运算和倍点运算, 实现了一致的点加-倍点 (double-and-add
always) 操作, 达到了抗 SPA 攻击的效果.
1.3 常见侧信道攻击及其防御
1999 年, Kocher 等人 [7] 指出一般的二进制标量乘算法是将乘法和加法转化为移位操作, 攻击者可以在每
一轮迭代中分析标量, 获取私密信息, 从而该计算方法不能抵抗侧信道攻击. 这是一种通过分析密码设备泄
露的边信道信息来推测秘钥的密码分析方法, 同时是目前最常见的密码算法攻击方式, 能通过加密设备在运
行过程中的边信道信息比如电压、功耗等的泄露来破解密码算法. 对于椭圆曲线标量乘算法, 常见的攻击
如下.
[7]
简单能量分析 (SPA) 攻击: 通过分析功耗曲线来获得密钥等私密信息. 例如, 当使用 double-and-add 算法进
行标量乘时, 如果攻击者能够从功耗曲线中区分点加运算和倍点运算, 就可以获取标量的值. 主要防护措施有: 原
子块处理, 一致的点加-倍点操作等.
[7]
差分能量分析 (DPA) 攻击: 使用统计技术从测量中获取私密信息. 攻击者通过为密码设备设置多个输入点,
记录并存储随时间变化的侧信道测量值, 通过分析大量功耗曲线的相对差异进而推测算法密钥, 主要防护措施有:
基点掩码, 随机化投影坐标, 随机密钥分割等.
修正能量分析 (refined power analysis, RPA) [18] 攻击: 利用特殊点 (x,0) 或 (0,y) 攻击随机化投影坐标的方法, 进
而使攻击者可以通过 DPA 攻击获取密钥, 相较 DPA 对设备的要求也更高更复杂. 主要防护措施有: 基点掩码, 随
机密钥分割等.
零值点能量分析 (zero power analysis, ZPA) [19] 攻击: 这种攻击不依赖于功耗分析, 而是通过分析目标设备在不
同操作状态下的电磁辐射或其他物理特性来获取敏感信息. ZPA 可以在设备处于低功耗或零功耗状态时进行攻
击, 相对于 DPA 更具挑战性, 但相较 DPA 对设备的要求也更高更复杂. 主要防护措施有: 基点掩码, 随机密钥分
割等.
Flush+Reload 攻击 [20] : 该方法由 Yarom 等人在 2014 年首次提出. 其原理是利用现代处理器的缓存机制. 攻击
者首先通过特定的指令将目标设备中的某些数据从缓存中清除 (Flush), 然后监视缓存中的访问情况, 当被攻击者
再次访问这些数据时, 攻击者可以通过观察访问时间的差异来推断出数据的敏感信息 (Reload). 通过不断重复
Flush 和 Reload 的过程, 攻击者可以逐渐还原目标设备中的数据, 包括密钥等敏感信息, 需要针对具体的攻击方式
决定防御措施.

2 基于 OWNAF 的安全高效标量乘算法方案

考虑在 wNAF 和 RWNAF 算法现有的思路及效率基础上, 通过调整 NAF 序列的生成方式来抵御侧信道攻击,
避免直接计算 k 的 NAF 形式来直接得出标量乘运算结果, 实现安全高效的标量乘算法, 该算法分为以下几个阶段.
2.1 预计算阶段
首先, 在 RWNAF 算法的基础上, 对算法中非 0 值的取值范围进行调整, 同时通过一定的处理规避可能存在子
序列中全为 0 的情况. 新的 OWNAF 算法如算法 7 所示.