Research On Fast Algorithms For Hyperelliptic Curve Cryptosystem

A detailed investigation of fast algorithms for Hyperelliptic Curve Cryptosystem (HECC) is given in this thesis. We have focused on many factors which influence on the performance of HECC from the viewpoint of finite field arithmetic, explicit formulae for group arithmetic and scalar multiplication algorithm, and on the optimized implementations of ECC and HECC. The key contributions follow below.1. Construction methods of two optimal tower fields (OTFs) GF(p22) and GF(p23) are given. Fast inversion formulae over two OTFs above are derived.2. 160-bits Quadratic Twist ECC is constructed over OTF GF((220 -3)23). Based on a combination of fast inversion formulae of OTF and Frobenius map of twist curves, the cryptosystem above is implemented.3. 175-bits ECC defined over optimal extension field (OEF) GF((229-3)7)and 176-bits genus two HECC defined over OTF GF((222 -3)22) are implemented. The performance of two cryptosystems is compared and analyzed in detail.4. For the first time, the inversion-free explicit formulae are derived for genus 3 HECC in projective coordinate system. Four representative finite fields including one prime field and three binary fields are selected to test the performance of new explicit formulae. The implementation speed of the new and original explicit formulae is compared and analyzed in detail.5. Using the look-up tables, the scalar multiplication algorithm based on efficient computable endomorphisms on special hyperelliptic curves is improved. Time and space complexity of improved algorithms are analyzed.6. Simultaneous Divisor Class Addition-Subtraction Algorithm is proposed. Explicit formulae of the algorithm are given in affine and projective coordinate system. Using this skill, the precomputation part of two scalar multiplication algorithms for HECC is accelerated.