Why Prime Numbers Are the Secret to Cryptography

Added: 2026-05-12

[00:00:00]I'm a mathematician, and I'm currently surrounded by some of the leading experts in cybersecurity. And I'm here today to ask them one very important question. Do you know what a prime number is? Yes. Yes. Yes. I absolutely do know what a prime number is. The most basic definition of a prime number is a number that is [music] divisible by itself and one. Now, there is some debate about whether one is included here, but I'll save that for another video. Prime numbers sit underneath some of the systems that help keep digital life secure. But don't just take it from me. Here's what the director of GCHQ [music] had to say. Prime numbers are a really crucial ingredient of being able to have strong crypt. In simple terms, cryptography is a way to protect information [music] by turning it into a secret code. Only people with the right key can unlock the code and [music] read the original message. Now, it turns out that prime numbers pose a very strange asymmetry that is key, pun intended, to keeping our information safe online.

[00:00:56]>> [music] >> And to show this, we need only ask one very simple question. What is 2 multiplied by 7? 2 multiplied by 7 is 14. 14. 14. Yes, that was a very simple times table question. But what if I gave you the final answer? Let's start with the number 91. You'd probably struggle to work backwards from there, wouldn't you? It would at least be harder than simply calculating 2 [music] multiplied by 7. I I would struggle to do that.

[00:01:22]Yes, I would. Yes. Yes. Yeah, it becomes a bit more difficult.

[00:01:27]I wouldn't even try. Well, it turns out that we can exploit that asymmetry, easy in one direction, hard in reverse, to explain one of the most important algorithms in cybersecurity. [music] But before we dive into the mathematics, I wanted to highlight a really beautiful success story from my time at CyberUK.

[00:01:45]Yes, mathematics is a crucial piece to cybersecurity, and it is a very exciting time to be in the field. I think that the mathematical geniuses of the future, this is the time to get them involved within cyber. But cybersecurity itself is not [music] just mathematics. It's not just coding. It's not just maths and tech, although those are obviously important components. But there are a range of other professional experiences that enable people to be very successful in this field. Some of the best auditors in the world are going to be lawyers.

[00:02:16]You know, it's not just a technical field. And the fact that you can do national good through a cybersecurity career. Be a technologist, you're a psychologist, you're an accountant, a mathematician. And this message really came through at the Women in Cyber Breakfast. Cybersecurity is so varied.

[00:02:32]It's technical, it's non-technical.

[00:02:35]Anyone can get involved in cyber. We have criminologists who make fantastic risk managers. We have mathematicians who make fantastic cryptographers. I was also able to speak to people who weren't in technical roles. I actually went to university and studied [music] geography.

[00:02:52]And it was the classic thing of coming out of university and not really knowing what I wanted to do. And honestly, tech never seemed like something that was available to me. I feel like I didn't have a science background. Now, what Aman had just highlighted [music] was a huge misconception, which she later realized herself. But actually, I've been so pleasantly surprised about how much information you can pick up, the people that you can learn from, the relationships that you can develop, and actually how much of a difference you can make to your customers and also the general public. I also spoke to the Chief Information Security Officer at HSBC, [music] who, yes, I did happen to ask some prime number questions to, but she had a really beautiful sentiment [music] to say about the role women are playing in cyber, too.

[00:03:34]Looking back at my career and thinking about 25 years ago, when I started out, we would never been able to pull rooms with just women in cyber, let alone women in technology. It's just been an incredible It It gave me goosebumps, if I put it that way. While we're moving on to the mathematics section [music] now, I wanted to highlight these thoughts.

[00:03:53]The cyber mission is so important, and we need people from a variety of different backgrounds. So, if you're interested in a career in cybersecurity, [music] then check out the link that I put in the description or pinned comment. And now, for the mathematical minds watching, let's look at one of the most famous ideas in public key cryptography.

[00:04:11]Okay, here's the setup. Suppose Bob wants to send Alice a message online, but the route between them is not private. Other people might be able to observe the data as it moves across the network. So, Alice needs something slightly strange, a method that lets anyone lock a message for her, but only she can unlock it.

[00:04:29]>> [music] >> That is public key cryptography, and this relies on two very simple mathematics. [music] Prime numbers and modular arithmetic.

[00:04:38]We've already touched upon prime numbers, and we've seen that P is prime if the only [music] integer factors are P and 1. And interestingly, there are infinitely [music] many primes. We can actually find prime numbers quite easily. We have some really fantastic methods of doing [music] so. But like you might have already guessed, we don't really have a great way of breaking numbers in terms of their prime factors.

[00:05:01]And this part is really crucial. Modular arithmetic works by picking a number and subtracting from [music] it multiples of some other number. If you look at a clock, this is actually a really great example. If someone tells us that the time is 15:00, [music] we simply subtract 12 from this to find the number three. So, the time is 3:00 p.m. So, we'd say in mathematics that 15 equals [music] 3 mod 12. 15 here is the number we started with, 12 is the number we're subtracting off, and three is the number we get when we do this [music] operation. We can also do it for a larger number. Let's say 134.

[00:05:36]Well, 134 subtract [music] 12 is 122.

[00:05:40]And if we keep subtracting 12, we finally get [music] to the answer of two. It's important to note that we go until we can't subtract any [music] more. That is, we don't want a negative number. So, we'd say that 134 equals [music] 2 mod 12. Amazing. Okay, so back to Alice and Bob. Alice has to start by creating her keys. To do [music] so, she chooses two prime numbers. We'll call them P and Q. Now, in real life, these primes are huge, but for illustrative purposes, we're going to choose P equals 2 and Q equals 7, like we had at the start. What Alice now needs to do is multiply these two numbers together to get a new number called N. So, N equals [music] P multiplied by Q. For our primes, this would give us 2 multiplied by 7, which we've already seen, and hopefully you already know, is the number N equals 14. Now, this number N is crucial. [music] It's going to be public. This is part of the information that Alice is going to give to the world, [music] so everybody knows that N equals 14. But that's okay, and we'll see why in just a moment. The next step in the algorithm is to compute this quantity here, which is P minus 1 multiplied by Q minus [music] 1. And this is what is known as the Euler totient function, which is actually what was displayed in the original paper for this algorithm.

[00:06:57]Although, there have been some slight changes to this, [music] but I'll save that for another video. Now, for our primes, this value would give us 2 minus 1, all multiplied by 7 minus 1, which [music] is just 1 times 6, which equals 6. The next step is to try and find a number that is co-prime with this new number that we've just derived, so with the number six.

[00:07:15]>> [music] >> What this means is that it shares no common factors with this number. So, let's choose E equals 5, because we know that six and five don't share any common factors.

[00:07:24]>> [music] >> So, if we want to send someone an encrypted message, all I need to do is tell them my N, which is 14, [music] and my E, which is five. Speaking of encrypted messages, we should probably create one. And this is [music] what Bob is going to send to Alice. This message is going to be denoted by the number M.

[00:07:39]So, this is what we don't want people to find. [music] It turns out that we can encode this message with the following beautiful mathematics.

[00:07:46]All we do is we [music] take C, where C is our encoded message. This equals M to the power E mod N. So, basically, if someone wants to send me an encrypted [music] message, I just tell them the numbers N and E.

[00:07:59]They know their M, that's their [music] message, and with all of this information, we can calculate the value C. So, in our case, [music] we can tell our friend Bob that our N equals 14 and E equals 5, and he decides he's going to send the hidden message M equals [music] 4 for some specific reason.

[00:08:16]Now, it's important here that M is less than N. And when you finish this video, why don't you try a bigger number here and see why it breaks. [music] It's some fun maths.

[00:08:25]Now, if we substitute in, we'd have C equals 4 to the power 5 mod 14, and this gives us a value of two. [music] So, our C value here is two. So, Bob sends this to Alice and says, "My encoded message is the [music] number two."

[00:08:39]But if we're Alice, what do we do with this now? What does the number two mean?

[00:08:43]We've been given the number two, but that wasn't Bob's original [music] message, was it? Bob's original message was M equals 4. So, what do we do now?

[00:08:51]Well, there is another [music] step in the algorithm, as is often the case with algorithms, and it's a very beautiful mathematical property, where D multiplied by E equals 1 mod P minus 1, all multiplied [music] by Q minus 1, as you can see on the screen here. Now, this might look a bit complicated, [music] but let's explain it all.

[00:09:10]If I'm Alice, then I know the value E. I also know P and Q. So, I need to find a number D, so that if I multiply it with the number E, and then keep taking off multiples of P minus [music] 1 Q minus 1, it will give me the remainder one.

[00:09:24]Let's try with our examples.

[00:09:25]>> [music] >> Alice knows that P minus 1 Q minus 1 is 6. She also knows that E equals 5, so this [music] expression would become 5 multiplied by D equals 1 mod 6. And if we solve this, we get the number five.

[00:09:39]>> [music] >> So, our D here equals 5. Okay, this might all seem very complicated, but we're about to reveal >> [music] >> why this is so beautiful.

[00:09:47]So, Bob sent us the number two. We have our P and Q and our N. But how do we find the hidden message? Well, it [music] is this beautiful piece of mathematics here, where we can say that M, the [music] message, equals C to the power D mod N. So, if we take the [music] encrypted message, which was C equals 2 in our case, and then use the D that we've just calculated, and we also of [music] course know N, we can plug them into this. So, the hidden message is going to be 2 to the power 5 mod 14, [music] which equals 4.

[00:10:19]And what's that number? That is the hidden number that Bob sent [music] to Alice. How incredible is that? That is our hidden number. And so, Bob has successfully sent this hidden message over the network to [music] Alice, and Alice has successfully retrieved it.

[00:10:34]Now, I realize that I've said Alice and I interchangeably in this, >> [music] >> but hopefully the message is clear. What you've just seen there is the RSA algorithm in action.

[00:10:43]>> [music] >> It's named after Ron Rivest, Adi Shamir, and Leonard Adleman.

[00:10:48]That was a lot of mathematics, [music] but to see this in the real world, you can actually inspect the certificate of a website. You can see the information about the public key and the algorithm used. Here, I went to Reddit, and you can see that it clearly states RSA right there. So, that's the RSA algorithm and an introduction to how mathematics is used in cybersecurity.

[00:11:07]>> [music] >> How beautiful was that? So, the next time someone asks, "When am I ever going to use this math? When am I ever going to use prime numbers?" [music] There's one clear answer. Every time mathematics helps keep information safe online. And if you want to be part of that story, too, then [music] make sure to check out the resources that I put in the description and the pin comment. I had the pleasure of attending Cyber UK with the National Cyber Security Centre, and I'm so grateful that I can make this video for you. So, if you're interested in a career in cybersecurity, or more generally in cyber itself, >> [music] >> then make sure to check out those resources. I'll also be releasing a video on why quantum computers [music] could change this story entirely, so make sure to subscribe. Thank you so much for watching, and a huge shout out to my members on here >> [music] >> who help make these videos possible.

[00:11:52]I'll see you all in the next one.