Cryptology ePrint Archive: Report 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.

Category / Keywords: implementation / Residue Number System, Modular Representation, Extended Euclidean Algorithm, Hardware Implementation, ECC, RSA

Original Publication (in the same form): IACR-CHES-2013
DOI: 10.1007/978-3-642-40349-1_14

Date: received 3 Mar 2015

Contact author: karim bigou at irisa fr, arnaud tisserand@irisa fr

Available format(s): PDF | BibTeX Citation

Version: 20150304:164026 (All versions of this report)

Short URL: ia.cr/2015/193

Discussion forum: Show discussion | Start new discussion