Transcription
We all know the story. Quantum computers will eventually break RSA, an encryption scheme that the internet depends upon. But how? There are many myths about quantum computers. If you see my last video, we explored why the whole "quantum computers perform all calculations at the same time" thing is misleading. That's because you only ever see one result per calculation. The trick is to inflate the probability of measuring the desired output. But how can we do that if we don't know what the correct output is? That's basically the whole challenge of getting quantum computers to work. Shaw's algorithm works by using one of these probability inflating systems called a quantum Fourier transform. That's what we'll explore in this video. A full breakdown of exactly how quantum computers use the QFT to run Shaw's algorithm and find the prime factors of very large numbers, which happens to break RSA.
And just so you know, I recently made a video about post-quantum cryptography, which told the story of an epic competition where cryptographers submitted encryption schemes and broke each other's all to find new encryption standards which are resistant to quantum attacks. In that video, I explore quantum computing, why RSA falls, and a detailed explanation of three new quantum-resistance schemes. It's a very long video, so I'm re-releasing it in four parts. This is part two. Don't worry if you haven't seen part one. I'll give a quick recap of a few essential details right now.
Quantum computers store states which have a probability of being observed. We write them like this: |ψ⟩ = Σ αᵢ |i⟩, where the coefficient squares to the probability of that state being observed. We can also entangle states, and measuring a value in one state can impact the probability of measuring a certain value in the other state. So let's say I square these integers. I set up the states with two registers and then I square the second. This sets up an input set and an output set. If I choose to measure the input set, there are four options, all with probability a quarter. Once I make the measurement, all the qubits are locked in this state. We say that the system collapses into this: |0⟩. But if I chose to measure the output register, there were two options, each with probability a half. After measurement, the qubits collapsed into this state: |0⟩, where I had a 50/50 chance of measuring either of the inputs that gave the observed output. When I applied a single squaring operation to this state, all four numbers got squared simultaneously. This is where the whole "quantum computer does all calculations at once" thing originates. The catch is that after measurement, I only ever see one answer. If I want to see all four squares, I'm going to need to do this whole thing at least four times. But let's say that I really want to find out which of these numbers square to four. And let's say that I can magically inflate the probability of measuring output four. Then I can more easily find out which of the inputs led to a square of four. The problem is, these magical probability inflators don't exist, except for a few specific cases. One probability inflator is the quantum Fourier transform, which is used as part of Shaw's algorithm to crack RSA, and that's what we'll explore now, beginning with a recap of how RSA works.
RSA is an asymmetric encryption scheme. So remember, this is where we all have our own public key which encrypts and private key which decrypts. Now, my public key is actually a pair of numbers. My private key is kept secret. Say Yellow Alex wants to message me with a letter Y, which in ASCII is 89. Using my public key, he does 89¹²⁷ mod 527. Now, a very quick aside about modular arithmetic in case you're unfamiliar. This means we take the remainder after dividing. So, 6 + 8 mod 12 is 2, because 14 / 12 is 1 remainder 2. You can also think of it as stripping away chunks of 12 until you get a number less than 12. We're going to use some shortcuts in this video. 51 + 23 can be done by taking the numbers modulo 12 before adding. We get the same answer because whether we delete the chunks of 12 before or after adding, it doesn't matter. More powerful is that because multiplication is repeated addition, we can use this shortcut when we multiply. The long way to do, say, 51 * 89 is to calculate it and then mod 12 it. But the quick way is to mod 12 the numbers first and then get the answer. These efficiency savings really matter because Yellow Alex's computer now has to do this without shortcuts. That is an extremely large number, around 250 digits long. But since we're taking it mod 527, we can execute the exponents one at a time. 89² is this, and then mod 527 it. To get 89³, just times it by another copy of 89 and then mod 527 it. So the numbers stay in a comfortable range, transforming one giant calculation into lots of tiny ones, which computers are very faster at. In the end, his message is transformed into the ciphertext of 387, gibberish to any third party. A bad actor might attempt to brute force messages here, trying various numbers until they get a match. But in the real RSA, these numbers are so enormous that this won't work.
Now, to decrypt, I take the ciphertext to the power of my secret key, which I'll now reveal as 223 mod 527, and I recover 89, which I transcribe as the letter Y. And again, brute-forcing my private key won't work because in reality, there are simply too many options. It feels magical, but like all magic tricks, there's more going on under the surface to explain how it's done. Now, because this video is mostly about quantum computers and the new quantum-resistance algorithms, I'm going to gloss over a few steps here, but I'll include some notes in the description if you want to get the full details. As we do this, I'll pick a specific example for you to visualize, but build up the general theory at the same time.
Now, RSA works because if we pick any number n as a modulus, then there is a magic power r. It's magic because no matter what number x we start with, xʳ ≡ 1 (mod n). For example, take 36. Its magic power is 6. And don't worry about how we calculate it, we'll get to that shortly. 7⁶ ≡ 1 (mod 36), 11⁶ ≡ 1 (mod 36), 25⁶ ≡ 1 (mod 36). All to the power of 6 are 1 mod 36. The only catch is that x and n can't share factors. Numbers sharing factors can never be 1 mod n. Now, notice that once we've found the magic power, then actually any multiple of it will be magic. Because if I do x^(r*k), this is (xʳ)ᵏ ≡ 1ᵏ ≡ 1 (mod n). For example, 7⁵⁴, a multiple of 6, will still reduce to 1 mod 36. Of course, 1 to the power of anything is just 1. So, I can delete these exponents here. RSA harnesses the power of this because if we have a power that gets me to 1, then multiplying one more time returns the original number. x^(rk+1) = x^(rk) * x¹ ≡ 1 * x ≡ x (mod n). Specifically, 7⁵⁵ will reduce to 7 mod 36. What's the big deal? Well, crucially, 55 can be split into two factors: 5 and 11. So, 7¹¹⁵ ≡ 7 (mod 36). And because 7¹¹ is unrecognizable, but it's recoverable with 5, 7¹¹ is scrambled, and then to the power of 5 unscrambles. Make 11 my public key for scrambling, 5 my private key for unscrambling, and hey presto, I have invented RSA.
There are two problems though. First is that if a bad actor discovered the magic power, they break the encryption. So if they discover six in this example, then they can keep taking multiples of 6 + 1 until they get a power that is a multiple of 11, like public key. Divide, and they have my private key. So this magic power needs to be hard to calculate. Secondly, this number x, or seven as I've used here, you'll recall is the message, and it must not share factors with the modulus, otherwise it doesn't work. Lots of numbers share factors with 36, and that limits which messages we can send. So, we need to be smart about which modulus we choose. Which numbers don't share factors with many other numbers? Well, your first instinct is probably primes. 37 doesn't share factors with anything except its multiples. And that's great, except the magic power of a prime is always one less than it. That's Fermat's Little Theorem, which we won't prove here as I fear the proof would go on for too long. The same excuse Fermat gave for not proving it. So which numbers to choose? Pause now if you want to consider. The answer is just to take the product of two primes. So a number like 35 balances both issues. There aren't that many numbers sharing factors with 35, and also, the magic power is difficult to calculate. In fact, it's the lowest common multiple of one less than each of its factors. Easy to calculate if we know the factors, but impossible to calculate without them.
"Big deal," I'll just factorize your modulus to break your silly little encryption scheme. 527 is actually 7 * 31. Pause now if you want to calculate his private key, but I know how. The so-called magic power is 240. Take multiples of that plus one until we find a multiple of 127. Then divide. Your private key is 223. And congratulations, you've broken our make-believe, really severely awful version of RSA. The real, sincerely amazing version of RSA uses numbers that are hundreds of digits long. As it turns out, factorizing large numbers is extremely difficult, intractable for classical computers. This is the advantage quantum computers have here. They can factorize very large numbers.
So, let's bring quantum computers back into play to see how Shaw's algorithm works, which breaks RSA and other systems like AES, Advanced Encryption Standard, which I won't discuss here because it committed the cardinal sin of adopting an unforgivably boring name. So recall that we set n to be the product of two primes p and q, and that RSA breaks when we find those factors. First, we're actually going to turn this into an easier problem. We're going to find a number that shares a factor with n. Another number that has p or q as a factor. Let me convince you that if we can do that, then we can factorize n easily. For example, factorizing a number like this is hard. Your only recourse is to run a very slow factoring algorithm. But if I tell you that 9,211 shares a factor with it, then the very fast Euclidean algorithm will tell you the common factor. I explored this in more detail in my DVD screensaver video, but we essentially repeatedly divide. We stop when we reach a zero remainder and return the last non-zero remainder. This tells us that 61 is a factor of this, and now we can divide to find the second factor. So the strategy is now to find a second number with a common factor, and we do it with Shaw's algorithm.
Shaw's algorithm works by choosing a specific number x, then finding a power r such that xʳ ≡ 1 (mod n). To be clear, this number r may not be the magic power of n. For example, earlier we saw that 36 has magic power 6. So x⁶ ≡ 1 (mod 36) for every x. But for some numbers, different powers work as well. Shor's will just output a power that works for our choice of x. Then turns that into a number sharing factors with n, and we can proceed from there. We'll explore this step first, which uses a trick you learned in high school. If xʳ ≡ 1 (mod n), well, remember that means that xʳ after deleting a whole bunch of n's is 1, which we can rearrange into this: xʳ - 1 = kn. We're also going to assume that r is the smallest power that has this property. And for now, we'll assume that r is even. And now to invoke that high school trick. Remember the whole difference of two squares thing. So we can rearrange this into (xʳ/² - 1)(xʳ/² + 1) ≡ 0 (mod n). This doesn't seem like a game-changer, but trust me, it's so powerful that frankly, it should be nerfed in the next number-theoretic patch. Why? Well, it's equal to kn. Now, n is built from two primes p and q. And k will be built from primes as well. Prime factorizations are unique. So, among these, the two numbers (xʳ/² - 1) and (xʳ/² + 1) must share the primes. And that means p and q must appear in one or the other, or both. Now, note that case A is actually impossible because if this were true, that means that (xʳ/² - 1) is equal to something*n. And with some rearranging, we see that this is xʳ/² ≡ 1 (mod n), and that's a contradiction because we assumed that r is the smallest power with this property. Now, case C is uninteresting to us because that will deliver a number that just is a multiple of n, and that actually doesn't help us. But case B is the jackpot because we found a number that shares a factor with n. So we can execute Euclidean algorithm on these. What if we find r, but then it isn't even? Well, then we can just choose a different base x and run through the process we're about to discuss and hope that this time we get an even r so we can continue with this process here.
So, it's about time we discuss how these magic powers are actually found. And this is where we need a quantum computer because when n is hundreds of digits long like it is in RSA, r has the potential to be hundreds of digits long as well. For a classical computer, there's no shortcut. You just have to keep taking powers over and over for longer than the age of the universe until you get one. How does a quantum computer handle this? Let's say we're trying to factorize 1,387. Let's say that we have 20 qubits. Now remember that means that they are capable of representing 2²⁰ different numbers, and we initialize the qubits so that each one is equally likely to be measured. So that means they all have a coefficient of √(1/2²⁰). And since that's the coefficient of all of them, I'll just factor that out. Now, these will be our input qubits. And like we did earlier, we'll entangle these with some output qubits. This will be the output of doing 2^input mod 1387. And now remember, somewhere during this process, there will be a magic power R with 2ᴿ ≡ 1 (mod 1387), i.e., another input R also with an output of 1. So we've got 0, 1, 2, 3, and so on, and eventually R, which gives an output of 1, and from there, the next input will give an output of 2, and then 4, and so on. In other words, this is periodic. And again, as we discussed earlier, 2R will also give an output of 1. And hopefully, you can see this will continue every R steps until at some point we reach 2²⁰. There's going to be a lot going on here. So just remember, we want R.
So at this stage, we measure the second register. There are actually only possibilities for what this will be, all equally likely. Let's say, for example, that we observe an 8 in the second register. Well, now our superposition collapses into this: |ψ⟩ = Σᵢ αᵢ |i⟩, where i = 3, 3+R, 3+2R, ... . Because without looking, we know our input qubits must be set to either 3, 3+R, 3+2R, and so on. Now, these are all equally likely with this probability because this whole sum has 2²⁰ entries, and there are R rows, which means there's 2²⁰ / R options for the inputs that give 8 as an output, and so 1 / (2²⁰ / R) = R / 2²⁰ is the probability of each one being measured. Now, what next? Well, measuring now would be useless. Let's say I do take a measurement on the first register and I get 9237. What does that tell me? I guess maybe that 3 + a bunch of R's is equal to 9237. But there are a lot of options there, and now I've lost my superposition. Now, you might think, "Okay, just restart the process from the beginning to get more information." But if I start again and measure the second register, maybe this time I observe a 661, a totally different output. A reading on the input register now won't tell me anything useful. Like, say I measure a 16373. Well, that's saying that this initial value a + a bunch of periods is this. But I don't even know what the initial value is here. For all I know, it's an enormous number. I'm not really getting enough useful information to infer the value of R.
So let's go back a couple of steps to when I had this superposition after measuring the second register and seeing 8. We want R. And I know that these states are equally spaced by R. So I need a way of measuring not one state, but measuring the distance between them. So how do I do that? Well, I am free to do operations to these qubits. I could times them all by two, or add five to them all, or I could do something really useful like applying a quantum Fourier transform. Now, this is technical. So first, I'll give you the overview, and then we'll dive into how it works. So the quantum Fourier transform swaps period for frequency. Let's draw our periodic superposition like this, all the way up to 2²⁰. All spikes are the same height because they're just as likely to be measured. The period is this distance R, and what I'm calling frequency is the number of spikes. And here there are 2²⁰ / R spikes. The quantum Fourier transform switches these, returning a new superposition with R spikes at multiples of 2π / 2²⁰. And you might question why this solves anything. We still have a periodic function. But crucially, it's the same periodic function regardless of our initial measurement on the second register. Whether we measure an 8, a 661, a 32, after the quantum Fourier transform, we are looking at this function. So after measuring this, we can get multiple readings on the same function and infer the period.
So let's execute this a few times to get a few readings on this function. Let's say that I get this on my first measurement. So this number is one of those spikes, which means it must be a multiple of 2π / 2²⁰. And dividing by 2²⁰, I see that k₁ / R is approximately 1/2. So that tells me that this measurement is almost exactly halfway down this axis. And that tells me that R must be a multiple of two, since we've observed the spike exactly halfway down. The next few measurements tell me even more. So, we've observed a spike a sixth along, and two-ninths along, and R must be a common multiple of all of these. So, we infer that R is equal to 18. We can double-check it if you'd like. If you do 2¹⁸ mod 1387, you will return 1. Now, we can do that high school trick to find 513. And since it isn't a multiple of 1387, it must share a factor. So applying Euclidean algorithm, we find a common factor of 19. Dividing gets us the other factor. Phew. So that's how we get there.
But how on earth does this quantum Fourier transform work that allows us to get these measurements? How can we take a function with one period and transform it into a function with a different period? Now, fair warning, this is a tricky bit of math, but stick with me because it involves some gorgeous visuals that build to a really intuitive picture. If you're unfamiliar with complex numbers, don't worry. It's only a couple of simple facts that we need. If you are familiar, stick around for a reminder. Anyway, for our purposes, complex numbers are points in this plane. An awesome property they have is that if you multiply two of them, the resulting number sits in a specific place. Its distance to the origin is found by multiplying the distances of the others to the origin. So here we have distance 2, distance 3. The result has distance 6. Also, if we measure this angle from the positive x-axis and add them, we get the angle of the result. Now, let's focus on the circle of radius 1. Multiplying two numbers on here will give us another number on the circle because distance 1 * distance 1 is distance 1. And if we take a number and square it, we double its angle. Cube it, we triple its angle, and so on. A root of unity is a number, say z, whose nth power is 1. And that means that its angle θ is such that nθ is 360°. So θ is 360°/n. So the third roots of unity are here, the fourth roots here, fifth roots, and so on. It's all very pretty.
With this, we can actually define the quantum Fourier transform. And to do so, let's look at a very small example: factorizing the number 21. So we're going to attempt to factorize the number 21, which I'm sure some of you can do, but we need this very small example to understand how the quantum Fourier transform works. Same setup as earlier, but this time we have four qubits, and our output register, instead of doing 2^input, will do 4^input mod 21. Why four? Honestly, because it produces a nice example. As it turns out, this is periodic with period 3, but we're not supposed to know that yet. That's what we're trying to find out. Now, we measure the second register and say we measure 4. Now we are left with this superposition, all spaced three apart. And I must stress, because this is such a simple example, we have to imagine that this period of three is totally unknown to us. And remember, the idea is to measure the distance between these values. That's the period. And the quantum Fourier transform does this by swapping a function with five spikes distance three apart to a function with three spikes distance five apart. So how does this work? Well, first, because we're working with four qubits, we'll work with z, a 16th root of unity. The quantum Fourier transform gives us a new superposition. Let me first state what it is and then we'll explore what it means and why it works. So we start with the old superposition, which in general can be written like this: |ψ⟩ = Σᵢ αᵢ |i⟩, where each αᵢ² is the probability of measuring i. Now, the quantum Fourier transform gives us a new superposition, which I'll write like this: |φ⟩ = Σ<0xE2><0x82><0x96> β<0xE2><0x82><0x96> |k⟩, where β<0xE2><0x82><0x96>² is now the new probability of measuring the number k. And here, a given β<0xE2><0x82><0x96> is defined to be the sum of all of the αᵢ, but where each is scaled by z^(i*k). And for good measure, we times the whole thing by 1/√2⁴. Now, take a deep breath, 'cause I know this looks horrendous, but it's simpler than it looks because remember, most of these αᵢ are zero. In our example, only those attached to 1, 4, 7, 10, and 13 are non-zero, and they are all the same: √(1/5). So I can factor out that √5, write it as √(1/80), and I'm left with just this sum here.
And to give us a sense of the purpose of this, let's take a peek at what these β<0xE2><0x82><0x96> actually look like. If we calculate all the β<0xE2><0x82><0x96> in this case, find their magnitudes and square them, we obtain the probability of measuring each value k. Put them on a graph, and we see that we are incredibly likely to roll a 0, 5, or 11. And why these numbers? Well, because we've turned our period 3 function into a period 5 function. But something feels a bit off about this. Why 0, 5, and 11 when apparently this should be period 5? That's because I lied a little bit earlier. This original function didn't have five spikes distance three apart. It actually had 16/3 or 5 and 1/3 spikes. That's because if I measure a 4, I have 5 spikes. But if I measure a 1, I actually have 6 spikes. So the average of those will be 16/3. It'll make more sense in a moment. And remember, we obtain this graph regardless of what we measure in the second register. So if we do all of this, say measuring a 16 in the second register, our resulting superposition is still transformed into this, and likewise if we measure a 1 in the second register. So we can get multiple readings on the same graph with ease, and we will prove that it doesn't matter which one we observe right now as we dissect this specific case to understand exactly why it works. And to do that, we essentially need to understand the size of β<0xE2><0x82><0x96> for various values of k. We expect it to be large when k is a multiple of 16/3 because that's where we see those big spikes. And since we're claiming it doesn't matter what we measure in the second register, let's write what the β<0xE2><0x82><0x96> look like for each possible measurement. So these are the β<0xE2><0x82><0x96> if we measure a 1, 4, or 16 in the second register, and we'll take their magnitude to see what they look like. Well, lucky for us, the magnitude of a product is the product of the magnitudes. And on these lower two, we'll extract a zᵏ. And that will reduce all of these exponents by 1k. Actually, it's a z²ᵏ that I wanted to take out for this bottom one. But it doesn't matter 'cause the point is the magnitude of z to the something is 1 because it's still a distance 1 away from the origin. So we can basically just cross that out and ignore it.
So now we notice we're basically looking at the same sum in each case. And that's why it doesn't matter what we measure in the second register. Don't worry about the fact that there's an extra term in this top one. We'll see in a moment that won't matter. So I'm actually going to get rid of these bottom two now because to understand when β<0xE2><0x82><0x96> is large, we just need to analyze this sum. So let's now look in the complex plane at what these powers of z look like. Recall that z is a 16th of the way around the circle. z³ is at 3/16. z⁶ is at 6/16, and so on. So this is what the k=1 case looks like. What is the magnitude of their sum? Well, complex numbers add like vectors. So given that they are roughly evenly spread around the circle, there will be a lot of cancellation, meaning their sum will be close to the origin, i.e., the magnitude of their sum is low. Now let's look at the k=2 case. To get our hands on this, we just take every z and double its angle. Again, we see that they are spread out quite a lot around the circle. So their sum is close to the origin. It has low magnitude. That's the same story for the k=3 and k=4 case. But watch what happens next. Taking one more power when k=5, we see them start to bunch up on one side of the circle, meaning that when we add them, the sum will run away quite far. The magnitude suddenly spikes at 5, and at 6, it still isn't bad either. Notice that the period of this is actually 5.33. So that's why we get the spike at 5, as these k's are integers. The next spike will be at 10.66, which is closest to 11. And as we run the k's forward, we see that at k=11, we get another big spike. So why is it that it runs away at multiples of 5.33? Well, I'm sure you realize now that the best possible outcome is if all these points bunch together and are actually in the same place. So they all run away from the origin in the same direction. Any deviation and their collective sprint will be inefficient. But since the first one is locked in place at 1, the best option is when they are all sitting at 1. And when k is 16/3, that inflates the exponent to a multiple of 16. So it's clear now when k is 16/3 or multiples thereof, these are all multiples of 16. Therefore, they're all 1, and therefore the sum has magnitude 5, as large as it can possibly be.
Now, this diagram is actually really satisfying when we let k take any real value rather than just an integer. So this dot represents the sum of the z powers, and we can see that as k grows, the sum gets stuck around the origin with low magnitude, and then suddenly they all align and the sum flies off. We can plot the curve that their sum follows, and we see that it spends a lot of time wandering around the origin, only flying off here. It's so cool. I spent hours watching these dots go around. To make things even clearer, we can graph the magnitude of the sum against k. So this graph is now tracking this distance, and we can see this characteristic Fourier interference pattern. This curve, by the way, is given by this polar function, and it was quite tricky to derive. Feel free to have a go at it yourself. Now, because we actually only have integer inputs, there is a bit of jank when we go back to the discrete setting. But for large enough numbers of qubits, we have enough resolution to make the correct inferences. That's why when deciding how many qubits to use, we usually overshoot by quite a lot. Recall that n was 21. A good benchmark is to use enough qubits to represent more than n² states. So 21² is 441. So we would use 9 qubits. This has the effect of confining the noise around the peaks. So now that if I roll 10 observations from this distribution, here are the results. Because these represent fractions of 512, we can see that they are really close to 1/3 and 2/3, indicating a period of 3, which, if you recall, was the whole point of this, even though we already knew and had to pretend that we didn't know it, but that's how it's done. For completeness, recall that we need this period to be even to execute that difference of two squares trick and complete the factorization. So, in practice, we would need to repeat this whole process with a different base, say 2. This time, to check your understanding, I'll just tell you that these are our observations after the quantum Fourier transform. Pause now to answer the following questions, because remember, in practice, this is the only information we get. Dividing by 512, we see a period of 6. Therefore, the distribution will have six peaks. And after the whole difference of two squares thing, we can get a common factor with 21 and therefore factorize it in the most complicated way possible. But now you know how the process works and how it can be applied to much larger numbers. And that's everything you need to understand Shaw's algorithm in its entirety. I really didn't want to skip the quantum Fourier transform because not only is it very pretty, it is also the reason that quantum computers are able to factorize large integers, allowing us to take multiple readings on the same function, thereby inferring the period.
So now you know exactly how quantum computers can crack RSA and why current encryption schemes are vulnerable. Equally as important, you now know that quantum computers aren't a magical black box that can solve any problem. No, the only reason they can crack RSA is because of this periodicity exploitable by the quantum Fourier transform. Let me close out this section with one remark. Quantum computers are real, right? So why hasn't RSA been broken already? Well, current quantum computers don't have enough qubits. As we saw, a lot of qubits are required, but even that is assuming that they are all perfect. For physics reasons, qubits are actually imperfect and have a chance to decohere. That means that we need way more than the theoretical minimum to crack RSA. Expert estimations vary. Some say 4,000 qubits, for others it's 10,000, but at time of recording, the most powerful gate-based quantum processors have around a thousand qubits. Still, quantum processes are getting more powerful all the time. So that's why it's really important that we switch now to quantum-resistance schemes. Thanks for watching. Next week, we'll explore the first of three quantum-resistance schemes which have been standardized by NIST. If you don't want to wait, you can check out the full video which explores why this quantum-resistance scheme survived the epic competition and was selected to be standardized. This has been another proof under the roof. Until next time.