"NIST key management guidelines further suggest that 15360-bit RSA keys are equivalent in strength to 256-bit symmetric keys."
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"
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.
Perhaps there's a fundamental limitation here?
Also, our knowledge of complexity theory is not sufficient to show that cryptography is even possible. I suspect that improvements in our knowledge of complexity theory will greatly improve our cryptographic primitives, in both security and efficiency.
What I hear you saying is "AES was designed with a practical implementation in mind, whereas asymmetric constructions were more 'discovered' from theoretical work that's often unweildy when reduced to practice". This about right?
The real issue is that no public-key algorithms are known other than those that are based on theoretical constructions.
I dunno. http://en.wikipedia.org/wiki/Merkle%27s_Puzzles always seemed pretty down-to-Earth to me, but they're inefficient as heck too. :-)
This is not to say that AES should not be trusted. AES is a fine cipher, it is efficient, and unless someone can show us a practical attack the heuristic evidence is pretty strong.
Now, as for Merkle puzzles, that system is not considered secure by cryptographic standards. A cryptographic construction is not secure unless it requires the adversary to do work that is exponential in some parameter in the system (the security parameter), while parties that know some secret (such a key) only do work that is polynomial in all parameters of the system. In the case of RSA, for example, parties that are aware of the secret key must do work that is cubic in the security parameter, while the adversary must do work that is exponential in the cube root of the security parameter. Whether such systems actually exist is still an open question, as it turns out; a positive answer to this question would imply that P does not equal NP. Cryptographers generally assume certain truths about complexity theory, beyond the P vs. NP problem, and cryptography research has actually opened new areas of complexity theory that are based on such assumptions (such as the notion of knowledge complexity, which emerged from the work on zero knowledge proof systems).
The reason I brought up Merkle puzzles is because they depend on a symmetric cipher or one-way hash function, giving them one foot in that first category.
But remember that before we build our Dyson sphere, we may get quantum computers, which makes our bruteforcing polynomial rather than exponential. Cryptsystems based on discrete log, EC discrete log or prime factorization (pretty much all existing crypto-infrastructure) are vulnerable.
More on this http://en.wikipedia.org/wiki/Post-quantum_cryptography
I think that's wrong. Grover's algorithm let's us speed up any algorithm, but not exponentially. You just take the sqrt of the run time.
Shor's algorithm lets us factor numbers in polynomial time. This would break RSA, but not every algorithm in general. I think, but I'm not 100% sure, that elliptic curve methods have no known polynomial time quantum algorithms, for example.
So are quantum computers not from matter and not in space? :)
Does quantum computing somehow get around the fundamental energy requirements?
For asymmetric systems, search is reduced to polynomial (if using the discrete log, EC discrete log or prime factorization).
Notice that the problem in question is: 'is a brute-force attack against a 256-bit AES encrypted document feasible?'.
But only that: there is no cryptanalysis in that. So read with the statement in mind.
Edit: And notice that any 256-bit key encryption algorithm is as safe as AES under brute-force.
Or, in other words, when you create a 256 bits RSA key, it's guaranteed that one of the factors will have at most 128 bits. Thus, it's only as strong as a 128 bits AES against brute force.
But anyway, that's a moot point, because criptoanalysis exists, and there are better than brute force attacks against both algorithms.