一种低复杂度的改进wNAF标量乘算法

赵石磊; 杨晓秋; 刘志伟; 于斌; 黄海

doi:10.12263/DZXB.20211016

您当前的位置：

首页 >

文章列表页 >

一种低复杂度的改进wNAF标量乘算法

学术论文 | 更新时间：2025-12-08

- 一种低复杂度的改进wNAF标量乘算法
- An Improved wNAF Scalar-Multiplication Algorithm with Low Computational Complexity
- 电子学报 2022年50卷第4期页码：977-983
- 作者机构：
  
  哈尔滨理工大学计算机科学与技术学院，黑龙江哈尔滨 150080
- 作者简介：
  
  [ "赵石磊男，1979年出生，黑龙江肇源人.博士，硕士生导师.主要研究方向为信息安全、可重构计算、IC设计、VLSI数字信号处理. E-mail: zhaosl@hrbust.edu.cn" ]
  [ "杨晓秋女，1997年出生，黑龙江省鹤岗人.现为哈尔滨理工大学计算机科学与技术学院硕士生.主要研究方向为信息安全、密码算法.E-mail: yangxq2022@163.com" ]
  [ "刘志伟男，1987年出生，黑龙江哈尔滨人.哈尔滨理工大学讲师、博士生.主要研究方向为可重构计算、高速密码算法、并行加密技术、密码芯片的安全设计等.E-mail: zwliu@hrbust.edu.cn" ]
  [ "于斌男，1984年出生，黑龙江饶河人.硕士，哈尔滨理工大学讲师.主要研究方向为密码算法、密码芯片设计和数字集成电路设计等.E-mail: yubin@hrbust.edu.cn" ]
  [ "黄海（通讯作者）男，1982年出生，内蒙古巴彦淖尔人.博士，教授，博士生导师，CCF高级会员.主要研究方向为信息安全、可重构计算、集成电路设计.E-mail: ic@hrbust.edu.cn" ]
- 基金信息：
  
  国家重点研发计划“光电子与微电子器件及集成”重点专项子课题(2018YFB2202100);黑龙江省自然科学基金优秀青年项目(YQ2019F010);黑龙江省普通高校基本科研业务费专项资金资助(2019KYYWF0214)
- DOI：10.12263/DZXB.20211016
  中图分类号： TN918.1;
- 收稿：2021-08-01，
  
  修回：2022-01-23，
  
  纸质出版：2022-04-25
- 稿件说明：
移动端阅览
赵石磊,杨晓秋,刘志伟等.一种低复杂度的改进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 .

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

暂无数据