Improving the Efficiency of Elliptic Curve Scalar Multiplication Using Binary Huff Curves

摘要

In 2010, Joye et. al brought the so-called Huff curve model, which was originally proposed in 1948 for the studies of diophantine equations, into the context of elliptic curve cryptography. Their initial work describes Huff curves over fields of large prime characteristic and details unified addition laws. Devigne and Joye subsequently extended the model to elliptic curves over binary fields and proposed fast differential addition formulas that are well-suited for use with the Montgomery ladder, which is a side-channel attack resistant scalar multiplication algorithm. Moreover, they showed that, in contrast to Huff curves over prime fields, it is possible to convert (almost) all binary Weierstrass curves into Huff form. We have implemented generalized binary Huff curves in software using a differential Montgomery ladder and detail the implementation as well as the optimizations to it. We provide timings, which show speed-ups of up to 7.4% for binary NIST curves in Huff form compared to the reference implementation on Weierstrass curves. Furthermore, we present fast formulas for mapping between binary Weierstrass and generalized binary Huff curves and vice versa, where in the back conversion step an implicit y-coordinate recovery is performed. With these formulas, the implementation of the differential Montgomery ladder on Huff curves does not require more effort than its counterpart on Weierstrass curves. Thus, given the performance gains discussed in this paper, such an implementation is an interesting alternative to conventional implementations. Finally, we give a list of Huff curve parameters corresponding to the binary NIST curves specified in FIPS 186-3.