High-Performance Cryptographic Computations in GPUs

Abstract

Abstract: Cryptology is an important foundation and tool of network security. In recent years, with the continuous and rapid development of big data industry, ecommerce and cloud computing, the amount of users, traffic volumes and the corresponding cryptographic calculations faced by various service providers are also rapidly rising. In response to this situation, researchers began to break the conventional pattern that cryptographic algorithms were implemented by CPUs, ASICs, and FPGAs, migrate them to various parallel computing platforms, such as graphics processing units (GPUs). Driven by huge demand of graphics rendering, artificial intelligence, etc., GPUs gain more than ten times of the computing power promotion over the last decade. Such performance advantages help the GPUbased cryptography implementations outperform others by a wide margin, and give them great potential. This paper summarizes the current progress of the GPUbased cryptography implementation, and gives a brief analysis of its development tendency.

Key words: graphics processing unit, RSA, elliptic curve cryptography, cryptographic computation, parallel computing

摘要： 密码技术是保障网络安全的重要基石和工具.近年来，随着大数据行业、电子商务和云计算技术的持续快速发展，各个服务商面对的用户量、业务量和相应的密码计算量也在急速地攀升；面向这一情况，研究人员开始打破密码算法由CPU，ASIC，FPGA实现的传统格局，将密码算法迁移至GPU等各类并行计算平台上.受到高分辨率图形渲染、人工智能的巨大需求所带动，GPU在过去10年获得超过10倍的计算性能提升，大幅领先于其他计算平台.这也使得基于GPU的高性能算法实现的性能远超其他平台的同类实现，显示出了GPU在密码算法实现领域的巨大潜能.内容主要包括2部分:一是总结基于GPU的高性能密码计算的发展和研究现状;二是简要分析它未来的发展趋势.

关键词: 图形处理器, RSA, 椭圆曲线密码学, 密码计算, 并行计算

郑昉昱董建阔林璟锵高莉莉. 基于GPU的高性能密码计算[J]. 信息安全研究, 2019, 5(1): 88-96.

References

[1] Nishikawa N, Amano H, Iwai K. Implementation of bitsliced AES encryption on CUDA-enabled GPU[C]//Proc of Int Conf on Network and System Security. Berlin :Springer,2017: 273-287 [2] Cheng W, Zheng F, Pan W, et al. High-performance symmetric cryptography server with GPU acceleration[C]//Proc of Int Conf on Information and Communications Security. Berlin: Springer, 2017: 529-540 [3] Diffie W, Hellman M. New directions in cryptography[J]. IEEE Trans on Information Theory, 1976, 22(6): 644-654 [4] Gallagher P, Kerry C. FIPS Pub 186-4: Digital signature standard[EB/OL]. [2015-12-22].https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf [5] Szerwinski R, Güneysu T. Exploiting the power of GPUs for asymmetric cryptography[C]//Proc of Intl Workshop on Cryptographic Hardware and Embedded Systems. Berlin:Springer, 2008: 79-99 [6] Harrison O, Waldron J. Public key cryptography on modern graphics hardware[EB/OL]. [2018-10-10].https://www.researchgate.net/publication/228992449_Public_key_cryptography_on_modern_graphics_hardware [7] Bernstein D J, Chen T R, Cheng C M, et al. ECM on graphics cards[C]//Proc of Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin:Springer, 2009: 483-501 [8] Bos J W. Low-latency elliptic curve scalar multiplication[J]. International Journal of Parallel Programming, 2012, 40(5): 532-550 [9] Dong J, Zheng F, Emmart N, et al. sDPF-RSA: Utilizing floating-point computing power of GPUs for massive digital signature computations[C]//Proc of 2018 IEEE Int Parallel and Distributed Processing Symp. Piscataway:IEEE, 2018: 599-609 [10] Pan W, Zheng F, Zhao Y, et al. An efficient elliptic curve cryptography signature server with GPU acceleration[J]. IEEE Trans on Information Forensics and Security, 2017, 12(1): 111-122 [11] Fleissner S. GPU-accelerated Montgomery exponentiation[C]//Int Conf on Computational Science. Berlin:Springer, 2007: 213-220 [12] Bernstein D J, Chen H C, Chen M S, et al. The billion-mulmod-per-second PC[EB/OL].[2018-10-09].https://www.researchgate.net/publication/254892277_The_billion-mulmod-per-second_PC [13] Neves S, Araujo F. On the performance of GPU public-key cryptography[C]// Proc of the 22nd IEEE Int Conf on Application-specific Systems, Architectures and Processors. Piscataway,NJ:IEEE, 2011: 133-140 [14] Zheng F, Pan W, Lin J, et al. Exploiting the potential of GPUs for modular multiplication in ECC[C]//Proc of Int Workshop on Information Security Applications. Berlin:Springer, 2014: 295-306 [15] Moss A, Page D, Smart N P. Toward acceleration of RSA using 3D graphics hardware[C]//Proc of IMA Int Conf on Cryptography and Coding. Berlin:Springer, 2007: 364-383 [16] Antao S, Bajard J C, Sousa L. Elliptic curve point multiplication on GPUs[C]//Proc of the 21st IEEE Int Conf on Application-specific Systems Architectures and Processors .Piscataway,NJ:IEEE, 2010: 192-199 [17] Antão S, Bajard J C, Sousa L. RNS-based elliptic curve point multiplication for massive parallel architectures[J]. The Computer Journal, 2011, 55(5): 629-647 [18] Pu S, Liu J C. EAGL: An elliptic curve arithmetic GPU-based library for bilinear pairing[C]//Proc of Int Conf on Pairing-Based Cryptography. Berlin:Springer, 2013: 1-19 [19] Jeffrey A, Robinson B D. Fast GPU based modular multiplication[EB/OL].http://on-demand.gputechconf.com/gtc/2014/poster/pdf/P4156_montgomery_multiplication_CUDA_concurrent.pdf [20] Harrison O, Waldron J. Efficient acceleration of asymmetric cryptography on graphics hardware[C]//Proc of Int Conf on Cryptology in Africa. Berlin:Springer, 2009: 350-367 [21] Cruz-Cortés N, Ochoa-Jiménez E, Rivera-Zamarripa L, et al. A GPU parallel implementation of the RSA private operation[C]//Proc of Latin American High Performance Computing Conf. Berlin:Springer, 2016: 188-203 [22] Jang K, Han S, Han S, et al. SSLShader: Cheap SSL acceleration with commodity processors[EB/OL].[2018-10-10].https://www.researchgate.net/publication/242935693_SSLShader_Cheap_SSL_Acceleration_with_Commodity_Processors?ev=auth_pub [23] Yang Y, Guan Z, Sun H, et al. Accelerating RSA with Fine-Grained Parallelism Using GPU[M]. Berlin: Springer, 2015: 454-468 [24] Zheng F, Pan W, Lin J, et al. Exploiting the floating-point computing power of GPUs for RSA[C]//Proc of Int Conf on Information Security. Berlin:Springer, 2014: 198-215 [25] Emmart N, Weems C. Pushing the performance envelope of modular exponentiation across multiple generations of GPUs[C]//Proc of 2015 IEEE Int Parallel and Distributed Processing Symp. Piscataway,NJ:IEEE, 2015: 166-176 [26] Dong J, Zheng F, Pan W, et al. Utilizing the double-precision floating-point computing power of GPUs for RSA acceleration[EB/OL].[2017-09-17].https://www.hindawi.com/journals/scn/2017/3508786/ [27] Koc C K, Acar T, Kaliski B S. Analyzing and comparing Montgomery multiplication algorithms[J]. IEEE Micro, 1996, 16(3): 26-33 [28] Hankerson D, Menezes A J, Vanstone S. Guide to Elliptic Curve Cryptography[M]. Berlin:Springer Science & Business Media, 2006 [29] Langley A, Hamburg M, Turner S. Elliptic curves for security[EB/OL]. (2016-07-06)[2018-10-11]. https://datatracker.ietf.org/doc/rfc7748/ [30] Josefsson S, Liusvaara I. Edwards-curve digital signature algorithm[EB/OL]. [2018-10-11]. https://datatracker.ietf.org/doc/rfc8032/ [31] Rescorla E. The transport layer security (TLS) protocol version 1.3[EB/OL]. [2018-08-28]. https://datatracker.ietf.org/doc/rfc8446/ [32] Bernstein D J, Chuengsatiansup C, Lange T. Curve41417: Karatsuba revisited[C]//Proc of Int Workshop on Cryptographic Hardware and Embedded Systems. Berlin:Springer,2014: 316-334 [33] Costello C, Longa P. Fourℚ[EB/OL].(2015-08-26)[2018-10-11].https://www.microsoft.com/en-us/research/project/fourqlib/?from=http%3A%2F%2Fresearch.microsoft.com%2Ffourqlib [34] Mahe E, Chauvet J M. Fast GPGPU-based elliptic curve scalar multiplication[EB/OL].[2018-10-10]. https://eprint.iacr.org/2014/198.pdf [35] Dong J, Zheng F, Cheng J, et al. Towards high-performance X25519/448 key agreement in general purpose GPUs[C]//Proc of 2018 IEEE Conf on Communications and Network Security. Piscataway,NJ: IEEE, 2018: 1-9 [36] Bernstein D J. Introduction to Post-Quantum Cryptography[M]// Berlin:Springer,2009: 1-14 [37] Hoffstein J, Pipher J, Silverman J H. NTRU: A ring-based public key cryptosystem[C]//Proc of Int Algorithmic Number Theory Symp. Berlin:Springer,1998: 267-288 [38] Hermans J, Vercauteren F, Preneel B. Speed records for NTRU[C]//Proc of Cryptographers’ Track at the RSA Conf. Berlin:Springer, 2010: 73-88 [39] Dai W, Doröz Y, Sunar B. Accelerating NTRU based homomorphic encryption using GPUs[C]//Proc of High Performance Extreme Computing Conf. Piscataway,NJ: IEEE,2014: 1-6 [40] Dai W, Sunar B, Schanck J, et al. NTRU modular lattice signature scheme on CUDA GPUs[C]//Proc of Int Conf on High Performance Computing & Simulation. Piscataway,NJ: IEEE, 2016: 501-508 [41] Tan T N, Lee H. High-performance Ring-LWE cryptography scheme for biometric data security[J]. IEIE Trans on Smart Processing & Computing, 2018, 7(2): 97-106 [42] Al Badawi A, Veeravalli B, Aung K M M, et al. Accelerating subset sum and lattice based public-key cryptosystems with multi-core CPUs and GPUs[EB/OL].[2018-12-11].https://www.sciencedirect.com/science/article/pii/S0743731518302831 [43] Zhu Z, Kim S, Rozhanski Y, et al. Understanding the security of discrete GPUs[C]//Proc of the General Purpose GPUs. New York:ACM, 2017: 1-11 [44] Vasiliadis G, Athanasopoulos E, Polychronakis M, et al. Pixelvault: using gpus for securing cryptographic operations[C]//Proc of the 2014 ACM SIGSAC Conf on Computer and Communications Security. New York:ACM, 2014: 1131-1142 [45] Jiang Z H, Fei Y, Kaeli D. A complete key recovery timing attack on a GPU[C]//Proc of 2016 IEEE Int Symp on High Performance Computer Architecture. Piscataway,NJ: IEEE,2016: 394-405 [46] Kocher P C. Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems[C]//Proc of A