Accelerating Pollard’s Rho Algorithm On The Elliptic Curve Discrete Logarithm Problem

Many forms of elliptic curve cryptography is slightly different, but all of them depend on the form which is widely acknowledged by the difficulty of solving elliptic curve discrete logarithm problem, corresponding the group of elliptic curve over finite field. Study shows that the elliptic curve cryptosystem is currently the only public key password that can’t be broken by the index algorithm.Discrete logarithm public key encryption algorithm is one of the most popular public key encryption algorithm, its security is far higher than the RSA algorithm, based on the decomposition of large numbers. According to decades of unremitting efforts of cryptographers. we have gotten a lot of achievements on solving elliptic curve discrete logarithm problem, and produced many of the classic algorithm, such as Shanks’baby-step giant-step algorithm (BSGS)[1], Pollard’s p algorithm [2], Pohlig-Hellman algorithm, Index Calculus dissuade algorithm, etc., and some algorithms to the special type of elliptic curve, like MOV algorithm [3]. SSAS algorithm and so on. We will focus our attention on Pollard’s p algorithm in this article.Pollard’s p algorithm based on the birthday paradox, is actually a defor-mation of the BSGS algorithm. In this algorithm, we look for matches or collision during the elements in group, and hope that we can recover out some information about the starting point from this collision. The operation time and is the same to the BSGS algorithm, but it doesn’t need storage space.Later, cryptanalysts put forward many kinds of improvement and opti- mization methods of the p algorithm on this basis. South Korea cryptologist Jung Hee Cheon. Jin Hong and Minkyu Kim [1] proposed a kind of improve-ment for p algorithm on the discrete logarithm in finite field. For the elements of G=<g>, still use the iterative function to generate a random sequence like in the original rho algorithm, and make sure they are exponent traceable. We selected a property as conditions to sift point, and define the elements which meet the property as distinguished points. Jung Hee Cheon et al., com-bine with an index function s:Gâ†'{0,1}, it maps1/r of the elements in G to0, the rest to1. Select a small positive integer δ, define the last point gi as a distinguished point which satisfies the equation s{gi-δ+1)=...=s(gi-1)=s(gi)=0Because the distinguished points defined through the path segment approach are not uniformly distributed within the random walk and that they tend to group together, for collision detection, it is sufficient to choose and store just one node from each string of distinguished points. We can get the aver-age distance between continuous strings or groups of distinguished points is r/r-1(rδ-1). That is, we will get a distinguished point by r/r-1(rδ-1) iteration computation.Then we will use tag tracing method to begin iterative computation. Before the start of the iteration, assume that we have an index function s:Gâ†'S={0,1,..., r-1} and a pre-computed table Ml, M={mi}i∈S. In iterative process, we don’t need to compute gi+i=gimsi in each iteration as before, by introducing an auxiliary index function bars:G x Mlâ†'S, it can be easier to compute gi+1. Then combined with the definition of distinguished points, choose the distinguished points generated by the iterative process and store them, until a collision is found. Compared with the iterative calculation process, time of compute the pre-computed table Ml can be ignored. This method will be faster than the original p algorithm.In this paper, we will extend the the improved method of p algorithm to discrete logarithm problem over elliptic curve. The p algorithm on the elliptic curve discrete: logarithm is similar to it on finite field, but the ECDLP is more, difficult than the DLP. In combination with predecessors’ ideas, we can consider to transform the elliptic curve discrete logarithm problem to finite field, and reapply the improvement methods of Jung Hoe Cheon et al.Method selected in this paper is MOV algorithm which was proposed by Menezes, Okamoto and Van.stone in199;5. Defining the bilinear of Weil pair Using the properties of bilinear pairings to complete the transformation of MOV algorithm. Its core idea is: the ECDLP is converted into a DLP on the multiplicative group of a finite field, actually transform Fq to its extension field Fqk. And n|qk-1is the necessary condition of the transformation of MOV.In practical application, this method is not effective for all of the elliptic curve1, but restricted by the expansion of the finite field number k. If the value of k is too large, the difficulty of solving the discrete logarithm problems is not reduced, the algorithm cannot be an effective operation. So we should choose small k. At present, when k <6through the operation, MOV algorithm is very effective1for a special kind of elliptic curve discrete logarithm, it’s the supersingular elliptic curve. The time of this process is subexponential. After using MOV algorithm to couverte the ECDLP to DLP, we can use the above improved p algorithm to solve the discrete logarithm problems.