I was wondering if it would be possible to crack a message that was encrypted with 512-bit PCKS1 encryption with the public key. I am doing a project for our science fair type thing at school and have created a simple messaging app that sends encrypted messages.

Would it be possible to decrypt these messages in a suitable amount of time (A couple of hours on a $5 DigitalOcean droplet) or is that totally ridiculous? If that idea isn't so far fetched, could you please also suggest a program to use for the cracking?

  • Of course it's possible to decrypt it, there still hasn't been an encryption standard that absolutely can not be broken (and the only way I think that would be possible would be embedding some sort of AI in it to dynamically prevent it from being broken). And I mean... the NSA can do it, so of course it's possible. I don't know how to do it though, I just know it's possible, and there are more than one ways of doing it.
    – Cestarian
    Nov 22 '15 at 5:25
  • @Cestarian, thanks for your input, I understand the NSA can do it but do you think that there is any chance I could do it in say a couple of hours, no I do not own a super computer :P Nov 22 '15 at 5:34
  • Honestly I don't know, it is probably possible either through a fault in the encryption algorithm (there's usually a hole in there somewhere) or a deliberately placed backdoor, if one is in place. I'm not really a crypto guy. But forcefully breaking the encryption you can not do as far as I know. At least not without that super computer you don't have, or so we tend to be told ;) But if someone has found a way, it's doubtful that you'll be able to get access to that method for free, unless it's already public knowledge, in which case google would give you the answer.
    – Cestarian
    Nov 22 '15 at 5:39
  • 1
    I don't know if there is an easy to use solution by now, but in principle it's possible to factor 512 bit RSA keys for about $100. See Is 512-bit RSA still safe for signature generation? Nov 22 '15 at 8:55
  • 1
    Last number I heard was $75. From the Factoring as a Service paper. Their python source code is on GitHub. (Haven't tried it.) Nov 22 '15 at 9:18

512 bit RSA was factored in 1999 with pretty advanced specialized hardware. It took 6 months. It should be much easier (though not trivial) today with modern PCs.

From Wikipedia

In 2009, Benjamin Moody factored an RSA-512 bit key in 73 days using only public software (GGNFS) and his desktop computer (dual-core Athlon64 at 1,900 MHz). Just under 5 gigabytes of disk was required and about 2.5 gigabytes of RAM for the sieving process.

That was about 7 years ago. Going by those stats, I am guessing a few modern desktop computers with intel i7 chips working together would factor 512-bit RSA within days or weeks. I doubt you can do it in a couple of hours though.


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.