It’s the End of RSA as We Know It (And I Feel Fine): An Introduction to Post-Quantum Cryptography

Cheers, again. Um My name's Lucy. I'm uh very happy to be here to speak to you today. Um Thanks for coming out at this time cuz if you're anything like me, you're a little bit sort of hungover and disheveled. Um I would rather sit in the shade. Um So, yes, this talk is called It's the end of RSA, the definite end of RSA um as we know it, and I feel fine. Um And that's because really it's sort of like a headline busting issue. Uh but it's got solutions, and there's people working on those solutions as we as we sort of work on it. Um So, yes, I'm Lucy. I'm from Belfast in Northern Ireland, um which is what this noise is. Um I studied uh software engineering at Queen's University, um and I'm going back in September to study applied cybersecurity part-time along with working on Post-Quantum um with my bachelor's degree and 5 years of experience in PwC as a uh tech consultant. Um I started at a company called Arqit uh where we work on enterprise-grade post-quantum security solutions. And that basically means that we work on every part of the post-quantum migration journey from like identifying and categorizing a company's cryptographic assets, so that's all the encryption they use, to then protecting their data against post-quantum, and then complying with future and present quantum legislation. Um While I do work in quantum as my day job, this talk is by no means a representative a representation of the company Arqit. Um all of the thoughts, opinions, and misinformation were completely out of my own head. Um, so you can't hold it against them. >> [laughter] >> Um, but every time I sort of explain post-quantum to someone, I have to start with the fact of like this is actually going to happen. So, the three facts I always start with is quantum computers are being developed right now, and they'll be available soon to a very limited group of people, so mostly governments and researchers first, before then you can go and buy a quantum iPhone um, in like 10 or 15 years. Uh, the second fact is quantum computers, by virtue of their quantumness, are much, much, much more powerful than classical computers. And then the third fact is because of this additional power, uh, quantum computers threaten the strength of our current encryption methods that we've used that are used thousands of times per second every time you like log in to a website. Um, so these are helpful to understand what the problem is. Like TLDR, we need to migrate all of our encryption methods. I always think of it as sort of like a Y2K scale of problem, except not everyone has 10 computers, and we don't know at what point in the '90s we're in because we don't know when a quantum computer is going to be developed. Um, but this is helpful to understand the what, but it's we there is more to dig into it to understand the like why and the how. Um, it's very easy to say that quantum computers are much more powerful, but why are they much more powerful? Um, so to sort of put some why and how behind it, we'll talk about the difference between classical and quantum computers, the physics that makes quantum computers quantum. Um, we'll talk about our current encryption standards and why they use prime numbers and why that's not going to be good enough anymore. Um and then we'll take a day or two to discuss one type of attack called harvest now decrypt later. And then I'll give you um some timelines so you know when to start panicking. Um It's it's pretty soon. Uh so the the foundation of our understanding will come from the difference between a classical and a quantum computer. Every computer you've ever used, although I probably shouldn't say this at EMF. At previous conferences this worked. At every computer a normal person has ever used is a classical computer. And it so it sends and stores data as a one or a zero. And you can think of that as a light bulb is off or on depending on whether current isn't flowing or is flowing. Um These are called bits because they're binary units. And the the the that's what's used in classical computing. So you've all heard of bit. Um Similarly to two bits are classical particles which can exist in a state of spin down or spin up. So you can think of this as your zero, your one. Um But in quantum technologies this particle can be in both a state of spin down and spin up at the same time. And it's hard to imagine something because we live in a real not quantum world. We're like too big to be quantum. It's hard for us to think of something traveling in two directions at the same time. Um So it's helpful to think of it as like a cloud of probabilities of potential states between zero and one. And it just exists as that cloud until something happens to it. Um and this is the difference between classical bits and quantum qubits. It's a good name. Um The other interesting thing about the The between these is because bits can only have one state at a time, their combined power of the whole computer increases linearly with the number of bits in it. Uh but for a quantum computer, because one qubit can have two states at once, there's a quadratic relationship. So, one qubit can have two states, two qubits can have four states, three qubits can have eight states, and then it follows all the square numbers. And that's fundamentally what makes them more powerful. They're not just like magic. It's like they can think quadratically more at once. Um So, that ability to exist in two states at once is our first quantum mechanic. Um and it's called superposition. And it can be uh represented by this formula, where psi is the current state of the qubit, zero and one are the two possibilities, and then A and B are the probability amplitudes. And I think I've confused other people with this before, but in other quantum things, they can have more than two possible resolutions. It's just in computers, because we already write everything for bits that have two possible solutions, um we use one and zero. But they can be 0 1 2 3 4. Um the next quantum mechanic you'll need to know is entanglement, which is the phenomenon the phenomena that two or more quantum particles of the same origin, so they have to be produced at the same time, can be linked so that the measurement of the state of one instantly impacts the state of the other one, no matter the distance. So, I went to a talk about this a few uh probably last year, uh where he just talked about entanglement the whole time, and I didn't understand it that much better after the talk, and it was like an hour long just on entanglement. Um But basically, the one thing I took away from that talk was two linked quantum particles can exist at opposite ends of the universe. But when you measure or interact with one, it will uh resolve into its like state, and then the other one will also resolve into its state. Um entanglement is a helpful quantum mechanic in our scenario because it lets the qubits work together, and they sort of like form these like waves that can then uh sort like organize and churn through a lot more data all linked, cuz bits don't really interact with each other. They sort of just like tally over. Um entanglement hasn't always been very well understood. In 1935, three scientists expressed their issues with entanglement. Um Einstein, who you've heard of, uh Podolsky, and Rosen, who you haven't heard of, um wrote their infamous EPR paper, where they sort of went "This theory doesn't work with like special relativity, and that's an issue because if this particle's on one side of the universe and this was on the other side, and they communicate to each other instantly, that's faster than the speed of light. So, that just they they can't be communicating, but we know that they do. So, we can't like call this solved until we figure out what they're actually doing." Um hold on. So, the EPR paper in 1935 said that this was impossible, but it was I think, I don't know, the '70s or the '90s. It was all before me. I can't remember. Um it but it was a Northern Irish physicist who worked at CERN, and he was called John Stewart Bell, but there's no relation. Um he came up with Bell's theorem, and basically solved this paradox, and said, "Yes, we don't really know how entanglement works because it doesn't abide by like local physics that we can understand. Um but also it doesn't break special relativity because you can't consider them communicating with each other. It's sort of like you do something to particle A and particle B randomly with no input, it just resolves. It doesn't know that it's going to do that. It doesn't receive any information. Um but you need to just like appreciate that that can happen because that's how it like weaves together. Uh the last thing to know about qubits but it's not really a quantum mechanic is called decoherence and it's basically if a quantum particle interacts too much with the real world, um it loses its quantumness and that's bad because we want to keep the quantumness much like the smoke. We want to keep it like inside. Um It's especially bad for quantum computers because it's then very hard to like swap out qubits and stuff. Um but there are ways to sort of prevent it so you can do it in a vacuum where there's no other particles to like interfere or you can do it super cold so then they're like moving around less and like bumping into each other less. So, I like to call this an engineer's understanding of quantum mechanics. It's not thorough but it's enough to know where we're going next. Um because the next place that we're going is back to classical computers uh because now that we know why quantum computers are much more powerful, we need to know why they are going to mess up our encryption. So, we need to know how our encryption works. Um and if you've ever done anything in cybersecurity, you'll know that we have the same cast of characters all the time. So, this is Alice and Bob. Um for the purposes of AMF, they're aliens because it's space themed. Um Alice has a public key and a private key. The The private key is They're both just long strings of numbers, but the private key can only exist on Alice's computer um until she pastes it into ChatGPT and then has to regenerate it. Um but the public key is public and it can go across the public internet to Bob. Um Bob wants to speak to Alice, so Bob can write his message in human-readable plain text um and then apply a cryptographic algorithm with the public key as a variable to turn this into ciphertext. Uh the ciphertext can then safely travel across back across the public internet because it's it's encrypted. Now, this is Whenever someone says it's encrypted, that's what they mean. It's in ciphertext um until it reaches Alice's personal machine in her personal network, at which point her machine will apply another cryptographic algorithm with the private key to turn it back into human-readable plain text. Um and you can think of these keys as just prime numbers. So the dark pink key, the public key, is the product of the two prime numbers in the private key. So here I've used three and five. Um and because these keys are different numbers, it's it's it's called public key encryption, but it's also called asymmetric cryptography because then you can also do symmetric cryptography where the keys are the same, but then you have the issue of exchanging the key over the public internet. So this this is used in like um TLS and it's um the primary version that's used all the time is called RSA, um and it has until now been very strong. >> [laughter] >> Um so we know what Why quantum computers so fast, we know how our current encryption works, but we need to know why a quantum computer is going to interfere with it. So, the reason that prime numbers are used in cryptography is because multiplying them forward is very easy. But, prime factorizing the product is very hard. So, 3 * 5 is >> [laughter] >> Uh the two prime factors of 713 are >> [laughter] >> So, this is very difficult because you can't divide it by two, you can't divide it by three, you can't divide it by five. Uh you have to uh a number like this only has four prime factors and it's going to be one, 713, and the two numbers that I want, but they're both prime numbers, so therefore I can't break them down anymore. Um so, this is very easy to do forward Oh, sorry. Yeah, 23 and 31, if you're interested. Uh this is very easy to do forwards and hard to do backwards. Um and obviously a computer could probably eventually get 23 and 31 out of 713. Uh but in actual encryption, these two pink numbers are many, many, many more digits long, up to 300 digits because it's 248-bit RSA. So, each of those numbers then combines to turn into the public key um with a little bit more math. So, the reason that quantum computers threaten this type of encryption is because they're much more powerful and in again, the '70s or the '90s, it definitely wasn't the '80s. Um but, Shor's algorithm was sort of proven that a quantum computer could break this kind of encryption um because of its quantum mechanics, because of its unique ability to sort of have the qubits work together. Um and like find it based on just like That's not in the the slide deck. >> [laughter] >> Um one attack that Oh, sorry. It might seem like quantum computers are a long way away, and it is always a bit of a joke that quantum computers will happen in the next 10 years, and that has been the same for the past 50 years. Um But, a way that your current data is threatened is through a process called harvest now, decrypt later, where if you have your sort of very sensitive document now, um which you have encrypted, someone could intercept that encrypted document, wait until uh commercially viable, cryptographically relevant quantum computer exists that could break this encryption, and then just decrypt it later on and they'll That scares a lot of people in sort of big businesses that are like, "They're just going to be able to read it all?" And it's like, "Yeah, but if you ever looked at encrypted data, it doesn't make any sense. So, you have to know what you're going after. So, I always say it's probably a big deal if you work in like government or health care stuff. Um but like, no one's intercepting your encrypted like signal messages and like holding on to them for 10 years for two reasons, in my opinion. What The first reason is they have to guarantee that the data is still going to be relevant by the time they get their quantum computer. And one example of this is bank cards. The bank card expires. So, if you've put it in a website and it's expired by the time they've got it, it's not of zero value, but it's of much less value than if they just came into your house and took your bank card, and then they would have the actual live data. So, it has to still be relevant by the time they have the quantum computer in order to make it worthwhile to store. The other thing is storing it isn't free. Um So, they'd have to harvest loads and loads of data that they don't really know what it is. They know who it's come from, and they know how it's encrypted, but they don't really know what it is. Then they have to pay to store it for an unknown amount of time, and then they have to hope that that's going the the money that they're going to get from like selling that data in 10 years is going to offset Oh, sugar. It's going to offset the cost it took to like store it for all that time. So, it's not really a big issue for individuals, but it is kind of a big issue for companies. Um and the company where I work are sort of getting more on top of this because they're like Um it becomes a bigger issue if, say, your company doesn't know anything about quantum yet and hasn't started a migration or hasn't even started thinking about a migration, and so you're getting further this way on the timeline, and the quantum Q-day, so it's like D-day but Q-day, is getting closer this way. The smaller that gap is, the let the more cost-effective harvest now decrypt later becomes, and the less sort of risky it becomes because you're not fronting as much money to store it before it's then going to be decrypted. So, it does become a bigger issue the longer you like leave it. Um But, like individually, it's not a big deal cuz like no one cares what you're texting. Um one way that big companies can sort of protect against harvest now decrypt later is through a hybrid hybrid encryption. So, say you have your sensitive document, you can encrypt that as it encrypt it in travel cuz there's different types of encryption uh using a classical key exchange method like we saw. Um And then you can simultaneously encrypt it with a post-quantum key exchange method. So, the classical one will be something like RSA, which is going to go away, and the post-quantum one will be something like ML-KEM, which is developed and approved by the National Institute of Standards or Science and Technology um in the US. So, they've developed ML-KEM, but it hasn't So, RSA is tested RSA is proven to work thousands of times per second, and everyone's on their phone all the time. So, you have the best of both worlds in that you know RSA works very well right now, and then you're hedging your bets by using the post-quantum key exchange method. People then ask, "Why don't we just use the post-quantum key exchange method?" We haven't tested it enough, not even nearly to the start to the level that RSA has been tested. So, there's no way to know if it's like completely bulletproof yet. Um so, yeah, this gets the best of both worlds um to sort of protect for now and later. Um oh, one point on that. It is important to think of this in sort of the timeline of like you go from your classical to your hybrid to then your post-quantum um because it builds into that like my create migration timeline. So, it's very helpful to sort of trial the post-quantum a little bit, figure out if it works, and then you can like apply different ones depending on sort of what standards come out. Um so, hybrid is like a like a bit of a stepping stone in the migration journey. Um and speaking of the migration timeline the UK's National Cyber Security Centre has set out this timeline March 2025, so it's a little bit out of date already. Um but basically, they want a full cryptographic inventory and planning done by 2028. And then they want or they're suggesting all companies abide by most most sensitive systems fully migrated to post-quantum encryption by 2031. And then to have the whole thing wrapped up by 2035. Um the most sensitive ones will be stuff like payroll or HR first and then the least sensitive ones will be like the IoT toaster in the office that no one uses. Like it can go last. Um the problem with this timeline is since I wrote this conference talk in March of this year, Google, Cloudflare, and Microsoft have all set their quantum deadline to 2029 Oh, it's 2029. Which is like way less than 2035. So, you've only really got like I mean, we're most We're kind of halfway through 2026. You've got like 3 years to do all of these steps that we're meant to take 10 years. Um the other timeline is for the financial services industry developed by a specific cyber group for financial services in the UK. Um and you can see that like it's hitting similar sort of milestones and they sort of got the same idea of like there needs to be analysis and then development and then application. Um but yeah, the deadline keeps changing because the advent of generative AI actually means that like a lot of this analysis towards a quantum computer can be done much quicker. Um but the the sort of the thing that's holding it back is like research time and funding to be able to like um put enough logical qubits together. And also, I kind of think of it as like why would a company want to migrate to post-quantum? It doesn't make them any money. Like they're just going to do it terribly and too late because they're start to lose money, but like they're not going to do it. A lot of companies are applying gen AI because they can save money by firing people. Um but they There's nothing for them to gain here. There's only stuff for them to lose really. Um so, I think like that's going to be a bit of an issue that like companies are going to lag behind even this timeline until some stuff just won't ever be migrated. The same way some stuff isn't even encrypted at all. Some stuff will be not encrypted, encrypted classically, and encrypted post-quantum. Um But yes, to recap, we know that classical computers use bits, quantum computers use qubits, which benefit from the quantum mechanics of superposition and entanglement. We know that asymmetric encryption or public key cryptography relies on very, very large prime numbers and the prime factorization of the product of those very large prime numbers. Um we know that harvest now decrypt later can be fended off, protected against by hybrid encryption. And we know the three key dates, which are subject to change, that uh the NCSC have put out, which are all discovery and inventory and planning done by 2028. The most important systems, so your your like your code base or your payroll or like your national insurance number has to be done by 2031, and then everything else has to be done by 2035. Um if you want to take a photo of a slide, it's probably this slide, cuz you'll forget all of this. Um But other than that, that's been an explainer of fundamentals of post-quantum cryptography, and my name's Lizzie Bell. >> [applause]