论文标题:超椭圆曲线密码体制快速算法研究
Research on Fast Algorithms for Hyperelliptic Curve Cryptosystem
论文作者 范欣欣
论文导师 王育民,论文学位 硕士,论文专业 通信与信息系统
论文单位 西安电子科技大学,点击次数 129,论文页数 85页File Size4571k
2005-01-01论文网 http://www.lw23.com/lunwen_498421072/ 公钥密码体制;椭圆曲线密码体制;超椭圆曲线密码体制;最优塔域;明确公式;标量乘
Public-Key Cryptosystem; Elliptic Curve Cryptosystem; Hyperelliptic Curve Cryptosystem; Optimal Tower Field; Explicit Formula; Scalar Multiplication
本文对超椭圆曲线密码体制快速算法进行了比较深入的研究，内容包括：从有限域算术、群运算的明确公式、标量乘算法的角度对影响超椭圆曲线密码体制性能的诸多因素进行的研究以及在不同的应用环境下椭圆曲线密码体制(ECC)与超椭圆曲线密码体制(HECC)的优化实现问题，我们主要的成果有： 1、给出了最优塔域GF(p~(2~2))与GF(p~(2~3))的构造方法并推导了上述两个有限域中快速求逆公式。 2、在最优塔域GF((2~(20)-3)~(2~3))上构造了160比特的二次孪生椭圆曲线密码体制并结合最优塔域上的快速求逆公式以及孪生曲线上Frobenius映射给出了该密码体制的快速实现。 3、实现了最优扩域GF((2~(29)-3)~7)上175比特的椭圆曲线密码体制以及最优塔域GF((2~(22)-3)~(2~2))上176比特亏格为2的超椭圆曲线密码体制，对两个密码体制的性能作了详尽的比较与分析。 4、首次在射影坐标系下对亏格为3的超椭圆曲线密码体制推导了无需求逆的明确公式。选取了4个有代表性的有限域(包括1个素数域及3个二元域)对新公式的性能进行了测试。对新公式与已有明确公式的实现速度进行了详尽的比较与分析。 5、利用查表法对基于特殊超椭圆曲线上有效自同态的标量乘算法进行了改进，分析了改进算法的时间与空间复杂度。 6、提出了同时除子类加—减算法，在仿射坐标系以及射影坐标系下给出了该算法的明确公式并利用该技巧提高了两种标量乘算法预计算部分的速度。
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.
|
