All the World’s Secret Numbers

Humans invented cryptography before they invented the alphabet. Over 4,000 years hieroglyphics turned to letters and letters to numbers. Early encryption algorithms based on simple permutations of the alphabet were replaced by locally varying (letter by letter) substitution rules enabled by mechanical/electrical engineering advances (ex: enigma machine), and then took a turn toward number theory in the 1970’s. Each sweeping change in algorithms almost always came in response the current one being broken. Once this happens cryptography has little use for the algorithm and, typically, a rather different one takes its place. How much more time is left in the rein of today’s RSA and elliptic curve algorithms? What will replace them? How are today’s battles between encryptors and code breakers different from the past?

The difference is in the scales: 1. the magnitude of people directly involved has ballooned, 2. the type of the information being encrypted has shrunk to the scale of the individual, and consequently, 3. the frequency with which encryption is used has grown to many times a day for most individuals. From classical times through World War 2 it was military leaders, powerful rulers, their spies, who had information requiring such secrecy, whereas today it is everyone with an ATM card, an email account, a facebook page- billions of people- depend directly upon encryption. Rarely do we recognize that without reliable cryptography the internet, now so ingrained in society, would be dismantled. We take for granted that the numbers and passwords, the tiny secrets that collectively unlock each of our online identities remain safely stowed away. Public key cryptosystems are prevalent in web security. They keep part of the information required for decryption publicly accessible, but design the algorithms such that it is useless on it’s own. The intended receiver of the message is sent a private key, which when used according to a simple rule decrypts the message. This is in contrast to symmetric key cryptosystems, developed earlier, which require both sender and receiver to exchange a key. Often this pair of keys must be unique to the message, requiring sophisticated management of the network.

What makes a good public key encryption algorithm? Most are based on unsolved problems in number theory. The idea is to use an essentially “one way” function (a function in mathematics takes in an input, a list of numbers, and yields an output, also a list of numbers). By “one way” we mean the function is easy to evaluate forwards (get the output from input) but extraordinarily difficult to invert (get input from output). The functions upon which the RSA algorithm is based is multiplication of large primes and modular exponentiation. There is no other method for finding the prime factors of a number aside from the brute force method of dividing the number by all the preceding primes. When numbers are large enough this becomes computationally implausible. Discrete exponentiation means raising a number to a power, modulo another (prime) number. Modulo (n) means that the numbers cycle back to 1 after multiples of n (so n+1=1, n+2=2…2n=n, and so on). So, for example 7^4 modulo 23 is 9 because 7^4=2401 and 2401/23= 104 remainder 9. It is very easy to compute 7^4 mod(23) and get 9, but very difficult to obtain 7 from the exponent, 4, and the modulus 23. As illustrated in the diagram the private key, d, yields the decrypted message in a single easily computable step.

There are two approaches to breaking RSA: either an new, fast algorithm for prime factorization or discrete logarithms (inverse of discrete exponentiation), or dramatically increasing computational power. Quantum computers would accomplish the latter. This tremendous increase in computing power is based on the fact that a quantum system is always in a superposition of states (until measurement) and quantum entanglement. A spin half particle (ex an electron) has a two dimensional space associated with it, simply because of what it is. The state of an electron in this space (it’s spin state) is described (according to a chosen basis) as a superposition of states. You can think of this as an arrow in a two dimensional plane, where the basis is the pair of axes you’ve chosen to draw. This is not entirely accurate because spin states don’t rotate in the same way as arrows in a sheet of paper, but for our purposes this is ok. Any arrow you draw you can write as the sum of a pair arrows (each of appropriate length) directed along the axes. This is what is meant by superposition. If one identifies one basis state with the number zero, and the other with the number 1, we have that a single bit can now be in a combination of states (i.e. in both states 0 and 1). If one introduces another electron there are a total of 4 basis states for the system. Introducing another yields 8 states, and n particles yields 2^n basis states. The key is that whereas a classical computer would always only be in one of the 2^n states a quantum computer is in all of them.

There are obstacles to making quantum computers a reality, namely decoherence, an interaction which tends to collapse the superposed state of a small system in the presence of a large macroscopic one. Nonetheless, the promise of computational power increasing by many orders of magnitude warrants continued study in the field. Computational limitations, a common obstacle in applied mathematics, physics, engineering, and a whole host of disciplines would vanish. So in 2 years, no it won’t be a reality, but 15 or 20? Possibly. What then will we do with all the world’s secret numbers? There are a few options already being studied: lattice-based and code-based (ex: McEliece) cryptosystems among others, which are as far as we know immune to quantum computers (though keys for McEliece have to be significantly larger due to Tanja Lange and Dan Bernstein’s work on information-set decoding). Another potential solution is, ironically, found in quantum mechanics itself: quantum key distribution. In sum, though we can’t be sure what will replace RSA and the like, we have 4,000 years of precedent for confidence that there will be a replacement. So I think this is cause for excitement as the future is looking rather bright from here.