If you’re anything like me, you need to send TOP SECRET messages all the time.
Just the other day, I was working on a really hard problem set for my History of Math class, so I decided to ask my good friend Maryam Mirzakhani to do it for me. This, of course, went against my University’s cheating policy, so I needed to be sure that my message was encrypted securely enough that my resourceful and mathematically gifted professor Evelyn Lamb couldn’t read my message and fail me for cheating.
Luckily, by the grace of modular arithmetic, I was able to have a quick exchange with Maryam just in time to hand in my assignment undetected. Below I’ll discuss the rad encryption algorithm Maryam and I used to exchange messages, and the clever but unfortunately unsuccessful algorithms my suspicious professor tried to discover our ploy.
We decided to encrypt with RSA and pay homage to the best public-key cryptosystem around. RSA is an asymmetric algorithm, which means that the keys of the sender and the receiver are completely independent. Maryam and I needed to independently complete the steps below to exchange encrypted messages.
1) I chose 2 extremely large prime numbers p and q.
I went with my favorite primes, 61 and 11.
2) Set my modulus to be n = p * q, and held on to a value I’ll call ϕ(n) = (p-1)*(q-1)
So for me, n = 11*61 = 671, and ϕ(n) = 10*60 = 160.
3) Chose the exponent “e” for my public key
The number e just needs to be coprime with ϕ(n), a common choice is 216 + 1 = 65,537 but 3 is sometimes just as good a choice.
I chose e = 7, just because I happen to like 7.
4) Found my private key exponent, “d” as the multiplicative inverse of e mod ϕ(n).
That is, find d such that d*e = 1 (mod ϕ(n)).
Normally, you can do this using the extended Euclidean Algorithm.
But I instead used the coveted Wolfram-Alpha algorithm, and found that d = 23.
After these steps Maryam and I each had a public and private key- you can think of these as keys that interchangeably lock and unlock the message. Anyone listening in (like Professor Lamb) can see each of our public keys- this is what allows strangers on the internet to securely exchange messages.
The public key consists of n and e, and the private key is d. My public key was (n = 187, e = 7) and my private key was d = 23 (but don’t tell Professor Lamb!) Maryam broadcast her public key, which was (n = 779167, e = 17).
I want to encrypt my message:
Hi Mimi! How great is the weather in California? Hey, I have a favor to ask…
First I converted the letters in my message into numbers by some publicly known agreed upon encoding, and broke my message into chunks so that the value of each chunk was less than Maryam’s public key value n, again with a publicly agreed upon scheme:
720 010 500 077 001 050 010 900 105 000 330 007 200 111…
I then encoded each chunk into the cypher-text c using Maryam’s public key (n = 779167, e = 17) as: c = me (mod n)
So specifically, c1 = 72017 (mod 779167)
c2 = 1017 (mod 779167) and so on.
I sent these encoded cypher-text chunks to Maryam, who then used her private key d to decode them into the message that I wrote:
m = cd (mod n)
This is because I encoded the cypher-text as c = me (mod n), so when Maryam computed cd, she had actually computed (me)d (mod n) = med (mod n). Recall that Maryam very carefully chose e and d so that e*d = 1 (mod ϕ(n)). This means, thanks to Fermat’s Little Theorem, that med (mod n) is the same as m1 (mod n). Excellent news, this is just my original message! Thanks, modular arithmetic!
We could now securely exchange messages, and for even more security I even left a signature in my message so that Maryam could be sure the message actually came from me.
But not so fast! Professor Lamb noticed that Maryam and I were exchanging mysterious messages, so she took a stab at decoding them.
Pollard’s p-1 Algorithm
RSA is a secure algorithm because it is very difficult to factor large numbers.
Recall that when I sent Maryam a message, I encoded the message m into cypher-text c using her public key (n and e) as:
c = me (mod n)
and she decoded the message using her private key d as:
cd = med (mod n) = m (mod n)
This is secure because, if you remember back to how Maryam chose e and d,
e*d = 1 (mod ϕ(n))
This means that for Professor Lamb to decode the message that I sent to Maryam, she needed to find d. To find d, she needed to know what ϕ(n) = (p-1)*(q-1) was, because you need to know the modulus before you can find the inverse of an element, and to find ϕ(n) she needed to figure out p and q. Therefore, the only thing standing between me and expulsion for cheating is the fact that it’s very hard to factor very large numbers. Notice, however, that all the other information is publicly available- c, e and n can be viewed by everyone.
Professor Lamb decided to try Pollard’s p-1 algorithm to factor Maryam’s public key modulus, n = 779167. She first decided to try the algorithm on a smaller, more manageable number, so she tried n = 5917. Here’s what she did:
1. She chose a positive number B.
Professor Lamb liked the number 5, so she set B = 5.
2. Computed m as the least-common multiple of the positive integers less than B.
m = lcm(1, 2, 3, 4, 5) = 60
3. Set a = 2.
Easiest step ever.
4. Found x = am – 1 (mod N) and g = gcd(x, N)
x = 260 – 1 (mod 5917) = 3417 (mod 5917)
g = gcd(3417, 5917) = 61
5. If g isn’t equal to 1 or N, then you’re done!
Professor Lamb found that 61 was a prime factor of 5917! Slick!
6. Otherwise, add 1 to a and try again. If you’ve already tried 10 times, just give up.
Luckily she didn’t need to use this step, but for a lot of different n’s she probably would have.
Feeling triumphant and confident in Pollard’s p-1 algorithm, Professor Lamb turned to Maryam’s public key modulus, n = 779167. The first 3 steps were the exact same as before, and for step 4 she found:
x = 260 -1 (mod 779167) = 710980
g = gcd(710980, 779167) = 1
Drat! Professor Lamb then had to proceed to step 6, increased a to 3 and try again:
x = 360 -1 (mod 779167) = 592846
g = gcd(592846, 779167) = 1
Double drat! Professor Lamb continued this for approximately 10 steps, and then gave up. (Really I should just be glad that she didn’t try to factor my public key modulus n = 187. Our encryption would have been much more secure if I had chosen much larger primes!)
Luckily for me, Maryam and I chose a secure encryption algorithm. RSA is set up so that to decode the message, you need to know the prime factors p and q of the modulus n. You need p and q so that you can find the inverse of the public key mod (p-1)(q-1), and these public and private key exponents work to encode and decode the message because of Fermat’s Little Theorem.
Professor Lamb tried to decode our secret messages by factoring Maryam’s public key modulus with Pollard’s p-1 algorithm, but unfortunately it did not yield a prime factor. Because finding large prime factors is such a difficult problem, Professor Lamb wasn’t able to read our secret messages, and I got an A on my homework.
– I obviously didn’t ask Maryam Mirzakani to do my Math History homework. She’s an incredibly intelligent lady, working on much, much more difficult things, and apparently getting awesome results.
– I obviously don’t endorse cheating and Professor Lamb’s homework is not too difficult. It is just difficult enough 🙂
– Even though I motivated the need for privacy in my silly article with my desire to keep my professor from finding out I was cheating, privacy is obviously very important for a wide range of reasons(possible hyperlink?), and is equally important to protect people who don’t have anything to hide.
– The ascii art image of Maryam Mirzakani is obvious very cool! It was made by my very talented friend Tobin Yehle, who wrote a neat program to translate photos into ascii art.