HECC除子标量乘并行集群算法设计
|
摘要
为了加快超椭圆曲线密码体制(HECC)中除子标量乘的运算速度,进行基于大数据技术的除子标量乘并行算法研究。根据"空间换时间"的策略对除子标量乘法常规方法进行改进,在任务规模为1016的条件下,运算耗时减少16.28%,提出基于负载均衡的任务划分优化方案。此方案分别将Hadoop集群平台、Spark集群平台、Spark-GPU集群平台的并行技术应用于改进后的除子标量乘算法中,研究并行算法与串行算法的运行效率。当问题规模一定时,随着节点个数的增加,不同集群平台的加速呈上升趋势,其中Spark-GPU并行算法的增长趋势最为明显,当节点个数为4时,Spark-GPU并行算法的加速比达到了261.84。通过对比3种集群平台的并行算法,发现Spark-GPU可以最有效地缩短运算耗时,加快除子标量乘法的运算速度。
A divisor scalar multiplication parallel algorithm based on the big data technology is studied to speed up the operation rate of the divisor scalar multiplication in the hyperelliptic curve cryptosystem(HECC). The conventional method of the divisor scalar multiplication is improved according to the "space-for-time" strategy,whose operation time computation is reduced by 16.28% under the condition that the task scale is 1016. A task partition optimization scheme based on load balancing is proposed. The operation efficiencies of the parallel algorithm and serial algorithm are studied by applying the parallel technologies of the Hadoop cluster platform,Spark cluster platform and Spark-GPU cluster platform to the improved divisor scalar multiplication algorithm. When the problem scale is fixed,the acceleration of different cluster platforms emerges in an upward trend with the increase of node quantity,in which the growth trend of the Spark-GPU parallel algorithm is the most obvious,and the speed-up ratio of the Spark-GPU parallel algorithm can reach 261.84 when the node quantity is 4. By comparing the parallel algorithms of three cluster platforms,it is found that the Spark-GPU parallel algorithm can most effectively reduce the operation time consumption and speed up the operation rate of divisor scalar multiplication.
A divisor scalar multiplication parallel algorithm based on the big data technology is studied to speed up the operation rate of the divisor scalar multiplication in the hyperelliptic curve cryptosystem(HECC). The conventional method of the divisor scalar multiplication is improved according to the "space-for-time" strategy,whose operation time computation is reduced by 16.28% under the condition that the task scale is 1016. A task partition optimization scheme based on load balancing is proposed. The operation efficiencies of the parallel algorithm and serial algorithm are studied by applying the parallel technologies of the Hadoop cluster platform,Spark cluster platform and Spark-GPU cluster platform to the improved divisor scalar multiplication algorithm. When the problem scale is fixed,the acceleration of different cluster platforms emerges in an upward trend with the increase of node quantity,in which the growth trend of the Spark-GPU parallel algorithm is the most obvious,and the speed-up ratio of the Spark-GPU parallel algorithm can reach 261.84 when the node quantity is 4. By comparing the parallel algorithms of three cluster platforms,it is found that the Spark-GPU parallel algorithm can most effectively reduce the operation time consumption and speed up the operation rate of divisor scalar multiplication.
引文
[1]KOBLITZ N.Hyperelliptic cryptosystems[J].Journal of cryptology,1989,1(3):139-150.
[2]KOBLITZ N.A family of Jacobians suitable for discrete log cryptosystems[C]//Proceedings of Conference on the Theory and Application of Cryptology.New York:Springer,1990:94-99.
[3]杨怡琳.超椭圆曲线上快速标量乘算法研究[D].杭州:杭州电子科技大学,2014.YANG Yilin.Research on fast scalar multiplication algorithm on hyperelliptic curves[D].Hangzhou:Hangzhou Dianzi University,2014.
[4]郝艳华,范欣欣,王育民.亏格为3的超椭圆曲线除子加法的并行算法[J].计算机科学,2007,34(8):114-119.HAO Yanhua,FAN Xinxin,WANG Yumin.Parallelizing explicit formula in Genus 3 hyperelliptic curves[J].Computer science,2007,34(8):114-119.
[5]朱艳蕊.超椭圆曲线标量乘快速算法研究[D].成都:西南交通大学,2013.ZHU Yanrui.Research on fast algorithm of superelliptic curve scalar multiplication[D].Chengdu:Southwest Jiaotong University,2013.
[6]游林.一类超椭圆曲线上的快速除子标量乘[J].电子学报,2008,36(10):2049-2054.YOU Lin.Fast divisor scalar multiplications on a class of hyperelliptic curves[J].Acta electronica sinica,2008,36(10):2049-2054.
[7]李建江,崔健,王聃,等.MapReduce并行编程模型研究综述[J].电子学报,2011,39(11):2635-2642.LI Jianjiang,CUI Jian,WANG Dan,et al.Survey of MapReduce parallel programming model[J].Acta electronica sinica,2011,39(11):2635-2642.
[8]江小平,李成华,向文,等.K-means聚类算法的MapReduce并行化实现[J].华中科技大学学报(自然科学版),2011,39(z1):120-124.JIANG Xiaoping,LI Chenghua,XIANG Wen,et al.Parallel implementing of K-means clustering algorithm using MapReduce programming mode[J].Journal of Huazhong University of Science and Technology(Natural science),2011,39(S1):120-124.
[9]周情涛,何军,胡昭华,等.基于GPU的Spark大数据技术在实验室的开发应用[J].实验室研究与探索,2017,36(1):112-116.ZHOU Qingtao,HE Jun,HU Zhaohua,et al.Department and application of the GPU-based Spark big data technology in laboratory[J].Research and exploration in laboratory,2017,36(1):112-116.
[10]杨冬进,娄建安,黄天辰.锂电池内阻测量的电路设计及其算法仿真[J].电子设计工程,2017,25(24):129-133.YANG Dongjin,LOU Jian’an,HUANG Tianchen.The circuit design of lithium battery internal resistance measurement and algorithm simulation[J].Electronic design engineering,2017,25(24):129-133.
[2]KOBLITZ N.A family of Jacobians suitable for discrete log cryptosystems[C]//Proceedings of Conference on the Theory and Application of Cryptology.New York:Springer,1990:94-99.
[3]杨怡琳.超椭圆曲线上快速标量乘算法研究[D].杭州:杭州电子科技大学,2014.YANG Yilin.Research on fast scalar multiplication algorithm on hyperelliptic curves[D].Hangzhou:Hangzhou Dianzi University,2014.
[4]郝艳华,范欣欣,王育民.亏格为3的超椭圆曲线除子加法的并行算法[J].计算机科学,2007,34(8):114-119.HAO Yanhua,FAN Xinxin,WANG Yumin.Parallelizing explicit formula in Genus 3 hyperelliptic curves[J].Computer science,2007,34(8):114-119.
[5]朱艳蕊.超椭圆曲线标量乘快速算法研究[D].成都:西南交通大学,2013.ZHU Yanrui.Research on fast algorithm of superelliptic curve scalar multiplication[D].Chengdu:Southwest Jiaotong University,2013.
[6]游林.一类超椭圆曲线上的快速除子标量乘[J].电子学报,2008,36(10):2049-2054.YOU Lin.Fast divisor scalar multiplications on a class of hyperelliptic curves[J].Acta electronica sinica,2008,36(10):2049-2054.
[7]李建江,崔健,王聃,等.MapReduce并行编程模型研究综述[J].电子学报,2011,39(11):2635-2642.LI Jianjiang,CUI Jian,WANG Dan,et al.Survey of MapReduce parallel programming model[J].Acta electronica sinica,2011,39(11):2635-2642.
[8]江小平,李成华,向文,等.K-means聚类算法的MapReduce并行化实现[J].华中科技大学学报(自然科学版),2011,39(z1):120-124.JIANG Xiaoping,LI Chenghua,XIANG Wen,et al.Parallel implementing of K-means clustering algorithm using MapReduce programming mode[J].Journal of Huazhong University of Science and Technology(Natural science),2011,39(S1):120-124.
[9]周情涛,何军,胡昭华,等.基于GPU的Spark大数据技术在实验室的开发应用[J].实验室研究与探索,2017,36(1):112-116.ZHOU Qingtao,HE Jun,HU Zhaohua,et al.Department and application of the GPU-based Spark big data technology in laboratory[J].Research and exploration in laboratory,2017,36(1):112-116.
[10]杨冬进,娄建安,黄天辰.锂电池内阻测量的电路设计及其算法仿真[J].电子设计工程,2017,25(24):129-133.YANG Dongjin,LOU Jian’an,HUANG Tianchen.The circuit design of lithium battery internal resistance measurement and algorithm simulation[J].Electronic design engineering,2017,25(24):129-133.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |