Improving Modular Inversion in RNS using the Plus-Minus Method

Karim Bigou 1 Arnaud Tisserand 1, *
* Auteur correspondant
1 CAIRN - Energy Efficient Computing ArchItectures with Embedded Reconfigurable Resources
Inria Rennes – Bretagne Atlantique , IRISA-D3 - ARCHITECTURE
Abstract : The paper describes a new RNS modular inversion algorithm based on the extended Euclidean algorithm and the plus-minus trick. In our algorithm, comparisons over large RNS values are replaced by cheap computations modulo 4. Comparisons to an RNS version based on Fermat's little theorem were carried out. The number of elementary modular operations is signi cantly reduced: a factor 12 to 26 for multiplications and 6 to 21 for additions. Virtex 5 FPGAs implementations show that for a similar area, our plus-minus RNS modular inversion is 6 to 10 times faster.
Keywords : Residue Number System Modular Representation Extended Euclidean Algorithm Hardware Implementation ECC RSA
Type de document :
Communication dans un congrès
Guido Bertoni and Jean-Sébastien Coron. CHES - 15th Workshop on Cryptographic Hardware and Embedded Systems - 2013, Aug 2013, Santa Barbara, United States. Springer, 8086, pp.233-249, 2013, LNCS. 〈10.1007/978-3-642-40349-1_14〉
Liste complète des métadonnées

Littérature citée [10 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-00825745
Contributeur : Arnaud Tisserand <>
Soumis le : vendredi 24 mai 2013 - 14:36:36
Dernière modification le : mercredi 11 avril 2018 - 02:01:16
Document(s) archivé(s) le : mardi 4 avril 2017 - 11:08:13

Fichier

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

Identifiants

Collections

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

Citation

Karim Bigou, Arnaud Tisserand. Improving Modular Inversion in RNS using the Plus-Minus Method. Guido Bertoni and Jean-Sébastien Coron. CHES - 15th Workshop on Cryptographic Hardware and Embedded Systems - 2013, Aug 2013, Santa Barbara, United States. Springer, 8086, pp.233-249, 2013, LNCS. 〈10.1007/978-3-642-40349-1_14〉. 〈hal-00825745〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

655

Téléchargements de fichiers

373

Contact


archive-ouverte@inria.fr