Why 256 bit keys are large enough

Re:Why 256 bit keys are large enough by dspillett on Monday December 17, 2012 @07:00AM (#4931937)

If you are trying to brute-force guess an RSA key, the fact that the factors which produce the key should be prime (well, co-prime with respect to each other to be more precise) has the potential to greatly reduce the search space. For small keys it is practical to have precomputed what this limited search space is so of the 2^N possible keys you can be fairly sure that you only need to check a much smaller subset of them. You still have to use brute-force, but unlike with symetic methods your search space can be much smaller than the entire keyspace. For larger keys this pre computation (and storage) becomes impractical (with current tech). I have no idea off the top of my head where the point it currently becomes impractical occurs relative to 256 bit keys though.

[ Parent | on HN ]

Re:Why 256 bit keys are large enough by Someone on Monday December 17, 2012 @01:17PM (#4933497)

I doubt this approach makes sense for any size prime. Let's assume a 50-digit number to factor. According to http://primes.utm.edu/howmany.shtml, there are over 10^21 primes less than 10^24. Let's assume you manage to store 10^3 of them in a byte of memory. Then, you would need 10^18 bytes, or a million terabytes of storage to store those primes.

That isn't practical, so let's scale back to primes around 10^20 (around 10^18 different primes) Then, you would need around a thousand terabytes (still assuming that you manage to compress your 64-bit or so primes to fit 1000 of them in 8 bits)

I'll assume you build the machine with those drives, and can do trial divisions in parallel, 1000 CPUs, a billion divisions per CPU per second. you still would need 10^6 seconds to do a complete search over all primes. Rounding down, that is a week.

For comparison, https://sites.google.com/site/bbuhrow/home claims:

"I've seen C90's factored in less than 4 minutes on an 8 core box.

According to what I understand, C90 is tech speak for "90 digits, product of two coprime numbers"

[ Parent | on HN ]

Re:Why 256 bit keys are large enough by ComputerGuru on Monday December 17, 2012 @02:11PM (#4933788)

Then, you would need 10^18 bytes, or a million terabytes of storage to store those primes. That isn't practical, so let's scale back to primes around 10^20 (around 10^18 different primes)

Actually, a million terabytes (an exabyte) is really quite feasible. Not on an individual scale, but I would be very surprised if governments (all of them, really) did not have this sort of thing set up.

[ Parent | on HN ]