电子学报 ›› 2022, Vol. 50 ›› Issue (4): 977-983.DOI: 10.12263/DZXB.20211016

• 学术论文 • 上一篇    下一篇

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

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

  1. 哈尔滨理工大学计算机科学与技术学院,黑龙江 哈尔滨 150080
  • 收稿日期:2021-08-01 修回日期:2022-01-23 出版日期:2022-04-25
    • 作者简介:
    • 赵石磊 男,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)

An Improved wNAF Scalar-Multiplication Algorithm with Low Computational Complexity

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

  1. School of Computer Science and Technology, Harbin University of Science and Technology, Harbin, Heilongjiang 150080, China
  • Received:2021-08-01 Revised:2022-01-23 Online:2022-04-25 Published:2022-04-25
    • Supported by:
    • National Key Research and Development Program of China Microelectronic and Optoelectronic Devices and Integration Key Project subject (2018YFB2202100); Excellent Youth Program of Natural Science Foundation of Heilongjiang Province (YQ2019F010); Fundamental Research Funds for Colleges and Universities of Heilongjiang Province (2019KYYWF0214)

摘要:

在物联网等资源受限的环境中,低计算复杂度、存储空间占用少的标量乘算法尤为重要.为了降低标量乘的计算复杂度,本文采用有符号的窗口非相邻算法(window width-Non-Adjacent Form,wNAF)生成标量k的wNAF链;用2n替换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.

Key words: scalar-multiplication, windowed non-adjacent form, addition chains

中图分类号: