Skip to main content
placeholder image

Study of modular inversion in RNS

Conference Paper


Abstract


  • Residue Numbers System have some features useful in implementations of cryptographic protocols. The main property of RNS is the distribution of the evaluation on large values over its small residues, allowing parallelization. This last property implies that we can randomize the distribution of the bases elements. Hence, the resulting arithmetic is leak resistant, i.e. robust against side channel attacks. One drawback of RNS is that modular inversion is not obvious. Thus, RNS is well suited for RSA but not really for ECC. We analyze in this paper the features of the modular inversion in RNS over GF(P). We propose a RNS Extended Euclidean Algorithm which uses a quotient approximation module.

Publication Date


  • 2005

Citation


  • Bajard, J. C., Meloni, N., & Plantard, T. (2005). Study of modular inversion in RNS. In Proceedings of SPIE - The International Society for Optical Engineering Vol. 5910 (pp. 1-9). doi:10.1117/12.617543

Scopus Eid


  • 2-s2.0-30644479888

Web Of Science Accession Number


Start Page


  • 1

End Page


  • 9

Volume


  • 5910

Abstract


  • Residue Numbers System have some features useful in implementations of cryptographic protocols. The main property of RNS is the distribution of the evaluation on large values over its small residues, allowing parallelization. This last property implies that we can randomize the distribution of the bases elements. Hence, the resulting arithmetic is leak resistant, i.e. robust against side channel attacks. One drawback of RNS is that modular inversion is not obvious. Thus, RNS is well suited for RSA but not really for ECC. We analyze in this paper the features of the modular inversion in RNS over GF(P). We propose a RNS Extended Euclidean Algorithm which uses a quotient approximation module.

Publication Date


  • 2005

Citation


  • Bajard, J. C., Meloni, N., & Plantard, T. (2005). Study of modular inversion in RNS. In Proceedings of SPIE - The International Society for Optical Engineering Vol. 5910 (pp. 1-9). doi:10.1117/12.617543

Scopus Eid


  • 2-s2.0-30644479888

Web Of Science Accession Number


Start Page


  • 1

End Page


  • 9

Volume


  • 5910