Parallel Efficiency Analysis On The Related Algorithms Of Elliptic Curve With GPU

Recently,the related algorithms of elliptic curve are widely used in the fields of cryptography and integer factorization.The Elliptic Curve Cryptography (ECC) has become one of the most important standards about information security, and the Elliptic Curve Method of factorization (ECM) has an significant application in the factorization of surplus factors for Number Field Sieve (NFS) which is the best algorithm to attack the RSA at present.Therefore, research on the rapid realization of ECC and ECM is of great significance both for the application of ECC and the attack of RSA.Along with the development of hardware and programmability about Graphics Processing Unit (GPU), it has been a current parallel computation platform with high performance which is applied in the fields of image processing, speech recognition and cryptography.The research of this paper is mainly for the parallel implementation method and the efficiency analysis of the related algorithms of elliptic curve on GPU, the main results are as follows:Firstly, the model of algorithm performance evaluation on GPU is established from the characteristics of the related algorithms of elliptic curve.By analyzing memory types, visit-save pattern, instruction types and thread organization and considering the influence of throughput and time delay, the evaluation formula about the algorithm's computing time and visit-save time is given in the model. The experimental results indicate that the model can evaluate the efficiency of the algorithm implementation effectively which is the foundation of efficiency analysis about the related algorithms of elliptic curve on GPU.Secondly, because modular multiplication is the key operation of the related algorithms for elliptic curve,three parallel implementation methods of modular multiplication under standard radix on GPU are offered.Similarly,the method under the RNS is given.Then,the efficiency of these methods are analyzed and compared with the model in the first section.The result shows that the best way of modular multiplication implementation on prime field with GPU is to complete one operation independently with single thread under the full word radix.Finally, the optimal implementation and efficiency analysis of ECDSA and ECM are given.Firstly, using the Edwards curve, we give the theory evaluation and experimental result of the algorithm's efficiency for the ECDSA on the prime field of 160bits, 192bits, 224bits, 256bits and 384bits. For example, in the prime field of 256bits, comparing with Crypto++560 on Pentium(R) 4 CPU 3.00GHz, the signature speed on NVIDIA 9800 GTX+ is 46 times faster and the verification speed is 35 times faster.Secondly, using the Montgomery curve, we could verify 6629 curves one second when choosing the first bound B1=1024 and the second bound B₂=57000 on the prime field of 160bits. The implementation provides an experimental support to the factorization of surplus factors in NFS of RSA1024.