Computing Dlp Of Koblitz Elliptic Curve

Elliptic Curve Cryptosystem(ECC) is one of the most popular public key cryptosystem. Because of the special construction, the length of the key to reach the safety level is very short and it can be implemented very efficiently. The Elliptic Curve Discrete Logarithm Problem(ECDLP) is the safety core of ECC. The fastest algorithm solving ECDLP is exponential time. It means that the encryption and signature based on ECDLP is much safer. The algorithms to solve ECDLP can be divided into two categories: algorithms that work in the general setting, and algorithms that use specific properties of the elliptic curve to develop a different approach. Pollard’s rho method and its parallelized variants are very efficient generic algorithms for computing ECDLP. In 1997, the Canadian company Certicom presented the Certicom ECC Challenge to encourage research in ECC and evaluation of its safety. The research on ECDLP has been developed to increase the industry’s understanding and appreciation for the difficulty of the elliptic curve discrete logarithm problem, and to encourage and stimulate further research in the security analysis of elliptic curve cryptosystems. Koblitz curve is a special elliptic curve defined in 2 like 2+ = 3+ 1 or 2+ = 3+ 2+ 1. There is a special map called Frobenius endomorphism on Koblitz curve. On Koblitz curve, group operation can be computed very fast, and Frobenius endomorphism and point halving can increase the speed of scalar multiplication. So Koblitz curve has been welcome and widely worked in the industrial standard. There are 5 Koblitz curves in the NIST recommended elliptic cures.This thesis concentrates on the safety problem of Koblitz curve, which is solving ECDLP on Koblitz curve. We implement the algorithm on Koblitz curve using polynomial bases and normal bases with the help of Frobenius endomorphism and point halving in software and solve ECDLP of 41 and 83 bits successfully. For the first time, we compare polynomial bases with normal bases in theory and practice in software implementation, and make a conclusion. Though normal bases are often used in hardware implementation, under the premise of combining Frobenius endomorphism and point halving on Koblitz curve, the efficiency of normal bases is higher than polynomial bases.