-2
$\begingroup$

I know nothing about cryptography.

I must present a completed ASP project to my university that proves I have learned clingo. I have heard that the task of recovering the plaintext private RSA key given the one encrypted with a password is rather simple, taking about a day on an average PC. So the task seems suitable.

I am looking for papers, tutorials and implementations in other languages-- anything that would enable me to complete the task within ~3 months.

$\endgroup$
4
  • 1
    $\begingroup$ With a secure passphrase, it'd take milennia even with all the world's computers combined. It'd only take a day if the password was chosen by a moron. $\endgroup$ Jul 23 '21 at 12:23
  • 1
    $\begingroup$ I'm not sure that logic programming for hard problems is a good match either. Yes, search, but I'm missing the way you need to logically describe the problem. I mean, I'm kinda doubtful that it will start to build e.g. rainbow tables all by itself, or perform a dictionary attack. $\endgroup$
    – Maarten Bodewes
    Jul 23 '21 at 13:30
  • $\begingroup$ @MaartenBodewes I can't imagine even one domain in which logic programming shines. Any idea about a most relevant SE to ask about that? $\endgroup$
    – Vorac
    Jul 23 '21 at 15:58
  • 1
    $\begingroup$ @Vorac Computer Science maybe, but I'd ask in chat first. You should have had some background on this before. If not, please ask an instructor or professor to give a hint (and hope it isn't the one I had)! $\endgroup$
    – Maarten Bodewes
    Jul 23 '21 at 16:16
0
$\begingroup$

The encryption of the key has nothing to do with RSA. Cracking it is as hard as cracking every other encrypted stuff using the same encryption algorithm (not RSA, because it would be encrypt symmetrically with something like AES). Best you can do is bruteforcing the password and hope it is a weak one. No magic here.

$\endgroup$
3
  • $\begingroup$ When bruteforcing how do I test if I've cracked it or rather need to try another password? $\endgroup$
    – Vorac
    Jul 23 '21 at 15:57
  • $\begingroup$ Usually RSA private keys are PKCS#1 encoded using a language to describe data structures (ASN.1) and its binary encoding (DER). Check out if you can find the structure, then you can be pretty certain you guessed the password / key correctly. $\endgroup$
    – Maarten Bodewes
    Jul 23 '21 at 16:15
  • $\begingroup$ @MaartenBodewes+ PKCS8 and PKCS12 and OpenSSL 'traditional' key files use CBC with PKCS5/7 padding, which gives dead-simple detection of most wrong guesses. PGP also has some redundancy that allows checking for wrong decrypt. OpenSSH new format does not have redundancy in the encryption, but does in its key format which is not PKCS1 or any other ASN.1. $\endgroup$ Jul 24 '21 at 1: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.