20100428, 02:41  #1 
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 7day 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! 
20100428, 03:14  #2 
"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, P1, 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 nbit 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! 
20100428, 03:30  #3 
"Ben"
Feb 2007
2×5×7×47 Posts 
I suppose its possible that someone who wasn't paying attention in class could pick p and q where pq 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?

20100428, 03:30  #4 
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, p1, 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? 
20100428, 03:32  #5 
Apr 2010
19 Posts 
Fermat's attack.

20100428, 03:43  #6  
"Ben"
Feb 2007
2×5×7×47 Posts 
Quote:
Quote:
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 specialq 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. 

20100428, 03:51  #7  
Apr 2010
19 Posts 
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:
Quote:
Quote:


20100428, 04:05  #8  
"Ben"
Feb 2007
2·5·7·47 Posts 
Quote:
Quote:
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 20100428 at 04:10 Reason: more info... 

20100428, 04:15  #9  
Apr 2010
10011_{2} Posts 
Quote:
Quote:


20100428, 10:59  #10 
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 RSA170; their postprocessing took almost two weeks, though your job is somewhat easier than that. 
20100428, 13:16  #11 
Apr 2010
23_{8} Posts 
So, what about the q0 and qintsize parameters for factmsieve.py, factMsieve.pl?

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
factoring 90 512bit RSA Keys in 3 minutes  MiniGeek  Lounge  1  20150317 17:27 
openssl weak keys  Unregistered  Information & Answers  1  20111007 22:14 
Asymetric keys  JohnFullspeed  Factoring  3  20110723 12:24 
Assignment keys  NBtarheel_33  PrimeNet  17  20100218 04:38 
Where I find the best program to it factor keys? I use AMD.  chrow  Factoring  5  20040219 10:15 