Key Takeaways
Modern cryptography is broken into two types: symmetric and asymmetric
Quantum computers can process exponentially more data than classical computers because their most basic unit of data, the qubit, can be 0 or 1 or a superposition of both
Quantum computing with Shor’s algorithm will crack asymmetric cryptography algorithms probably within the next 20 years while symmetric cryptography is safe from quantum decryption
On my first day of Harvard’s introductory cryptography course, the professor, legendary mathematician and cryptographer Boaz Barak, put the following quote on his opening slide: “Human ingenuity cannot concoct a cipher which human ingenuity cannot resolve.” Edgar Allan Poe, 1841
Cryptography is the study of secure communications techniques that allow only the sender and intended recipient of a message to view its contents. It is closely associated with encryption, which is the act of scrambling ordinary text into what's known as ciphertext and then back again upon arrival.
Today’s cryptosystems and their applications would be unimaginable to Poe. These include secure communication without sharing a secret, electronic voting without a trusted authority, anonymous digital cash, and many more. Nevertheless, Poe’s statement is likely to prove true again as we approach the doom of today’s widespread cryptography systems that the media has dubbed the “Cryptocalypse”. The Cryptocalypse will be enabled by quantum computers and is predicted to “break the internet” by cracking all encryption algorithms that are used to secure emails, bank accounts, and all over-the-internet communication. This blog identifies what type of cryptography systems are actually in trouble and explains why.
Cryptography Today
Modern cryptography can be broken down into two approaches: symmetric and asymmetric. These two methods will be affected differently by the rise of quantum computing so it's important to understand where they are used and why.
Symmetric cryptography uses one shared key for both encryption and decryption. The entities communicating via symmetric encryption must exchange the key so that it can be used in the decryption process. Symmetric encryption algorithms are very secure (Advanced Encryption Standard (AES) encryption algorithms take billions of years to crack using brute-force) and fast (because of shorter key lengths and relative simplicity compared to asymmetric encryption). Due to the better performance and faster speed of symmetric encryption (compared to asymmetric), symmetric cryptography is typically used for bulk encryption / encrypting large amounts of data, e.g. for database encryption. The big problem with symmetric cryptography is securely distributing the keys and keeping them secure after distribution.
Asymmetric cryptography uses a key pair consisting of a private and a public key. The public key is used for encryption and to verify signatures and can be shared freely. The private key is used for decryption and to sign data and is kept secret by its owner. Some examples of asymmetric encryption include Rivest Shamir Adleman (RSA) and the Diffie-Hellman exchange method. Bitcoin is one example of an application of this type of cryptography also known as public key cryptography. The benefits of asymmetric cryptography include not having to distribute keys and easy message authentication by using private keys to digitally sign files. The main disadvantages are that it’s slower than symmetric because of longer key lengths and more complex calculations. Why the long keys and complex math? Because, in theory, public keys can crack private keys - they’re mathematically linked - so we use extraordinarily long key lengths to make this virtually impossible, at least for now.
Curious about how RSA cryptography works?
Let’s take a look at an example of one of the most common asymmetric algorithms in action, RSA. Alice wants to send Bob a secret message, the letter “C”, that Eve cannot read.
The “encryptor” (AKA Bob’s public key): (5, 14)
This pair of numbers is public, and is used by Alice (the sender) to encrypt messages.
The “decryptor” (AKA Bob’s private key): (17, 14)
The first number in this pair of numbers is private, i.e. only known by Bob (the receiver). This pair is used to decrypt messages.
1. Alice encrypts the message “C” using (5, 14).
First, “C” is converted into an integer. In ASCII, “C” maps to the integer 67. But for simplicity, let’s say it maps to 3 instead.
Then, 3 is encrypted. 3⁵ mod 14 = 5.
2. Alice sends the result, 5, to Bob. If Eve peeks and sees this message, it tells her nothing.
3. Bob decrypts the result using (17, 14).
5¹⁷ mod 14 = 3.
The result is 3. Bob maps 3 back to a character, which is “C”, to get the original message.
Bob’s keys are (5, 14) and (17, 14). These numbers were not completely random and you’ll notice that one number is in both keys: 14. Where did the 14 come from? Bob chose two prime numbers, p and q, and multiplied them together (in this case he chose p = 2 and q = 7). The other components of his keys 5 and 17 were derived from clever yet simple calculations using p and q. This means that if you could find out what Bob chose for p and q then you could do the same calculations to find out Bob’s private key, 17! Then why would Bob ever expose the product of p and q, 14, to the world in his public key?!
The trick is that prime factorization is not an easy calculation. Naively, the reason this is difficult is that to factor the number n you have to check every number between 0 and sqrt(n) until you find either p or q. A computer will search for prime factors of a number starting at 2 and then going through every number until it finds one that divides the number we started with. In our example, it would be pretty quick because 2 is the first number it checks and happens to be what Bob chose. This is why modern public key algorithms choose HUGE prime numbers for their p and q. RSA-4096 uses two 2,048-bit prime numbers. A 2,048 bit number gives you 22048 distinct numbers. As a reference point, the number of atoms in the observable universe is 2256. You could have every computer on Earth looking for p and q and it would still take 300 trillion years to do it.
Main takeaway: If there was a way to efficiently factor large integers, then we could crack modern asymmetric cryptography. This would make online shopping, online banking, email, and wireless home networks all insecure. It’s been unbreakable for about 50 years now, what’s changing that is making people worry? Shor’s algorithm and the rise of quantum computing.
How close are we to breaking asymmetric cryptography?
This is a brief timeline of the events relevant to quantum computing getting closer to breaking the modern public key infrastructure:
1959: Richard Feynman proposes the possibility of using quantum effects for computation
1980: First quantum computing architecture proposed by David Benioff
1984: IBM researchers propose DB84, the first quantum cryptography protocol
1994: Peter Shor describes an algorithm to factor large integers in polynomial time (this would be used for cracking asymmetric encryption)
1996: Lov Grover describes an algorithm that finds the input to a black box function with high probability in O(sqrt(n)) evaluations of the function reducing the complexity of brute forcing a 128-bit key to ~264 operations (this would be used for cracking symmetric encryption)
2016: NIST solicits submissions for Public Key PQC algorithms
2019: Google announces “quantum supremacy” after performing a calculation that would take 10,000 years on a classical computer in 200 seconds on a quantum computer
Shor’s algorithm is a way of factoring a number n that doesn’t involve checking every number between 0 and sqrt(n). It is named after MIT professor Peter Shor. With classical algorithms factoring becomes increasingly time-consuming as n grows large, but with Shor’s the difficulty does not increase as much with n. The algorithm itself is quite complicated, and if you are curious how it works you can read about it here. The catch is that Shor’s algorithm will only work on a quantum computer.
Why does Quantum Computing threaten cryptography?
Quantum computing is a mind-blowing technology. One of the best videos I’ve found that describes how it works can be watched here. Classical computers perform calculations using the definite position of a physical state - such as on or off, 1 or 0 - this state is called a bit. Quantum computers use the quantum state of an object to produce what’s known as a qubit. These states are the undefined properties of an object before they’ve been detected, such as the spin of an electron or the polarization of a photon. The main takeaway from that video is that the amount of information contained by N qubits is equivalent to the amount of information contained by 2N bits. This means quantum computers have the potential to process exponentially more data compared to classical computers.
A few things to note about quantum computing:
A quantum computer can carry out any operation of a traditional computer, but traditional computers cannot carry out quantum operations.
Problems that cannot be solved computationally (e.g. Halting Problem) still cannot be solved on a quantum computer.
If a computation does not involve a large amount of potential solutions (straightforward arithmetic) it is likely to be faster on a traditional computer.
Is a Cryptopocalypse coming?
Media coverage proclaims that quantum computers will break the internet, or at least the cryptography securing our communications on the internet. Other coverage claims it won’t or won’t be able to for decades. So which is it?
The short answer - modern asymmetric encryption is doomed, symmetric will be fine.
For most symmetric algorithms, double the key size and you’ll be just as safe as you are today. This is because symmetric encryption is a black box. The hacker has no clue as to what the secret key is, so the only approach is to brute force every possible value.
Unfortunately for today’s public key infrastructure, factoring large integers is a perfect use case for quantum computing. Using Shor’s algorithm, quantum computing will break most current public-key cryptography. However, breaking a 2048 bit RSA is estimated to require at least 4,000 stable qubits.
When Google announced that it had achieved “quantum supremacy” — or that it used a quantum computer to run, in minutes, an operation that would take thousands of years to complete on a classical supercomputer — that machine operated on 54 qubits. While IBM’s Q 53 system operates at a similar level, many current prototypes operate on as few as 20 — or even five — qubits. To get to the 4000 qubit requirement for cracking RSA could take many years. How many years? Really it’s impossible to say because we can’t predict what kind of improvements will occur. It could be 10 years or 20 or 5, but why wait to fix what we know will be broken?
The implications of the Cryptocalypse are huge and many organizations are taking steps now to prepare. Future blog posts will discuss what the federal government is doing to prepare, what the cryptocurrency community is doing to prepare, and what all organizations can do to be ready for the big switch to quantum-resistant cryptography.