Study of Modular Inversion in RNS

摘要

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 paral-lelization. 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.