Optimizing Elliptic Curve Scalar Multiplication for Small Scalars

Pascal Giorgi 1, * Laurent Imbert 2, 1 Thomas Izard 1
* Auteur correspondant
1 ARITH - Arithmétique informatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : On an elliptic curve, the multiplication of a point P by a scalar k is defined by a series of operations over the field of definition of the curve E, usually a finite field Fq. The computational cost of [k]P = P + P + * * * + P (k times) is therefore expressed as the number of field operations (additions, multiplications, inversions). Scalar multiplication is usually computed using variants of the binary algorithm (double-and-add, NAF, wNAF, etc). If s is a small integer, optimized formula for [s]P can be used within a s-ary algorithm or with double-base methods with bases 2 and s. Optimized formulas exists for very small scalars (s 5). However, the exponential growth of the number of field operations makes it a very difficult task when s > 5. We present a generic method to automate transformations of formulas for elliptic curves over prime fields in various systems of coordinates. Our method uses a directed acyclic graph structure to find possible common subexpressions appearing in the formula and several arithmetic transformations. It produces efficient formulas to compute [s]P for a large set of small scalars s. In particular, we present a faster formula for [5]P in Jacobian coordinates. Moreover, our program can produce code for various mathematical software (Magma) and libraries (PACE).
Type de document :
Communication dans un congrès
Mathematics for Signal and Information Processing, 2009, San Diego, CA, United States. pp.74440N, 2009, Proceeding of SPIE. 〈http://spie.org/x648.html?product_id=830092&origin_id=x648〉. 〈10.1117/12.827689〉
Liste complète des métadonnées

Littérature citée [9 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00424282
Contributeur : Pascal Giorgi <>
Soumis le : mercredi 14 octobre 2009 - 17:33:52
Dernière modification le : jeudi 24 mai 2018 - 15:59:21
Document(s) archivé(s) le : mardi 16 octobre 2012 - 12:15:16

Fichier

spie_ecc.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Pascal Giorgi, Laurent Imbert, Thomas Izard. Optimizing Elliptic Curve Scalar Multiplication for Small Scalars. Mathematics for Signal and Information Processing, 2009, San Diego, CA, United States. pp.74440N, 2009, Proceeding of SPIE. 〈http://spie.org/x648.html?product_id=830092&origin_id=x648〉. 〈10.1117/12.827689〉. 〈lirmm-00424282〉

Partager

Métriques

Consultations de la notice

166

Téléchargements de fichiers

152