I have an RSA key (generated by PuTTYgen) that's set up for logging in to a bunch of machines via SSH. Or rather, i HAD such a key. (The computer it was on crashed, to the point that a reinstall of XP was required. The private key file is encrypted by the file system, and now that it's basically on what looks like a whole other OS and user, whatever XP would do to decrypt the key apparently can't be done anymore.)
What i have left is an OpenSSL-compatible base64 of the public key (from one of the machines still set up to accept passwords), and of course the passphrase to the key. I might(!) still have an old backup of the registry from before the machine died as well, but would have to search for it. Either way, it sounds like it might not be possible to recover the key file itself. (If it is possible, that'd be great. But the prospects aren't looking good so far.)
Is there any way to recover the private key, if i can't recover the actual file that contained it? Perhaps by importing the public key into PuTTYgen or openssl and doing some reverse thing on it? Contacting all the admins involved and sending them new keys could be a pain, so that's pretty much a last resort.
Best Answer
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).