Computationally infeasible is basically how one says 'really hard' in an academic paper without sounding silly. Almost always this term shows up in papers related to cryptography, since that is one of the few fields where one wants to try to make things as difficult as possible. However, this is a pretty slippery concept, because what is computationally infeasible one decade may be trivial the next. For example, when DES was originally introduced, the NSA claimed it would take millions of years to brute force a key. But 20 years later, it could be done in days or weeks (albeit with a substantial amount of hardware).

Over the last 20 years, there have been three main factors involved in changing what is or is not considered infeasible. These are:

  • Processor improvements: Moore's Law, considered over a decade or more, can really change things. In addition to the obvious Mhz increases, the superior instruction sets , better compilers, and vast increases in memory speed and size all make problems that previously needed a supercomputer solvable on a fast PC.
  • Algorithmic advances: For problems like factoring, algorithmic advances can also cause major speedups. For larger (512+ bit) RSA keys, factoring using the Generalized Number Field Sieve is ten times faster than older methods.
  • New computing methods: Quantum computing, biological computing, and other such advances may, in the future, prove to provide machines much faster than we will get just by 'sitting around' and waiting for Moore's law to speed things up. It might be possible that if a quantum computer was powered by all the energy put out by the sun for an entire year, it could crack a 256-bit cryptokey (this is highly speculative in all senses of the word, and assumes advances in many different scientific areas). However, even for such a monstrous machine, a 512-bit key would be completely out of reach.

Right now (2003) the current estimate for what is computationally infeasible is roughly 290 operations. In addition to this lower bound, we can also say what will never be feasible with any possible technology - at least, any which could conceivably be built by humans in the next 1000 years, which is good enough for me. If you can manage to build Dyson spheres around every sun in the galaxy and use all the power you collect to run quantum computers, that's a different story. But, even then, 21024 operations seems to be impossible. Exponentials are funny things, huh?

† As an aside, this is why security engineering requires a completely different mindset from, say, building a toaster or an oil refinery.

‡ This includes more and larger registers, SIMD extensions like SSE2 and VIS, and instructions like fused multiply-add to decrease bottlenecks in algorithms.

Log in or register to write something here or to contact authors.