Paper 2018/009

Evaluation of Resilience of randomized RNS implementation

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

Abstract

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)$.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint. MINOR revision.
Keywords
RNSmoduli randomizationMonte CarloECCside channel attackDPACPADPA Square
Contact author(s)
jerome courtois @ lip6 fr
History
2018-01-02: received
Short URL
https://ia.cr/2018/009
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/009,
      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{https://eprint.iacr.org/2018/009}},
      url = {https://eprint.iacr.org/2018/009}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.