# RSA private/public keys

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. Apr 14, 2015 at 15:27

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.

• 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. Apr 14, 2015 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)? Apr 14, 2015 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. Apr 14, 2015 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. Apr 14, 2015 at 15:23