摘要
有限域上的椭圆曲线在公钥密码学中获得诸多应用,比如椭圆曲线密码系统、基于身份的加密体制和基于同种的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.
作者
张婧炜
赵昌安
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)
出处
《密码学报》
CSCD
2018年第3期315-323,共9页
Journal of Cryptologic Research
基金
国家重点研发计划(2017YFB0802503
2017YFB0802504)
国家自然科学基金(61472457)
国家留学基金
广东省自然科学基金(2014A030313609)
岭南基金
广东财经大学校级科研项目(14GJPY12001)~~
