Research On Accelerating The Relative Algorithms Of ECC

Public Key Cryptosystems is key technology of realizing information security. Public Key Cryptosystems based on the Elliptic Curve theory are divided into two types: Elliptic Curve Cryptography (ECC) and Identity-Based Cryptosystems (IBC). Efficiently implementing cryptosystem is one of hot points in cryptography realm. Modifying and optimizing every implementing algorithm is the primary content of it. Scalar multiplication and multiple scalar multiplications are the most crucial algorithms of implementing Elliptic Curve Cryptosystems. Computing Tate Pairing is the kernel algorithm of implementing Identity-Based Cryptosystems. In this dissertation, we studied these two aspects.First, basing on point halving, this thesis proposed a new efficient algorithm of computing kP+lQ on an elliptic curve over the finite field with characteristic 2 and analyzed the computational efficiency. When the ratio I/M of inversion to multiplication cost is small, this new algorithm is about 5%～30% faster than the traditional algorithms.Subsequently, We studied the Duursma-Lee algorithm and the modified Duursma-Lee algorithm that are algorithms of computing Tate pairing of supersingular elliptic curve over finite fields with characteristic three. We directly reduced the Duursma-Lee algorithm applying the theory of divison from the defination of Tate Pairing. Then we introduced a new equavalent defination of Tate pairing of supersingular elliptic curve over finite fields with characteristic three or two, that it has lower final exponent. We proposed two refined algorithms of the modified Duursma-Lee algorithm. The two algorithms are enhanced by 6.7% and 13.3% respectively, comparing with the costs of the modified Duursma-Lee algorithm.Eventually, we also modified Miller algorithm of computing Tate pairing over the finite field with which characteristic is prime p (p>3) . The modified algorithm is enhanced by 12%.