Mission accomplished (key-only attack on RSA)

Happy April Fools Day! I simply generated all the keys which are ‘broken’ in the comments, except the one with the certificate. That one was a different story – remember the big Debian OpenSSL fail? That means the key was easy to guess. Really breaking a previously secure cert would be quite un-nice, as SSL does not have any forward secrecy (in the most often used mode), i.e. disclosure of the key even of an expired cert would allow an attacker to decrypt sessions sniffed long ago, while the key was in use.

The RSA cryptosystem is used in a lot of critical protocols, and much of our internet security depends on RSA being secure. The security of RSA is based on the assumption that the product of two very big primes is very hard to factor, i.e. it is hard to determine those primes from their product. The public key contains the product, but not the primes. If you were able to obtain those primes, you could calculate an intermediate value, and then the private key.

It’s been a long night, and to make a long story short, I got an algorithm implemented and tested that does calculate the private from the public key. I am going to publish the details at a later time, when I am not as tired and able to write down and explain the algorighm in a understandable way.

As you certainly want to see some proof, I guess this is the easiest way to do it: You post the public key in the comments (only default keys with e=0x10001, I’m too lazy to fix the algorithm so it takes other exponents), I post the private (decryption) exponent.

I will check the moduli against the SSL observatory database, so please, refrain from posting keys of real certificates for me to break, I will not do it. Use [sourcecode]your key here[/sourcecode] tags when posting it or WordPress will break the dashes. Note that wordpress hides the part of the keys and exponents that does not fit, you can still copy them.

Please keep the maximum key length at 2048 bits. The algorithm is approximately linear to the key length both in time and memory requirements, and I simply do not have enough RAM to break anything over 2048 bits.

EDIT: Ok, I REALLY have to get some sleep now, I have closed the comments for now, I will break the remaining keys tomorrow.