一种灵活的椭圆曲线密码并行化方法

doi:10.3969/j.issn.1006-2475.2018.02.015

计算机与现代化

一种灵活的椭圆曲线密码并行化方法

（深圳信息职业技术学院计算机学院,广东深圳518172）

收稿日期:2017-06-06 出版日期:2018-03-08 发布日期:2018-03-09
作者简介:邬可可(1980-),男，江西九江人,深圳信息职业技术学院计算机学院高级工程师,博士,研究方向:密码学与密码设备的侧信道分析; 黄国伟(1981-),男,副教授,博士,研究方向:网络系统安全与评估; 孔令晶(1983-),女,讲师,博士,研究方向:网络协议,机器学习。
基金资助:
广东省自然科学基金资助项目(2014A030310299); 深圳市科技计划项目(JCYJ20160415113927863, JCYJ20160307101532282, JCYJ20160527101106061); 深圳信息职业学院科研培训项目(ZY201710)

A Flexible Parallelization Method for Elliptic Curve Cryptosystems

(Computer School, Shenzhen Institute of Information Technology, Shenzhen 518172, China)

Received:2017-06-06 Online:2018-03-08 Published:2018-03-09

摘要/Abstract

摘要： 提出标量划分与整合模型，基于此模型，提出一种灵活的椭圆曲线密码标量乘的并行化处理方法。由于该方法是基于标量乘的算法操作级别，因此能在各种不同处理器数量的并行系统中实现。相对于现有的基于固定数量处理器的标量乘并行化方法，本文的并行化方法是灵活的。同时，本文提出的标量乘并行化方法最优时间复杂度可以减少到(logk)A+kD。通过实例比较，本文提出的方法的最优时间复杂度比经典的二进制方法减少了大约30%。

关键词: 椭圆曲线密码, 标量乘, 并行计算, 并行系统, 二进制方法

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

中图分类号:

TP309.7

邬可可,黄国伟,孔令晶. 一种灵活的椭圆曲线密码并行化方法[J]. 计算机与现代化, doi: 10.3969/j.issn.1006-2475.2018.02.015.

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.

参考文献

［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]	王鑫, 吴俊辉, . 基于FPGA的分子动力学模拟交互控制系统[J]. 计算机与现代化, 2022, 0(09): 25-31.
[2]	李艳梅1,殷新春1,2,邵梦丽2. 基于多基表示的滑动窗口椭圆曲线多标量乘算法[J]. 计算机与现代化, 2019, 0(01): 11-.
[3]	项武铭，李雪巍. 基于CUDA的梯级泵站调度算法实现[J]. 计算机与现代化, 2018, 0(11): 60-.
[4]	赵博颖，肖鹏，张力. 基于Docker的MPI和OpenMP混合编程[J]. 计算机与现代化, 2018, 0(05): 60-.
[5]	桑喆1，邓川1，苟聪1，刘开兴2，白明泽1. 基于JNI和C+〖KG-*3〗+的Intel集成众核并行方法[J]. 计算机与现代化, 2018, 0(04): 32-.
[6]	王龙，姚文明. 基于Spark的并行遗传算法在物流配送问题中的应用[J]. 计算机与现代化, 2018, 0(01): 19-22.
[7]	栗家棋，郑昊. 基于矢量地图数据的异构混合快速绘制框架[J]. 计算机与现代化, 2018, 0(01): 56-61.
[8]	邬可可，高月芳，闫立军. 一种抵御差分侧信道分析的椭圆曲线同构方法[J]. 计算机与现代化, 2017, 0(10): 105-110.
[9]	孙立华1，胡牧1，孟庆强1，钱亚康1，王松2. 配网线损大数据高性能计算解决方案[J]. 计算机与现代化, 2016, 0(12): 42-46,50.
[10]	汪方良，施慧彬. 基于OpenCL的人脸识别与隐藏系统[J]. 计算机与现代化, 2016, 0(1): 16-19,58.
[11]	赵成龙1，施慧彬1，俞忻峰2. 基于OpenCL的双GPU基数排序算法[J]. 计算机与现代化, 2015, 0(1): 27-30.
[12]	贺维维，吴京，曾瑶源. 基于MPI+OpenMP的红外弱小目标检测并行计算[J]. 计算机与现代化, 2014, 0(7): 53-57.
[13]	王兴，王介君，孙宁，汪瑶. 基于GPU的交叉相关外推并行化算法[J]. 计算机与现代化, 2014, 0(2): 213-218.
[14]	张唯唯，张玉洁. 基于GPU的并行报文分类方法[J]. 计算机与现代化, 2014, 0(11): 9-14.
[15]	刘晴和，杨云，贺兴亚，徐文春，周媛媛. 基于业务分割的并行式大数据迁移策略研究[J]. 计算机与现代化, 2014, 0(11): 86-89.

一种灵活的椭圆曲线密码并行化方法

A Flexible Parallelization Method for Elliptic Curve Cryptosystems

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价