Is there a concept where pre-computed tables can be used for prime number factorization ? Is it possible that a computer can generate millions of prime numbers, store it and then effectively determine the factors ?
Add a comment
|
5 Answers
It's unlikely. The primes involved are huge, so the keyspace is massive. Just how massive depends on your key size, but let's pick 512-bit primes for a lower bound example.
The prime counting function gives us an estimate of how many prime numbers are below a given number. It is difficult to compute precisely, but a close estimate is defined as π(x) = x / ln(x), where ln is the natural logarithm. As such, we can compute an estimate of the expected number of primes below the highest value in an n-bit number by computing π(2^n). If we want to exclude all numbers that aren't exactly n-bit, we compute π(2^n) - π(2^(n-1)). This isn't technically required, but it gives us a nice lower bound of how many large primes there are for that key size.
For n = 512 the number of primes required for an exhaustive list is 1.885×10151. If we can store every prime in a 512-bit entry, that's 1.207×10153 bytes, which is 132 orders of magnitude more than we have disk storage capacity in the world.
So no, not really feasible.
answered Dec 10, 2012 at 20:38
-
1
-
2Just as a quick side node: The subtraction part nicely demonstrates an interesting quirk of picking n-bit prime numbers. It's not like generating a random stream of bytes, where each bit has an equal probability of being either 1 or 0. In fact, picking a 512-bit prime whose first 10 bits just happen to be 0 is bad, because you no longer have a 512-bit prime, you have an 502-bit prime. So technically a random n-bit prime is only theoretically random over n-1 bits, with its most significant bit always set to 1. Thankfully the keyspace is so large it doesn't make a difference. Commented Dec 10, 2012 at 22:41
-
@Polynomial: As an additional question to your last comment regarding keyspace, is the choice of the random prime number within the keyspace truly random ? I've never seen an implementation of RSA before, its just black box to me. Commented Dec 10, 2012 at 23:13
-
2
-
1The prime counting function is not defined as
π(x) = x / ln(x)-- that wouldn't make sense, sinceπ(x)must always be an integer andx / ln(x)is never an integer. Instead, it is approximated byx / ln(x)in a certain mathematical sense. Commented Dec 11, 2012 at 2:35
Rainbow table: each "color" takes a random input (the output hash of the last iteration or the original hash) and returns an output that maps to whatever pattern you wanted (e.g., all letters). That is then hashed and fed back to the input.
Because we can also specify a reduction function that takes any random string and deterministically maps it to whatever output pattern we want, this works for passwords. There is no definable function to take an input value and output a number that is known to be prime as a result, however.
Every number that isn't known to be prime because you've already tested it will need to be testeed for primeness. Thus, unless a number is stored as a known prime value, there is no time / memory tradeoff to be had.
answered Dec 10, 2012 at 20:46
What you're talking about here is not feasible. Crypto doesn't simply calculate large primes, you would need to factor the product of two primes.
What you'd need to do is compute millions of prime numbers and feed them into an insanely large array. Then you'd need to duplicate that array so you had two dimensional array. Then you would need to multiple every single entry in the first dimension against every single entry in the second dimension, and store the two primes and the result in a second array. This second array would be gigantic, and by gigantic I mean completely unable to be stored in any capacity, but it would hold your answers.
-
You can't factor primes at all - that's why they're prime. RSA uses semiprimes, which are the product of two primes. Commented Dec 10, 2012 at 20:53
-
Thank you, I accidentally messed that up when I was editing. I meant to say calculate primes/large primes.– JZeollaCommented Dec 10, 2012 at 22:16
Certainly not easy but... "where there is a will there is a way" IF you wanted all prime numbers from number 2--> 512bit in a table then all possible products then yes this would be unfeasably large. But lets go back and speculate as to why someone might want it. Just suppose someone has a scenario where they were using a pair of similar bit-length prime numbers to make a big number that would be difficult for others to factor to a pair of primes (sound familiar...?) Not all possible combinations of primes would be needed as only similar bit-lengths would be used. This dramatically reduces the table size. Anyway to be pedantic this would be a Rainbow Cube not table as this requires several dimensions. The ability to determine factrs of these large primes is certainly difficult as the memory-resident size of the cubes (when held in RAM for efficient analysis) is too large for a cheap PC, however there are certainly some large organisations who hold giant multidimensional structures of these kind of proportions (such as Google for their searches). It seems highly unlikley that there are not heavily resourced organisations out there who already have calculated and use such prime cubes. The difficulty of factoring the pair of primes is the "headline" difficulty for e.g. RSA, but don't underestimate the additionla difficulty produced by the step for generating the private key because it has a modular calc.
As already mentioned above, there isn't anywhere near the storage space required in the entire world. I'd wager that before we even get to that amount of storage, a quantum computer running Shor's algorithm (or a similar algorithm) will have nullified the need.
-
Interesting, that would also mean that the RSA's claim that "2048 bit keys will hold good for the next few decades" would be invalidated. It would be great if you add references in you answer to help future viewers :) Commented Dec 11, 2012 at 0:13