mersenneforum.org Factoring RSA Keys
 Register FAQ Search Today's Posts Mark Forums Read

 2010-04-28, 02:41 #1 Romulas   Apr 2010 19 Posts 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!
 2010-04-28, 03:14 #2 bsquared     "Ben" Feb 2007 2×5×7×47 Posts 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, YAFU, 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!
2010-04-28, 03:30   #3
bsquared

"Ben"
Feb 2007

2×5×7×47 Posts

Quote:
 Originally Posted by Romulas Of course, as you can already see, this is a poor idea, for there are very MANY primes that are 81 digits long.
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?

 2010-04-28, 03:30 #4 Romulas   Apr 2010 19 Posts 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?
2010-04-28, 03:32   #5
Romulas

Apr 2010

19 Posts

Quote:
 Originally Posted by bsquared 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?
Fermat's attack.

2010-04-28, 03:43   #6
bsquared

"Ben"
Feb 2007

2×5×7×47 Posts

Quote:
 Originally Posted by Romulas 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.
Sounds pretty cool. Is this an undergraduate class?

Quote:
 Originally Posted by Romulas 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.
Unfortunately, no. I wrote it for testing the factorization routines in YAFU, not for encryption purposes.

Quote:
 Originally Posted by Romulas 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.
Have you been to Jeff's site yet?
Quote:
 Originally Posted by Romulas 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?
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.

2010-04-28, 03:51   #7
Romulas

Apr 2010

19 Posts

Quote:
 Originally Posted by bsquared Sounds pretty cool. Is this an undergraduate class?
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:
 Originally Posted by bsquared Unfortunately, no. I wrote it for testing the factorization routines in YAFU, not for encryption purposes.
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:
 Originally Posted by bsquared Have you been to Jeff's site yet?
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:
 Originally Posted by bsquared 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.
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.

2010-04-28, 04:05   #8
bsquared

"Ben"
Feb 2007

2·5·7·47 Posts

Quote:
 Originally Posted by Romulas 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.
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:
 Originally Posted by Romulas 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.
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.

Last fiddled with by bsquared on 2010-04-28 at 04:10 Reason: more info...

2010-04-28, 04:15   #9
Romulas

Apr 2010

100112 Posts

Quote:
 Originally Posted by bsquared 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.
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:
 Originally Posted by bsquared 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.
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.

 2010-04-28, 10:59 #10 jasonp Tribal Bullet     Oct 2004 3,529 Posts 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.
 2010-04-28, 13:16 #11 Romulas   Apr 2010 238 Posts So, what about the q0 and qintsize parameters for factmsieve.py, factMsieve.pl?

 Similar Threads Thread Thread Starter Forum Replies Last Post Mini-Geek Lounge 1 2015-03-17 17:27 Unregistered Information & Answers 1 2011-10-07 22:14 JohnFullspeed Factoring 3 2011-07-23 12:24 NBtarheel_33 PrimeNet 17 2010-02-18 04:38 chrow Factoring 5 2004-02-19 10:15

All times are UTC. The time now is 06:04.

Thu Sep 24 06:04:00 UTC 2020 up 14 days, 3:14, 0 users, load averages: 1.24, 1.37, 1.33