How does cryptography work?

A new arithmetic

Let’s start off with a puzzle: When is 10 + 4 equal to 2? Please do try to solve this little puzzle by not reading any further. The rest of this paragraph will contain hints and eventually a solution. For example, this puzzle is effectively asking: When is 14 equal to 2? The numbers are slightly more convenient if we ask this as: When is 12 equal to 0? You might think that 12 would have to be some special number in some context, and maybe that context would become more clear if the question were: When is 24 equal to 0? The idea of getting as far as 24 then starting from the beginning should be familiar, and the fact that I used the word “When” in the question might help too, as this puzzle is related to time. The number 24 is significant in the context of time because it is the number of hours in a day, of course, and we do think of “24 o’clock” as being the same as “0 o’clock”. That is in the 24 hour system of timekeeping though, but to answer the original question we need to consider the 12 hour system, where 14 o’clock is called 2 o’clock. The question is really asking then: What time is it on the 12 hour clock if you add 4 hours to 10 o’clock? The answer being 2 o’clock. If you spotted this without any clues then well done, it is by no means obvious, although perhaps your eyes and your unconscious picked up on a few useful words in this paragraph before you tried solving it. Maybe then I should have encrypted all these clues using the ROT13 cipher.

So, people are used to dealing with a number system on a day to day basis where the numbers can only get so high before starting back at zero again. If you know what ROT13 is, then that is a letter-based system that follows the same principle. People may ask themselves “What time will it be in six hours?” or “How many hours is it until 08:00 tomorrow?” but they may not realise there is a generalisable system here. In mathematics the name of the more general system of arithmetic is called modular arithmetic (or “clock arithmetic”). The 12 hour clock system works “modulo 12” (and ROT13 works “modulo 26”) so 2 and 14 are the same modulo 12. This is written mathematically as:

2 ≡ 14 modulo 12

The underlying principle is that:

a ≡ b modulo n

means

a = b + k × n

for some value of k. All the numbers involved here are positive whole numbers, although k could be a negative whole number if required. Also note that “modulo n” is often abbreviated to “mod n”.

You could look up all about this in a school maths textbook or online, but I will give some examples here to explain just the minimum amount required to make some sense of cryptography. Consider the sum:

200 ≡ 74 mod 3

This is true because:

200 = 74 + 42 × 3

which is what the definition of “modulo” given above says (k is 42 in this example). The numbers 200 and 74 are quite big, though, and we would probably rather say:

200 &equiv 2 mod 3

which is equally true, but 2 is a nicer number to work with than 74. In fact, any positive whole number, when viewed modulo 3, is equal to 0, 1 or 2. Just as in the 12 hour clock (modulo 12) all sums involving hours result in a number between 1 and 12 inclusive, all sums done mod n can be reduced to a number between 1 and n inclusive, although mathematicians prefer working with zero so they would choose an equivalent range of numbers which is the range from 0 to n-1 inclusive.

Now that addition in modulo world is defined, I will rush forward and say that a lot of other arithmetic you are familiar with should work as normal under this system. For instance:

12 - 5 &equiv 7 mod 13

and

3 × 9 mod 13 &equiv 27 mod 13 ≡ 1 mod 13

Unfortunately division is a bit harder. Consider the question:

3 × Χ &equiv 1 mod 13

As we are dealing with whole numbers, we can’t say that Χ is 1/13^th as that number doesn’t exist in these situations. To find Χ then, one could use a “brute force” approach and try each of the following calculations:

3 × 1 ≡ 3 mod 13 3 × 2 ≡ 6 mod 13 3 × 3 ≡ 9 mod 13 3 × 4 ≡ 12 mod 13 3 × 5 ≡ 15 ≡ 2 mod 13 3 × 6 ≡ 18 ≡ 5 mod 13 3 × 7 ≡ 21 ≡ 8 mod 13 3 × 8 ≡ 24 ≡ 11 mod 13 3 × 9 ≡ 27 ≡ 1 mod 13

eventually finding the number which makes this work, meaning that Χ is 9.

In the worst case you would have to go through all the numbers mod 13 and only on the last one (12) would you find the answer. Admittedly in the best case, the first number you tried would be the right one, so that means this method requires between 1 and n multiplication sums to solve a division modulo n, with the average number of sums required being n/2. It turns out there is a better method for solving these divisions though, if you just want to solve the specific case of:

a × Χ &equiv 1 mod n

where a is “coprime” to n. This improved, faster method is called the Extended Euclidean Algorithm, and fortunately the specific sort of division problem just mentioned is precisely the sort of calculation that is needed when using public key cryptography. Unfortunately, however, I haven’t explained what “coprime” means, and I might need to explain what “prime” means first, but once I have done that you can look up the Extended Euclidean Algorithm (after looking up the standard Euclidean Algorithm) or just assume that it works. The important thing is that you realise that sums like:

a × Χ &equiv 1 mod n

can be solved relatively quickly (quicker than another calculation I will mention later on).

Primes

To give another, less interesting puzzle, I could ask: What do 12 and 30 have in common? There are probably a multitude of answers to that question, though, and the only one that’s relevant right now is the answer: Six. What I mean is, both numbers are multiples of 6, because 12 is 2 × 6 and 30 is 5 × 6. It is also true that they are both multiples of 2 as well as both being multiples of 3, but 6 is the biggest number that they are both multiples of. The other way to look at this is to say that 2, 3 and 6 are “factors” of 12 and 30, or “divisors” of 12 and 30. Finding the “greatest common divisor” (GCD) of two numbers (which was 6, in the case of the two numbers 12 and 30) turns out to be really significant for some uses of mathematics. One way to find the GCD, though, involves turning the two numbers into their prime factors, so I will explain what “prime” means while demonstrating how to find the GCD.

Considering 12 first, this number can be split into two numbers which, when multiplied together, equal 12. For example, 4 × 3 = 12, so 4 and 3 are both factors (divisors) of 12. The number 4 can be further “factorised” by noticing that 4 = 2 × 2, so 2 is a factor of 4 and thus a factor of 12 too. This is as far as the process can go, though, as 2 cannot be factorised any further, and nor can the 3 from the first factorisation. This means that 2 and 3 are called “prime”, they cannot be factorised into anything smaller. The more technical definition is that a prime number is a number which has exactly two factors: itself and the number 1. For example the number 3 is prime because it has only two factors: 3 and 1 (and 3 × 1 = 3). Just for completeness, I will demonstrate this “prime factorisation” for the number 30 as well: 30 = 15 × 2, and 15 = 5 × 3.

So the two numbers can now be expressed as a “product of their prime factors”:

12 = 3 × 2 × 2 30 = 5 × 3 × 2

The word “product” just means “multiplied together”. By looking at these two prime factorisations, it is possible to see that what they have in common are the factors 3 and 2. Obviously 3 × 2 is equal to 6, which is why the GCD of 12 and 30 is 6. Mathematicians would write this as:

gcd(12, 30) = 6

It’s also worth noting here that if 30 had two 2s in its factorisation, like 12 does, then the common factors would be 3, 2 and 2, so it is possible to have several instances of a certain prime number in common between two numbers.

The quick way to explain what coprime means now is that two numbers a and b are coprime (or “relatively prime”) if:

gcd(a, b) = 1

Even though I’ve explained what a GCD is, though, that definition might not be readily understandable. Perhaps a better explanation, then, is that if you determine the prime factorisation of two numbers, and the two lists of primes don’t have any numbers in common, then the two numbers must be relatively prime. Of course, every number has 1 as a factor, so any pair of numbers will have 1 as a common factor, but if that’s the only factor in common then the GCD is 1 and the numbers are coprime.

n, p, q, e, d, m and c

Here is another riddle: What can you spell with the letters n, p, q, e, d, m and c? The answer: RSA. That might make more sense when I start to use some of the maths I’ve explained so far. For instance, the next step in my explanation is to get you to imagine a number n which is the product of just two primes, to which I’ll assign the letters: p and q. Writing this mathematically, then:

n = pq

There are lots of numbers that could fit this equation, such as:

15 = 3 × 5

but the mathematics will work for any numbers n, p and q which have the properties I’ve described.

The important thing to note is that it is relatively quick to come up with a prime number (or at least to test whether a chosen number is prime) and even quicker to multiply two such numbers together, but if someone gives you such a number n and asks you to find the unique pair of factors p and q from which it was created, this turns out to be very hard. When I said that solving

a × Χ &equiv 1 mod n

is relatively quick, I meant that it is quicker than this problem, factorising the product of two primes.

Now that you have these three numbers, n, p and q, imagine that you came up with a forth number e which is less than n and in fact has the following properties:

0 < e < (p-1)(q-1) gcd(e, (p-1)(q-1)) = 1

that is to say, e and (p-1)(q-1) are coprime. To test whether the e you have chosen really is coprime to (p-1)(q-1) you can again use the Euclidean Algorithm, which, as mentioned before, is relatively fast. You can then use the Extended Euclidean Algorithm to find a final number d which fits this equation:

ed ≡ 1 mod (p-1)(q-1)

This is where the interesting application really starts. Imagine you are Alice and you have done all these calculations and generated n, p, q, d and e. Further, imagine you want to talk to Bob in secret but you can only send each other messages which might be read by your adversary Carol. So you send Bob two of these numbers you’ve come up with, the n and e. Of course, Carol will see these numbers too, but that doesn’t matter, those are not secret numbers, they are your “public” numbers and we call the two of them together your “public key”. The important thing is that you keep the number d secret, as that is your “private key”. This is why it matters that it is difficult to factorise n, because if it wasn’t then Carol could find p and q and she would have intercepted e, so she could work out d, your secret.

So what does Bob do with n and e, and why are they so important? Well, let’s say he wants to send you a magic number m without Carol finding out what that number is. He can calculate a new number c using the formula:

c ≡ m^e mod n

and send you that instead, knowing that Carol cannot find out m even if she knows c.

Why couldn’t she, though, if she intercepts c and already found out e and n? Well, she could try raising the intercepted number c to the power 1/e and doing the calculation:

c^1/e ≡ (m^e)^1/e ≡ m^e(1/e) ≡ m¹ ≡ m mod n

which would calculate m, but to do that she would need to know what 1/e is. Remember, modular arithmetic only works for whole numbers, and just dividing 1 by the whole number e isn’t going to give you a whole number. What she would need is a number f such that:

1/e ≡ f mod n

or, equivalently:

1 ≡ ef mod n

but that means that f would be d and it is really difficult to work out d, as mentioned earlier.

Fortunately you (Alice), the intended recipient of the message, do know what d is, so you can do the calculation

c^d ≡ (m^e)^d ≡ m^ed ≡ m¹ ≡ m mod n

which means you can find out Bob’s secret number m and Carol can’t. Actually all this “something to the power something” business should be proven a bit more rigorously, but you can look up the proof and it isn’t that much more difficult.

Conclusion

Taking a step back from the mathematics, then, what has happened is that Alice has generated a private key and a public key, and made the public key available to anyone, and Bob has used that public key to turn a numerical message m into an encrypted numerical message c which he can safely send to Alice knowing that only she can decrypt it, using her private key. It might seem like a limitation that only numerical messages can be encrypted, but it is simple to assign a different number to each letter of the alphabet, so that any textual message can be encrypted using this method too. In fact, as any information stored on a computer or sent over a computer network can be represented as a stream of ones and zeros, this means any computer file or online communication can be encrypted with this method. The applications of this technology are as limitless as they are ubiquitous, and there should be no reason why all data on PCs and the internet shouldn’t be encrypted nowadays.

The only question is, when Bob gets Alice’s public key, how does he know it’s really hers and not Carol’s?