Improving Modular Inversion in RNS using the Plus-Minus Method
| Autor: | Karim Bigou, Arnaud Tisserand |
|---|---|
| Přispěvatelé: | Energy Efficient Computing ArchItectures with Embedded Reconfigurable Resources (CAIRN), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-ARCHITECTURE (IRISA-D3), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA), Financement de thèse DGA-INRIA, Guido Bertoni and Jean-Sébastien Coron, ANR-12-BS02-0002,PAVOIS,Protections Arithmétiques Vis à vis des attaques physiques pour la cryptOgraphIe basée sur les courbeS elliptiques(2012), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS) |
| Jazyk: | angličtina |
| Rok vydání: | 2013 |
| Předmět: |
Modulo
Computation 02 engineering and technology Residue number system Extended Euclidean Algorithm Hardware Implementation [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR] RSA ACM: B.: Hardware/B.2: ARITHMETIC AND LOGIC STRUCTURES 0202 electrical engineering electronic engineering information engineering ECC Arithmetic Hardware_ARITHMETICANDLOGICSTRUCTURES [SPI.NANO]Engineering Sciences [physics]/Micro and nanotechnologies/Microelectronics Field-programmable gate array Residue Number System Mathematics Fermat's Last Theorem Virtex business.industry Modular Representation [INFO.INFO-AO]Computer Science [cs]/Computer Arithmetic 020206 networking & telecommunications Modular design 020202 computer hardware & architecture Extended Euclidean algorithm business |
| Zdroj: | CHES-15th Workshop on Cryptographic Hardware and Embedded Systems-2013 CHES-15th Workshop on Cryptographic Hardware and Embedded Systems-2013, Aug 2013, Santa Barbara, United States. pp.233-249, ⟨10.1007/978-3-642-40349-1_14⟩ Cryptographic Hardware and Embedded Systems-CHES 2013 ISBN: 9783642403484 CHES |
| DOI: | 10.1007/978-3-642-40349-1_14⟩ |
| Popis: | International audience; 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|