CUDA based Implementation of Parallelized Pollards Rho Algorithm for ECDLP: A Review

Abstract

NVidia has introduced Compute Unified Device Architecture (CUDA) libraries for parallel programming approach to High Performance Computing on Graphic Processing Units (GPU) and developed the use of graphics cards for solving hard computational problems in different field like fluid dynamics, molecular dynamics, computer vision, image processing and weather forecasting. This paper shows how CUDA libraries and hardware can be utilized in cryptography area to develop crypto analytic tool. Due to increased data communications over internet, cryptography become a real necessity for secure communication. Sometimes, private key cryptography are less secure, so public key cryptography are required for communication over insecure channels. Elliptic curves offer less communication overhead due to use of theory of elliptic curves. In general case, security is strongly based on the intractability of an arithmetic problem such as Discrete Logarithm Problem (DLP). Elliptic curve cryptography reduces the solution of DLP in the elliptic curve group points and gives efficient solution for ECDLP. Various methods are derived but are less efficient in solving cases of the generalized DLP. Some methods have deterministic running time. Some methods with probabilistic running time such as Pollards rho method requires less space and time so it provides an better solvability. Pollards rho method and its parallelized version are best generic algorithms for solving Elliptic curve discrete logarithms. However, Collision detection always consumes more time and space, while computing discrete logarithms in cyclic groups of large orders with Pollards rho method.

We describe an implementation of a parallelized Pollards rho attack on ECDLP, based on recent study about the optimization of Pollards rho method using GPU CUDA architecture.