Faster Addition and Doubling on Elliptic Curves
Edwards recently introduced a new normal form for elliptic curves. Every elliptic curve over a non-binary field is birationally equivalent to a curve in Edwards form over an extension of the field, and in many cases over the original field.
- PDF / 565,404 Bytes
- 22 Pages / 430 x 660 pts Page_size
- 47 Downloads / 261 Views
Department of Mathematics, Statistics, and Computer Science (M/C 249) University of Illinois at Chicago, Chicago, IL 60607–7045, USA [email protected] 2 Department of Mathematics and Computer Science Technische Universiteit Eindhoven, P.O. Box 513, 5600 MB Eindhoven, Netherlands [email protected]
Abstract. Edwards recently introduced a new normal form for elliptic curves. Every elliptic curve over a non-binary field is birationally equivalent to a curve in Edwards form over an extension of the field, and in many cases over the original field. This paper presents fast explicit formulas (and register allocations) for group operations on an Edwards curve. The algorithm for doubling uses only 3M + 4S, i.e., 3 field multiplications and 4 field squarings. If curve parameters are chosen to be small then the algorithm for mixed addition uses only 9M + 1S and the algorithm for non-mixed addition uses only 10M + 1S. Arbitrary Edwards curves can be handled at the cost of just one extra multiplication by a curve parameter. For comparison, the fastest algorithms known for the popular “a4 = −3 Jacobian” form use 3M + 5S for doubling; use 7M + 4S for mixed addition; use 11M + 5S for non-mixed addition; and use 10M + 4S for non-mixed addition when one input has been added before. The explicit formulas for non-mixed addition on an Edwards curve can be used for doublings at no extra cost, simplifying protection against side-channel attacks. Even better, many elliptic curves (approximately 1/4 of all isomorphism classes of elliptic curves over a non-binary finite field) are birationally equivalent — over the original field — to Edwards curves where this addition algorithm works for all pairs of curve points, including inverses, the neutral element, etc. This paper contains an extensive comparison of different forms of elliptic curves and different coordinate systems for the basic group operations (doubling, mixed addition, non-mixed addition, and unified addition) as well as higher-level operations such as multi-scalar multiplication. Keywords: Elliptic curves, addition, doubling, explicit formulas, register allocation, scalar multiplication, multi-scalar multiplication, sidechannel countermeasures, unified addition formulas, complete addition formulas, efficient implementation, performance evaluation.
Permanent ID of this document: 95616567a6ba20f575c5f25e7cebaf83. Date of this document: 2007.09.28. This work has been supported in part by the European Commission through the IST Programme under Contract IST–2002–507932 ECRYPT. This work was carried out while the first author was visiting Technische Universiteit Eindhoven.
K. Kurosawa (Ed.): ASIACRYPT 2007, LNCS 4833, pp. 29–50, 2007. c International Association for Cryptology Research 2007
30
1
D.J. Bernstein and T. Lange
Introduction
The core operations in elliptic-curve cryptography are single-scalar multiplication (m, P → mP ), double-scalar multiplication (m, n, P, Q → mP + nQ), etc. Miller, in his Crypto ’85 paper introducing elliptic-curve cryptography, proposed carrying out t
Data Loading...
