On-the-Fly Multi-Base Recoding for ECC Scalar Multiplication without Pre-Computations

Thomas Chabrier 1 Arnaud Tisserand 1, *
* Auteur correspondant
1 CAIRN - Energy Efficient Computing ArchItectures with Embedded Reconfigurable Resources
Inria Rennes – Bretagne Atlantique , IRISA-D3 - ARCHITECTURE
Abstract : Scalar recoding is popular to speed up ECC scalar multiplication: non-adjacent form, double-base number system, multi-base number system. But fast recoding methods require pre-computations: multiples of base point or off-line conversion. In this paper, we present a multi-base recoding method for ECC scalar multiplication based on i) a greedy algorithm starting least significant terms first, ii) cheap divisibility tests by multi-base elements and iii) fast exact divisions by multibase elements. Multi-base terms are obtained on-the-fly using a special recoding unit which operates in parallel to curve-level operations and at very high speed. This ensures that all recoding steps are performed fast enough to schedule the next curve-level operations without interruptions. The proposed method can be fully implemented in hardware without pre-computations. We report FPGA implementation details and very good performances compared to state-of-art results.
Keywords : elliptic curve cryptography scalar multiplication DBNS MBNS divisibility test exact division by constant
Type de document :
Communication dans un congrès
ARITH - 21st IEEE International Symposium on Computer Arithmetic, Apr 2013, Austin, TX, United States. IEEE, pp.219-228, 2013, 〈10.1109/ARITH.2013.17〉
Liste complète des métadonnées

Littérature citée [29 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-00772613
Contributeur : Arnaud Tisserand <>
Soumis le : jeudi 10 janvier 2013 - 18:22:40
Dernière modification le : mercredi 11 avril 2018 - 02:00:24
Document(s) archivé(s) le : jeudi 11 avril 2013 - 04:08:52

Fichier

PID2635353.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

Collections

INRIA | IRISA | IRISA-D3 | UR1-UFR-ISTIC | UNIV-RENNES | INRIA-RENGRE

Citation

Thomas Chabrier, Arnaud Tisserand. On-the-Fly Multi-Base Recoding for ECC Scalar Multiplication without Pre-Computations. ARITH - 21st IEEE International Symposium on Computer Arithmetic, Apr 2013, Austin, TX, United States. IEEE, pp.219-228, 2013, 〈10.1109/ARITH.2013.17〉. 〈hal-00772613〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

486

Téléchargements de fichiers

367

Contact


archive-ouverte@inria.fr