Paper 2013/026

RSA private key reconstruction from random bits using SAT solvers

Constantinos Patsakis

Abstract

SAT solvers are being used more and more in Cryptanalysis. Their efficiency varies depending on the structure of the algorithm they are applied to. However, when it comes to integer factorization, or more specially the RSA problem, SAT solvers prove to be at least inefficient. The running times are too long to be compared with any well known integer factorization algorithm, even when it comes to small RSA moduli numbers. The recent work on cold boot attacks has sparkled again the interest on partial key exposure attacks and RSA key reconstruction. In this work, contrary to the search tree or lattice-based approaches that most of these works use, SAT solvers are used. The focus is on the study of two scenarios, one where there is disclosure of random bits of $p$ and $q$ and one for the case where the public exponent $e$ is equal to three. In both cases, we provide a more efficient modeling of RSA as an instance of a satisfiability problem, and manage to reconstruct the private key, given a part of the key, even for public keys of 1024 bits in few seconds.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Keywords
SAT solversRSApartial key exposurefactoringpublic-key cryptography
Contact author(s)
patsakik @ scss tcd ie
History
2013-05-07: revised
2013-01-24: received
See all versions
Short URL
https://ia.cr/2013/026
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/026,
      author = {Constantinos Patsakis},
      title = {RSA private key reconstruction from random bits using SAT solvers},
      howpublished = {Cryptology ePrint Archive, Paper 2013/026},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/026}},
      url = {https://eprint.iacr.org/2013/026}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.