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

Ifpis any prime number andais any whole number thatpdoesn’t divide evenly (i.e, without a remainder) then, if you raiseato the power ofp-1 and then divide byp, you get a remainder of 1 no matter what exact numbersaandpare.

**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**?

**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

pandq, findingpq(a.k.a.n) is a doddle and (p-1)*(q-1) is also simplicity itself to calculate. But findingpandqgivennis 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.

[…] of indices of prime numbers left remainders of one (happening to be based on something that Eoghan has recently blogged about). Again, I thought there was hope – a couple of marks here and there, and I would at least have […]

By:

A Different Kind of Olympics » Every Day is Election Dayon August 15, 2008at 8:15 pm

[…] of indices of prime numbers left remainders of one (happening to be based on something that Eoghan has recently blogged about). Again, I thought there was hope – a couple of marks here and there, and I would at least have […]

By:

Gav Reilly | Tokyo, Part 2on January 28, 2009at 12:04 pm