Optimization of RSA key reconstruction algorithms

Degree: Master
Contact Person: Florian Sieck / Sebastian Berndt

Field of Research

A common use case in cryptographic research is to reconstruct private or symmetric encryption and signing keys from partial information, e.g., information obtained from side-channels (cache attacks, power attacks, …). In the case of RSA, Heninger and Shacham developed a method which explores a search space bit by bit and prunes potential candidates based on the available side-channel information and conditions derived from the RSA equations. In two of our own recent works, we build on this algorithm and extend it to proceed in chunks of arbitrary size and information content. Additionally, we extend it to deal with keys that were constructed with Carmichael’s instead of Euler’s totient function.

Project Scope

In the future we would like to continue research on RSA key reconstruction and investigate options for dealing with errors in the obtained side-channel information or further improve pruning of the search space. Furthermore, we are interested in reducing the overhead introduced to explore the search space of “Carmichael keys” compared to “Euler keys”.

The Heninger and Shacham method is usually used to reconstruct keys where side-channel information is only available in non-continuous chunks. If a sufficiently long sequence of continuous bits was obtained, the Coppersmith method based on the shortest vector problem might be a more suitable approach. Additionally, it can be used after having reconstructed candidates of sufficient bit lengths with the method from Heninger and Shacham. We followed this approach in one of our works and would like to investigate whether the performance of the Coppersmith method can be further improved to speed up reconstruction / sort out non-viable candidates.