Posted by: Eoghan | August 14, 2008

Fermat’s Fermaths 3

A WWII Enigma Machine. An earlier attempt at an uncrackable code.
A WWII Enigma Machine. An earlier attempt at an uncrackable code.

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! 😉

Recap
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.

Proved his Little Theorem, only stated the Last Theorem.

Fermat: Proved his Little Theorem, only stated the Last Theorem.

Encrypting
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.

Decrypting
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”.

Advertisements

Responses

  1. Loving this! I’m one of those people who likes hard maths in a kind of casual way where I can’t really do it for myself but enjoy someone who knows what they’re talking about telling me about it, this is great! Do more mathsy things Eoghan! Mags

  2. Like Margeurite, I like all this stuff and like my Catholicism, I’m a non practioner.

    I went to see Simon Singh speak in the RDS a couple of years ago and he was brilliant, though he didn’t mention Fermat.

    Lar

  3. […] – bookmarked by 6 members originally found by brightideasguru on 2008-09-14 Fermat’s Fermaths 3 https://casacaseycourtney.wordpress.com/2008/08/14/fermats-fermaths-3/ – bookmarked by 6 members […]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: