Paper 2018/009

Evaluation of Resilience of randomized RNS implementation

Jérôme Courtois, Lokman Abbas-Turki, and Jean-Claude Bajard


Randomized moduli in Residue Number System (RNS) generate effectively large noise and make quite difficult to attack a secret key $K$ from only few observations of Hamming distances $H=(H_0, ..., H_{d-1})$ that result from the changes on the state variable. Since Hamming distances have gaussian distribution and most of the statistic tests, like NIST's ones, evaluate discrete and uniform distribution, we choose to use side-channel attacks as a tool in order to evaluate randomisation of Hamming distances . This paper analyses the resilience against Correlation Power Analysis (CPA), Differential Power Analysis (DPA) when the cryptographic system is protected against Simple Power Analysis (SPA) by a Montgomery Powering Ladder (MPL). While both analysis use only information on the current state, DPA Square crosses the information of all the states. We emphasize that DPA Square performs better than DPA and CPA and we show that the number of observations $S$ needed to perform an attack increases with respect to the number of moduli $n$. For Elliptic Curves Cryptography (ECC) and using a Monte Carlo simulation, we conjecture that $S = O((2n)!/(n!)^2)$.

Available format(s)
Publication info
Preprint. MINOR revision.
RNSmoduli randomizationMonte CarloECCside channel attackDPACPADPA Square
Contact author(s)
jerome courtois @ lip6 fr
2018-01-02: received
Short URL
Creative Commons Attribution


      author = {Jérôme Courtois and Lokman Abbas-Turki and Jean-Claude Bajard},
      title = {Evaluation of Resilience of randomized {RNS} implementation},
      howpublished = {Cryptology ePrint Archive, Paper 2018/009},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.