My problem is a common one: I deleted my SSH key, and forgot to set rm to point to a .trash file. I have the public key, and I need to get in this server. I am not doing this on anyone else's server. I have enough resources to do it, I just need a program.

  • Assuming you do have the resources to do it (perhaps you intentionally make it small enough to be feasable and thus insecure..), what format is it in? – user2813274 Jul 23 '14 at 20:30

If it was possible (with existing technology) to rebuild the private key from the public key, then everybody would be doing it.

Asymmetric algorithms are designed to avoid that. In the case of RSA, rebuilding the private key from the public key is equivalent(*) to integer factorization, which is a hard problem whose difficulty raises quite sharply when the integer size is increased. Current world record for a non-special integer (i.e. a properly generated RSA key) is 768 bits and it took some substantial effort, estimated to about 2000 CPU-year. An important point is that part of the algorithm requires a system with a lot of very fast RAM (we are talking terabytes here), and nobody knows yet how to handle that part with existing technology in the case of a 1024-bit RSA modulus. We have some preliminary designs for specialized hardware which might achieve it, but would cost a lot (not mere millions of dollars) and be rather bulky.

Bottom-line is that you won't succeed in cracking your SSH key, even if you use the best available hardware.

(*) Cracking RSA, as in "computing a forged signature", is not proven equivalent to integer factorization; but rebuilding the private key is equivalent to factoring the modulus.

  • Thanks everyone for the answers! I realized that while SSH uses keys, I should be able to just go into SFTP and edit my authorized_keys file. – StackExchange User Mar 27 '13 at 18:38
  • EDIT: I realize that I can't do that. Oops! – StackExchange User Mar 27 '13 at 18:40

As other answers already tell you, forget about brute-forcing the key. It can't be done. Not in a million years (or at least not for a million dollars).

(Unless the key was generated with a buggy implementation.)

What you may be able to do, but even that is by no means assured, is recover the deleted file. Deleting a file only removes it from the directory listing, it doesn't wipe the file contents, so the contents may still be sitting around on the disk. The space is marked as free, so it may be reused by another file. So you must immediately stop writing to the disk. A dirty shutdown is preferable.

Make a copy of the partition containing the file and work from that copy, it's safer. Use a carving tool (TestDisk is a bootable Linux distribution that contains a good collection) to locate free blocks that contain something that looks like a private key file. It's very recognizable: the file begins with -----BEGIN RSA PRIVATE KEY-----. A private key file is less than one block long on most filesystems, so it won't be fragmented: once you find the first block, you have the whole thing.

You may or may not be able to find the private key file this way. It may already have been overwritten. Even if you do find it, expect to spend hours setting up your recovery environment and digging through deleted blocks. Arranging for an alternate way to access the server is likely to be less effort.

In the future, remember to make backups of all critical data such as private keys. Store them in a safe place, of course, but to remember that availability (keeping stuff accessible) is a security property, it's not all about confidentiality (keeping stuff inaccessible).

  • Actually, EXT3 deletes the whole file, writing it over with 0's. – StackExchange User Mar 27 '13 at 18:41
  • 3
    @IanCarroll No, it doesn't. That would make deletion needlessly slow. Ext3 only zeroes out the directory entry (the file name, its metadata and the location of the block table) and part of the block table. It doesn't zero the file data, so it is possible (but never assured) that you will be able to find the deleted data in the free space. – Gilles 'SO- stop being evil' Mar 27 '13 at 20:14
  • Ah, sorry! Didn't know that. – StackExchange User Mar 28 '13 at 21:50

The whole points of asymmetric encryption is that it is impossible to recover a private key from a public key. So what you want to do is completely unfeasible.

Generate a new key pair and forget about recovering the old one.

  • 3
    Actually, there are some things that are impossible with our current knowledge of the laws of physics. security.stackexchange.com/a/6149/10211 And no, unless you have access to a working quantum computer it isn't feasible. – user10211 Mar 26 '13 at 16:25

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.