Fast Algorithm Of Elliptic Curve Cryptography

In 1985, Koblitz and Miller independently proposed using the group of points on an elliptic curve defined over a finite field to construct cryptosystem, that is elliptic curves cryptography(ECC)([1][2]). Its idea is that finding a safe elliptic curve and by encoding, messages are embedded in elliptic curve, and then cipher these points on the curve. Its safety depends on discrete logarithm problem over Abelian group of points on elliptic curve. Because computing the discrete logarithm more difficulty than the discrete logarithm over multiplication group, so it is possible to construct quite safe cryptosystem. While maintaining the same level of security, elliptic curve cryptogram have smaller key size, bandwidth savings, and faster implementations, so it was employed extensively in smart card and wireless devices and so on.The operation consume most time is multiplication of a point on the elliptic curve with an integer in the system, which was called multiple point operation. Since the system mainly depends on multiple point operation, so the cost of executing the system depends mostly on the cost of the multiple points operation. Therefore, the key of the efficient executing elliptic curve cryptogram is the efficient computing of multiple point. In the paper, I proposed three methods of computing multiple point, which increase the efficiency of computing multiple point on the original basis.Recursive algorithm deduces recursive formula of doubling point firstly, then deduce recursive formula of random multiple point. The recursive algorithm incorporates the two formulas, and derive efficient recursive algorithm of computing nP. The efficiency was increased 38% than point by point algorithm.On the base of addition formula, ternary algorithm deduces triple point formula. Then on the base of mending algorithm of a signed digit representation in radix r for an integer which was proposed by S.Aron and F.S.Wheeler([14]), derive a signed digit representation of minimal Hamming weight for an integer in radix 3. By triple point computing nP step by step. The efficiency of Ternary algorithm was increased 12.4% than double algorithm.ω-NAF recursive algorithm employs recursive formula of doubling point to mend width-ωwindow method, which the efficiency ofω-NAF recursive algorithm wasincreased 1-(16+6ω)/(9+9ω)than width-ωwindow method.