Factoring a 160 digit RSA key

[swistak]

Hi!

I am a first year mathematics student at Imperial College London. Our teacher in computing class has set us an extra credit assignment - cracking the RSA key visible on his website. My question is, if that sort of feat is doable in less than 2 weeks on an i7 dual core laptop? Of course I am not allowed to ask anyone to do the factoring for me, but I am allowed to use any tools available. Currently I am trying to do it in maple, however from what I have read, it does not have the GNFS algorithm built in, will this affect my performance significantly? Please excuse me if my questions are silly or idiotic, but I am still reading up on lots of topics connected with sieving, factoring and it is sort of difficult for me to get my head around all that :)

Thank you
Tom

[Batalov]

No, not in two weeks, not on a laptop.

Sieving would take ~5000 core-hrs (on a 2-yr old CPU), so probably half that on a new CPU; that's about 100 core-days. And the linear algebra step alone would take a week at least. With 16 modern cores, you could probably do it in two weeks. (give or take)

P.S. However, his task could be a trick question - and what he wants is for you guys to try ECM just in case his key is a bad key. This reminds about the strange key from Knuth's book.

[bsquared]

Originally Posted by swistak

Hi!

I am a first year mathematics student at Imperial College London. Our teacher in computing class has set us an extra credit assignment - cracking the RSA key visible on his website. My question is, if that sort of feat is doable in less than 2 weeks on an i7 dual core laptop? Of course I am not allowed to ask anyone to do the factoring for me, but I am allowed to use any tools available. Currently I am trying to do it in maple, however from what I have read, it does not have the GNFS algorithm built in, will this affect my performance significantly? Please excuse me if my questions are silly or idiotic, but I am still reading up on lots of topics connected with sieving, factoring and it is sort of difficult for me to get my head around all that :)

Thank you
Tom

You've come to the right place; there is a lot of factoring expertise around here. I don't claim much myself, but I know that you'll need more hardware to be able to factor a 160 digit number in less than 2 weeks. A single dual core won't cut it.

You will need GNFS, which involves obtaining and learning to run several programs. I'll point you here first, feel free to ask further questions after looking over the guide.

[bsquared]

Originally Posted by Batalov

P.S. However, his task could be a trick question - and what he wants is for you guys to try ECM just in case his key is a bad key. This reminds about the strange key from Knuth's book.

Yeah, good point. How much about factorization techniques did you learn in this class? Maybe he has a specific approach in mind other than brute force with GNFS - something you learned about in class... fermat even, perhaps.

[swistak]

Originally Posted by bsquared

Yeah, good point. How much about factorization techniques did you learn in this class? Maybe he has a specific approach in mind other than brute force with GNFS - something you learned about in class... fermat even, perhaps.

Thanks for your feedback. I am looking through the guide you posted. Generally we did not do any factoring techniques at all - we are supposed to find out about it by ourselves. I imagine this should not be an easy task at all, as in past 12 years this has only been done by first years 3 times, the first number was 40 digit, the next was 80 and 120, but last time someone has factored a 150 digit key as well. Is it possible that someone has just gotten lucky with pollard's rho algorithm?

We are free to use whatever and I am fairly sure there is no specific approach in mind, I guess, however, that in my case we are expected to find a way that is fast at the cost of accuracy. I could try clustering up a couple of friends computers for this task.

Are there any other attacks on RSA? I could try encoding data with this key and exponent (37) lots of times to find how many permutations does it take for it to get back to the original input, would that take longer?

[TimSorbet]

Originally Posted by swistak

Thanks for your feedback. I am looking through the guide you posted. Generally we did not do any factoring techniques at all - we are supposed to find out about it by ourselves. I imagine this should not be an easy task at all, as in past 12 years this has only been done by first years 3 times, the first number was 40 digit, the next was 80 and 120, but last time someone has factored a 150 digit key as well. Is it possible that someone has just gotten lucky with pollard's rho algorithm?

In the past, have the keys all been good RSA keys? E.g. were they all semiprimes with both factors the same (or within 1) digit size and without anything that made them trivial to factor if you use a certain method (e.g. easy P-1 or P+1 values, or it's a square or something)?
40 and 80 are trivial (seconds to minutes) on any computer. 120 digits, assuming it doesn't have any small or easily-discoverable factors, can be done in a few days to a week or two with a computer. 150 and 160 digits, assuming it doesn't have any small or easily-discoverable factors, require significant hardware to finish within two weeks. Not the sort of thing a teacher would expect each person in a class to do.
The sieving part of GNFS can be run in parallel between completely different computers quite efficiently (we do it commonly around here, e.g. to factor this 170 digit composite number with no small factors, or this c161 which the GNFS took 11 days altogether, 4 of which was the linear algebra step). If you are allowed to collaborate with the rest of the class and you all work together, putting all your computers on it 24/7 until the sieving is done, then have the person with the best computer run the post-processing, it could probably be done before the deadline. The biggest difficulties would be getting some number of non-GNFS-familiar people to administrate it and get it running on each computer, and getting someone with a good enough computer to do the post-processing, but neither is insurmountable.
Of course, you would want to first run a significant amount of ECM, along with P-1, P+1, and any other factoring methods that might help, just in case the key isn't good at all.

Originally Posted by swistak

Are there any other attacks on RSA? I could try encoding data with this key and exponent (37) lots of times to find how many permutations does it take for it to get back to the original input, would that take longer?

As far as I know, for a good key, factoring the public key is the easiest way to break it.

[Random Poster]

Originally Posted by swistak

Are there any other attacks on RSA? I could try encoding data with this key and exponent (37) lots of times to find how many permutations does it take for it to get back to the original input, would that take longer?

Yes, that would take very much longer. The expected cycle length for the operation x -> x^k (mod n) is nearly n for most k.