Study of modular inversion in RNS
Jean-Claude Bajard, Nicolas Méloni, Thomas Plantard · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 2005
Residue Numbers System have some features which are fine for some implementations of cryptographic protocols. The main property of RNS is the distribution of the evaluation on large values on its small residues, allowing parallelization. This last property implies that we can randomize the distribution of the bases elements. Hence, the obtained arithmetic is leak resistant, it is robust against side channel attacks. But 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.