mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2010-04-28, 02:41   #1
Romulas
 
Apr 2010

19 Posts
Default 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!
Romulas is offline   Reply With Quote
Old 2010-04-28, 03:14   #2
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2×5×7×47 Posts
Default

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!
bsquared is offline   Reply With Quote
Old 2010-04-28, 03:30   #3
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2×5×7×47 Posts
Default

Quote:
Originally Posted by Romulas View Post
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?
bsquared is offline   Reply With Quote
Old 2010-04-28, 03:30   #4
Romulas
 
Apr 2010

19 Posts
Default

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?
Romulas is offline   Reply With Quote
Old 2010-04-28, 03:32   #5
Romulas
 
Apr 2010

19 Posts
Default

Quote:
Originally Posted by bsquared View Post
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.
Romulas is offline   Reply With Quote
Old 2010-04-28, 03:43   #6
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2×5×7×47 Posts
Default

Quote:
Originally Posted by Romulas View Post
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 View Post
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 View Post
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 View Post
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.
bsquared is offline   Reply With Quote
Old 2010-04-28, 03:51   #7
Romulas
 
Apr 2010

19 Posts
Default

Quote:
Originally Posted by bsquared View Post
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 View Post
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 View Post
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 View Post
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.
Romulas is offline   Reply With Quote
Old 2010-04-28, 04:05   #8
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2·5·7·47 Posts
Default

Quote:
Originally Posted by Romulas View Post

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 View Post
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...
bsquared is offline   Reply With Quote
Old 2010-04-28, 04:15   #9
Romulas
 
Apr 2010

100112 Posts
Default

Quote:
Originally Posted by bsquared View Post
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 View Post
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.
Romulas is offline   Reply With Quote
Old 2010-04-28, 10:59   #10
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3,529 Posts
Default

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.
jasonp is offline   Reply With Quote
Old 2010-04-28, 13:16   #11
Romulas
 
Apr 2010

238 Posts
Default

So, what about the q0 and qintsize parameters for factmsieve.py, factMsieve.pl?
Romulas is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
factoring 90 512-bit RSA Keys in 3 minutes Mini-Geek Lounge 1 2015-03-17 17:27
openssl weak keys Unregistered Information & Answers 1 2011-10-07 22:14
Asymetric keys JohnFullspeed Factoring 3 2011-07-23 12:24
Assignment keys NBtarheel_33 PrimeNet 17 2010-02-18 04:38
Where I find the best program to it factor keys? I use AMD. 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.