Fermet

Fermet

If you are in higher education, you know all about the Research Excellence Framework (REF), and where we grade papers for their star rate. A 4-star paper has a world-leading advancement, and where you will be lots of maths and results. But there was a time when research really did contribute massively to changing things, and one of the great was Pierre de Fermat. So let’s have a bit of fun first.

In cryptography we love prime numbers and the mod operator. So let’s take a bet. I think I can predict your answer. First select a number from the following:

2,4,6,9,10,12,14,15,16,18,20,21,22,24,25,26,27,28,29,30,32,33,34,35,36

and next select a number from this list:

2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97

Okay. The arithmatic may be a bit difficult if you select one of the larger ones … but go ahead and pick two values.

Have you done it?

Okay … next take the first value and raise it to the power of the second value minus 1 (you may need a calculator for it). So if you select 4 from the first list and 5 from the second, it will be 4 to the power of 4 which should give 256.

Next take the result of the remainder of a divide by the second number. If we have 256 then we divide by 5 to give 51 remainder 1 (so the answer is the remainder, which is 1 — keep that a secret).

Okay .. you might need the mod button on your calculator, but have you done that?

Now do you want to take a bet I can predict your answer?

$1 … okay … I’ll take that.

Now I think your answer is … mmmm … it’s tough … but I think is less than 10? Is that right? Well … from the look on your face …. I think it is one!

Is it correct? Thank you for the $1.

How does it work?

We are using Fermat’s Little Theorem from 1640, and where he determined that:

a^(p-1) mod p = 1

where p is a prime number and a has no common factors in p.

Let’s take an easy one, a=4, p=5:

a^(p-1) gives 4⁴ = 256
and then 256 mod 5 = 1

Let’s take a few other ones, just to test:

• a=6, p=7 Try. This should give 1.
• a=12, p=17 Try. This should give 1.
• a=21, p=31 Try. This should give 1.
• a=21, p=22 Try. This should not give 1. Why? p isn’t a prime number!

So what?

Without this magic little theorem the security of the Internet would not quite be how it is. It is Fermat’s Little Theorm (which was generalised by Euler) that became the core of RSA, and which now is the main public key method used on the Internet. It often is used to prove identity, and in creating secure tunnels, so this theorem ended up stopping you from identity theft!

Inverse Mod

Fermat’s theory can be applied into finding the inverse of a (mod p), such as finding a^{-1} (mod p). First we start with Fermat’s theroem:

And which can become:

and then we multiply both sides by a^{-1}:

In Go, the code for this is:

func fermatInverse(a, N *big.Int) *big.Int {
    two := big.NewInt(2)
    nMinus2 := new(big.Int).Sub(N, two)
    return new(big.Int).Exp(a, nMinus2, N)
}

And here is the code:

or if you prefer Python:

a=64
p=97
invmod=pow(a,p-2,p)
print invmod

RSA

The beauty of RSA is breathtaking. I have two values d and e, and I share e and a prime number n. If you want to send me a message (m) you:

Cipher = m^e mod (n)

and you send it to me, and I just basically raise your Cipher to the power of d, and I get the orginal message back again:

Message = Cipher^d mod (n)

To compute the keys we use Fermat’s theorm. First take two prime numbers named p and q, and calculate n and Phi(n):

n= p xq

Phi(n) = (p-1) x (q-1)

Now we must select a value of e, so that there is no common factor in Phi. Finally we select a value so that:

(e x d) mod n = Phi(n) +1

Magic!

For example if we select p =7 and q = 11, we get:

n=77

Phi(n) = 60

Now, gcd(e,Phi)=1, so Phi(n) has factors of 2, 3, 4, 5, 6, 10.., so we must avoid these. Let’s select 9 … no that doesn’t work as it has a factor of 3. Let’s select 13:

e=13

Now we must compute:

(e * d) mod (Phi(n)) = 1

(13 * d) mod 60= 1

To find d we need to find the inverse mod of 13 (mod 77):

e=13
p=60
invmod=pow(e,p-1,p)
print invmod

The result for this is a value of 37 for d.

Our public key is (e,n) or (13,77) and the decryption key is (d,n) or (37,77).

Let’s take a message of 5. The cipher is:

Cipher =5¹³ mod 77 = 26

and let’s decrypt:

Message = 26³⁷ mod 77 = 5

Yipeeee!!!!!!!!!!!!!!!!!!!!!!!!!!!! [Try it here]

If you want to try a few more they are [here].