This paper presents a new shape for ordinary elliptic curves
over fields of characteristic 2. Using the new shape, this paper presents
the first complete addition formulas for binary elliptic curves, i.e., addition
formulas that work for all pairs of input points, with no exceptional
cases. If n = 3 then the complete curves cover all isomorphism classes of
ordinary elliptic curves over F2n.
This paper also presents dedicated doubling formulas for these curves
using 2M+ 6S + 3D, where M is the cost of a field multiplication, S is
the cost of a field squaring, and D is the cost of multiplying by a curve
parameter. These doubling formulas are also the first complete doubling
formulas in the literature, with no exceptions for the neutral element,
points of order 2, etc.
Finally, this paper presents complete formulas for differential addition,
i.e., addition of points with known difference. A differential addition and
doubling, the basic step in a Montgomery ladder, uses 5M+ 4S + 2D
when the known difference is given in affine form.
|Title of host publication||Cryptographic Hardware and Embedded Systems - CHES 2008 (10th International Workshop, Washington DC, USA, August 10-13, 2008, Proceedings)|
|Editors||E. Oswald, P. Rohatgi|
|Place of Publication||Berlin|
|Publication status||Published - 2008|
|Name||Lecture Notes in Computer Science|