Parallel Algorithm Research For Divisor Scalar Multiplication In Hyperelliptic Curve Cryptography

As an extension of the elliptic curve cryptosystem(ECC),the algebraic structure of the hyperelliptic curve cryptosystem(HECC)is more complex,more secure,and has a broader application prospect.However,there are still some bottleneck problem in HECC that need to be solved urgently.The most prominent problem is how to speed up the operation of the divisior scalar multiplication on the Jacobian group,thus improving the efficiency of the entire cryptosystem.In this paper,firstly the optimization and performance analysis of the traditional divisior scalar multiplication algorithm are carried out,and then the general parallelization model of the divisior scalar multiplication is proposed.Finally,the algorithm is designed and implemented,and two experiments are carried out on the Spark platform:time-consuming comparison experiment of the divisior scalar multiplication serial algorithm based on local environment,acceleration ratio experiment of the divisior scalar multiplication parallel algorithm based on Spark cluster environment.The specific research contents are as follows:(1)Optimization and performance analysis of traditional divisior scalar multiplication algorithmAccording to the basic computing architecture of HECC,research has been carried out from bottom to up.In addition to optimization for atomic algorithms such as domain operations and Jacobian group operations,the traditional divisior scalar multiplication algorithm in HECC is studied and improved,such as the binary algorithm,the NAF algorithm,the sliding window algorithm,etc.,and the time complexity is analyzed and discussed.(2)Proposal and performance analysis of general parallelization model of the divisior scalar multiplicationFrom the theoretical level,parallelization design of the divisior scalar multiplication is carried out.The general parallelization model of the divisior scalar multiplication is proposed,which is the splitting and integrating model,and the time complexity of the parallelization model is analyzed.(3)Time-consuming comparison experiment of the divisior scalar multiplication serial algorithm based on local environmentFrom the practical application aspect,compare operation time-consuming of the traditional algorithm and the optimization algorithm.The experimental results show that the optimization algorithm has higher computational efficiency than the traditional algorithm.The efficiency of the sliding window optimization algorithm is the largest,which is increased by 10.66%.The computational efficiency of other optimization algorithms is also increased by about 10%compared with the traditional algorithm,so the effectiveness of the optimization algorithm is fully proved.(4)Acceleration ratio experiment of the divisior scalar multiplication parallel algorithm based on Spark cluster environmentCombined with the common divisior scalar multiplication algorithm,the splitting and integrating model is used for parallel design,and the divisior scalar multiplication parallel computing is performed based on the Spark cluster environment,and analyze the computational time-consuming and acceleration ratio of parallel algorithms from the two aspects of "same task scale,different number of nodes" and "same number of nodes,different task scale".The experimental results show that:(a)When the task size is fixed(the bit length is 150),if the number of nodes in the cluster is gradually added,the acceleration ratio will continue to grow.When the number of nodes is 8,the acceleration ratio of the generalized double-base chain algorithm based on the Spark cluster platform reaches 7.4247.However,as the number of nodes increases,the communication overhead between nodes increases,so the growth rate of the acceleration ratio decreases gradually.(b)When four nodes are configured in the cluster,as the scale of the problem increases,the running time required by the algorithm basically shows an exponential growth trend,and the growth rate of the acceleration ratio is also very obvious,eventually approaching the limit acceleration ratio 4.0.In addition,the security analysis of the divisior scalar multiplication optimization algorithm is performed.The analysis results show that the optimization algorithm can resist SCA attacks and has better security performance than the traditional divisior scalar multiplication serial algorithm.In summary,the optimization of the traditional divisior scalar multiplication algorithm are carried out in this article,and the general parallelization model of the divisior scalar multiplication is proposed,and experiments are designed in Spark environment.The experimental results shows that the computational efficiency of the divisior scalar multiplication optimization algorithm is higher than that of the divisior scalar multiplication algorithm,and it is more secure.At the same time,the divisior scalar multiplication parallelization algorithm has a good acceleration ratio in the Spark cluster environment,which shows that the divisior scalar multiplication parallelization algorithm can effectively shorten the computational time,thus improving the overall implementation efficiency of HECC.