Paper 2015/193

Improving Modular Inversion in RNS using the Plus-Minus Method

Karim Bigou and Arnaud Tisserand

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 significantly 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.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published by the IACR in CHES 2013
DOI
10.1007/978-3-642-40349-1_14
Keywords
Residue Number SystemModular RepresentationExtended Euclidean AlgorithmHardware ImplementationECCRSA
Contact author(s)
karim bigou @ irisa fr
arnaud tisserand @ irisa fr
History
2015-03-04: received
Short URL
https://ia.cr/2015/193
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/193,
      author = {Karim Bigou and Arnaud Tisserand},
      title = {Improving Modular Inversion in RNS using the Plus-Minus Method},
      howpublished = {Cryptology ePrint Archive, Paper 2015/193},
      year = {2015},
      doi = {10.1007/978-3-642-40349-1_14},
      note = {\url{https://eprint.iacr.org/2015/193}},
      url = {https://eprint.iacr.org/2015/193}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.