In 1994, Peter Shor publishes the paper “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer” that leads to the world thinking that Quantum Computers can break the internet encryption.
Is it true? Yes… but. a BIG but.
And I know, clickbaity title, but hey, we are in the #QuantumComputing world after all 🙂
Now, I won’t lie to you. Understanding Shor’s algorithm is complicated. It requires a fair knowledge of algebra, theory of big numbers, modular arithmetics, Fourier transforms, and of course Quantum Computing. It will be also useful if you know about destructive interference, the key “super power” of the qubits that makes the quantum option “viable” in a decent amount of time (that is not billions of years).
Enough chatter. This is the code you need to run to find the prime factors of the number 15:
from qiskit import Aer
from qiskit.aqua import QuantumInstance
from qiskit.aqua.algorithms import Shor
backend = Aer.get_backend('qasm_simulator')
quantum_instance = QuantumInstance(backend)
print(Shor(N=15, quantum_instance=quantum_instance).run())
That’s it. Easy right? You only need Python3 and the Qiskit libraries. Run that code and depending on your CPU it might take a second or two (after all, it is a simulator). I will leave as homework running it on a real device.
Now, let’s break the internet! But first, the basics. The “Internet” encryption is based on RSA, and this is how a typical key would look like:
<RSAKeyValue><Modulus>miGeCzmPneAtvDsC8iTDM+9pqCM40pC8Ly+bp2uEj874UnficBpctHN6flmAYQoVDxgLkBfdwRG+1hm1QhmyQu7yEXFxaFSbqvwL/8ZextswgFx9MQlgbXiNvAh5a4uQvFeVz27LvXaGq4bwt1OzITwWIbD/YLdjeugQyrzn3wU=</Modulus>
<Exponent>AQAB</Exponent>
</RSAKeyValue>
That is the stuff you share publicly. Anybody can have it and with it do lots of nice things. It can ensure you and only you sent the message, and that no middleman tampered with it along the way. But that is not the complete key. The complete one is this (what is called the key pair):
<RSAKeyValue>
<Modulus>miGeCzmPneAtvDsC8iTDM+9pqCM40pC8Ly+bp2uEj874UnficBpctHN6flmAYQoVDxgLkBfdwRG+1hm1QhmyQu7yEXFxaFSbqvwL/8ZextswgFx9MQlgbXiNvAh5a4uQvFeVz27LvXaGq4bwt1OzITwWIbD/YLdjeugQyrzn3wU=</Modulus>
<Exponent>AQAB</Exponent>
<P>zDDA1JW+ohghtYzDHwZa+eK5iApEyR8p4gh01NdlwHpQOGiroENscdfL37O1rUBMKGWyUVSPsM5iRvQ/nJ9GFw==</P><Q>wT1CgvAkFWF8oFlGY6bKlCEcHeTKd1JinHSsikQxiuM6EKEFPnZ2LvUxnAJAFivN0WnkNB/ly9ed28sLTJcRQw==</Q><DP>ewZMyEjIqOUdOkNrNIAhxDkkS6DUPNE37OXnbm2w8r0/JB18enzlE9pPDaM7LP12ZUiQnYvzXzWZ5OI4iWc1VQ==</DP><DQ>XelRq6TdRG7OTHdWmBN1HCxDJ9wK8ZZeSj8Bo2ik0yS/EVnP3J1hrkyHQZRuZNgA/KcDurlNypUNKMYyxZQdVQ==</DQ><InverseQ>whh8tGO0bFPzq+14zl0CGSMbRdhuxyDQvblRCp/McaS8hC6p0SavSr68Q9VJ13KprkiqFoaW7ivx3r7cJDiVGg==</InverseQ><D>PPuUFojdw+9Q6SrIDZpyCXhua3IUJ2vQqTLC+UjXGDchlS+NziEAEP2nt5od60cb8e7nlEl9Gci1ouxlBRQ5rRiyMQocX68+K5cJahh6jYGFbL3yGnfv29/U9fyQ/Uuxddq/odAK4HSzlKMoyjEViU+1rZa6zjtdgNfVWSgfE7k=</D></RSAKeyValue>
Note there are some other values there that should be kept secret. That is like the pin code of your credit card! (even we all know is your brith date!) There is lot of stuff in there, but for now the only thing you need to know is that D is your decryption key, an Modulus equals to P times Q. And those happen to be prime numbers (I know, they are letters, but letters in a computer are numbers after all right? In our case encoded in Base64). So P and Q are what we call the prime factors for Modulus. (P*Q=Modulus). (What the hell is a Modulus after all? To get that knowledge you have to be behind the paywall :D)
And Modulus is in plain sight for everyone to see in EVERY message you send over whatsapp. (Hahahaha, finally you will be able to spy your brother in law messages!!!)
So, we just have to intercept the message (your friendly neighbourhood 14yo hacker will tell you how to do it). Plug in the modulus into the code I showed you above and some algebra later, boom. You can decrypt Whatsapp messages, private Facebook conversations, or the code a Credit Card PoS sends to its bank with the amount paid (among many other things)
Now, you can go ahead and plug in the number in the code above…
…or not.
If you have tinkered with that code you might have realized that once you put bigger numbers it is the end. Your computer will be set on fire. You can send the job to one of IBMs quantum computers on the IBMQExperience. You can use for free the 16 Qubits one. But still it is not enough. Today you are better off calculating it with your brain.
So no, you can’t break the internet just yet. You will have to wait a bit.
No worries, keep that code snippet close. No need to understand the algorithm, no need to now anything further. Just wait until we have bigger, less noisy, quantum computers and you will be able to do so. Some people say 10 years, some others 30 years until we get there. Most likely by then we will have some other post-quantum encryption algorithm that can’t be broken with a Quantum Computer. Oh well… we also missed the blockchain opportunity.
Now what I’m trying to show here is the good steps forward on abstracting the physical layers, the topology and the hardware. Very soon software developers will be able to code on Quantum Computers, without knowing the algebra behind, the Dirac notation or maybe even Quantum Mechanics. After all, In classical computing, do you know what exactly does the Java’s garbage collector inside your machine? Do you know how the logical gates are assembled inside a CPU? No, right? (for the majority of you at least!) I believe this is the same. We will have a framework with a library with a function that says p, q = factor(N) and that will be all we need to know.
Exciting times!