Curve25519椭圆曲线算法GPU高速实现

doi:10.3969/j.issn.1671-1122.2017.09.029

信息网络安全 ›› 2017, Vol. 17 ›› Issue (9): 122-127.doi: 10.3969/j.issn.1671-1122.2017.09.029

Curve25519椭圆曲线算法GPU高速实现

成娟娟^1,^2,³, 郑昉昱^1,²(), 林璟锵^1,², 董建阔^1,^2,³

1.中国科学院信息工程研究所信息安全国家重点实验室,北京100093
2.中国科学院数据与通信保护研究教育中心,北京100093
3.中国科学院大学网络空间安全学院,北京100049

收稿日期:2017-08-01 出版日期:2017-09-20 发布日期:2020-05-12
作者简介:
作者简介：成娟娟（1992—）,女,山西,硕士研究生,主要研究方向为高性能密码实现技术;郑昉昱（1988—）,男,福建,助理研究员,博士,主要研究方向为GPU并行计算、高速密码算法实现;林璟锵（1978—）,男,福建,研究员,博士,主要研究方向为软硬件安全、网络安全、系统安全;董建阔（1992—）,男,河北,博士研究生,主要研究方向为高性能密码实现技术。
基金资助:
国家自然科学基金[61602476]

High-performance Implementation of Curve25519 on GPU

Juanjuan CHENG^1,^2,³, Fangyu ZHENG^1,²(), Jingqiang LIN^1,², Jiankuo DONG^1,^2,³

1.State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China
2.Data Assurance and Communication Security Research Center, Chinese Academy of Sciences, Beijing 100093, China
3.College of Cyberspace Security, University of Chinese Academy of Sciences, Beijing100049, China

Received:2017-08-01 Online:2017-09-20 Published:2020-05-12

摘要/Abstract

摘要：

密钥交换是一种在非保护信道中建立共享密钥的方法,被广泛运用在包括TLS/SSL等网络安全协议中。基于椭圆曲线密码算法的Diffie-Hellman算法（ECDH）由于其出色的计算效率,在密钥交换协议中被逐步推广使用。目前主流的ECDH中采用的椭圆曲线是NIST P系列曲线,但随着对性能的迫切要求以及对其安全性的怀疑,IETF在2016年1月正式将Curve25519曲线用于密钥交换,称为X25519密钥交换协议;随后各大开源安全软件也进行跟进,优先推荐使用X25519。X25519的主要计算瓶颈是Curve25519的椭圆曲线点乘算法,文章提出了一种利用GPU的Curve25519的椭圆曲线点乘算法,通过对有限域算术优化和曲线算法优化,在NVIDIA GeForce GTX 780Ti达到了每秒138万次的吞吐率,相较之前基于GPU的实现获得了5.6倍的性能提升。

关键词: 图形处理器, 椭圆曲线, Curve25519, 密钥交换

Abstract:

Widely used in a large range of Internet security protocols such as TLS/SSL, key exchange provides a method to establish a shared secret between two parties in unprotected channel. Among the key exchange algorithms Elliptic-Curve Diffie- Hellman (ECDH) is currently preferred and popularized by the industry. The prevailing ECDH employs NIST P Curve as the underlying elliptic curve, however, with the requirement of high performance and questioning of its security, in January, 2016, IETF officially applied Curve25519 to key exchange in RFC 7748, called X25519 key exchange protocol. And later, many mainstream open-source projects recommended X25519 as the default key exchange protocol. The bottleneck of X25519 lies in the scalar multiplication of Curve25519.This contribution proposed a GPU-accelerated Curve25519 implementation, having yielded a throughput of 1.38 million scalar multiplication per second in NVIDIA GeForce GTX 780Ti, 5.6 times faster than the previous fastest work.

Key words: graphic processing unit (GPU), elliptic curves, Curve25519, key exchange

中图分类号:

TP393

成娟娟, 郑昉昱, 林璟锵, 董建阔. Curve25519椭圆曲线算法GPU高速实现[J]. 信息网络安全, 2017, 17(9): 122-127.

Juanjuan CHENG, Fangyu ZHENG, Jingqiang LIN, Jiankuo DONG. High-performance Implementation of Curve25519 on GPU[J]. Netinfo Security, 2017, 17(9): 122-127.

图/表 4

参考文献 24

[1]	MILLER V S. Use of Elliptic Curves in Cryptography[EB/OL]. , 1985.
[2]	KOBLITZ N.Elliptic curve cryptosystems[J]. Mathematics of computation, 1987, 48(177): 203-209.
[3]	BERNSTEIN D J, LANGGE T.Failures in NIST’s ECC Standards[EB/OL]., 2015.
[4]	BERNSTEIN D J.Curve25519: New Diffie-Hellman Speed Records[EB/OL]. , 2006.
[5]	LANGLEY A, HANBURG M.Elliptic Curves For Security[J].Order, 2016(500): 39081.
[6]	BERNSTEIN D J.25519 Naming[EB/OL]., 2014
[7]	VIEGA J, MESSIER M, CHANDRA P.Network Security with OpenSSL: Cryptography forSecure Communications[M]. New York: “O’Reilly Media, Inc.”, 2002.
[8]	DÜLL M, HAASE B, HINTERWǞLDER G,et al. High-Speed Curve25519 on 8-bit, 16-bit, and 32-bit Microcontrollers[J]. Designs, Codes and Cryptography, 2015, 77(2-3): 493-514.
[9]	FAZ-HERNÁNDEZ A, LÓPEZ J. Fast Implementation of Curve25519 Using AVX2[EB/OL]. .1007/978-3-319-22174-8_18, 2015.
[10]	MAHE E, CHAUVET J M.Fast GPGPU-Based Elliptic Curve Scalar Multiplication[J]. IACR Cryptology ePrint Archive, 2014(1): 198.
[11]	BERNSTEIN D J, CHEN T R, CHENG C M, et al. ECM on Graphics Cards[EB/OL]. ,2009.
[12]	BERNSTEIN D J, CHEN HC, CHEN MS, et al.The Billion-Mulmod-Per-Second PC[EB/OL]., 2009.
[13]	GIORGI P, IZARD T, TISSERAND A.Comparison of Modular Arithmetic Algorithms on GPUs[EB/OL]., 2009.
[14]	ANTÃO S, BAJARD Jean-Claude, and SOUSA Leonel. Elliptic Curve Point Multiplication on GPUs[EB/OL]. , 2010.
[15]	PU S, LIU J C. EAGL: an Elliptic Curve Arithmetic GPU-Based Library for Bilinear Pairing[EB/OL]., 2013.
[16]	SZERWINSKI R,GÜNEYSU T. Exploiting the Power of GPUs for Asymmetric Cryptography[J]. Cryptographic Hardware and Embedded Systems-CHES2008(1):79-99.
[17]	PAN W, ZHENG F, ZHAO Y, et al.An Efficient Elliptic Curve Cryptography Signature Server with GPU Acceleration[J]. IEEE Transactions on Information Forensics and Security, 2017, 12(1): 111-122.
[18]	BROWN M, HANKERSON D, LÓPEZ J, et al. Software Implementation of the NIST Elliptic Curves over Prime Fields[J]. Topics in Cryptology—CT-RSA2001(1):250-265.
[19]	ZHANG D, BAI G. High-Performance Implementation of SM2 Based on FPGA[EB/OL]., 2016.
[20]	MONTGOMERY P L.Speeding the Pollard and Elliptic Curve Methods of Factorization[J]. Mathematics of computation, 1987, 48(177): 243-264.
[21]	BERNSTEIN D J, BIRKNER P, JOYE M, et al. Twisted Edwards Curves[EB/OL]., 2008.
[22]	BERNSTEIN D J, LANGE T. FasterAddition and Doubling on Elliptic Curves[EB/OL], 2007.
[23]	NVIDIA C. CUDA C Programming Guide[EB/OL]., 2013-6-23.
[24]	ZHENG F, PAN W, LIN J, et al. Exploiting the Potential of GPUs for Modular Multiplication in ECC[EB/OL]., 2014.

Curve25519椭圆曲线算法GPU高速实现

High-performance Implementation of Curve25519 on GPU

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 4

参考文献 24

相关文章 15

编辑推荐

Metrics

本文评价

[1]	韦永霜, 陈建华, 韦永美. 基于椭圆曲线密码的RFID/NFC安全认证协议[J]. 信息网络安全, 2019, 19(12): 64-71.
[2]	李喆, 韩益亮, 李鱼. 基于Polar码的密钥交换方案[J]. 信息网络安全, 2019, 19(10): 84-90.
[3]	程庆丰, 阮展靖, 张瑞杰. 对三个无双线性对的密钥协商协议分析[J]. 信息网络安全, 2019, 19(1): 16-26.
[4]	周志彬, 张少波, 罗恩韬, 李超良. 一种无可信第三方的批量RFID所有权转移协议[J]. 信息网络安全, 2018, 18(6): 18-27.
[5]	张小红, 郭焰辉. 基于椭圆曲线密码的RFID系统安全认证协议研究[J]. 信息网络安全, 2018, 18(10): 51-61.
[6]	杜庆灵. 基于身份的动态群通信签密方案[J]. 信息网络安全, 2017, 17(9): 42-44.
[7]	张曙光, 咸鹤群, 刘红燕, 侯瑞涛. 云存储环境中基于离线密钥传递的加密重复数据删除方法研究[J]. 信息网络安全, 2017, 17(7): 66-72.
[8]	游伟青, 陈小明, 齐健. 一类抗量子计算的公钥密码算法研究[J]. 信息网络安全, 2017, 17(4): 53-60.
[9]	贾徽徽, 王潮, 顾健, 陆臻. 基于Grover量子中间相遇搜索算法的ECC攻击错误bit的修正[J]. 信息网络安全, 2016, 16(6): 28-34.
[10]	张言胜, 汪学明, 仇各各. 一种新的动态门限数字签名方案研究[J]. 信息网络安全, 2016, 16(6): 62-67.
[11]	陆思奇, 范书珲, 韩旭, 程庆丰. 一种基于CAFL模型的抗弹性泄露密钥交换协议研究[J]. 信息网络安全, 2016, 16(4): 31-37.
[12]	陈宇航, 贾徽徽, 姜丽莹, 王潮. 基于Grover算法的ECC扫描式攻击[J]. 信息网络安全, 2016, 16(2): 28-32.
[13]	. 有限域上椭圆曲线 Jacobian 群求阶算法综述与比较[J]. , 2014, 14(7): 41-.
[14]	李明;王赛;李亮;严文涛. 边信道攻击防范措施的研究[J]. , 2013, 13(Z): 0-0.
[15]	聂意新;刘彬彬;任伟. SM2密码算法的Java实现与评测[J]. , 2013, 13(8): 0-0.