Abstract
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 .
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.
Permanent ID of this document: 592248bfa170d87d90a8d543cb645788. Date of this document: 2008.05.16. This work has been supported in part by the European Commission through the IST Programme under Contract IST–2002–507932 ECRYPT, in part by the National Science Foundation under grant ITR–0716498, and in part by the Ministry of Science, Research and Technology of I. R. Iran under scholarship no. 800.147.
Chapter PDF
Similar content being viewed by others
Keywords
References
Agnew, G.B., Mullin, R.C., Vanstone, S.A.: An implementation of elliptic curve cryptosystems over \(F_{2^{155}}\). IEEE Journal on Selected Areas in Communications 11, 804–813 (1993); Citations in this document: §7, §7
Bernstein, D.J., Lange, T.: Faster addition and doubling on elliptic curves. In: Asiacrypt 2007 [24] pp. 29–50 (2007); Citations in this document: §1, §1, §1, §1
Billet, O., Joye, M.: The Jacobi model of an elliptic curve and side-channel analysis. In: AAECC 2003 [12] pp. 34–42 (2003), http://eprint.iacr.org/2002/125 ; MR 2005c:94045. Citations in this document: §1
Blake, I.F., Seroussi, G., Smart, N.P. (eds.): Advances in elliptic curve cryptography. London Mathematical Society Lecture Note Series, vol. 317. Cambridge University Press, Cambridge (2005); MR 2007g:94001. See [17]
Brier, É., Déchène, I., Joye, M.: Unified point addition formulae for elliptic curve cryptosystems. In: [32], pp. 247–256 (2004); Citations in this document: §1
Brier, É., Joye, M.: Weierstrass elliptic curves and side-channel attacks. In: PKC 2002 [31], pp. 335–345 (2002), www.geocities.com/MarcJoye/publications.html ; Citations in this document: §1, §7
Cohen, H., Frey, G. (eds.): Handbook of elliptic and hyperelliptic curve cryptography. CRC Press, Boca Raton (2005); MR 2007f:14020. See [9], [25]
Desmedt, Y.G. (ed.): PKC 2003. LNCS, vol. 2567. Springer, Heidelberg (2002); See [16], [33]
Doche, C., Lange, T.: Arithmetic of elliptic curves. In: [7], pp. 267–302 (2005); MR 2162729. Citations in this document: §2, §6, §6
Edwards, H.M.: A normal form for elliptic curves. Bulletin of the American Mathematical Society 44, 393–422 (2007), http://www.ams.org/bull/2007-44-03/S0273-0979-07-01153-6/home.html ; Citations in this document: §1
Fischer, W., Giraud, C., Knudsen, E.W., Seifert, J.-P.: Parallel scalar multiplication on general elliptic curves over \(\mathbb{F}_p\) hedged against non-differential side-channel attacks (2002), http://eprint.iacr.org/2002/007 ; Citations in this document: §7
Fossorier, M., Høholdt, T., Poli, A. (eds.): AAECC 2003. LNCS, vol. 2643. Springer, Heidelberg (2003), MR 2004j:94001. See [3]
Gaudry, P.: Variants of the Montgomery form based on Theta functions (2006), http://www.loria.fr/~gaudry/publis/toronto.pdf ; Citations in this document: §7, §7
Gaudry, P., Lubicz, D.: The arithmetic of characteristic 2 Kummer surfaces (2008), http://eprint.iacr.org/2008/133 ; Citations in this document: §7
Izu, T., Takagi, T.: A fast parallel elliptic curve multiplication resistant against side channel attacks. In: PKC 2002 [31], pp. 280–296 (2002); Citations in this document §7
Izu, T., Takagi, T.: Exceptional procedure attack on elliptic curve cryptosystems. In: PKC 2003 [8], pp. 224–239 (2002); Citations in this document: §1
Joye, M.: Defences against side-channel analysis. In: [4], pp. 87–100 (2005); Citations in this document: §1
Joye, M., Quisquater, J.-J.: Hessian elliptic curves and side-channel attacks. In: CHES 2001 [22], pp. 402–410 (2001); MR 2003k:94032, www.geocities.com/MarcJoye/publications.html ; Citations in this document: §1
Joye, M., Yen, S.-M.: The Montgomery powering ladder. In: CHES 2002 [20], pp. 291–302 (2003), http://www.gemplus.com/smart/rd/publications/pdf/JY03mont.pdf ; Citations in this document: §7
Kaliski Jr., B.S., Koç, Ç.K., Paar, C. (eds.): CHES 2002. LNCS, vol. 2523. Springer, Heidelberg (2003); See [19]
Kim, K.H., Kim, S.I.: A new method for speeding up arithmetic on elliptic curves over binary fields (2007), http://eprint.iacr.org/2007/181 ; Citations in this document: §6
Koç, Ç.K., Naccache, D., Paar, C. (eds.): CHES 2001. LNCS, vol. 2162. Springer, Heidelberg (2001); MR 2003g:94002. See [18], [27]
Koç, Ç.K., Paar, C. (eds.): CHES 1999. LNCS, vol. 1717. Springer, Heidelberg (1999); See [29]
Kurosawa, K. (ed.): ASIACRYPT 2007. LNCS, vol. 4833. Springer, Heidelberg (2007); See [2]
Lange, T.: Mathematical countermeasures against side-channel attacks. In: [7], pp. 687–714 (2005); MR 2163785, Citations in this document: §1
Lange, T.: A note on López-Dahab coordinates. Tatra Mountains Mathematical Publications 33, 75–81 (2006), http://eprint.iacr.org/2004/323 ; MR 2007f:11139. Citations in this document: §6
Liardet, P.-Y., Smart, N.P.: Preventing SPA/DPA in ECC systems using the Jacobi form. In: CHES 2001, [22], pp. 391–401 (2001); MR 2003k:94033, Citations in this document: §1
López, J., Dahab, R.: Improved algorithms for elliptic curve arithmetic in GF(2n). In: SAC 1998, [35], pp. 201–212 (1999); MR 1715809, Citations in this document: §6
López, J., Dahab, R.: Fast multiplication on elliptic curves over GF(2m) without precomputation. In: CHES 1999, [23], pp. 316–327 (1999); Citations in this document: §7, §7, §7, §7
Montgomery, P.L.: Speeding the Pollard and elliptic curve methods of factorization. Mathematics of Computation 48, 243–264 (1987), http://links.jstor.org/sici?sici=0025-5718(198701)48:177243:STPAEC2.0.CO;2-3; MR 88e:11130. Citations in this document: §7
Naccache, D., Paillier, P. (eds.): PKC 2002. LNCS, vol. 2274. Springer, Heidelberg (2002); MR 2005b:94044. See [6], [15]
Nedjah, N., Mourelle, L.M. (eds.): Embedded cryptographic hardware: methodologies & architectures. Nova Science Publishers (2004); ISBN 1–59454–012–8. See [5]
Stam, M.: On Montgomery-like representations for elliptic curves over GF(2k). In: PKC 2003, [8], pp. 240–254 (2002); Citations in this document: §7, §7, §7
Stein, W. (ed.): Sage Mathematics Software (Version 2.8.13). The Sage Group (2008), http://www.sagemath.org Citations in this document: §3
Tavares, S., Meijer, H. (eds.): SAC 1998. LNCS, vol. 1556. Springer, Heidelberg (1999); MR 1715799. See [28]
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bernstein, D.J., Lange, T., Rezaeian Farashahi, R. (2008). Binary Edwards Curves . In: Oswald, E., Rohatgi, P. (eds) Cryptographic Hardware and Embedded Systems – CHES 2008. CHES 2008. Lecture Notes in Computer Science, vol 5154. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-85053-3_16
Download citation
DOI: https://doi.org/10.1007/978-3-540-85053-3_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-85052-6
Online ISBN: 978-3-540-85053-3
eBook Packages: Computer ScienceComputer Science (R0)