Fermat’s Fermaths 2

In part one we met Pierre de Fermat, a French mathematician of the 17th Century whose famous Last Theorem terrorised mathematicians for three centuries and whose Little Theorem can be used cunningly to create codes. This code system is called RSA after the mathematicians who developed it.

N.B. In this post xy (for example) will mean the product when the two numbers x and y are multiplied together. Indented text is reference material that can be skipped over.

Fermat’s Little Theorem
If p is any prime number and a is any whole number that p doesn’t divide evenly (i.e, without a remainder) then, if you raise a to the power of p-1 and then divide by p, you get a remainder of 1 no matter what exact numbers a and p are.

1. Mind your Ps and Qs.

To make a code that exploits the power of the Little Theorem we start by secretly picking two distinct prime numbers, p and q. In reality these will be huge 100-digit-plus monster numbers that would eat you and everyone you care about given half a chance but for this example we can use p = 37 and q = 41, which are much smaller and cuter. We compute (p-1)*(q-1), which is 36 * 40 in this case, i.e. 1440. In passing let’s call pq something snappier. How about n?

An artist's impression of a giant man-eating prime

2. Pick an E, any E.

Second, pick any number smaller than n that has no factors in common with (p-1)(q-1). In our example (p-1)(q-1)  is 1440, which is 2*2*2*2*2*3*3*5, so we pick a number that isn’t a multiple of 2 or 3 or 5… like 7. Whatever number we choose is known as e.

3. D is for “Devilishly hard to figure out”

We announce n and e to the world or at least to everyone who might want to send us a secret message. This pair (n, e) is known as the public key. Meanwhile we sneakily calculate a number (called d) which has the property that when you multiply it by e and then divide by (p-1)(q-1) you get a remainder of 1. d is the private key.

Rivest, Shamir and Adleman, who invented the RSA code.

In our example d could be 823 since de is then 823 * 7 = 5761 and 1440 goes into 5761 four times leaving a remainder of 1. Calculating d is easy if you know p and q but really hard if you don’t. And, even if you know n, which is pq, it’s really hard and long-winded to figure out what p and q themselves are. So tedious in fact that even super-fast computers would need centuries to do it. This difference provides the security of the code.

Daddy, what’s a “trapdoor function”?

Multiplication and factorisation are exact opposites. Take 7 and 11 and multiply them together to get 77. Factorising 77 means finding the numbers that multiply together to give 77, i.e. 7 and 11. Multiplying is much easier than factorising, to check this you can quickly see how long it takes you to multiply 41 and 53 together versus finding the two factors of 1739. You can use a calculator to help you.

So if we know p and q, finding pq (a.k.a. n) is a doddle and (p-1)*(q-1) is also simplicity itself to calculate. But finding p and q given n is tough. It isn’t proven yet but mathematicians generally believe there is no quick way to do this task in general. All you can do is trial-and-error. Hence the slowness. This asymmetry between the opposites (multiplication and factorisation) is known as a “trapdoor”, i.e. easy to fall into but very hard to climb out of again.

With these 3 steps complete we are ready to send some secrets. In the next post.