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

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
2025,36(10):4542−4557 [doi: 10.13328/j.cnki.jos.007301] [CSTR: 32375.14.jos.007301] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563

*
基于两种新标量表示的安全高效标量乘算法

程 石, 胡 志, 陶 铮

(中南大学 数学与统计学院, 湖南 长沙 410083)
通信作者: 胡志, E-mail: huzhi_math@csu.edu.cn

摘 要: 标量乘法是传统椭圆曲线密码 (ECC) 的核心运算. 标量表示决定了标量乘法算法中的迭代方式, 进而直接
影响算法的安全性和效率. 提出两种新的标量表示算法: 一种称为规则窗口非相邻算法 (ordered window width non-
adjacent form, OWNAF), 它将传统的窗口非相邻算法与随机密钥分割处理相结合, 在提升计算效率的同时可以抵
抗能量分析攻击; 另一种称为窗口联合正则形式 (window joint regular form, wJRF), 它由传统的联合正则形式改进
而来, 适用于多标量乘算法, 与已有算法相比, 在减少基础计算量的同时有着更好的安全性.
关键词: 标量乘算法; 侧信道攻击; 窗口非相邻形式; 联合正则形式
中图法分类号: TP301

中文引用格式: 程石, 胡志, 陶铮. 基于两种新标量表示的安全高效标量乘算法. 软件学报, 2025, 36(10): 4542–4557. http://www.jos.
org.cn/1000-9825/7301.htm
英文引用格式: Cheng S, Hu Z, Tao Z. Safe and Efficient Scalar Multiplication Algorithms Based on Two New Scalar Representations.
Ruan Jian Xue Bao/Journal of Software, 2025, 36(10): 4542–4557 (in Chinese). http://www.jos.org.cn/1000-9825/7301.htm

Safe and Efficient Scalar Multiplication Algorithms Based on Two New Scalar Representations

CHENG Shi, HU Zhi, TAO Zheng
(School of Mathematics and Statistics, Central South University, Changsha 410083, China)
Abstract: Scalar multiplication is the core operation in traditional elliptic curve cryptography (ECC). Scalar representations determine the
iterations in scalar multiplication algorithms, which directly affect the security and efficiency of the algorithms. This study proposes two
new scalar representation algorithms. One algorithm is ordered window width non-adjacent form (OWNAF) which combines traditional
window non-adjacent form with random key segmentation and can resist energy analysis attacks while yielding better efficiency. The other
is called window joint regular form (wJRF), which is improved from the traditional joint regular form. The wJRF algorithm is applicable
to multi-scalar multiplication algorithms, which can reduce computational costs and ensure sound security compared with the existing
algorithms.
Key words: scalar multiplication algorithm; side channel attack; window non-adjacent form; joint regular form
[2]
椭圆曲线密码 (ECC) 算法作为一种非对称密码体制算法, 自 1985 年由 Millerl 和 [1] Koblitz 分别独立地提出
以来, 已被广泛地应用于保护网络空间安全. 特别地, 由于 ECC 具有较高的安全等级和较小的密钥长度等特点, 十
分适合应用在智能卡等存储资源受限的环境. 椭圆曲线标量乘算法是椭圆曲线密码的核心运算, 其实现直接影响
密码系统的效率和安全性. 随着侧信道攻击技术的发展, 传统的标量乘算法如 wNAF 算法 [3] 等逐渐显露出安全隐
患, 会在使用过程中暴露一定的侧信道信息, 被攻击者加以利用. 因此, 实现高效安全的椭圆曲线标量乘算法成为
椭圆曲线密码中的重要研究问题.

椭圆曲线标量乘运算通常表示为 [k]P = P+ P+...+ P, 其中 k 是一个整数, P 是椭圆曲线上的点. 标量乘运算
又被称为点乘运算, 由点加和倍点两种运算交替实现. 而点加、倍点运算最终由有限域的各种模运算完成. 因此,

* 基金项目: 国家自然科学基金 (61972420); 湖南省自然科学基金 (2020JJ3050)
收稿时间: 2024-06-06; 修改时间: 2024-08-27; 采用时间: 2024-10-08; jos 在线出版时间: 2025-01-24
CNKI 网络首发时间: 2025-01-26