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

Answer 1

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.

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.

Answer 3

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.