Proving RSA Encryption: An Application of Group Theory (Part 3: Digital Signatures and Euler's Totient Function)

[linkstandalone]

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 any element of $\mathbb{Z}_{pq}$ will reduce to 1 if raised to the power of $(p-1)(q-1)$ modulo $(p-1)(q-1)$ by Euler's Theorem. Let us finally prove that pesky lemma from the first post.

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 public key to verify the signature. cd to the directory where you downloaded my public key, and run

gpg --import simonspublickey.gpg
to add my public key to your keyring.

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!