In the cell below, we will pick a few things. (Our secret is still that math is cool.) We need a prime number \(p\), and some legitimate exponent \(e\) that won't mess things up too badly.

What do I mean by that? Remembering that when we solved \[x^{3}\equiv 5 \text{ mod}(17)\text{ as }3^{3i}\equiv 3^{5}\text{ mod}(17)\] we ended up in the world of \(\phi(17)=16\) and solving \[3i\equiv 5 \text{ mod}(16)\, .\] In order to keep using this idea, we will pick an exponent coprime to \(\phi(p)\).

Now, I just take my message and raise it to the \(e\) power modulo \(p\) - simple as that!

Here I picked \(p=29\), useful since it's close to 26, and more or less arbitrarily picked an exponent \(e=9\).

• I still first had to encode “MathIsCool” to numbers.
• Then I exponentiated each number in the coded version, modulo 29.
• To be precise, I sent each number \[a\to a^9\text{ mod }(29)\; .\]

Leaving aside for the moment that the letter A will now have the unfortunate property that it always stays 1, and hence basically unencrypted (this is because we are doing a toy example), how on earth would we ever decrypt this? Do we have a way to invert \[a^9\text{ mod }(29)\] in any way?

Naturally, we do! We will use exponentiation again to do so. We just need something that solves \[\left(a^9\right)^f\equiv a\text{ mod }(29)\; ,\] or more concisely \[a^{9f}\equiv a^1\text{ mod }(29)\; .\] (We can think of \(f\) as a power that inverts the original power \(9\).).

From our earlier discussion, this is just a solution to \[9f\equiv 1\text{ mod }(28)\] and we know we can find this.

This method of encryption is known as the Diffie-Hellman, or D-H, method (named after its originators, who proposed it in the mid-70's).

Now we will do a more real example of this. Notice how important it was that we chose an initial exponent \(e\) that was coprime to \(\phi(p)=p-1\).

For convenience, I'll just take the next prime bigger than my message.

I factored \(p-1\) so I could find something coprime to it.

The encrypted message is now just one number. Now we need the decryption key. Luckily, that's just as easy as taking an inverse modulo \(p-1\):

Here is an extended example:

Our first awesome encryption scheme does the following:

• Turn your message into a number \(x\).
• Pick a prime \(p\) and an exponent \(e\) such that \(gcd(e,p-1)=1\).
• Encrypt to a secret message by taking \[m=x^e\text{ mod }(p)\; .\]

Want to decrypt?

• First, find an inverse modulo \(p-1\) to \(e\), called \(f\), so that \[ef\equiv 1\text{ mod }(p-1)\]
• Decrypt (if you want) by taking \[m^f\equiv \left(x^e\right)^f\equiv x^{ef}\equiv x^1\equiv x\text{ mod }(p)\]
• Celebrate in your opponent's destruction.

Feel free to see what happens with your own short messages.

Or you can choose a prime on your own.

Remember, the key that makes it all work is that (thanks to Euler's Theorem/Fermat's Little Theorem) exponents of congruences mod \(n\) live in the world of congruences mod \(\phi(n)\), as long as they are numbers coprime to \(\phi(n)\). That's why \(gcd(e,p-1)=1\) is important. Here's how that can go wrong.

So far, so good, but what happens when we try to decrypt?

It turns out not even to be possible to go backwards.