Fermat’s Little Theorem Became The Core of Security on the Internet
Fermat’s Little Theorem Became The Core of Security on the Internet
Let’s bet …
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?
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!
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
a^(p-1) mod 1 gives 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!
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 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= 61
If we try some values:
d (13*d) mod 60
1 13
2 26
3 39
4 52
….
35 35
36 48
37 1
So we have 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].