An Improved wNAF Scalar-Multiplication Algorithm with Low Computational Complexity

ZHAO Shi-lei; YANG Xiao-qiu; LIU Zhi-wei; YU Bin; HUANG Hai

doi:10.12263/DZXB.20211016

您当前的位置：

首页 >

文章列表页 >

An Improved wNAF Scalar-Multiplication Algorithm with Low Computational Complexity

PAPERS | 更新时间：2025-12-08

- An Improved wNAF Scalar-Multiplication Algorithm with Low Computational Complexity
- ACTA ELECTRONICA SINICA Vol. 50, Issue 4, Pages: 977-983(2022)
- 作者机构：
  
  哈尔滨理工大学计算机科学与技术学院，黑龙江哈尔滨 150080
- 作者简介：
- 基金信息：
- DOI：10.12263/DZXB.20211016
  CLC： TN918.1;
- Received：01 August 2021，
  
  Revised：2022-01-23，
  
  Published：25 April 2022
- 稿件说明：
移动端阅览
赵石磊,杨晓秋,刘志伟等.一种低复杂度的改进wNAF标量乘算法[J].电子学报,2022,50(04):977-983.

ZHAO Shi-lei,YANG Xiao-qiu,LIU Zhi-wei,et al.An Improved wNAF Scalar-Multiplication Algorithm with Low Computational Complexity[J].ACTA ELECTRONICA SINICA,2022,50(04):977-983.
赵石磊,杨晓秋,刘志伟等.一种低复杂度的改进wNAF标量乘算法[J].电子学报,2022,50(04):977-983. DOI： 10.12263/DZXB.20211016.

ZHAO Shi-lei,YANG Xiao-qiu,LIU Zhi-wei,et al.An Improved wNAF Scalar-Multiplication Algorithm with Low Computational Complexity[J].ACTA ELECTRONICA SINICA,2022,50(04):977-983. DOI： 10.12263/DZXB.20211016.

摘要

在物联网等资源受限的环境中，低计算复杂度、存储空间占用少的标量乘算法尤为重要.为了降低标量乘的计算复杂度，本文采用有符号的窗口非相邻算法（window width-Non-Adjacent Form，wNAF）生成标量

http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=39122670&type=

http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=39122665&type=

1.43933344

2.28600001

的wNAF链；用

http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=39122679&type=

http://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=39122675&type=

2.53999996

2.20133328

替换wNAF链中的奇数，替换后的差值则通过构造微小的加法链进行弥补.该算法能降低预计算点的个数，解决wNAF标量乘不适用于窗口宽度较大的问题.相较于wNAF算法、swNAF算法和基于素数预计算的算法，当窗口宽度为11时，该算法只需要12个预计算点，预计算点分别减少了98.83%，96.49%和94.42%，标量乘计算复杂度优化了78.23%，68.94%和43.63%.

Abstract

It is very important that scalar multiplication algorithm has low computational complexity and less storage space in the resource constrained environment such as the Internet of things. In order to reduce the complexity of scalar multiplication

wNAF is used to generate the wNAF chain of scalar k; it replaces odd number with power of 2

and makes up the difference between power of 2 and odd by building the addition chain. At the same time

the algorithm reduces the number of precomputed points

and solves the problem that wNAF scalar multiplication is not suitable for large window width. Compared the wNAF

swNAF

and precomputation algorithm based prime

only 12 are needed to store the precomputed points

and the number of precomputed points are optimized by 98.83%

96.49%

and 94.42%

and the scalar multiplication calculation stage are optimized by 78.23%

68.94%

and 43.63% when the window width is 11.

关键词

Keywords

references

张亮 . 改进的基于整数拆分形式标量乘快速算法 [J]. 中国电子科学研究院学报 , 2016 , 11 ( 5 ): 490 - 494 .

ZHANG L . Improved fast scalar multiplication algorithm based on signed integer splitting form [J]. Journal of China Academy of Electronics and Information Technology , 2016 , 11 ( 5 ): 490 - 494 . (in Chinese)

ISLAM M M , HOSSAIN M S , HASAN M K , et al . FPGA implementation of high-speed area-efficient processor for elliptic curve point multiplication over prime field [J]. IEEE Access , 2019 , 7 : 178811 - 178826 .

KHLEBORODOV D . Fast elliptic curve point multiplication based on binary and binary non-adjacent scalar form methods [J]. Advances in Computational Mathematics , 2018 , 44 ( 4 ): 1275 - 1293 .

徐明 , 史量 . 基于伪四维投射坐标的多基链标量乘法 [J]. 通信学报 , 2018 , 39 ( 5 ): 74 - 84 .

XU M , SHI L . Pseudo 4D projective coordinate-based multi-base scalar multiplication [J]. Journal on Communications , 2018 , 39 ( 5 ): 74 - 84 . (in Chinese)

OKEYA K , SCHMIDT-SAMOA K , SPAHN C , et al . Signed binary representations revisited [C]// Annual International Cryptology Conference . Berlin : Springer , 2004 : 123 - 139 .

李忠 , 彭代渊 . 基于滑动窗口技术的快速标量乘法 [J]. 计算机科学 , 2012 , 39 ( 6A ): 54 - 56, 64 .

LI Z , PENG D Y . Fast scalar multiplication based on sliding window technology [J]. Computer Science , 2012 , 39 ( 6A ): 54 - 56, 64 . (in Chinese)

ALIMORADI R , ARKIAN H R , RAZAVIAN S M J , et al . Scalar multiplication in elliptic curve libraries [J]. Journal of Discrete Mathematical Sciences and Cryptography , 2021 , 24 ( 3 ): 657 - 666 .

LIU S G , QI G L , WANG X A . Fast and secure elliptic curve scalar multiplication algorithm based on a kind of deformed fibonacci-type series [C]// 2015 10th International Conference on P2P, Parallel, Grid, Cloud and Internet Computing (3PGCIC) . Xi'an : IEEE , 2015 : 398 - 402 .

HUANG H , NA N , XING L , et al . An improved wNAF scalar-multiplication algorithm with low computational complexity by using prime precomputation [J]. IEEE Access , 2021 , 9 : 31546 - 31552 .

史量 , 徐明 . DWNAF: 带门限的动态窗口的NAF标量乘法 [J]. 计算机科学 , 2017 , 44 ( 10 ): 159 - 164 .

SHI L , XU M . DWNAF: A dynamic window NAF scalar multiplication with threshold [J]. Computer Science , 2017 , 44 ( 10 ): 159 - 164 . (in Chinese)

LIU S G , SUN X J . A fast scalar multiplication algorithm based on alternate-zeckendorf representation [J]. International Journal of Network Security , 2018 , 20 ( 5 ): 931 - 937 .

Khleborodov D . Fast elliptic curve point multiplication based on window Non-Adjacent Form method [J]. Applied Mathematics and Computation , 2018 , 334 : 41 - 59 .

ZHANG Z B , WU L J , MU Z L , et al . A novel template attack on wNAF algorithm of ECC [C]// 2014 Tenth International Conference on Computational Intelligence and Security . Beijing : IEEE , 2014 : 671 - 675 .

DANGER J L , GUILLEY S , HOOGVORST P , et al . Improving the Big Mac Attack on Elliptic Curve Cryptography [M]. Berlin : Springer , 2016 : 374 - 386 .

DOU Y Q , WENG J , MA C G , et al . Fast scalar multiplication algorithm using constrained triple-base number system and its applications [C]// 2015 10th International Conference on Broadband and Wireless Computing, Communication and Applications(BWCCA) . Zhengzhou : IEEE , 2015 : 426 - 431 .

CHUDNOVSKY D V , CHUDNOVSKY G V . Sequences of numbers generated by addition in formal groups and new primality and factorization tests [J]. Advances in Applied Mathematics , 1986 , 7 ( 4 ): 385 - 434 .

WANG W B , FAN S Q . Attacking OpenSSL ECDSA with a small amount of side-channel information [J]. Science China Information Sciences , 2017 , 61 ( 3 ): 1 - 14 .

RASMI M , SOKHON A A , SH M , et al . A survey on single scalar point multiplication algorithms for Elliptic curves over Prime fields [J]. IOSR Journal of Computer Enginnering , 2016 , 18 ( 2 ): 31 - 47 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

No data

Related Author

Shi-lei ZHAO

Xiao-qiu YANG

Zhi-wei LIU

Bin YU

Hai HUANG

Related Institution

School of Computer Science and Technology， Harbin University of Science and Technology

⁰