Genetic programming for improved cryptanalysis of elliptic curve cryptosystems

Abstract

Public-key cryptography is a fundamental compo- nent of modern electronic communication that can be constructed with many different mathematical processes. Presently, cryp- tosystems based on elliptic curves are becoming popular due to strong cryptographic strength per small key size. At the heart of these schemes is the intractability of the elliptic curve discrete logarithm problem (ECDLP). Pollard’s Rho algorithm is a well known method for solving the ECDLP and thereby breaking ciphers based on elliptic curves. It has the same time complexity as other known methods but is advantageous due to smaller memory requirements. This paper considers how to speed up the Rho process by modifying a key component: the iterating function, which is the part of the algorithm responsible for determining what point is considered next when looking for a collision. It is replaced with an alternative that is found through an evolutionary process. This alternative consistently and significantly decreases the number of iterations required by Pollard’s Rho Algorithm to successfully find a solution to the ECDLP.