Paper 2021/1558

RSA Key Recovery from Digit Equivalence Information

Chitchanok Chuengsatiansup, University of Adelaide
Andrew Feutrill, University of Adelaide, Data61
Rui Qi Sim, University of Adelaide
Yuval Yarom, University of Adelaide

The seminal work of Heninger and Shacham (Crypto 2009) demonstrated a method for reconstructing secret RSA keys from artial information of the key components. In this paper we further investigate this approach but apply it to a different context that appears in some side-channel attacks. We assume a fixed-window exponentiation algorithm that leaks the equivalence between digits, without leaking the value of the digits themselves. We explain how to exploit the side-channel information with the Heninger-Shacham algorithm. To analyse the complexity of the approach, we model the attack as a Markov process and experimentally validate the accuracy of the model. Our model shows that the attack is feasible in the commonly used case where the window size is 5.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. ACNS 2022
RSA side channel partial information
Contact author(s)
chitchanok chuengsatiansup @ adelaide edu au
rui sim @ adelaide edu au
yval @ cs adelaide edu au
2022-06-05: revised
2021-11-29: received
See all versions
Short URL
Creative Commons Attribution


      author = {Chitchanok Chuengsatiansup and Andrew Feutrill and Rui Qi Sim and Yuval Yarom},
      title = {RSA Key Recovery from Digit Equivalence Information},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1558},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.