Combining Montgomery Ladder for Elliptic Curves Defined over $\F_p$ and RNS Representation
Jean-Claude Bajard, Sylvain Duquesne, Nicolas Méloni · 2006
In this paper, we combine the RNS representation and the Montgomery ladder on elliptic curves in Weierstrass form. These two techniques are relevant for implementation of elliptic curve cryptography on embedded devices since they have leak-resistance properties. We optimize formulae for addition and doubling of the Montgomery ladder in terms of modular reductions to obtain a competitive and secure implementation. Afterwards, we explain the advantages of the RNS representation, especially in hardware and for embedded devices, and show that, contrary to other approaches, ours takes optimal advantage of a dedicated parallel architecture.