New random walk technique and collision detection algorithm to improve the pollard rho attack of solving discrete logarithm problem on elliptic curves

Abstract

Elliptic curve cryptography is a revolutionary in the history of public key cryptography that is protected by a hard problem Elliptic Curve Discrete Logarithm Problem (ECDLP). A wide research has been done on cryptanalysis of ECDLP. In 1978 Pollard developed an algorithm with a “Monte-Carlo” method for solving ECDLP called Pollard Rho attack which is the quickest algorithm. Since then the algorithm was modified to increase the efficiency of Pollard Rho algorithm in relatively short time to find the insecurity of the elliptic curve cryptosystem. The present paper designs a new random walk technique and collision detection algorithm to improve the performance of Pollard Rho algorithm.