A Flexible Parallelization Method for Elliptic Curve Cryptosystems

doi:10.3969/j.issn.1006-2475.2018.02.015

Abstract

Abstract: This paper proposes a flexible parallel method of scalar multiplication for elliptic curve cryptosystems (ECC) based on the proposed scalar partition and integration models. Focusing on parallelizing ECC scalar multiplication operations at the scalar multiplication algorithm level, the proposed method can be implemented into various parallel systems. In contrast to previous parallel scalar multiplication methods, the proposed method is flexible. Furthermore, the time complexity of the proposed parallel scalar multiplication method can be reduced to (logk)A+kD. The optimal time complexity of the proposed method is reduced about 30% compared with classic binary method by an example.


Key words: elliptic curve cryptosystems, scalar multiplication, parallel computing, parallel systems, binary method

CLC Number:

TP309.7

WU Ke-ke, HUANG Guo-wei, KONG Ling-jing. A Flexible Parallelization Method for Elliptic Curve Cryptosystems[J]. Computer and Modernization, doi: 10.3969/j.issn.1006-2475.2018.02.015.

References

［1］ Miller V S. Use of elliptic curves in cryptography［C］// LNCS Advances in Cryptology. 1985,218:417-426.
［2］ Koblitz N. Elliptic curve cryptosystems［J］. Mathematics of Computation, 1987,48(177):203-209.
［3］ Knuth D E. The Art of Computer Programming Volume 2: Seminumerical Algorithms［M］. 3rd ed. Beijing: Tsinghua University Press, 2002:461-465.
［4］ Hankerson D, Menezes A, Vanstone S. Guide to Elliptic Curve Cryptography［M］. Springer-Verlag, London, 2004:95-123.
［5］ Aoki K, Hoshino F, Kobayashi T, et al. Elliptic curve arithmetic using SIMD［C］// Proceedings of International Conference on Information Security. 2001:235-247.
［6］ Izu T, Takagi T. Fast elliptic curve multiplications with SIMD operations［C］// Proceedings of International Conference on Information Security. 2002:217-230.
［7］ Izu T, Takagi T. A fast parallel elliptic curve multiplication resistant against side channel attacks［C］// Proceedings of the 5th International Workshop on Practice and Theory in Public Key Cryptosystems. 2002:280-296.
［8］ Izu T. Fast elliptic curve multiplication resistant against side channel attacks［J］. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2005,88(1):161-171.
［9］ Mishra P K. Pipelined computation of scalar multiplication in elliptic curve cryptosystems［C］// Proceedings of the 6th International Workshop on Cryptographic Hardware and Embedded Systems. 2004:328-342.
［10］Longa P, Miri A. Fast and flexible elliptic curve point arithmetic over prime fields［J］. IEEE Transactions on Computers, 2008,57(3):289-302.
［11］Al-Otaibi A, Al-Somani T F, Beckett P. Efficient elliptic curve parallel scalar multiplication methods［C］// 2013 8th International Conference on Computer Engineering & Systems(ICCES). 2013:116-123.
［12］Azarderakhsh R, Reyhani-Masoleh A. Parallel and high-speed computations of elliptic curve cryptography using hybrid-double multipliers［J］. IEEE Transactions on Parallel and Distributed Systems, 2015,26(6):1668-1677.
［13］Bos J W. Low-latency elliptic curve scalar multiplication［J］. International Journal of Parallel Programming, 2012,40(5):532-550.
［14］Realpe-Munoz P C, Velasco-Medina J. High-performance elliptic curve cryptoprocessors over GF(2m) on Koblitz curves［J］. Analog Integrated Circuits and Signal Processing, 2015,85(1):129-138.
［15］Al-Somani T F. High-performance generic-point parallel scalar multiplication［J］. Arabian Journal for Science and Engineering, 2017,42(2):507-512.
［16］Asif S, Kong Yinan. Highly parallel modular multiplier for elliptic curve cryptography in residue number system［J］. Circuits, Systems, and Signal Processing, 2017,36(3):1027-1051.
［17］Oliveira T, Lopez J, Rodriguez-Henriquez F. The Montgomery ladder on binary elliptic curves［J］. Journal of Cryptographic Engineering, 2017,7(4):1-18.

[1]	WANG Xin, WU Jun-hui, . FPGA-based Interactive Control System for Molecular Dynamics Simulation [J]. Computer and Modernization, 2022, 0(09): 25-31.
[2]	LI Yan-mei1, YIN Xin-chun1,2,SHAO Meng-li2. Multi-scalar Multiplication Algorithm for Elliptic Curve Based on MBNS and Sliding Window [J]. Computer and Modernization, 2019, 0(01): 11-.
[3]	XIANG Wu-ming, LI Xue-wei. A CUDA-based Cascade Pumping Station Scheduling Algorithm [J]. Computer and Modernization, 2018, 0(11): 60-.
[4]	ZHAO Bo-ying， XIAO Peng， ZHANG Li. Hybrid Programming of MPI and OpenMP Based on Docker [J]. Computer and Modernization, 2018, 0(05): 60-.
[5]	SANG Zhe1, DENG Chuan1, GOU Cong1, LIU Kaixing2, BAI Mingze1. A Parallelization Method with JNI and C+〖KG-*3〗+ for Many Integrated Core Application [J]. Computer and Modernization, 2018, 0(04): 32-.
[6]	WANG Long， YAO Wen-ming. Application of Parallel Genetic Algorithm Based on Spark in Logistics Distribution [J]. Computer and Modernization, 2018, 0(01): 19-22.
[7]	LI Jia-qi， ZHENG Hao. A Heterogeneous Mixed Fast Drawing Framework Based on Vec-map Data [J]. Computer and Modernization, 2018, 0(01): 56-61.
[8]	WU Ke-ke, GAO Yue-fang, YAN Li-jun. An Elliptic Curve Isomorphism Method for Resisting Differential Side-channel Analysis [J]. Computer and Modernization, 2017, 0(10): 105-110.
[9]	SUN Li-hua1, HU Mu1, MENG Qing-qiang1, QIAN Ya-kang1, WONG Song2. Solution for High Performance of Distribution Network Line Loss Big Data [J]. Computer and Modernization, 2016, 0(12): 42-46,50.
[10]	WANG Fang-liang， SHI Hui-bin. Face Recognition and Hiding System Based on OpenCL [J]. Computer and Modernization, 2016, 0(1): 16-19,58.
[11]	WANG Xing1, MIAO Chun-sheng1, WANG Xiu-jun2, FAN Zhong-xin1. Improvement and Optimization on Radar Extrapolation Algorithm Based on OpenCL [J]. Computer and Modernization, 2014, 0(8): 81-86+90.
[12]	HE Wei-wei, WU Jing, ZENG Yao-yuan. Parallel Computing of Infrared Small Target Detection Based on MPI and OpenMP [J]. Computer and Modernization, 2014, 0(7): 53-57.
[13]	WANG Xing, WANG Jie-jun, SUN Ning, WANG Yao. GPU-based Parallel Algorithm for Cross-correlation Extrapolation [J]. Computer and Modernization, 2014, 0(2): 213-218.
[14]	ZHANG Wei-wei, ZHANG Yu-jie. Parallel Packet Classification Method Based on GPU [J]. Computer and Modernization, 2014, 0(11): 9-14.
[15]	LIU Qing-he, YANG Yun, HE Xing-ya, XU Wen-chun, ZHOU Yuan-yuan. Research on Parallel Big Data Migration Strategy Based on Job Segmentation [J]. Computer and Modernization, 2014, 0(11): 86-89.