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

doi:10.12263/DZXB.20211016

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

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

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

哈尔滨理工大学计算机科学与技术学院，黑龙江哈尔滨 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

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)

摘要/Abstract

摘要：

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

中图分类号:

TN918.1

赵石磊, 杨晓秋, 刘志伟, 等. 一种低复杂度的改进wNAF标量乘算法[J]. 电子学报, 2022, 50(4): 977-983.

Shi-lei ZHAO, Xiao-qiu YANG, Zhi-wei LIU, et al. An Improved wNAF Scalar-Multiplication Algorithm with Low Computational Complexity[J]. Acta Electronica Sinica, 2022, 50(4): 977-983.

图/表 6

表1 预计算点及个数

窗口宽度	预计算点	预计算点的个数
5	${20 P, 21 P, 22 P, ⋯, 25 P}$	6
6	${20 P, 21 P, 22 P, ⋯, 26 P}$	7
…	…	…
n	${20 P, 21 P, 22 P, ⋯, 2 n + 1 P}$	n+1

表1 预计算点及个数

窗口宽度	预计算点	预计算点的个数
5	${20 P, 21 P, 22 P, ⋯, 25 P}$	6
6	${20 P, 21 P, 22 P, ⋯, 26 P}$	7
…	…	…
n	${20 P, 21 P, 22 P, ⋯, 2 n + 1 P}$	n+1

表2 本文预计算点与wNAF预计算点之间的差值

窗口宽度	预计算点之间的差值
5	${1 P, 3 P, 5 P, 7 P}$
6	${1 P, 3 P, 5 P, 7 P, 9 P, ⋯, 15 P}$
…	…
n	${1 P, 3 P, 5 P, 7 P, 9 P, ⋯, (2 n - 2 - 1) P}$

表2 本文预计算点与wNAF预计算点之间的差值

窗口宽度	预计算点之间的差值
5	${1 P, 3 P, 5 P, 7 P}$
6	${1 P, 3 P, 5 P, 7 P, 9 P, ⋯, 15 P}$
…	…
n	${1 P, 3 P, 5 P, 7 P, 9 P, ⋯, (2 n - 2 - 1) P}$

图1 低复杂度的改进wNAF标量乘算法在不同窗口下的计算复杂度分析

表3 预计算点比较

窗口宽度	本文算法	wNAF算法	swNAF算法	基于素数预计算算法	与wNAF算法相比减少的百分比	与swNAF算法相比减少的百分比	与素数预计算相比减少的百分比
5	6	16	6	11	62.5%	0.0%	45.45%
6	7	32	11	18	78.13%	36.36%	61.11%
7	8	64	22	31	87.5%	63.63%	74.19%
8	9	128	43	54	92.97%	79.1%	83.33%
9	10	256	86	97	96.09%	88.37%	89.69%
10	11	512	171	140	97.85%	93.57%	92.14%
11	12	1 024	342	215	98.83%	96.49%	94.42%

表4 预计算点所需的模乘次数比较

窗口宽度	预计算所需模乘次数				模乘次数减少比率/%
窗口宽度	本文算法	wNAF算法	swNAF算法	基于素数预计算算法	wNAF算法	swNAF算法	基于素数预计算算法
5	48	266	161	186	81.95	70.19	74.19
6	53	522	313	266	89.85	83.07	80.08
7	62	1 304	648	522	95.25	90.43	88.12
8	71	2 058	1 286	842	96.55	94.48	91.57
9	80	4 106	2 593	1 386	98.05	96.91	94.23
10	88	7 792	5 177	2 608	98.87	98.30	96.63
11	97	15 574	10 376	4 463	99.38	99.07	97.83

表5 4种算法总体计算复杂度对比

算法	标量 $k$ 的长度	窗口宽度	算数运算阶段所需模乘次数	标量乘所需模乘次数	标量乘减少比率/%	算法	标量 $k$ 的长度	窗口宽度	算术运算阶段所需模乘次数	标量乘所需模乘次数	标量乘减少比率/%
wNAF算法	256	8	3 015	5 073	20.34	基于素数预计算算法	256	8	3 110	3 952	-2.25
	384		4 523	6 581	9.0%		384		4 660	5 502	-8.83
	521		6 136	8 194	1.44		521		6 320	7 162	-11.37
	256	9	2 764	6 870	41.48		256	9	3 025	4 411	8.86
	384		4 249	8 355	28.40		384		4 607	5 993	0.18
	521		5 838	9 944	18.64		521		6 317	7 703	-5.02
	256	10	2 113	9 905	59.33		256	10	2 688	5 296	23.94
	384		3 579	11 371	47.85		384		4 032	6 640	10.69
	521		5 148	12 940	37.81		521		5 466	8 074	0.32
	256	11	2 901	18 475	78.23		256	11	2 672	7 135	43.63
	384		4 352	19 926	70.35		384		4 000	8 463	30.19
	521		5 905	21 479	62.63		521		5 418	9 881	18.77
swNAF算法	256	8	2 678	3 964	-1.91	本文算法	256	8	3 971	4 041
	384		4 018	5 304	-11.42		384		5 918	5 988
	521		5 436	6 722	-16.77		521		8 005	8 076
	256	9	2 633	5 226	23.08		256	9	3 940	4 020
	384		3 957	6 550	8.67		384		5 903	5 982
	521		5 360	7 953	-1.72		521		8 020	8 090
	256	10	2 603	7 780	48.23		256	10	3 940	4 028
	384		3 896	9 073	34.64		384		5 842	5 930
	521		5 284	10 461	23.07		521		7 960	8 048
	256	11	2 572	12 948	68.94		256	11	3 925	4 022
	384		3 865	14 241	58.51		384		5 812	5 908
	521		5 238	15 614	48.60		521		7 929	8 026

表5 4种算法总体计算复杂度对比

算法	标量 $k$ 的长度	窗口宽度	算数运算阶段所需模乘次数	标量乘所需模乘次数	标量乘减少比率/%	算法	标量 $k$ 的长度	窗口宽度	算术运算阶段所需模乘次数	标量乘所需模乘次数	标量乘减少比率/%
wNAF算法	256	8	3 015	5 073	20.34	基于素数预计算算法	256	8	3 110	3 952	-2.25
	384		4 523	6 581	9.0%		384		4 660	5 502	-8.83
	521		6 136	8 194	1.44		521		6 320	7 162	-11.37
	256	9	2 764	6 870	41.48		256	9	3 025	4 411	8.86
	384		4 249	8 355	28.40		384		4 607	5 993	0.18
	521		5 838	9 944	18.64		521		6 317	7 703	-5.02
	256	10	2 113	9 905	59.33		256	10	2 688	5 296	23.94
	384		3 579	11 371	47.85		384		4 032	6 640	10.69
	521		5 148	12 940	37.81		521		5 466	8 074	0.32
	256	11	2 901	18 475	78.23		256	11	2 672	7 135	43.63
	384		4 352	19 926	70.35		384		4 000	8 463	30.19
	521		5 905	21 479	62.63		521		5 418	9 881	18.77
swNAF算法	256	8	2 678	3 964	-1.91	本文算法	256	8	3 971	4 041
	384		4 018	5 304	-11.42		384		5 918	5 988
	521		5 436	6 722	-16.77		521		8 005	8 076
	256	9	2 633	5 226	23.08		256	9	3 940	4 020
	384		3 957	6 550	8.67		384		5 903	5 982
	521		5 360	7 953	-1.72		521		8 020	8 090
	256	10	2 603	7 780	48.23		256	10	3 940	4 028
	384		3 896	9 073	34.64		384		5 842	5 930
	521		5 284	10 461	23.07		521		7 960	8 048
	256	11	2 572	12 948	68.94		256	11	3 925	4 022
	384		3 865	14 241	58.51		384		5 812	5 908
	521		5 238	15 614	48.60		521		7 929	8 026

参考文献 18

1	张亮. 改进的基于整数拆分形式标量乘快速算法[J]. 中国电子科学研究院学报, 2016, 11(5): 490-494.
	ZHANGL. 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)
2	ISLAMM M, HOSSAINM S, HASANM 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.
3	KHLEBORODOVD. 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.
4	徐明, 史量. 基于伪四维投射坐标的多基链标量乘法[J]. 通信学报, 2018, 39(5): 74-84.
	XUM, SHIL. Pseudo 4D projective coordinate-based multi-base scalar multiplication[J]. Journal on Communications, 2018, 39(5): 74-84. (in Chinese)
5	OKEYAK, SCHMIDT-SAMOAK, SPAHNC, et al. Signed binary representations revisited[C]//Annual International Cryptology Conference. Berlin: Springer, 2004: 123-139.
6	李忠, 彭代渊. 基于滑动窗口技术的快速标量乘法[J]. 计算机科学, 2012, 39(6A): 54-56, 64.
	LIZ, PENGD Y. Fast scalar multiplication based on sliding window technology[J]. Computer Science, 2012, 39(6A): 54-56, 64. (in Chinese)
7	ALIMORADIR, ARKIANH R, RAZAVIANS M J, et al. Scalar multiplication in elliptic curve libraries[J]. Journal of Discrete Mathematical Sciences and Cryptography, 2021, 24(3): 657-666.
8	LIUS G, QIG L, WANGX 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.
9	HUANGH, NAN, XINGL, et al. An improved wNAF scalar-multiplication algorithm with low computational complexity by using prime precomputation[J]. IEEE Access, 2021, 9: 31546-31552.
10	史量, 徐明. DWNAF: 带门限的动态窗口的NAF标量乘法[J]. 计算机科学, 2017, 44(10): 159-164.
	SHIL, XUM. DWNAF: A dynamic window NAF scalar multiplication with threshold[J]. Computer Science, 2017, 44(10): 159-164. (in Chinese)
11	LIUS G, SUNX J. A fast scalar multiplication algorithm based on alternate-zeckendorf representation[J]. International Journal of Network Security, 2018, 20(5): 931-937.
12	KhleborodovD. Fast elliptic curve point multiplication based on window Non-Adjacent Form method[J]. Applied Mathematics and Computation, 2018, 334: 41-59.
13	ZHANGZ B, WUL J, MUZ 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.
14	DANGERJ L, GUILLEYS, HOOGVORSTP, et al. Improving the Big Mac Attack on Elliptic Curve Cryptography[M]. Berlin: Springer, 2016: 374- 386.
15	DOUY Q, WENGJ, MAC 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.
16	CHUDNOVSKYD V, CHUDNOVSKYG 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.
17	WANGW B, FANS Q. Attacking OpenSSL ECDSA with a small amount of side-channel information[J]. Science China Information Sciences, 2017, 61(3): 1-14.
18	RASMIM, SOKHONA 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.

[1]	翁江, 姬伟峰, 吴玄, 李映岐, 张林锋, 孟浩. Jacobi Quartic曲线上GLV/GLS标量乘算法[J]. 电子学报, 2021, 49(9): 1783-1789.
[2]	庞世春;刘淑芬;从福仲;姚志林. 一种Montgomery型椭圆曲线的高效标量乘算法[J]. 电子学报, 2011, 39(4): 865-868.
[3]	王念平. 一种新的五元联合稀疏形式表示算法及其应用[J]. 电子学报, 2011, 39(1): 114-118.
[4]	鲍皖苏;陈辉. 基于双基表示的并列点乘算法[J]. 电子学报, 2009, 37(4): 873-876.
[5]	游林. 一类超椭圆曲线上的快速除子标量乘[J]. 电子学报, 2008, 36(10): 2049-2054.
[6]	刘铎;戴一奇. 优化扩域上椭圆曲线标量乘的一个新算法[J]. 电子学报, 2005, 33(8): 1451-1456.
[7]	唐文;唐礼勇;陈钟. 基于Markov链的椭圆曲线标量乘法算法性能分析[J]. 电子学报, 2004, 32(11): 1778-1781.
[8]	白国强;周涛;陈弘毅. 一类安全椭圆曲线的选取及其标量乘法的快速计算[J]. 电子学报, 2002, 30(11): 1654-1657.

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

An Improved wNAF Scalar-Multiplication Algorithm with Low Computational Complexity

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 6

参考文献 18

相关文章 8

编辑推荐

Metrics