Lots of modern encryption (RSA comes to mind) are based on the fact that factoring large numbers is hard. However, multiplying large numbers is much easier, and table lookups are very easy. Since these large numbers are semiprimes (in all encryption methods I can think of, anyways), why not just make a table of the products of a bunch of primes and use a lookup to find some large number's prime factors? Would such a table just also be computationally expensive to make? Or too big to store or search through or something?
2
migrated from security.stackexchange.com Aug 19 '15 at 14:48
This question came from our site for information security professionals.
-
1$\begingroup$ Yes. The table would be way too big. What you are describing is basically brute force. $\endgroup$ – TTT Aug 19 '15 at 4:45
5
$\begingroup$
$\endgroup$
The prime number theorem says that there are approximately $N/\log{N}$ primes less than $N$.
If we consider $2048$ bit RSA, that means the primes we are using are $1024$ bits. How many $1024$ bit prime numbers are there? Approximately $2^{1025}/\log{2^{1025}} = 2^{1025}/1025\approx 2^{1015}$ (from the theorem). So, just to store the primes we are going to need that many entries in a database. In your lookup table, if you store the modulus and one prime, you can compute the other prime.
How much storage would it require to just store the primes (forget the modulus)? Well, that would be $1024 * 2^{1015}$ bits, which is around
481560916771158684800786922703235625631274322714142263414417884163925873322306437689024231009526751394401758326916367106052034484602375642882110959089521812209947069992139877256008949136579813164413834190131240610432508865633901300457687591589632190325582710683886781973951695733384278544896131740867054246692573031629150247882082682647773168904426336814855367810693467547461780797071163567159452928068892906992787178135839959347223507647240845924670958716173279750751341651541295792537288393481542519773223140547524361834615428274169543954961376881442030303829940191406452725012875774576546969913TB (yes, terabytes).
Put another way, there are about $2^{272}$ atoms in the known universe. So even if you could store one prime number in a single atom, it would take more atoms than are in the known universe.
-
$\begingroup$ You are calculating the number of primes 1024 bits or less. Not that it really changes the conclusion of course. $\endgroup$ – otus Aug 22 '15 at 11:25
