While the US and British governments undoubtedly have the resources to obtain the best computers and cryptographers that money can buy, they cannot (at far as I know) break really good encryption systems. This is why they have achieved much of their success the old-fashioned way and resorted to cheating, such as getting computer and chip makers and communication companies to collaborate with them to install back doors. News reports based on leaked documents by (who else?) Edward Snowden show that the NSA may have bribed RSA, one of the most important companies in the security industry, to get them to provide a loophole that the NSA could exploit.

Documents leaked by former NSA contractor Edward Snowden show that the NSA created and promulgated a flawed formula for generating random numbers to create a “back door” in encryption products, the New York Times reported in September. Reuters later reported that RSA became the most important distributor of that formula by rolling it into a software tool called Bsafe that is used to enhance security in personal computers and many other products.

Undisclosed until now was that RSA received $10 million in a deal that set the NSA formula as the preferred, or default, method for number generation in the BSafe software, according to two sources familiar with the contract.

One consequence of revelations such as this is that computer security professionals are being urged to boycott a conference organized by RSA. Another consequence is that companies are being asked to avoid compromised chip makers like Intel and Via Technologies. The cryptographic systems depend on random number generators built into the hardware and these are thought to have also been compromised

The basic problem for the NSA is that the best encryption involves prime numbers and breaking them involves factoring a number into two primes. As a simplified example, a communication may use the number 35 as part of its scrambling process. The NSA and GCHQ can get hold of that number easily but what they really need to unencrypt the message is not just the number 35 but its two prime factors 5 and 7. This factoring problem starts getting incredibly difficult as the number gets larger and it is a game in which the encrypter has the advantage.

In 2009, computer scientists using classical methods were able to discover the primes within a 768-bit number, but it took almost two years and hundreds of computers to factor it. The scientists estimated that it would take 1,000 times longer to break a 1,024-bit encryption key, which is commonly used for online transactions.

As the NSA and its accomplices in other countries get bigger and more powerful computers and its cryptographers develop better algorithms, all that needs to be done to defy them is to use yet larger numbers, requiring yet larger computers.

A huge leap in computer technology would be the development of so-called quantum computers. These are computers that designed based of the idea of ‘quantum superposition’. This is when that what we think of as two distinct states can co-exist simultaneously. It is bascially the Schrodinger Cat problem. Such a computer, if it could be built, would reduce enormously the time taken to solve massive problems, including the ones involving factoring of large numbers into their component primes.

A large-scale quantum computer, however, could theoretically break a 1,024-bit encryption much faster. Some leading Internet companies are moving to 2,048-bit keys, but even those are thought to be vulnerable to rapid decryption with a quantum computer.

Christopher Monroe is one of those scientists who worked on the NSA’s quantum computer program.

The reasons for trying to build a quantum computer are no secret. Most of the world’s computers encrypt their data using very large numbers. To break the code, spy agencies have to divide the numbers by other numbers — prime numbers. Finding the right prime numbers can take a while.
“A thousand-digit number might take a full year of a team of supercomputers,” says Monroe. “You can add another hundred digits, and forget it — you won’t be able to ever do it.”
…

That’s where a quantum computer comes in. Most computers work using bits of data — ones and zeros. The bits in quantum computers can be both one and zero at the same time. What’s more, these quantum bits can all be interconnected in a fundamental way. Known as entanglement, this connecting of bits effectively allows the computer to try many numbers at once.

“It can look at them all at the same time and there’s a huge speed-up by doing that,” Monroe says.

A code that was impossible to break could be cracked in weeks, days — maybe even hours.

Naturally, scientists have been working on supercomputers for a long time because it is both an interesting and important problem and it should be no surprise that the Snowden documents reveal that the NSA has also been pouring vast resources into it, although there is no evidence that they have been more successful than other scientists.

The tricky thing about quantum superposition is maintaining that state over time. The superposed states are called ‘coherent’ but they are highly sensitive to interactions, even thermal ones, with the environment. Even the slightest disturbance can cause the states to ‘decohere’ and lose their superpositioning and drop into one or the other states. Creating a large-scale quantum computer and keeping these delicate systems isolated in order to maintain coherence is a huge technological challenge.