Part one introduced Fermat and his “Last” and “Little” Theorems. Part two showed the preliminary steps for creating an uncrackable* code. We picked two different primes, p and q, a whole number e smaller than pq (aka n), which has no factors in common with (p-1)(q-1) and a whole number d with the property that de has remainder 1 when divided by (p-1)(q-1). We released n and e to the world and kept d, p and q private.
* Not a guarantee! 😉
p = 37 and q = 41 in our example. They would be much, much bigger in practice.
pq = n = 1517. This is the first half of the public key.
(p-1)(q-1) = 1440.
e = 7. No factors in common with 1440. This is the second half of the public key.
d = 823. de = 5761 which gives 4 remainder 1 when divided by 1440. d is the private key.
Also, to speed things up when discussing remainders, instead of saying “7 has remainder 2 when divided by 5” we can say 7 is equal to 2, modulo 5 or 7 = 2 mod 5.
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.
In our new notation, a^(p-1) = 1 mod p.
Alice takes her message M and converts it to a number m (known as the plaintext), using some agreed technique, e.g. A = 01, B = 02, etc…
She raises m to the power of e (the public key), then divides by n and takes the remainder, c. This is the ciphertext that Alice sends to Bob. m^e = c mod n.
Do try this at home
Using the numbers in our example, try turning “MY” into a secret message. Answers at the bottom of this post. You will need the cunning technique given at the end of this post to help you in the calculations.
Bob takes c and raises it to the power of d (the private key) and divides by n. The remainder he gets will mathemagically be equal to m, the plaintext Alice encrypted. He converts back to text, e.g. 01 = A, 02 = B, etc… and reads the message. c^d = m mod n.
Do try this at home 2
Using the numbers in our example, try cracking the secret message “238”.
Why it Works?
So no doubt you’re wondering how it all works. Why does the original number pop out no matter what? Well, it goes a little something like this…
The Long Version
c^d = (m^e)^d mod n = m^de mod n.
Recall that de = 1 mod (p-1)(q-1) by design. So de = 1 mod (p-1) and de = 1 mod (q-1).
Hence, there are two whole numbers, call them a and b, such that;
de = a(p-1) + 1
de = b(q-1) + 1.
Fermat’s Little Theorem says m^(p-1) = 1 mod p, since p is prime.*
Hence, m^de = m^(a(p-1)+1) = m*(m^(p-1))^a = m*(1^a) mod p. So m^de = m mod p.
Also, m^de = m^(b(q-1)+1) = m*(m^(q-1))^b = m*(1^b) mod q. So m^de = m mod q.
Since p and q are two distinct primes m^de = m mod pq = m mod n.
* Strictly speaking FLT is only true if p doesn’t divide m but if it does then it divides m^de as well so m^de = m (=0) mod p anyway.
The Short Version
Raise c to the power of d, divide by n and take the remainder. Fermat’s Little Theorem and some other cunning mathsy manipulations guarantee you’ll get m, the original message as your answer.
Cunning Technique for Raising to Big Powers While Taking Remainders under Division so as to Avoid Melting Your Calculator
If x = a mod n, then there is some whole number b such that x = bn + a. So x^2 = (bn + a)^2 = (bn)^2 + 2abn + a^2. Since (bn)^2 and 2abn are both divisible by n, the remainder of x^2 is the same as the remainder of a^2 when divided by n.
Example: Say we want to know the remainder of 7^8 when dividing by 9.
7^2 = 49. 49 = 4 mod 5.
7^4 = (7^2)^2 = 4^2 mod 5 = 16 mod 5 = 1 mod 5.
7^8 = (7^4)^2 = 1^2 mod 5 = 1 mod 5 since squaring 1 just gives 1.
Quick Check: 7^8 = 5764801 which gives 1152960 when you divide by 5 and a remainder, conveniently enough, of 1.
Answers to Puzzles
“MY” encrypts to 928. Decoding 238 yields 1415, which reads “NO”.