二元域上椭圆曲线的Weierstrass形式到Edwards形式的转换算法  

Algorithm of Converting Weierstrass Form into Edwards Form for Elliptic Curves over Binary Fields

作　　者：张婧炜 赵昌安 ZHANG Jing-Wei;ZHAO Chang-An(School of Information Science, Guangdong University of Finance and Economics, Guangzhou 510320, China;School of Mathematics, Sun Yat-Sen University, Guangzhou 510275, China;Guangdong Key Laboratory of Information Security, Guangzhou 510006, China)

机构地区：[1]广东财经大学信息学院,广州510320 [2]中山大学数学学院,广州510275 [3]广东省信息安全技术重点实验室,广州510006

出　　处：《密码学报》2018年第3期315-323,共9页Journal of Cryptologic Research

基　　金：国家重点研发计划(2017YFB0802503;2017YFB0802504);国家自然科学基金(61472457);国家留学基金;广东省自然科学基金(2014A030313609);岭南基金;广东财经大学校级科研项目(14GJPY12001)~~

摘　　要：有限域上的椭圆曲线在公钥密码学中获得诸多应用,比如椭圆曲线密码系统、基于身份的加密体制和基于同种的Diffie-Hellman密钥交换等等.椭圆曲线具有多种代数方程表现形式,例如Weierstrass形式、Edwards形式、Huff形式和Hessian形式等.椭圆曲线的不同代数表达式在应用实现时有不同优势.与经典的Weierstrass形式相比,Edwards形式从计算效率和安全角度来说具有更多优势.故而近年来不少研究工作专注于Edwards形式的椭圆曲线.但传统椭圆曲线密码系统的标准参数均在Weierstrass形式下给出的,不便于工程人员在Edwards形式下做算法实现.本文的主要贡献是给出将二元域上椭圆曲线的Weierstrass形式到Edwards形式的转换算法.转换过程主要利用了Shallue-Woestijne算法和半分有理点算法,与已有结果相比,我们新提出的算法不依赖于任何条件并具有确定性多项式时间复杂度.实际上新的算法只需要很少的计算量.另外,我们还在附录中给出相应的例子以详细说明从Weierstrass形式到Edwards形式的转换过程.Elliptic curves over finite fields have found many applications in public key cryptography,such as elliptic curve cryptosystems（ECC）, identity-based encryption, isogeny-based Diffie-Hellman key exchange, etc. Elliptic curves have a variety of algebraic equations including Weierstrass form,Edwards form, Huff form, Hessian form, etc. Different forms of elliptic curves have their own merits.Compared with the classical Weierstrass form, the Edwards form has more advantages with respect to efficiency and security. However, the parameters of traditional ECC used in standards are given in the Weierstrass form. It is inconvenient for engineers to implement cryptographic algorithms in the Edwards form. This paper gives an algorithm of converting the Weierstrass form into the Edwards form for elliptic curves over binary fields. The converting process makes use of the Shallue-Woestijne algorithm and the halving a rational point algorithm. The proposed algorithm has a deterministic polynomial time complexity and does not require any additional condition compared with the previous results. In addition, only a small amount of computation is required in the proposed algorithm. An example is illustrated explicitly for the conversion process from the Weierstrass form into the Edwards form in the Appendix.

关 键 词：椭圆曲线 半分有理点算法 Edwards形式 Weierstrass形式 

分 类 号：TP309.7[自动化与计算机技术—计算机系统结构]