| In 1976, Diffie and Hellman proposed a view of public key cryptosystem. This is a revolution in cryptography, and has a very important historical landmark. Before, al-most all the cryptosystems are built on the basis of substitution and transposition, but the public key cryptosystem is different from the previous cryptosystem, which is bas-ed on a special mathematical functions. In public key cryptography system, each user has its own public key and private key, but calculates private key from the known pu-blic key is difficult.Since then, a lot of public key cryptography systems are proposed. Their security is based on their own mathematical problems. Some of public key cryptography is su-ccessful; some have been proved to be unsuccessful. Now, only 3 types of public key cryptography are considered to be safe and effective. According to its mathematical pr-oblem, these systems can be divided into:(1) Integer factorization problem;(2)Discrete logarithm problem;(3) Elliptic curve discrete logarithm problem.Among them, the elliptic curve is considered as the most secure public key cryp-tography system. The 163-bit ECC is equivalent to the 1024-bit RSA. Therefore, with the increasing of computing power and key length, relative to other public key crypto-graphy, ECC is more to attract our attention.Cryptography and cryptanalysis are contradictory things on both sides, they promote each other. On one hand, Cryptanalysis is a threat to the security of Cryptology. On the other hand, this makes a great promote of Cryptography by responding to a variety of threats. From the ideal angle, the security of the cryptography system should not rely on the confidentiality of the algorithm, but depend only on the secrecy of the key. For the Public key cryptography, such as ECC, it depends on the confidentiality of the private key.In 1978, Pollard invented a method f called Pollard's rho algorithm, which is used to solve DLP at first. Now it can also be used to solve ECDLP. For all known algorithms in solving ECDLP, Pollard's rho algorithm is the most effective and fastest algorithm. It can be said that the security of ECC depends on the efficiency of Pollard's rho algorithm. If Pollard's rho algorithm can solve ECDLP in a short time, the security of the ECC system will be greatly reduced. Therefore, this paper is mainly researching the theory and implementation of Pollard's rho algorithm.Calculating the order of ECC is critical in Cryptanalysis. There is a lot of algorit-hm for calculating the order of ECC, including:Schoof algorithm and SEA algorithm, complex multiplication algorithm, Baby-Step-Giant-Step, Satoh algorithm, Harley al-gorithm and so on. This paper researches some of them and implements the Schoof al-gorithmSecondly, this paper discusses the commonly used algorithms for solving ECDLP. Where, the attack on the general elliptic curve algorithms is including: Baby-Step-Giant-Step algorithm, Pollard's rho algorithm, Pohlig-Hellman algorithm, Pollard's lambda algorithm; Attack on the special curve is including:MOV attack, FR attack, SSAS attack, Weil drop attacks (GHS attack) and so on. Through analyzing a variety of attack algorithms, the paper proposes a standard of generating secure elliptic curves.Finally, according to the median order of elliptic curves (Decimal), we have a grouped experiment. We have chosen number of iterations, time and as the evaluation criteria of Pollard's rho attack algorithm's performance. When the median order of elliptic curves is 4, the ECDLP can be resolved on average 77.8 times collisions and 1.0049 seconds. When the median order of elliptic curves is 5, the ECDLP can be resolved on average 282.2 times collisions and 3.2966 seconds. This proves that the implementation of Pollard's rho algorithm is correct and effective. Then we improve the iteration function of Pollard's rho attack algorithm was improved. The original iteration function consists of two point additions and a point doubling operation. The improved iteration function contains r point additions and q point doubling operation. And r and q can be chosen. After a lot of experiments, we found that when r is 30 and q is 10, L is only 0.7125. However, when we use the original iteration function, L is 1.2216.The performance is improved 42.7%. And this greatly improves the efficiency of the algorithm. |
