Georgie Bumpus

You might have heard of RSA. It’s one of the first and most important examples of what’s known as a trapdoor function. This is a function which is easy to compute but relatively hard to reverse, and it’s exactly what’s needed for public key encryption, which we’ll talk about in the next paragraph. RSA is pretty old for an algorithm (1977), but it’s still widely used whenever computers need to talk to each other. Email clients often use it, as well as VPNs, chat servers, digital signatures, browsers and so on. The reason it’s still used so widely, even if it is the same age as Kanye West, is that no one has found a good enough way to break it yet.

The key (pun intended) to RSA is the concept of asymmetric encryption. This is different in the sense that the person encrypting and the person decrypting use different tools (or keys) to do what they need to do. In a simple substitution cipher, both the encryptor and the decryptor use the same key: a table like the one in fig 1 from the last article. Imagine Bob wants to send a message to Alice but doesn’t want Eve to be able to read it. He could use one of the ways we discussed in the first article, but this would require him exchanging identical keys with her, which is as difficult to do securely as it is to send the message in the first place – unless he can meet up with her personally (in which case he might as well just tell her the message). A better way would be for Bob to produce some sort of lock and make the design publicly available, but make sure only he knows how to unlock it. We call the lock the public key and the key he uses to unlock it the private key. Now let’s look at a way to implement this in an actual algorithm.

Time to unpack this a bit – well, a lot. The key idea is that Alice takes two big prime numbers and multiplies them together, and because only she knows how to factorise it, only she can solve the equation M ≡ C^d mod n. It’s not at all immediately obvious why this is, so let’s have a look at the number theory behind it. We’ll need a definition and not one but two really cool theorems, so if you haven’t read the bit about modular arithmetic in the first article, you should definitely go and do that now.

Remember when we talked about the number of multiplicative ciphers and how multiplying by a number that shares a factor with 26 will give us a pretty useless cipher? We’re going to make that a bit more precise by introducing the idea of coprimality. It’s related to being prime: we can think of a prime number p as one whose only common factor with every other number not of the form kp, for k an integer, is 1. However, we say two numbers p and q are coprime if the only factor they share is 1. This is also known as being relatively prime. The function φ(n) is defined as being the number of numbers less than n which are coprime to n, that is, φ(n):= {k is an integer such that hcf{k, n} = 1}. This might seem like a pretty annoying function to calculate values for, as you’d have to go through each number and check if it’s coprime, but actually there’s a very handy formula to calculate it that we’re going to get to shortly.

Let’s look at some examples before we start putting this function into use. 

• φ(9): the numbers under 9 are 1-8, and the only factor of 9 besides 1 is 3. Therefore, the numbers which are coprime to 9 and less than it, will be every number besides multiples of 3, i.e. 3 and 6. Hence φ(9)=8-2=6
• φ(12): here we need to get rid of multiples of 2, 3, 4 and 6 since those are the factors of 12 which aren’t 1. In practice, every multiple of 4 and 6 is also a multiple of 2 and 3, so we only need to worry about 2 and 3. The multiples of these below 12 are 2,3,4,6,8,9,10 – so 7 numbers. Therefore, φ(12)=11-7=4
• We can say something a bit more general for prime numbers p – see if you can think of an expression for φ(p). If you’re stuck, try thinking about φ(5), φ(7) and φ(11) and work out the pattern [*for the answer, look in the footnote at the end of the article].

Now it’s time to get into the theorems…

Our first theorem is an extension of Fermat’s little theorem which is explained here. This one, the Fermat-Euler theorem, says that a^φ(n) ≡ 1 mod n, for any integer n where a is coprime to n.

Your first thought is probably one of: “What? Where did that come from?” or “Wow that’s so cool, but why?” – mine definitely was of that sort when I first saw this theorem. Unfortunately the proof is pretty involved and you need a decent amount of background for it, so I don’t have space for it here. If you’re interested, go check out the link above, which explains a special case of this theorem. Alternatively Wikipedia might be helpful, or UKMT do a great number theory book with this proof in it. Otherwise, you’ll just have to take it on trust.

This is combining modular arithmetic and a function we only just learned about so time for more examples!

• 2^φ(9) = 2⁶ = 64 = 63 + 1, so 2^φ(9) ≡ 1 mod 9 (yay!)
• 3^φ(12) = 3⁴ = 81 = 72 + 9, so 3^φ(12) ≡ 9 mod 12 – this doesn’t work because 12 and 3 aren’t coprime
• Let’s try 5^φ(12) instead: 5⁴ = 625 = 624 + 1 = 52 x 12 + 1, so 5^φ(12) ≡ 1 mod 12 (yay!)

Our second theorem tells us how to work out φ(n) if n is a product of 2 primes, p and q: it says that φ(n)=(p-1)(q-1). I’m not going to prove this one either, but you might like to take some time to think about why it’s true [*hint: use the footnote at the bottom of the page]. 

Now going back to the RSA algorithm, since e is prime, it’s coprime to φ(n), so has an inverse mod φ(n). The rest follows by exponential laws and the first theorem because (M^e)^d ≡ M^kφ(n)+1 ≡ 1^kM ≡ M(mod n).

Remember the algorithm we got all this maths from? A good question would be why is it secure enough that it’s used billions of times each day to secure our communications? Basically, to find M given C, we need to factorise n, and factorising numbers is really hard for computers to do. This may not make sense – computers can do anything as long as there’s an algorithm for it – but the concept of “difficulty” in computing (computer scientists call this complexity) is related to the time it takes for a computer to complete a given algorithm. If the number of steps in the algorithm to run is bounded above by the size of the input n to the power of some positive integer k, we say the algorithm is of polynomial time. Otherwise, it is of non-polynomial time (computer scientists aren’t very original when it comes to naming things). Informally speaking, non-polynomial things take longer for computers to work out. The fastest factoring algorithm so far is just below exponential time (so the number of steps in the algorithm is bounded by 2ⁿ or something similar, for n the size of the input), and would take about a million years to break RSA-1024, which is one of the newer generations of RSA. 

These algorithms are an area of active research, and a great example of why mathematical research is so important. If someone finds a polynomial time algorithm that can factor primes quickly, RSA may need to be completely replaced with another trapdoor function. Perhaps fortunately no-one’s found an algorithm that can do this yet though…

Actually, that isn’t quite true. There is one polynomial time algorithm for factoring primes, but it has quite a significant catch: it runs on a computer we haven’t invented yet. Shor’s algorithm (in case you want to google it) runs on a quantum computer. The cool idea behind quantum computers is that it can run a bunch of calculations simultaneously! In a regular computer like the one you’re reading this article on, the computer stores information and processes information using hundreds of billions of miniscule switches- called bits – that can take either 0 or 1 as a value. But, of course, these switches can only be on or off at any one time. However, the bits in a quantum computer – called qubits (kyoo-bits) – can have both values at the same time! You can think of it as trying to find the way through a maze. A regular computer would try each path in turn, but a quantum computer could try every path at once, because it’s capable of both making and not making a given turning simultaneously. 

So far, no scientist has created a quantum computer good enough to actually run this algorithm, but only time will tell how long RSA stands up. No need to panic though – your emails will be safe. As you’ll see in the next article, as there’s another important trapdoor function that cryptographers use…

*φ(p) is just p-1, since by definition of a prime number, every positive integer strictly below p does not divide p, so the only factor p has in common with the numbers below it is 1.

Article 1: Substitution Ciphers

Article 3: Elliptic Curve Cryptography