Think of A Number ... The Answer is 1
Let's bet ...
In cryptogaphy 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 arthimatic 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 remainer 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?
50p ... 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 50p. Want to try again? What do you mean no!
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^3 = 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 * q
Phi(n) = (p-1) * (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 * 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 77 = 61
If we try some values:
d (13*d) mod 77
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^13 mod 77 = 26
and let's decrypt:
Message = 26^37 mod 77 = 5
Yipeeee!!!!!!!!!!!!!!!!!!!!!!!!!!!! [Try it here]
If you want to try a few more they are [here].