Rainbow tables as a solution to large prime factoring

Question

In explanations I've read about public key cryptography, it is said that some large number is come up with by multiplying together 2 extremely large primes. Since factoring the product of large primes is almost impossibly time-consuming, you have security.

This seems like a problem that could be trivially solved with rainbow tables. If you know the approximate size of primes used and know there are 2 of them, you could quickly construct a rainbow table. It'd be a mighty large table, but it could be done and the task could be parallelized across hardware.

Why are rainbow tables not an effective way to beat public key crypto based on multiplying large primes?

Disclaimer: obviously tens of thousands of crazy-smart security conscious people didn't just happen to miss for decades what I thought up in an afternoon. I assume I'm misunderstanding this because I was reading simplified layman explanations (eg: if more than 2 numbers are used) but I don't know enough yet to know where my knowledge gap is.

Edit: I know "rainbow table" relates to using pre-calculated hashes in a lookup table but the above sounds like a rainbow table attack so I'm using the term here.

---

Edit 2: As noted in the answers, there's no way to store just all of the primes, much less all of their products.

• This site says there are about this many 512 bit primes: ((2^511) * 1) / (512 log(2)) = 4.35 × 10¹⁵¹
• The mass of the sun is 2 × 10³⁰ kg or 2 × 10³³ g
• That's 2.17 × 10¹²⁴ primes per gram of the sun.
• Qty. of 512 bit numbers that can fit in a kilobyte: 1 kb = 1024 bytes = 8192 bits / 512 = 16
• That can fit in a terabyte: 16*1024*1024*1024 = 1.72 × 10¹⁰
• Petabyte: 16*1024*1024*1024*1024 = 1.72 × 10¹³
  
• Exabyte: 16*1024*1024*1024*1024*1024 = 1.72 × 10¹⁶

Even if 1 exabyte weighed 1 gram, we're nowhere close to reaching the 2.17 × 10¹²⁴ needed to be able to fit all of these numbers into a hard drive with the mass of the sun

Ebenezer

Hmmm… but to efficiently iterate over those primes you only need to store primes up to 2^256, of which there are ~6.5*10^74. You don't really need to store every binary digit of those primes either, there are better encodings. Optimistically say each prime fits in one byte. If each bit were stored on a single iron atom, the storage would weigh (55.847 g / avogadro's number * 6.5*10^74 * 8) which Google says is a cool 5*10^50 kg, or 400 million times the mass of the Milky Way. Well… it's fun to get carried away with such calculations, but there's always a cleverer way… – Farinaceous

^ - compression, is key. Also, dinah, you have only taken into consideration raw storage, not slack space. – Dentil

Answer 1

From one of my favorite books ever, Applied Cryptography by Bruce Schneier

"If someone created a database of all primes, won't he be able to use that database to break public-key algorithms? Yes, but he can't do it. If you could store one gigabyte of information on a drive weighing one gram, then a list of just the 512-bit primes would weigh so much that it would exceed the Chandrasekhar limit and collapse into a black hole... so you couldn't retrieve the data anyway"

In other words, it's impossible or unfeasible, or both.

Renick

FWIW, I haven't weighed disk drives lately, but the 360GB drive I just stuck into my laptop is a whole lot lighter than a pound (c. 400g), so we're doing better than the gram per gigabyte. I wonder how many bit-lengths of prime numbers we'd need now to create a black hole, and if Bruce updated that in his latest book (gotta buy it sometime). – Tiffin

I think even at a TB per gram it would still far exceed the limit if my quick finger math is to be believed. – Renick

you're correct. I did the math and appended the original question. – Ebenezer

But isn't it also hard for the key generator to generate primes? Key generators have to use certain algorithms that can only reach a certain subset of primes, IIRC. That means we would only have to tabulate the primes that can be possibly generated by our generator. I wonder if that wouldn't drastically reduce the number? – Homologate

Great answer.. I was thinking the same question as the Dinah, and couldn't see the problem with this.. I'm glad the answer is in physics and not as a software problem, because that did seem a little too trivial to solve. – Shea

Answer 2

The primes used in RSA and Diffie-Hellman are typically on the order of 2⁵¹². In comparison, there are only about 2²⁵⁶ atoms in the known universe. That means 2⁵¹² is large enough to assign 2²⁵⁶ unique numbers to every atom in the universe.

There is simply no way to store/calculate that much data.

---

As an aside, I assume you mean "a large table of primes" - rainbow tables are specificly tailored for hashes, and have no real meaning here.

Jenn

I don't follow how you got the final stat from the 2 preceding ones. – Ebenezer

@Dinah: 2^512 numbers / 2^256 atoms = 2^256 numbers/atom – Jenn

Answer 3

I think the main problem is that rainbow tables pregenerated for certain algorithms use a rather "small" range (usually something in the range of 128 bits). This doesn't usually cover the whole range, but speeds the brute force process up. They usually consume some TB of space.

In prime factorization, primes are much larger (for secure RSA, 2048 bits are recommended). So the rainbow tables wouldn't be "mighty large", but impossible to store anywhere (using up like millions of TB of space).

Also, rainbow tables use hash chains too further speed up the process (Wikipedia has a good explanation) which can't be used for primes.

Phenomenology

The largest rainbow tables are of 10 characters alpha-numeric, which is around 57-bits of security, no where near 128-bits. – Jenn

OK, so the difference is even more extreme. Thanks for clarification. – Phenomenology