First, the message is encrypted using a secret key, which is in turn encrypted with a public key. This means that you don't need to break the public key to get at the message, breaking the secret key is actually better, as verifying you have the right key is sooo much easier.
Second, the time it takes to break a key... Because you can do the computations in parallel (no two tests interact with each other), you can wire up massively-parallel decryption circuits to do this. The speed-up is impressive. So much so, that the British wartime "Colossus" machine is faster at breaking Enigma-type codes than a modern Pentium II, by several orders of magnitude.
(Whereas a P2 can test one key at a time, the Colossus could test hundreds. Whereas a P2 uses general-purpose hardware, with a software layer, the Colossus was a purely hardware device.)
Now, let's get a benchmark on this. The "rule of thumb" used to set the maximum exportable bit-length was that no message should take longer than 10 minutes to decrypt. This means that 56-bit encryption could be broken by brute-force in under 10 minutes, maybe a decade or so ago.
Let's now apply Moore's Law - computing power doubles every 2 years. That's 2^5, if we assume 10 years, which would increase the capability to 61 bits in 10 minutes, today. Actually, given that (prior to unrestricted distribution) the proposal was to move the limit to 64 bits. Which, if you look at the figure I got above, now seems somewhat more understandable.
Ok, so let's say they can break 64-bit encryption in 10 minutes, today, in bulk. How large a bulk is difficult to even guess at, but if you could tie those resources together, to make a distributed computer, you could increase the number of bits you could handle in the same time by log2(N), where N is the number of nodes in the distributed network.
The fabled "Echelon" system is purportedly capable of monitoring hundreds of millions of parallel signals, simultaneously, in the largest distributed network ever built. Would this be big enough, though, to crack "strong" encryption?
Not quite, but it's getting there. Assuming something in the order of 100 million devices, capable of cracking 64 bits in 10 minutes, your cluster could be expected to chew through 91 bits in the same timeframe. Ok, let's see what happens if we increase our timeframe. (10 minutes is a bit short for something potentially major.)
In one day, you could increase the number of bits gone through, by sheer brute-force, to 98. Because of diminishing returns, this is about the best you could expect to break in any reasonable time-frame, even using the best computer resources you can find.
Once you get to this point, you have to look for weaknesses in the strategy for producing keys, or in the algorithm itself. In other words, shrink the effective search-space, rather than increase the speed of searching it. Given that the security agencies have the very best mathematicians on the planet (and then some!), it is entirely believable that such exploits have been found, especially in closed-source products such as PGP.
However, is brute-forcing the key the only way to do this? No. If computers are relied-upon, then a sufficiently-skilled operative could easily back-door your encryption system. All that they would need to do, in fact, is install a binary patch, such that the range of keys actually chosen from is within the range that the agency can search for. It's unlikely anybody would detect such tampering, and we know from reports by the Internet Auditing Project that such agencies can modify binaries without detection by intrusion detection systems.
[ Parent ]