NSA seeks to build quantum computer

[GURPS]

NSA seeks to build quantum computer that could crack most types of encryption


In room-size metal boxes #secure against electromagnetic leaks, the National Security Agency is racing to build a computer that could break nearly every kind of encryption used to protect banking, medical, business and government records around the world.

According to documents provided by former NSA contractor Edward Snowden, the effort to build “a cryptologically useful quantum computer” — a machine exponentially faster than classical computers — is part of a $79.7 million research program titled “Penetrating Hard Targets.” Much of the work is hosted under classified contracts at a laboratory in College Park, Md.

The development of a quantum computer has long been a goal of many in the scientific community, with revolutionary implications for fields such as medicine as well as for the NSA’s code-breaking mission. With such technology, all current forms of public key encryption would be broken, including those used on many secure Web sites as well as the type used to protect state secrets.

Physicists and computer scientists have long speculated about whether the NSA’s efforts are more advanced than those of the best civilian labs. Although the full extent of the agency’s research remains unknown, the documents provided by Snowden suggest that the NSA is no closer to success than others in the scientific community.

every quantum leap in computing [pun intended] limits the usefulness of the current encryption standards


in WW II the Enigma was thought unbreakable [and really was but for lazy radio operators or sloppy operations]

The exact figure for settings of the plugboard with 10 pairs of letters connected is 150,738,274,937,250

To see how this is worked out you must know some basic facts about permutations and combinations.

Given n distinct objects there are n! ways of arranging them in sequence, where n! means the product n x (n-1) x (n-2)... 3 x 2 x 1.
For example the six digits 1,2,3,4,5,6 can be arranged in 6 x 5 x 4 x 3 x 2 x 1=720 different orders (bell-ringers will be familiar with this.)

Given a set of n distinct objects there are C(n,r) ways of dividing it into two sets of size r and (n-r), where C(n,r) means
n! / r! (n-r)!

[clip]

From this formula we can find out something which often surprises people, which is that the number of possible plugboard pairings is greatest for 11 pairs, and then decreases:

1 pair: 325
2 pairs: 44.850
3 pairs: 3,453,450
4 pairs: 164,038,875
5 pairs: 5,019,589,575
6 pairs: 100,391,791,500
7 pairs: 1,305,093,289,500
8 pairs: 10,767.019,638,375
9 pairs: 58,835.098,191,875
10 pairs: 150,738,274,937,250
11 pairs: 205,552,193,096,250
12 pairs: 102,776,096,548,125
13 pairs: 7,905,853,580,625

Again, if you don't believe this can happen, have a look at the number of ways you can put 2 pieces of wire into 6 plugboard sockets: there are 45 ways, three times as many as you get with 3 wires. (Hint: imagine pulling out one of the three wires.)

because no one could brute force decrypt a message in real time to have meaningful intelligence
even today, there are a could of messages intercepted during WW II that have only now [last 10 yrs] been revealed
again the capture of code books, enigma machines and sloppy operation led to early sucess by Polish Mathematicians ....

in the 1990's PGP was pretty nifty ...

Security quality

To the best of publicly available information, there is no known method which will allow a person or group to break PGP encryption by cryptographic or computational means. Indeed, in 1996, cryptographer Bruce Schneier characterized an early version as being "the closest you're likely to get to military-grade encryption."[1] Early versions of PGP have been found to have theoretical vulnerabilities and so current versions are recommended. In addition to protecting data in transit over a network, PGP encryption can also be used to protect data in long-term data storage such as disk files. These long-term storage options are also known as data at rest, i.e. data stored, not in transit.

The cryptographic security of PGP encryption depends on the assumption that the algorithms used are unbreakable by direct cryptanalysis with current equipment and techniques. For instance, in the original version the RSA algorithm was used to encrypt session keys. RSA's security depends upon the one-way function nature of mathematical integer factoring.[2] Similarly, the symmetric key algorithm used in PGP version 2 was IDEA, which might at some point in the future be found to have previously undetected cryptanalytic flaws. Specific instances of current PGP or IDEA insecurities (if they exist) are not publicly known. As current versions of PGP have added additional encryption algorithms, the degree of their cryptographic vulnerability varies with the algorithm used. In practice, each of the algorithms in current use are not publicly known to have cryptanalytic weaknesses.

New versions of PGP are released periodically and vulnerabilities are fixed by developers as they come to light. Any agency wanting to read PGP messages would probably use easier means than standard cryptanalysis, e.g. rubber-hose cryptanalysis or black-bag cryptanalysis i.e. installing some form of trojan horse or keystroke logging software/hardware on the target computer to capture encrypted keyrings and their passwords. The FBI has already used this attack against PGP[3][4] in its investigations. However, any such vulnerabilities apply not just to PGP but to any conventional encryption software.

In 2003 an incident involving seized Psion PDAs belonging to members of the Red Brigade indicated that neither the Italian police nor the FBI were able to decrypt PGP-encrypted files stored on them.[5]

it all depends on the bit size of the key ... a 256k bit key from 1996 [previously large] is now way to small, and can be broken in a matter in hours or days .... 4096k bit keys would take significantly longer to guess all of the possible permutations ...

one time pads are still the go to item for unbreakability ...