In my original post I said that on average it would take 250 tries to crack a 100 bit key. That is way off: You would have to try 299, or half of the 2100 possible keys. At one million tries per nanosecond, it would take over 20 million years to find the key. I shudder to think about a key 1000 bits long.

WorkHorse: Thanx for the info about Dan Brown. His concepts did not seem sound. You reinforced my opinion of code cracking via brute force. I do not know what NSA can do in this age of computers. An obsolete Laptop (say 800Mhz) can easily encrypt/decrypt using a 1000 bit key. Prior to the modern PC, the time required to encrypt/decrypt was critical. It had to be done using manual methods. A computer with a lot of parallel processors could break such codes, and some methods were crackable via sophisticated analysis rather than brute force methods.

Decrypting a message is a bit different from trying to get an ATM PIN number or a password for logging on to a computer. When attempting to decode an intercepted message, there is no software that will ignore you after 3-10 bad guesses. The brute force methods try every possible key until a sensible message is obtained. The algorithm to decide if the decrypted text is sensible might take more time that the decryption algorithm.

I do not think that sophisticated algorithms are necessary if the key is long enough. The weird complex algorithms are required by the Public Key methods. The mathematics is a bit difficult to understand, but the concept of Trap Door functions is not complicated. They are called Trap Door functions due to an analogy: It is easy to fall through a trap door, but very difficult to climb back out of dungeon you fell into. There are various mathematical processes that are easy to work in one direction, but difficult to reverse. A trivial example is polynomial roots and coefficients. Given the roots, there are easy algorithms which will determine the coefficients. For fifth order and higher polynomials, It is has been proven that there are no analytical methods for determining the roots if you know the coefficients.

The first Public Key method (from about 1975) used the product of two very large prime numbers as an encryption key. To decrypt a message, you had to know the prime factors. Knowing the prime factors, it is easy to find the product, but determining the factors from the product is tuff if the smaller prime has 300 or more digits. Note that classical methods usually (always?) use the same key for both encryption and decryption, while Public Key methods require that the keys be different.

The advantage of such methods is due to what spooks call the down stream loading problem for the standard key methods. Prior to Public Key methods, a courier had to deliver keys, which might not be easy if the spook/soldier who wants to send you a message is under deep cover behind the Iron Curtain or is on a battlefield. With Public Key methods, you can announce the key over public TV or in a radio broadcast. Another interesting advantage of Public Key methods is the ability to verify the sender of a message via processing of an encrypted signature.

WossName: You, like may others, believe that future computers will be fast enough to solve any problem in a reasonable amount of time. This is flat out not a valid belief.

BTW: I will believe in the effectiveness of quantum computers when they build one that can do something more difficult than factoring a 2-digit number, which is not much to show for 20 or so years of effort. I wonder if this technology is being driven by an academic Publish or Perish motivation.

50 years ago, cryogenic computers were prophesied to be the great technology of the future. Much money and resources were invested in this technology. The prototypes could do some significant computations, but practical problems and other developments doomed this technology. I wonder if quantum computers will turn out to be another great concept which did not get out of the laboratory.

I also wonder if quantum effects will put a limit on miniaturization of CPU circuitry and nanotechnology.