tailieunhanh - Fast Algorithms for Elliptic Curve Cryptosystems over Binary Finite Field

In the underlying finite field arithmetic of an elliptic curve cryptosystem, field multiplication is the next computational costly operation other than field inversion. We present two novel algorithms for efficient implementation of field multiplication and modular reduction used frequently in an elliptic curve cryptosystem defined over GF (2n ). | Fast Algorithms for Elliptic Curve Cryptosystems over Binary Finite Field Published in . Lam and E. Okamoto Eds. Advances in Cryptology ASIACRYPT 99 vol. 1716 of Lecture Notes in Computer Science pp. 75-85 Springer-Verlag 1999. Yongfei Han1 Peng-Chor Leong2 Peng-Chong Tan2 and Jiang Zhang1 1 Gemplus Corporate R D APDC Security Crypto Dept 89 Science Park Drive 04-01 05 Singapore 118261 yfh69@ 2 Centre for Advanced Information Systems School of Applied Science Nanyang Technological University Singapore 639798 Abstract. In the underlying finite field arithmetic of an elliptic curve cryptosystem field multiplication is the next computational costly operation other than field inversion. We present two novel algorithms for efficient implementation of field multiplication and modular reduction used frequently in an elliptic curve cryptosystem defined over GF 2n . We provide a complexity study of the two algorithms and present an implementation performance of the algorithms over GF 2167 . Keywords. Galois field arithmetic elliptic curve cryptosystems field multiplication modular reduction. 1 Introduction In 1985 Neil Koblitz and Victor Miller independently proposed the elliptic curve cryptosystem whose security rests on the discrete logarithm problem over points on an elliptic curve. Elliptic curve cryptography can be used to provide both a digital signature scheme and an encryption scheme. With the apparent advantage of high cryptographic strength relative to key size elliptic curve cryptosystems have gained much popularity in the implementation of discrete logarithm based public key protocols. The shorter key size generally leads to improved computational efficiencies and smaller storage and bandwidth requirements. Although elliptic curve cryptosystem can be based on finite field of any characteristic it is generally practical to implement within the prime or binary finite field . Certain classes of elliptic curves such as the subfield curves .