Open Access Open Access  Restricted Access Subscription or Fee Access

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

Sudarshan B. Khemnar, Roopika Chaudhary, Dr. D.B. Kulkarni

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.


Keywords


Compute Unified Device Architecture(CUDA), Cryptoanalysis, Elliptic Curves, Discrete Logarithm Problem (DLP), Elliptic Curves Discrete Logarithm Prob-lem( ECDLP), High Performance Computing, Graphics Processing Unit(GPU).

Full Text:

PDF

References


G. M. De Dormale, P. Bulens, and J. J. Quisquater, Collision search for elliptic curve discrete logarithm over GF (2 m) with FPGA. Springer, 2007.

W. Diffie and M. E. Hellman, “New directions in cryptography,” Information Theory, IEEE Transactions on, vol. 22, no. 6, pp. 644–654, 1976.

J. H. Silverman, Advanced topics in the arithmetic of elliptic curves. Springer Science & Business Media, 1994, vol. 151.

D. E. Knuth, “Seminumerical algorithms. the art of computer programming,” 1969.

E. Teske, Speeding up Pollard’s rho method for computing discrete logarithms. Springer, 1998.

M. Chinnici, S. Cuomo, M. Laporta, A. Pizzirani, and S. Migliori, “Cuda based implementation of parallelized pollard’s rho algorithm for ecdlp,” 2000.

P. C. Van Oorschot and M. J. Wiener, “Parallel collision search with cryptanalytic applications,” Journal of cryptology, vol. 12, no. 1, pp. 1–28, 1999.

H. C. Van Tilborg and S. Jajodia, Encyclopedia of cryptography and security. Springer Science & Business Media, 2011.

C¸. K. Koc¸, T. Acar, and B. S. Kaliski Jr, “Analyzing and comparing montgomery multiplication algorithms,” Micro, IEEE, vol. 16, no. 3, pp. 26–33, 1996.

S. A. Vanstone and A. J. Menezes, Guide to Elliptic Curve Cryptography. Springer, 2004.

http://www.certicom.com/.

N. Koblitz, A. Menezes, and S. Vanstone, The state of elliptic curve cryptography," in Towards a Quarter-Century of Public Key Cryptography. Springer, 2000, pp. 103-123.

V. Miller, Use of elliptic curves in cryptography," in Advances in CryptologyCRYPTO85 Proceedings. Springer, 1986, pp.417-426.

N. Koblitz, “Elliptic curve cryptosystems," Mathematics of computation, vol. 48, no. 177, pp. 203{209, 1987.

E. Teske, on random walks for pollards rho method," Mathematics of computation, vol. 70, no. 234, pp. 809-825, 2001.


Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.