Combining leak–resistant arithmetic for elliptic curves defined over Fp and RNS representation

International audience— In this paper we give a survey of a method combining the residue number system (RNS) representation and the leak-resistant arithmetic on elliptic curves. These two techniques are relevant for implementation of elliptic curve cryptography on embedded devices. It is well known that the RNS multiplication is very efficient whereas the reduction step is costly. Hence, we optimize formulae for basic operations arising in leak-resistant arithmetic on elliptic curves (unified addition, Montgomery ladder) in order to minimize the number of modular reductions. We also improve the complexity of the RNS modular reduction step. As a result, we show how to obtain a competitive secured implementation. Finally, we show that, contrary to other approaches, this method takes optimally the advan-tage of a dedicated parallel architecture. Résumé. — Dans cet article, nous donnons un survol d'une méthode qui combine le système de représentation des nombres basé sur les restes chinois (RNS) avec les formules de loi de groupe sur les courbes elliptiques qui sont résistantes aux attaques par fuites. Ces deux techniques sont particulièrement intéressantes pour l'implémentation de cryptosystèmes basés sur les courbes elliptiques dans des systèmes embarqués. Dans le système de représentation RNS, la multiplication de grands entiers est très efficace contrairement à la réduction modulaire. Nous réécrivons donc ici les formules de la loi de groupe pour les modèles de courbes elliptiques résistant aux fuites (loi d'addition unifiée, forme de Mont-gomery) dans le but de minimiser le nombre de réductions modulaires. Nous améliorons aussi la complexité de l'étape de réduction. Ces deux aspects permettent d'obtenir des implémentations sécurisées compétitives. Finalement, nous montrons que, contrairement aux autres approches, cette méthode peut profiter pleinement d'une architecture parallèle dédiée. 2010 Mathematics Subject Classification. — 14G50