Jacobi Quartic曲线上GLV/GLS标量乘算法

doi:10.12263/DZXB.20191005

电子学报 ›› 2021, Vol. 49 ›› Issue (9): 1783-1789.DOI: 10.12263/DZXB.20191005

Jacobi Quartic曲线上GLV/GLS标量乘算法

翁江¹^,², 姬伟峰¹, 吴玄¹, 李映岐¹, 张林锋³, 孟浩³

^1.西安电子科技大学网络与信息安全学院, 陕西西安 710071
^2.空军工程大学信息与导航学院, 陕西西安 710077
^3.北京市海淀区复兴路14号院10分队, 北京 100089

收稿日期:2019-09-03 修回日期:2021-01-24 出版日期:2021-10-21
- 作者简介:
- 翁　江　男，1986年3月出生，陕西西安人. 现为空军工程大学信息与导航学院讲师，主要研究方向为网络密码和椭圆曲线密码. E-mail: wengjiang858@163.com
- 基金资助:
- 国家自然科学基金 (61902426); 中国博士后科学基金第69批面上项目 (2021M692502)

GLV/GLS Scalar Multiplication on Jacobi Quartic Curves

WENG Jiang¹^,², JI Wei-feng¹, WU Xuan¹, LI Ying-qi¹, ZHANG Lin-feng³, MENG Hao³

^1.School of Network and Information Security, Xidian University, Xi’an, Shaanxi 710071, China
^2.Information and Navigation College, Air Force Engineering University, Xi’an, Shaanxi 710077, China
^3.Unit 10, Courtyard 14, Fuxing Road, Beijing 100089, China

Received:2019-09-03 Revised:2021-01-24 Online:2021-10-21 Published:2021-09-25
- Supported by:
- National Natural Science Foundation of China (61902426); The 69th Batch of General Program of China Postdoctoral Science Foundation (2021M692502)

摘要/Abstract

摘要：

目前GLV/GLS (Gallant，Lambert，Vanstone / Galbraith, Lin, Scott)标量乘算法的研究主要集中在Weierstrass曲线上，尝试寻找和构造更多或者更高次数的可有效计算的自同态.本文主要研究了Jacobi Quartic曲线上GLV/GLS标量乘算法.首先利用曲线之间的双有理等价，给出了该类曲线在素域上可有效计算自同态的具体构造，得到2维GLV方法.然后考虑椭圆曲线的二次扭曲线，利用曲线之间双有理等价和Frobenius映射，给出了该类曲线在二次扩域上可有效计算自同态的具体构造，得到2维GLS方法.将上述GLV和GLS方法结合起来，同时利用曲线在二次扩域上的两个不同的自同态，得到4维GLV方法.最后针对j不变量为0或1728两类特殊形式的椭圆曲线，利用更高次的扭曲线，得到4维GLV方法.实验结果表明：对于Jacobi Quartic曲线，2维GLV方法和4维GLV方法比5-NAF方法分别提速37.2%和109.4%以上.同时，在三种不同的实现方式下，Jacobi Quartic曲线上标量乘效率都优于Weierstrass曲线.

关键词: 椭圆曲线, Jacobi Quartic曲线, 标量乘, GLV方法, GLS方法, 可有效计算的自同态

Abstract:

At present, GLV/GLS scalar multiplication mainly focuses on the Weierstrass curves, attempting to find and construct more and more efficient computable endomorphism. In this paper, we study the applications of GLV/GLS method on Jacobi Quartic curve. Firstly, we present the concrete construction of efficiently computable endomorphism for this type of curves over prime field by exploiting birational equivalence between curves, and obtain 2-dimensional GLV method. Secondly, we consider the quadratic twists of elliptic curves. By using birational equivalence and Frobenius mapping between curves, we present methods to construct efficiently computable endomorphisms of this type of curves over the quadratic extension field, and obtain a 2-dimensional GLS method. Finally, we obtain the 4-dimensional GLV method on elliptic curves with j-invariant 0 or 1728 by using higher degree twists. The experimental results show that the speedups of 2-dimensional GLV method and 4-dimensional GLV method than 5-NAF method exceed 37.2% and 109.4% for Jacobi Quartic curves respectively. At the same time, under the three implementations above, the scalar multiplication on the Jacobi Quartic curves is always more efficient than that on the Weierstrass curves.

Key words: elliptic curve, Jacobi Quartic curve, scalar multiplication, GLV method, GLS method, efficiently computable endomorphism

中图分类号:

TP309

翁江, 姬伟峰, 吴玄, 等. Jacobi Quartic曲线上GLV/GLS标量乘算法[J]. 电子学报, 2021, 49(9): 1783-1789.

Jiang WENG, Wei-feng JI, Xuan WU, et al. GLV/GLS Scalar Multiplication on Jacobi Quartic Curves[J]. Acta Electronica Sinica, 2021, 49(9): 1783-1789.

图/表 2

表1 两种不同形式椭圆曲线上点运算的开销

曲线形式	DBL	ADD	mADD
ExtJQuartic	2M+5S	7M+4S	6M+3S
Jacobian	1M+8S	11M+5S	7M+4S

表2 两类曲线上不同标量乘实现方法计算开销比较

曲线	实现方法	算个数	计算开销	加速
$E J (F p 22)$	4GLV+INT（3-NAF）	$2 i + 608 m + 559 s$	$1164.8 m$	109.4%
$E J (F p 1)$	2GLV+INT（4-NAF）	$2 I + 659.2 M + 840.6 S$	$1953.7 M ≈ 1777.9 m$	37.2%
$E J (F p 1)$	5-NAF	$2 I + 864 M + 1455 S$	$2680.8 M ≈ 2439.5 m$	-
$E (F p 22)$	4GLV+INT（3-NAF）	$2 i + 587 m + 798 s$	$1325.5 m$	114.3%
$E (F p 1)$	2GLV+INT（4-NAF）	$2 I + 561.4 M + 1258.8 S$	$2211.4 M ≈ 2012.4 m$	41.1%
$E (F p 1)$	5-NAF	$2 I + 629.7 M + 2248.7 S$	$3121.1 M ≈ 2840.2 m$	-

表2 两类曲线上不同标量乘实现方法计算开销比较

曲线	实现方法	算个数	计算开销	加速
$E J (F p 22)$	4GLV+INT（3-NAF）	$2 i + 608 m + 559 s$	$1164.8 m$	109.4%
$E J (F p 1)$	2GLV+INT（4-NAF）	$2 I + 659.2 M + 840.6 S$	$1953.7 M ≈ 1777.9 m$	37.2%
$E J (F p 1)$	5-NAF	$2 I + 864 M + 1455 S$	$2680.8 M ≈ 2439.5 m$	-
$E (F p 22)$	4GLV+INT（3-NAF）	$2 i + 587 m + 798 s$	$1325.5 m$	114.3%
$E (F p 1)$	2GLV+INT（4-NAF）	$2 I + 561.4 M + 1258.8 S$	$2211.4 M ≈ 2012.4 m$	41.1%
$E (F p 1)$	5-NAF	$2 I + 629.7 M + 2248.7 S$	$3121.1 M ≈ 2840.2 m$	-

参考文献 22

1	GallantR P, LambertR J, VanstoneS A. Faster point multiplication on elliptic curves with efficient endomorphisms[A]. Advances in Cryptology-CRYPTO 2001, 21st Annual International Cryptology Conference[C]. Santa Barbara, California, USA: Proceedings, 2001. 19 - 23.
2	ParkY H, JeongS, KimC H, et al. An alternate decomposition of an integer for faster point multiplication on certain elliptic curves[A]. International Workshop on Public Key Cryptosystems[C]. Paris, France: Springer, 2002. 323 - 334.
3	SicaF, CietM, QuisquaterJ J. Analysis of the gallant-lambert-vanstone method based on efficient endomorphisms: elliptic and hyperelliptic curves[A]. International Workshop on Selected Areas in Cryptograph[C]. Newfoundland, Canada: Springer, 2002. 21 - 36.
4	GalbraithS D, LinX, ScottM. Endomorphisms for faster elliptic curve cryptography on a large class of curves[J]. Journal of Cryptology, 2011, 24(3): 446 - 469.
5	ZhouZ, HuZ, XuM, et al. Efficient 3-dimensional GLV method for faster point multiplication on some GLS elliptic curves[J]. Information Processing Letters, 2010, 110(22): 1003 - 1006.
6	HuZ, LongaP, XuM. Implementing the 4-dimensional GLV method on GLS elliptic curves with j-invariant 0[J]. Designs, Codes and Cryptography, 2012, 63(3): 331 - 343.
7	LongaP, SicaF. Four-dimensional gallant-lambert-vanstone scalar multiplication[A]. Advances in Cryptology-ASIACRYPT 2012 [C]. Beijing, China: Springer, 2012. 718 - 739.
8	BosJ W, CostelloC, HisilH, et al. Fast cryptography in genus 2[J]. Journal of Cryptology, 2016, 29(1): 28 - 60.
9	BuhlerJ, KoblitzN. Lattice basis reduction, jacobi sums and hyperelliptic cryptosystems[J]. Bulletin of the Australian Mathematical Society, 1998, 58(01):147 - 154.
10	FurukawaE, KawazoeM, TakahashiT. Counting points for hyperelliptic curves of type y²=x⁵+ax over finite prime fields[A]. International Workshop on Selected Areas in Cryptography[C]. Ottawa, Canada: Springer, 2003. 26 - 41.
11	GuillevicA, IonicaS. Four-dimensional GLV via the weil restriction[A]. International Conference on the Theory and Application of Cryptology and Information Security[C]. Bengaluru, India: Springer, 2013. 79 - 96.
12	BosJ W, CostelloC, HisilH, et al. High-performance scalar multiplication using 8-dimensional GLV/GLS decomposition[A]. International Conference on Cryptographic Hardware and Embedded Systems[C]. Santa Barbara, CA, USA: Springer, 2013. 331 - 348.
13	于伟, 李宝, 王鲲鹏, 等. 特征3有限域上椭圆曲线的co-Z Montgomery算法[J]. 计算机学报, 2017, 40(05):1121 - 1133.
	YuW, LiB, WangK P, et al. Co-z montgomery algorithm for elliptic curves over finite fields of characteristic 3[J]. Chinese Journal of Computers, 2017, 40(05): 1121 - 1133. (in Chinese)
14	YuW, WangK P, LiB, et al. Montgomery algorithm over a prime field[J]. Chinese Journal of Electronics, 2019, 28(01): 39 - 44.
15	YouL, YangY L, GaoS H. Divisor class halving algorithms for genus three hyperelliptic curves[J]. Chinese Journal of Electronics, 2020, 29(01): 97 - 105.
16	Silverman. The Arithmetic of Elliptic Curves[M]. New York, USA: Springer, 2009.
17	HankersonD, MenezesA J, VanstoneS. Guide to Elliptic Curve Cryptography[M]. New York, USA: Springer, 2004.
18	WashingtonL C. Elliptic Curves Number Theory and Cryptography[M]. Florida, USA: CRC Press, 2008.
19	BilletO, JoyeM. The Jacobi model of an elliptic curve and side-channel analysis[A]. International Symposium on Applied Algebra, Algebraic Algorithms, and Error-Correcting Codes[C]. Toulouse, France: Springer, 2003. 34 - 42.
20	Magma. Magma Computational Algebra System[EB/OL]. , 2019.
21	HisilH, CarterG, DawsonE, et al. Jacobi quartic curves revisited[A]. Australasian Conference on Information Security and Privacy[C]. Brisbane, Australia: Springer, 2009. 452 - 468.
22	LongaP, MiriA. New composite operations and precomputation scheme for elliptic curve cryptosystems over prime fields[A]. International Workshop on Public Key Cryptography[C]. Barcelona, Spain: Springer, 2008. 229 - 247.

[1]	赵石磊, 杨晓秋, 刘志伟, 于斌, 黄海. 一种低复杂度的改进wNAF标量乘算法[J]. 电子学报, 2022, 50(4): 977-983.
[2]	李森森, 黄一才, 郁滨, 鲍博武. 基于PUF的低开销物联网安全通信方案[J]. 电子学报, 2019, 47(4): 812-817.
[3]	翁江, 康晓春, 豆允旗, 马传贵. 一类j=0超奇异椭圆曲线的性质及其标量乘算法[J]. 电子学报, 2018, 46(9): 2131-2138.
[4]	陈昕, 宋亚鹏, 刘志强. 一种新型的LTE-A网络切换认证协议[J]. 电子学报, 2017, 45(2): 485-491.
[5]	张文芳, 王小敏, 郭伟, 何大可. 基于椭圆曲线密码体制的高效虚拟企业跨域认证方案[J]. 电子学报, 2014, 42(6): 1095-1102.
[6]	翁江, 豆允旗, 马传贵. 双基数链算法计算Tate对的一种改进[J]. 电子学报, 2012, 40(9): 1775-1782.
[7]	陈琳;孙万忠;陈性元;戴紫彬. 基于有符号数字系统的Montgomery模逆算法及其硬件实现[J]. 电子学报, 2012, 40(3): 489-494.
[8]	张李军;王鲲鹏. 环Z_n上椭圆曲线的群法则及其在Paillier系统中的应用[J]. 电子学报, 2011, 39(8): 1733-1738.
[9]	庞世春;刘淑芬;从福仲;姚志林. 一种Montgomery型椭圆曲线的高效标量乘算法[J]. 电子学报, 2011, 39(4): 865-868.
[10]	黎明;吴丹;戴葵;邹雪城. 高性能可扩展公钥密码协处理器研究与设计[J]. 电子学报, 2011, 39(3): 665-670.
[11]	邵春雨;苏锦海;魏有国;周晶晶. 一种双矩阵组合公钥算法[J]. 电子学报, 2011, 39(3): 671-674.
[12]	王念平. 一种新的五元联合稀疏形式表示算法及其应用[J]. 电子学报, 2011, 39(1): 114-118.
[13]	冯涛;王毅琳;马建峰. 一种新的基于椭圆曲线密码体制的 Ad hoc组密钥管理方案[J]. 电子学报, 2009, 37(5): 918-924.
[14]	鲍皖苏;陈辉. 基于双基表示的并列点乘算法[J]. 电子学报, 2009, 37(4): 873-876.
[15]	代战锋;温巧燕;李小标. 基于分布式PKI的P2P网络认证技术[J]. 电子学报, 2009, 37(11): 2561-2564.

Jacobi Quartic曲线上GLV/GLS标量乘算法

GLV/GLS Scalar Multiplication on Jacobi Quartic Curves

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 2

参考文献 22

相关文章 15

编辑推荐

Metrics