RSA Attack

[adam]

CP and I are working on a way to quickly factor a large number, essentially through bruteforce/rainbow table type attack. The concept is to generate a list of prime numbers (since all composites can be evenly divided by 2 or more primes) which will reduce the search range when trying to factor a number.

We ran up to the 32-bit limit fairly quickly, which gave us over 2GB of primes (though they're not stored as efficiently as they could be). If anyone has a 64-bit computer we can play with (i.e. shell access so we can code/debug) we can go up to 2^64. But even with the right hardware, we're not sure how well this will scale, and even if it does work out well, there's the issue of hitting the 64-bit limit (which gives us 18 digit numbers).

The math in a BigInt class is horribly slow compared to built-in types; so unless we start using 128-bit CPUs, this program is essentially stuck here. However, it does very well at generating small primes. If you're interested in the details, I wrote up a paper (PDF warning) explaining in a little more detail how it works.

The source for the program is available via SVN:
https://www.diseasedmind.com/svn/genPrime/

We're working on implementing another algorithm which eliminates a lot of the math involved. Currently this alternative (genPrime_b) isn't as fast as the original, but we have an idea on how we can speed it up. That's not quite finished, but the source is also available via SVN.

Comments, suggestions, patches, and encouragement are all welcome either via e-mail, here, or on our forum http://www.dc949.org/forum

[bascule]

Re: RSA Attack

Factoring large numbers is an NP complete problem. As you've no doubt started realizing, as the size of the primes goes up, the computational penalty associated with brute-force factorization increases exponentially.

Also, you're running into the slowness of arbitrary precision libraries.

The only practical way of factoring 1024-bit+ RSA keys is to use a massively parallel quantum computation. The approach has already been designed, but right now humans are incapable of engineering the hardware necessary to accomplish it:

http://en.wikipedia.org/wiki/Shor's_algorithm

Shor's algorithm works in O((log N)^3) time and O(log N) space

[adam]

Re: RSA Attack

The problem I have with shor's algorithm is that it's probabilistic. However, the "mod by all previous primes" algorithm (if it has an official name, I don't know it) doesn't scale very well and essentially dies when using types that's aren't native to the architecture.

Our next attempt is at a rolling sieve, which uses much less factoring. This eliminates the problem of scaling, but it uses up quite a bit of memory (the more the better).

The idea is to get a list of known primes and we'll have every private key possible. After that it's just a matter of finding the one that matches. Yes, that will be a lot of numbers, but its tremendously less than the amount of numbers that would be needed to try if you were to try every number from 2 - n (or even [2, every odd number through n]). As for scaling, primes become much more scarce when you get into the larger numbers, so the number of primes between 2^31 and 2^32 would be less than 2^30 through 2^31.

Yes, finding all known primes is a massive problem, which requires an insane amount of CPU power. But it only needs to be done once. We'll start with being able to crack the small keys and as the list of primes grows, so will the cracking ability.

[CP99]

Re: RSA Attack

...Our next attempt is at a rolling sieve...

Just to clarify, were using a modified version of the Sieve of Eratosthenes which limits the size of the number array based on memory constrictions, then executes the sieve in a series of chunks.

[bascule]

Re: RSA Attack

Well, this was interesting. Three institutes managed to factor a 1017-bit number:

http://blog.wired.com/wiredscience/2..._mathemat.html

[jeremycec]

Re: RSA Attack

Well, this was interesting. Three institutes managed to factor a 1017-bit number:

http://blog.wired.com/wiredscience/2..._mathemat.html

If they can factor special 307-digit numbers, I wonder how long until they collect the $$$ for factoring a 309-digit "regular" number (as well as the shorter numbers in the RSA Factoring Challenge)?

jcec

[adam]

Re: RSA Attack

Does anyone know what software / algorithm they were running in their cluster? I'm wondering if it was using GGNFS or proprietary software.