Comparison of Modified Pollard Rho for Discrete Logarithm Problem with the Original

Abstract

Elliptic Curve cryptosystems require small key size to implement public key cryptosystems and appear to be more secure and efficient. The security of Elliptic Curve cryptosystems is based on the difficulty of solving Elliptic Curve Discrete Logarithm Problem (ECDLP). The underlying basis of the many popular Public Key Scheme like Diffie-Hellman and ElGamal is Elliptic Curve Discrete Log Problem (ECDLP). The strength of such public key schemes is predicated on the problem of solving the ECDLP. The best methods for solving ECDLP has time complexity exponential within the size of the underlying field. ECDLP is based on Cryptosystems are popular as they provide good security at key sizes much smaller than number theoretical Public Key Schemes like RSA cryptosystem. ECDLP based cryptosystems are widespread in use, continuous efforts are being done on monitoring the effectiveness of latest attacks or improvements on existing attacks on ECDLP over large field. This paper shows a variant of generic algorithm Pollard’s Rho for locating ECDLP using cycle detection with stack and a mix of cycle detection and random walks. Pollard’s Rho algorithm using cycle detection with stack requires lesser number of iterations than Pollard’s Rho original algorithm in finding the collision. The iteration function
used in Pollard’s Rho algorithm is not random enough (Knuth, 1969), So Teske proposed a better iteration function by applying more arbitrary multipliers. Random walks allow the iteration function to act randomly than the primary iteration function, thus, the Pollard rho method performs more efficiently than the original. The experiment results show that the proposed methods decrease the number of iterations and speed up the computation of discrete logarithm problem on elliptic curves.