Recover an SSH private key?

Solution 1:

Presently the only way of "recovering" the Private key from the Public key is by exhaustive search (brute force). The system was specifically designed this way so that you could issue your public key to anyone without worrying about them being able to figure out your private key.

Edit:
Warning! Simplified explanation ahead!

Assuming you had RSA keys (the most common), the public key has two number in it: n and e. The private key has the same n, and another number d. Originally there were two huge prime numbers p and q which were used to calculate n, d, and e so that n and e could encrypt a text; n and d could decrypt the cyphertext. You have n and e. You can factor n to figure out p and q; the problem is that n is a freaking huge number with tons of possible p and q numbers. Currently there is no known way to do this quickly; I'm not sure if hackers have even bothered with writing tools to try. So in essence, no it's realistically not possible.

When you assign a passphrase to a key, it just does a simple encryption on the private key stored on your computer. The public key isn't affected at all by this. The passphrases are relatively easy to break compared to the private key itself; so this should not be relied on for primary security (you should keep your private key in safe places only).

Solution 2:

I'm pretty sure there's no way of recovering the private key if you have the public key - this would be a big security risk otherwise, because anyone with a public key would then be able to determine the private key from it.

---

Solution 3:

If I understand correctly, you want to generate a compatible private key from the public key. If this was possible, the whole system would be pointless. If you do manage it, I'd like to know how to I generate my bank's private key from their SSL certificate.