3

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?

8
  • 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, 2015 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, 2015 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, 2015 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, 2015 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, 2015 at 9:18

1 Answer 1

4

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.

0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .