Cryptology ePrint Archive: Report 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.

Category / Keywords: public-key cryptography / RSA, side channel, partial information

Original Publication (in the same form): ACNS 2022

Date: received 27 Nov 2021, last revised 29 Nov 2021

Contact author: rui sim at adelaide edu au, yval at cs adelaide edu au, andrew feutrill at data61 csiro au, chitchanok chuengsatiansup at adelaide edu au

Available format(s): PDF | BibTeX Citation

Version: 20211129:122427 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]