2

Is it possible to recover a private key, given a public key and a substring/a part of the corresponding private key?

  • How did you end up with a partial private key? And what exactly do you mean by that? Part of the private exponent d? Or part of a "full" private key with d, p, q, dp etc.? The the latter case you might have received the full` value of p or q which would make factoring trivial. – CodesInChaos Apr 14 '15 at 15:27
2

Yes, but it depends on how much of the private key you have.

RSA can always be brute-forced if you know the public key; it is protected by the sheer length of time that it will take to try out all possible factors.
If you have part of the private key, this means you can rule out a number of candidates - those that don't contain this part of the private key.
How much of an advantage this is, depends on how big the public/private key pair is, and how much of the private key you have.

  • 3
    I believe that you can use lattice reduction method to attack RSA if you know part of the private key far more efficiently than brute-force. But I'm no expert in that kind of maths. – CodesInChaos Apr 14 '15 at 11:46
  • Thank you, S.L. Barth. Are there any ready to use utilities that can help to figure out a missing private key with the data given (public key and a part of the corresponding private key)? – Evgeny Apr 14 '15 at 11:59
  • @Evgeny Not that I'm aware of, but there might well be. You might get help on Software Recommendations, but be sure to read their Help Center before posting. I'm not active there myself, so I'm not certain if this question fits the criteria there. – S.L. Barth - Reinstate Monica Apr 14 '15 at 12:22
  • There might be password crackers that allow for partially known private keys. It sounds like a problem that developers would find challenging, especially given the possibility of using advanced mathematics like the lattice-reduction that @CodesInChaos mentions. – S.L. Barth - Reinstate Monica Apr 14 '15 at 15:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.