引用格式：吴昆，胡现刚，张学超，等.椭圆曲线标量乘高效方案设计［J］.网络安全与数据治理，2024，43（8）：28-34.
引言
相比RSA等算法，ECC的计算量和密钥长度已经有了很大的降低，但是它的数学结构仍较复杂，对于一些计算能力和存储资源受限的应用场景如无线传感器网络（Wireless Sensor Network，WSN）来说，算法所需的计算时间和计算量会极大地缩短网络的生命周期［1］。在ECC密码体制中，标量乘（Q=kP）是算法安全性的关键，其运算速度从整体上决定了算法的执行效率［2］。因此，对标量乘法进行轻量化改进，将显著减少ECC密码方案的资源消耗。
目前，对标量乘的优化主要集中在两方面，一是对算法本身进行设计，以减少点加和倍点的运算次数，如Montgomery算法［3］及其改进算法［4-5］，基于非相邻形式（Non-Adjacent Form，NAF）标量乘快速算法［6］及其改进方案［7-8］。二是对底层域运算进行改进，如文献［9］通过对多项式乘法和模约减等域运算进行合理优化设计，使得基于二进制域Koblitz曲线的标量乘算法比素数域上计算速度更快、效率更高；文献［10］针对ATmega128微控制器的特点，对有限域上平方和乘法运算进行了优化；文献［11］提出使用最优素数域（OPF）作为底层代数结构；文献［12］提出了一种适用于MICAz电机特点的标量乘计算方案；文献［13］利用优化的掩码操作数技术进行模块加法和减法，以减少掩码计算的次数和延迟；文献［14］提出了一种基于乘法器编码的多项式乘法方法。
结合以上思想，本文以传感器节点中常用的8 bit ATmega128芯片为目标平台，通过对二进制域上ECC标量乘法底层的域运算进行研究，针对乘法运算，提出一种联合区块相乘的思想，并进一步设计出3级Karatsuba乘法算法；针对减法运算，通过将减法运算与模运算相结合，提出一种模快速约减算法；针对模平方运算，通过预处理的方式建立查找表，并结合模运算同时处理，提出一种快速模平方算法；针对逆运算，结合扩展Euclideam算法，提出一种求模逆算法；最后，基于Montgomery算法设计了二进制域上的标量乘快速实现方案。理论和实验分析表明，本文方案减少了计算过程的基本运算和内存读写次数，提高了标量乘法的计算效率。
本文详细内容请下载：
http://www.chinaaet.com/resource/share/2000006102
作者信息：
吴昆1，胡现刚2，张学超3，汪晓睿1
(1.91977部队,北京100071;
2.南部战区海军参谋部，广东湛江524000;
3.中央军委政法委，北京100000)
