Factoring RSA Keys
 

Hey everyone!

I'm new to these forums, and from what I've seen, there are some pretty impressive minds crawling them!

Well, I am in a cryptology class and I have an exam coming up. My exam lasts one week, during which, we have an opportunity to attack our classmates' public keys (LUC RSA) for extra credit.

One thing that boggles my mind is the fact that the professor wants both our factors (p and q) to be 81 digits long, producing keys larger than 528 bits!

So, I am wondering if any of you have direction on how I can go about factoring these massive numbers?

I had one idea, but I think it is well forfeit. I was thinking, since all the primes are 81 digits, I could just compute all the primes that are 81 digits long and then run a trial division on all of the keys based on the primes in that range. Of course, as you can already see, this is a poor idea, for there are very MANY primes that are 81 digits long.

Now, I see how onerous of a task this factoring will be, so I was wondering if there is a program which will split up the work between many computers (not in a network). I would like something I can specify bounds on, so I can set up each computer to run a separate set. There is a limitation on the computers I have available however. I have access to labs at school running Windows XP and Fedora 10. Neither of which I will have administrative privileges over, but both have Python and Perl installed, along with C compilers and the like.

Finally, there are 10 other students in this class. Not very many. So, I'm hoping to crack at least half of their keys in the 7-day period. I believe if I can get something going as described earlier, I will have enough computing power to do this, especially if some of the students make weak keys.

Anyhow, any suggestions? And thanks for your time and discussion!

What have you covered in this class on the topic of factorization?

Maybe you are already familiar with the various methods, but the size of your target numbers limits your options.

A good key of size 528 bits is really only accessible with GNFS. Unless you have a lot of computers you probably won't be able to tackle more than one with this method in 7 days. This assumes you'll be able to learn how to use it effectively before then, which is not trivial especially when distributing jobs among many computers.

A "weak" key of size 528 bits is still rather likely to be inaccessable to anything but GNFS. Simply picking random 81 digit primes p and q will likely give one a strong enough key. Its possible that p or q picked in this fashion will have properties making it factorizable by ECM, P-1, or P+1, but not likely.

If you would like to easily generate a pretty strong key, my program, [URL="http://sites.google.com/site/bbuhrow"]YAFU[/URL], has a function called rsa which will generate a random n-bit strong pseudoprime. I wouldn't use it to protect anything valuable, but its probably good enough for a problem like this. I'm sure there are other freeware tools out there which will do similar things. Cryptool comes to mind.

Good luck and have fun!

[quote=Romulas;213401]
Of course, as you can already see, this is a poor idea, for there are very MANY primes that are 81 digits long.
[/quote]

I suppose its possible that someone who wasn't paying attention in class could pick p and q where p-q is really small (e.g. a twin prime pair in the neighborhood of 81 digits). In this case you could factor the key in milliseconds... any guesses how?

We've covered some important ones which help us understand about creating strong keys. Such as Fermat's attack, Pollard Rho's attack, p-1, initial segment attack, etc. Of course, the professor won't mention ECM, GNFS, MPQS, or any of the like... I suppose that's because those algorithms are just smart brute force attacks, while the others attack a certain specification in a number. What's crazy, is we have mostly done Elliptic Curve Cryptology and we just got into RSA at the end of the semester (about 2 weeks ago). But it is all pretty simple anyhow, except when really getting into understanding the math behind the more difficult algorithms.

By the way, does your YAFU program provide the actual prime factors? Those are needed in creating a private key, and thus encrypting and decrypting.

Well, I would like to use GNFS, but I can't seem to get it to work right. I have gotten msieve to work with factmsieve.py, but nothing further. I'm not sure how to get going on creating polynomials that are suitable for the number either.

Also, to address my biggest question, is there a way I can set up bounds, so I can set them up on multiple machines running at once, but at different levels?

[quote=bsquared;213405]I suppose its possible that someone who wasn't paying attention in class could pick p and q where p-q is really small (e.g. a twin prime pair in the neighborhood of 81 digits). In this case you could factor the key in milliseconds... any guesses how?[/quote]
Fermat's attack.

[quote=Romulas;213406] We've covered some important ones which help us understand about creating strong keys. Such as Fermat's attack, Pollard Rho's attack, p-1, initial segment attack, etc. Of course, the professor won't mention ECM, GNFS, MPQS, or any of the like... I suppose that's because those algorithms are just smart brute force attacks, while the others attack a certain specification in a number. What's crazy, is we have mostly done Elliptic Curve Cryptology and we just got into RSA at the end of the semester (about 2 weeks ago). But it is all pretty simple anyhow, except when really getting into understanding the math behind the more difficult algorithms.
[/quote]
Sounds pretty cool. Is this an undergraduate class?

[quote=Romulas;213406]
By the way, does your YAFU program provide the actual prime factors? Those are needed in creating a private key, and thus encrypting and decrypting.
[/quote]
Unfortunately, no. I wrote it for testing the factorization routines in YAFU, not for encryption purposes.

[quote=Romulas;213406]
Well, I would like to use GNFS, but I can't seem to get it to work right. I have gotten msieve to work with factmsieve.py, but nothing further. I'm not sure how to get going on creating polynomials that are suitable for the number either. [/quote]

Have you been to [URL="http://gilchrist.ca/jeff/factoring/nfs_beginners_guide.html"][COLOR=#0066cc]Jeff's site [/COLOR][/URL]yet?
[quote=Romulas;213406]
Also, to address my biggest question, is there a way I can set up bounds, so I can set them up on multiple machines running at once, but at different levels? [/quote]

This is where things might get (more) tricky. In principle it is easy to do simply by assigning each computer a different range of special-q to work on. However I don't think anything freely available will manage this for you across a compute cluster. You are left with either running multiple carefully configured factmsieve scripts manually or driving gnfs from the command line manually, or writing your own management software/script.

[quote=bsquared;213409]Sounds pretty cool. Is this an undergraduate class?[/quote]
This class is both undergraduate and graduate. However, the graduates have to give a presentation on a topic in cryptology and how to create a strong public key in the area of study.


[quote=bsquared;213409]Unfortunately, no. I wrote it for testing the factorization routines in YAFU, not for encryption purposes.[/quote]

I guess it won't help in getting a strong key then, lol. Unless I can factor it before the exam, which won't be very likely!

[quote=bsquared;213409]Have you been to [URL="http://gilchrist.ca/jeff/factoring/nfs_beginners_guide.html"][COLOR=#0066cc]Jeff's site [/COLOR][/URL]yet?[/quote]
I have, but it seems more Windows oriented than Linux. In addition, I can't seem to even get the software properly set up on Linux -- I always get loads of errors when attempting to build the source files.

[quote=bsquared;213409]This is where things might get (more) tricky. In principle it is easy to do simply by assigning each computer a different range of special-q to work on. However I don't think anything freely available will manage this for you across a compute cluster. You are left with either running multiple carefully configured factmsieve scripts manually or driving gnfs from the command line manually, or writing your own management software/script.[/quote]
I want to manually set each computer to a different range, and when it's done, it does two things: either finds or doesn't find the factorization, knocks out the range specified so more ranges can be tackled.

[quote=Romulas;213410]

I have, but it seems more Windows oriented than Linux. In addition, I can't seem to even get the software properly set up on Linux -- I always get loads of errors when attempting to build the source files.

[/quote]

There are links to linux binaries somewhere on Jeff's page. I thought there were build instructions as well, using gcc, but I can't remember for sure.


[quote=Romulas;213410]
I want to manually set each computer to a different range, and when it's done, it does two things: either finds or doesn't find the factorization, knocks out the range specified so more ranges can be tackled.[/quote]

This is why it is tricky - parallelized GNFS doesn't work that way. Each machine will be busy generating vast amounts of data which is useless by itself. Only after a sufficient amount has been generated can you combine all of the individual data sets and feed the resulting tens of gigabytes to msieve for magical transformation into factors several days later. Determining "sufficient" can itself be a difficult problem: the many separately located multi-gigabyte files have to periodocially be manually concatenated and processed for up to several hours just to find out if you have enough data to stop or not. Keeping track of what computer is working on what will also likely be a manual task in some fashion.

I do have some custom software which can submit jobs across a batch queuing system (qsub) to automate parallelization a little, but it's fragile enough that I would hesitate to distribute it even if that functionality happens to work for you.

[quote=bsquared;213411]There are links to linux binaries somewhere on Jeff's page. I thought there were build instructions as well, using gcc, but I can't remember for sure.[/quote]
There are linux binaries for a 64-bit system, but I believe most of my machines are 32-bit. I don't recall seeing any build instructions, using gcc.



[quote=bsquared;213411]This is why it is tricky - parallelized GNFS doesn't work that way. Each machine will be busy generating vast amounts of data which is useless by itself. Only after a sufficient amount has been generated can you combine all of the individual data sets and feed the resulting tens of gigabytes to msieve for magical transformation into factors several days later. Determining "sufficient" can itself be a difficult problem: the many separately located multi-gigabyte files have to periodocially be manually concatenated and processed for up to several hours just to find out if you have enough data to stop or not. Keeping track of what computer is working on what will also likely be a manual task in some fashion.

I do have some custom software which can submit jobs across a batch queuing system (qsub) to automate parallelization a little, but it's fragile enough that I would hesitate to distribute it even if that functionality happens to work for you.[/quote]
Hmm... Is there any efficient way to get this working? As you said, and I know, that the keys will be too large to factor on a single machine (within 7 days) -- I need to split up the work. I probably shouldn't use anything unstable since I don't have administrative privileges in the labs on campus.

Finishing both the sieving and postprocessing together in a week or less is a very tall order; just the postprocessing will take almost a week on a fast machine with 4GB of memory.

Look up the details of the factorization of RSA-170; their postprocessing took almost two weeks, though your job is somewhat easier than that.

So, what about the q0 and qintsize parameters for factmsieve.py, factMsieve.pl?