How’s this for the plot of a spy story:
William Friedman, often regarded as the father of American cryptography, shares a meal in 1951 with his Swiss friend Boris Hagelin. They make a “handshake agreement” where Hagelin’s company will, in exchange for certain payments, allow the CIA and the BND to essentially control the development of the company’s mechanical encryption and decryption machines. For the next 30+ years, the CIA and the BND are able to read the crypto traffic of essentially any country in the world except for the “Five Eyes” (a very private club consisting of Australia, Britain, Canada, New Zealand, and the United States), China, and the Soviet Union.
Here’s the thing: this isn’t the plot for a spy story. This is a short summary of something that actually happened. The operation’s codename was Rubicon, the company was Crypto AG, and Rubicon was quite possibly the most successful intelligence operation in history.
This looks like a fun way to while away the hours . . .
Warning: not for the weak of geek!
Shor’s algorithm describes how to factor the product of pairs of very large prime numbers. The catch is that Shor’s algorithm requires a quantum computer to run on and while quantum computers do exist today, there aren’t any that are powerful enough to run Shor’s algorithm on the products of prime numbers which are big enough to be ‘interesting’.
Experts predict that there will be quantum computers sometime in the next couple of decades that should be able to run Shor’s algorithm on the products of very large (i.e. ‘interesting’) prime numbers.
Sidebar: If I have two very large prime numbers A and B then it is fairly easy to multiply them together to get a considerably larger number C. If I then give you C but don’t tell you the values of A and B that were multiplied together to get C then figuring out the values of A and B gets crazy difficult if A and B are large enough. Shor’s algorithm is able to figure out what the values of A and B are even if A and B are very large.
BTW, most modern encryption relies on the assumption that if A and B are prime and large enough and then it is extremely difficult to figure out the values of A and B if one only has the product of A and B.