Paper 2021/1558
RSA Key Recovery from Digit Equivalence Information
Chitchanok Chuengsatiansup and Andrew Feutrill and Rui Qi Sim and Yuval Yarom
Abstract
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.
Metadata
- Available format(s)
- Category
- Public-key cryptography
- Publication info
- Published elsewhere. ACNS 2022
- Keywords
- RSAside channelpartial information
- Contact author(s)
-
rui sim @ adelaide edu au
yval @ cs adelaide edu au,andrew feutrill @ data61 csiro au,chitchanok chuengsatiansup @ adelaide edu au - History
- 2022-06-05: revised
- 2021-11-29: received
- See all versions
- Short URL
- https://ia.cr/2021/1558
- License
-
CC BY