No, The NSA Does Not Have Encryption-Breaking Quantum Computers

By Duane Thresher, Ph.D.          December 7, 2019

Many people who absolutely should be using email encryption, like VIPs, don't because they say the National Security Agency (NSA), and thus the CIA, FBI, etc., can break the encryption (decrypt) anyway so why bother; the encryption will just point out their email to the NSA as worth breaking. The slightly more knowledgeable of these people say that the NSA can break this encryption because they have encryption-breaking quantum computers. The IT incompetent NSA does nothing to dissuade them of this belief because it makes their job of reading people's emails much easier. And the IT incompetent media, universities, and tech companies can't hype quantum computers enough — it sells ads and gets funding and investors, much like bogus artificial intelligence stories do. However, without any NSA-insider knowledge you could have been fairly sure the NSA doesn't have encryption-breaking quantum computers and now with the NSA-insider revelations of Edward Snowden you can be very sure the NSA doesn't have encryption-breaking quantum computers. So encrypt your email. Let Apscitu help you do it right so it is actually unbreakable.

Nowadays, breaking encryptions must be done via mathematical calculations on a computer and the security of an encryption is based on how fast it would take without the encryption key to break the encryption. If it would take on average millions of years then that is the same as being unbreakable.

Most people know about a computer's "brain", the CPU (Central Processing Unit) or just "processor". They may also have heard of Moore's Law and through a misconstruing of it, think it means processor speed will double every year or so (it actually says the density of components, like transistors, in integrated circuits (ICs or "chips") will double every year or so, which is not the same thing). Computer salesmen, including for supercomputers, and the media got used to selling new computers every year based on dramatically faster processor speeds and now they are dependent on that.

At some point it became impossible to dramatically increase the speed of a single processor. Enter "parallel processing", whereby multiple processors, often on the same chip, are used instead of a single processor to increase speed, by doing calculations concurrently instead of sequentially. The fastest computers in the world, supercomputers, are now the ones with the most processors (numbering in the thousands) and personal computers have dual-core (two processor) or quad-core (four processor) chips.

(Full disclosure: I am an expert on parallel processing and supercomputers, having attended NASA's High Performance Computing School and rewritten large parts of the NASA GISS climate model to run on parallel processing supercomputers, as well as having a BS in Electrical Engineering and Computer Science from MIT.)

The dirty big secret of parallel processing is that many, if not most, problems are not amenable to being solved faster by it. If each calculation in a solution requires the output of the previous calculation, i.e. calculations have to be sequential not concurrent, then parallel processors provide no advantage over a single processor. You can see this yourself if you have a multi-processor personal computer and have set up a performance meter to show the activity of each processor. You will see that most things you do on the computer mostly use a single processor.

Even for those problems that are amenable to parallel processing, at some point so many processors are required to solve the problem fast enough, that it becomes impractical. If it takes most, all, or more of the existing processors in the world to break a single encrypted email fast enough then that is the same as being unbreakable. (This would be especially true if most emails, no matter how trivial, were encrypted, so that it would not be known which ones were worth the effort of breaking.)

For example, RSA — named after its discoverers MIT computer scientists Ronald Rivest, Adi Shamir, and Leonard Adleman — is the actual encryption used, originally illegally, in the most well-known encryption system in the world, PGP (Pretty Good Privacy). (For more on RSA, PGP, and encryption, see Incompetent Encryption Is Worse Than No Encryption.) The difficulty in breaking RSA is based on the time-consuming difficulty of finding two very large prime factors of an even larger number. There is (as yet) no easy mathematical formula for this and so it is like looking for a needle in a haystack, actually worse.

This prime factorization is amenable to being solved by parallel processing but the numbers involved are so large it would still take too many processors to break even a single encrypted email fast enough to be practical.

Enter quantum computers, which are based on quantum theory. Quantum theory attempts to explain the behavior of subatomic particles. It is bizarre, to say the least. Ever hear of Schroedinger's Cat, who is both dead and alive? Scientists trying to understand and explain quantum theory invoke infinite alternate universes. Really. This is not to say that quantum theory is wrong; it is one of the most successful scientific theories ever. Successful meaning accurately predictive, although the predictions tend to be statistical, which is of limited usefulness (knowing 16.67% of dice throws will be a 6 tells you nothing about what an individual dice throw will be; Einstein insisted that "God does not play dice with the universe").

As most people know, traditional computers, including parallel processing supercomputers, use bits, which mathematically can be 0 or 1 and physically are a low or high (relatively) voltage. These bits are grouped (e.g. bytes) to represent larger numbers, one bit combination per number. By performing, electronically, mathematical operations on these bit groups, problems can be solved.

Quantum computers have bits too, called "qubits", which physically are states (often spin direction) of subatomic particles. The states of these subatomic particles become "entangled" such that all combinations are represented at once by qubits. Unlike traditional computers, which have to iterate to the solution, with quantum computers, the solution is essentially already there, so they theoretically can be much faster than traditional computers.

If trying to understand and explain quantum theory and computers is maddeningly difficult — the preceding is a great simplification — actually building a quantum computer is much harder. Just for starters, the hardware must be kept near absolute zero and isolated for quantum effects not to be completely obliterated by macroscopic factors. Beyond that there is no one best way, at a basic level, to build a quantum computer, like there is for traditional computers.

Quantum computers have significantly high error rates. A computer with a non-zero error rate is unusable. If a computer has a non-zero error rate, how do you know its solution is correct, unless you already know the solution, in which case why do you need the computer?

Those who claim to have built quantum computers say they need to do more work, i.e. need more funding/investment, to get the error rate down. However, this error rate may be inherent. When Bell Labs spent a lot of time and money trying to reduce noise in telephone lines (it limited the number of conversations that could be carried on a single line, requiring more lines, which are expensive) they found that some significant noise was physically inherent in the system and could not be reduced.

That's just the quantum computer hardware. Figuring out how to solve a problem, i.e. the software, with a quantum computer is even harder (it depends on the problem being solved), which is why I didn't try to explain it more above. Quantum computers are thus applicable to even fewer problems than parallel processing computers, although the mentioned prime factorization of RSA encryption is supposedly amenable to quantum computing.

The hyperbole about quantum computers is as fantastical as their concept. This hyperbole is necessary to sell ads and get funding and investors, just like for artificial intelligence, fusion, superconductivity, nanotechnology, gene therapy, perpetual motion, etc.

Most recently, in October 2019, Google grandly claimed it had a 53-qubit computer that could solve in 200 seconds an arcane problem (not even an important one like encryption breaking) whose solution would take 10,000 years for the current world's fastest computer, a parallel processing supercomputer built by IBM for the Department of Energy. IBM pointed out that their supercomputer would actually only take 2.5 days, not 10,000 years! And if they added even more processors, not even an unreasonable number, it could take significantly less than 2.5 days.

Besides the probably-insurmountable difficulties for anyone of building an encryption-breaking quantum computer, as if that weren't enough, how else could you have been fairly sure that the NSA hasn't built an encryption-breaking quantum computer?

The head of a project to build an encryption-breaking quantum computer would obviously have to be highly-educated in the appropriate field. For example, Robert Oppenheimer, the head of the U.S. atomic bomb project during World War II, was himself a highly-educated physicist.

The private company Booz Allen Hamilton, Booz for short, does a lot of the work for the NSA. Much of what people think NSA employees do is actually done by Booz. Edward Snowden actually worked for Booz when he hacked the NSA as an insider and many of the secret NSA documents that Snowden stole and released (see ahead) have the Booz logo on them.

Booz's Chief Innovation Officer, who would be in charge of huge innovations like quantum computers, is Susan Penfield. You would rightly expect that Penfield was a highly-educated computer scientist and electrical engineer/physicist, i.e. an IT expert. She is not, not even close. Incredibly, Penfield only has a BS in management. She thinks entangled is about her hair and a qubit is a 1980s video game character (Q*bert).

All Booz's Susan Penfield does (and can do) is hang around social media (her photo above is from her Twitter page, where her inane motto is "let your innovation light shine bright!") and go around giving supposedly inspirational but misleading talks to impressionable girls about STEM careers ("you don't need a good STEM education, girls can do anything"). Like many, Penfield hides her IT incompetence behind the women's movement.

Now with the NSA-insider revelations of Edward Snowden you can be very sure the NSA doesn't have encryption-breaking quantum computers.

Recently, while using one of my fake Facebook accounts (no one should have a real Facebook account), Facebook perfunctorily informed me about their use of facial recognition on Facebook user photos. I remembered that the Snowden documents showed that Facebook aids and abets the NSA, but I went through the Snowden documents again to refresh my memory of the extent.

I was again struck by what was in the Snowden documents, as every IT expert who actually reads them is. The variety and extent of ways the NSA has to eavesdrop on people's communications is shocking.

But I was also struck, for the first time, by what was not in the Snowden documents — no mention of the use of encryption-breaking quantum computers.

Most of the Snowden documents are internal NSA advertising for the variety and extent of ways the NSA has to eavesdrop on people's communications. In any business, workers have to know what tools are available. That's why Snowden chose the documents to steal from the NSA — they give a good overview.

So if encryption-breaking quantum computers, which would make many other methods superfluous (see the Quantum program next), are not advertised, you can be very sure the NSA doesn't have them.

The NSA does have a program they call "Quantum" — obviously to imply they have encryption-breaking quantum computers — but it is not about encryption breaking. In fact, it is a method to get around encryption, which is admitting they can't break it, by hacking personal computers so they can get to the message before encryption or after decryption.

While the Snowden documents are several years old now, it's extremely unlikely, given the above, that the NSA developed encryption-breaking quantum computers in those few years. The Snowden documents are full of "coming soon" announcements, none of which are about encryption-breaking quantum computers.

Even if there were prime factoring quantum computers that could break RSA, there are encryptions that are as good or better than RSA, some that can't be broken even theoretically by a quantum or any other computer.

In fact, with PGP most email messages are not actually encrypted by RSA because it is too processor intensive to do so. Only the key to another encryption is encrypted by RSA and then sent with the message, which is encrypted by the other encryption, a less processor intensive but no easier to break encryption.

RSA was invented to solve the key distribution problem — if you have to securely communicate with many people, like in the military during war, securely getting the encryption key to everyone is a big problem.

RSA uses a public key, which anyone, including the enemy, can have, for encrypting (only) and a private (secret) key, which only the recipient has to have, for decrypting (only), whereas other encryptions only have a private (secret) key for encrypting and decrypting, which both sender and recipient have to have.

If key distribution is not a problem, like between just two people who can easily contact each other at least once using other than email, there are encryptions that can't be broken even theoretically by a quantum or any other computer.

For example, there is one-time pad encryption. This was used for messages between the President of the United States and the leader of the Soviet Union during the Cold War. In one-time pad encryption each character of a message is encrypted with a different key, which is another character, randomly chosen. Both sides have to have these keys, which are pads of sheets of characters that must only be used once and then destroyed, hence the name.

Even if you could quickly enough try every possible character (27, for alphabet/space only messages) for every character in the encrypted message, looking for a non-gibberish message — and for alphabet/space only messages, the total number of possible "messages" would be 27 to the power of the number of characters in the message, a huge number for even short messages — you would end up with a large number of non-gibberish reasonable messages.

For example, "attack on december eleventh" could also validly be decrypted as "attack on september seventh" or even "milk bread cheese eggs soda" because they all have the same number of characters, 27 (note the total number of possible "messages" would be about 443 followed by 36 zeroes). Without the one-time pad there is no way to know which non-gibberish message is the intended one.

(Did you ever hear the saying that if you have an infinite number of monkeys, each randomly pecking at a keyboard, one of them will produce Shakespeare's Macbeth? That's not hyperbole, that's the power of large numbers. It's actually an understatement since much other literature would be produced as well.)

The moral of this story is you should use email encryption for all your emails. It will prevent your emails from being read by the NSA or anyone else who shouldn't. NSA-insider Edward Snowden himself has said this. Snowden, apparently describing the NSA's deceivingly-named Quantum program, also said that the way the NSA gets around encryption is by intercepting the message before it is encrypted (sent) or after it is decrypted (received) on personal computers due to sender or recipient IT incompetence. For that reason, you should have Apscitu set up your email encryption.