We've finally proved Fermat's Little Theorem and explained some of the machinery behind groups and rings. Let's continue by defining an important function.

__Definition__* (Euler's Totient Function):* Let $\varphi: \mathbb{Z}^+ \to \mathbb{Z}^+$ be defined as $\varphi(n) = $ the number of integers less than or equal to $n$ that are relatively prime to $n$ for $n \in \mathbb{Z}^+. \varphi$ is also known as the **Euler phi-function**.

As you can see, it can be quite hard to procure a general formula for $\varphi(n)$ for all $n$. However, in some cases it is relatively easy— for example, if $n$ is prime, then $\varphi(n)$ is simply $n-1.$ Recall from the last post that the Euler phi-function simply defines the *order* of the multiplicative group of units $\mathbb{Z}_n^*.$ We now state an important theorem:

__Theorem__* (Euler's Theorem):* Let $a \in \mathbb{Z}$ be relatively prime to $n,$ that is, $\text{gcd}(a,n)=1.$ Then
\[
a^{\varphi(n)} \equiv 1 \, (\text{mod} \, n),
\]
where $\varphi$ denotes the * Euler phi-function,* and $n \in \mathbb{Z}^+.$

** Proof:** Euler's Theorem is equivalent to the following statement: For all $a \in \mathbb{Z}_n^*$, $a^{\varphi(n)} \equiv 1$ (mod $n$). We know from a previous theorem that any element of a finite group raised to the power of the order of the group is $1.$ Since $|\mathbb{Z}_n^*|=\varphi(n)$, we have
\[
a^{\varphi(n)} \equiv a^{|\mathbb{Z}_n^*|} \equiv 1 \, (\text{mod} \, n). \quad \boxtimes
\]

Notice that the reasoning behind the proof is almost the exact same as the proof of Fermat's Little Theorem: **Indeed, Euler's Theorem is simply a generalization of Fermat's Little Theorem—** Fermat's Little Theorem simply describes the case where $n$ is prime.

Let's calculate $\varphi(n)$ for $n=pq$, where $p$ and $q$ are two prime numbers. We want to find the number of integers less than or equal to $n$ that are relatively prime to $n$. First, note that the number of integers less than or equal to $n$ is $n-1,$ or $pq-1$. We want to subtract the number of integers that have a multiple in common with $n.$ This is what we have so far:
\[
\varphi(n) = (pq - 1) - ? - ?
\]
Since $n$ is composed of two prime numbers, this would entail the multiples of $p$ and $q$ (due to the unique factorization of $n$) that are less than $n$, since $n=pq$ is already accounted for. There are $p-1$ multiples of $q$ and $q-1$ multiples of $p$ that are less than or equal to $n$. This makes sense if you think about $n$ this way. Without loss of generality,
\[
n = pq = q + \cdots + q
\]
$p$ times. Then the distinct numbers
\begin{align}
&1:q \\
&2:q + q \\
&3:q + q + q \\
& \vdots \\
&p-1:q + \cdots + q
\end{align}
are all multiples of $q$ that are less than $n$, hence why we stopped at the term $p-1$. Our goal is find the *number* of factors of $q$: then there must be $p-1$ factors since the set the set $\{1, 2, 3, \cdots p-1 \}$ has $p-1$ elements. A similar argument holds for the factors of $p$. We have some more information on how $\varphi(n)$ looks now...
\begin{align}
\varphi(n) &= (pq - 1) - (p - 1) - (q - 1) \\
&= pq - p - q + 1 \\
&= p(q-1)-(q-1) \\
&= (p-1)(q-1).
\end{align}
...Oh yeah, it's all coming together.

Now we finally understand the reasoning behind choosing the seemingly arbitary number $(p-1)(q-1)$: it's the * order of the multiplicative group of integers mod $pq$*, which means

** Lemma:** Let $n=pq$, where $p$ and $q$ are two distinct primes. If $a$ is an integer relatively prime to $n$ and $w$ is an integer such that $w \equiv 1 \, \text{mod} \, (p-1)(q-1)$, then
\[
a^w \equiv a \, (\text{mod} \,n).
\]

** Proof:** Since $w \equiv 1 \, \text{mod} \,(p-1)(q-1), w = k(p-1)(q-1)+1$ for some $k \in \mathbb{Z}$. So
\begin{align}
a^w &= a^{k(p-1)(q-1)+1} \\
&= a^{(p-1)(q-1)^k}a \\
&= a(a^{\varphi(n)})^k \\
&\equiv a(1)^k \ \small{\text{by Euler's Theorem}} \\
&= a \, (\text{mod} \, n).
\end{align}

With that, we've finally finished the theory behind RSA Encryption. Let's end this series with a real-world application, follow along on your Linux machines everyone! (Disclaimer: This should work on any machine with GPG installed).

We can use RSA Encryption to digitally sign messages, that is, generate a signature that anybody with my public key can decrypt, but only I can encrypt. Go ahead and grab yourself of a copy of GnuPG, the program we're going to use to create keys and verify signatures. If you're on Linux, just run

`sudo pacman -S gnupg`

or some variant (if you're using Linux, I hope you know how to install packages).
We'll use the same notation as the original post, refer back to it if you need to. Go ahead and download my public key, the message we're going to be verifiying, and the digital signature generated by RSA Encryption.

The algorithm starts by encoding $m$ (hello_world.txt) as an integer. We generate the digital signature by using my * private key* and letting the singature equal
\[
m^s \, (\text{mod} \, n).
\]
The resultant signature is encoded in the file hello_world.sig above.

If you want to generate a GPG key pair and sign a file of your own, go ahead and open your terminal emulator and run

`gpg --gen-key`

and follow the instructions. To generate the digital signature for a file, run
`gpg --output file.sig --detach-sig file`

and replace `file.sig`

with whatever name you want your signature file to be, and `file`

with the file you want to sign.
Now since I used my * private key* to sign this file, you'll need my

`cd`

to the directory where you downloaded my public key, and run
`gpg --import simonspublickey.gpg`

to add my public key to your We verify the signature works by raising it to the power of $r$ (which is in the public key) to yield \[ (m^s)^r \equiv m^{rs} \equiv m \, (\text{mod} \, n) \] by our lemma. Isn't that neat? Basically, it compares both the message $m$ and the signature raised to the power of $r$, denoted $(m^s)^r$, and checks to see if the two match— if they do then great, if they don't, then the signature has been compromised/the message has been tampered with since it was sent, and should not be trusted.

To follow along on your own machine, `cd`

to the directory you downloaded the files in and run

`gpg --verify hello_world.sig hello_world.txt`

Look at the third line of the output, which should read
`gpg: Good signature from "Simon ... " [unknown]`

If it does, then we've successfully verified the digital signature using the steps described. We conclude that I am indeed the author of the message, and that it hasn't been tampered with since publication. (You can ignore the "`WARNING: This key is not certified with a trusted signature!`

" message, it just means I haven't signed my GPG key yet.)
And that's a wrap! If you want to send me encrypted emails, you have my public key now so feel free to do so. Together, we can use the power of math and encryption to protect our content from the peering eyes of the NSA!