# RSA: Fermat's Little Theorem and the multiplicative inverse relationship between mod n and mod phi(n)

I'm learning about the proof of the RSA encryption algorithm, and I'm clearly fudging or missing something, because for me it doesn't add up.

When generating keys for RSA encryption, we make sure that:
$ed \equiv 1\pmod{\varphi(n)}$

But when encrypting or decrypting, we use:
$C \equiv M^e \pmod{n}$

$ed \equiv 1 \pmod{n}$

because now raising $C$ to $d$ will get us $M$ again.

But we use $\varphi(n)$ instead.

I understand that we use $\varphi(n)$ to make $d$ difficult to compute, since to find $\varphi(n)$ you need to know the prime factorisation of $n$.

But how do you link a multiplicative inverse mod $\varphi(n)$ with a multilicative inverse mod $n$?

From reading around it seems that according to Fermat's Little Theorem, a multilicative inverse mod $\varphi(n)$ will hold mod $n$.

If a multiplicative inverse relationship works for $\varphi(n)$ and $n$, why does an attacker not work out the multiplicative inverse of $e \pmod{n}$? Even if the key were originally made mod $\varphi(n)$, surely using an inverse mod $n$ would work just as well?

• What you're missing is that "if we had made" $ed = 1\ (mod\ n)$ then $\hspace{2.21 in}$ "raising $C$ to $d$ will" usually not "get us $M$ again". $\;$ – user991 May 30 '14 at 22:49
• i'm sorry, perhaps i've phrased this badly - i guess what i'm asking is what am i missing about the proof? if an inverse for mod phi(n) holds for mod n, does an inverse for mod n hold for mod phi(n)? and if not, why is this? – peregrine42 May 30 '14 at 23:51
• Even if there was such a symmetry, I don't see how that would help, since the encryption algorithm is not doing any computations mod phi(n). $\:$ Furthermore, powering is different from multiplying. $\:$ (p.s., What is "a multilicative inverse"?) $\;\;\;\;$ – user991 May 31 '14 at 0:50

You are misunderstanding Fermat's Little Theorem (or rather, its more general form as Euler's Theorem) which does not state that a multiplicative inverse modulo $\varphi(n)$ is the same modulo $n$. What the theorem says is that if you have an integer $a$ coprime* to $n$, then the following is true:

$$a^{\varphi(n)} \equiv 1 \pmod{n}$$

In other words, the order of the group $(\mathbb{Z}/n\mathbb{Z})^\times$ is $\varphi(n)$. In other words, the relationship above induces a cyclic order on the powers of $a$ modulo $n$, meaning if you keep multiplying $a$ with itself you will eventually get $1$ (not necessarily after exactly $\varphi(n)$ exponentiations, but Lagrange's theorem says that if $k$ is the smallest nonzero $k$ such that $a^k \equiv 1 \pmod{n}$ then $k$ must divide $\varphi(n)$. Perhaps more intuitively, it (informally) means that powers of an integer modulo $n$ behave as if they were taken modulo $\varphi(n)$. Note this says nothing about multiplicative inverses being the same.

So what does this mean? It means that when you raise a plaintext $M$ to the power $e$, you get:

$$M^e \equiv C \pmod{n}$$

So how exactly do you decrypt this? One possibility is to take the $e$th root modulo $n$, but this is expensive and problematic. Fortunately, there is another way. Since we know from above that:

$$M^{\varphi(n)} \equiv 1 \pmod{n}$$

It follows that, for any integer $k$:

$$M^{k \varphi(n) + 1} \equiv M \pmod{n}$$

So we just need to find an integer* $d$ such that $ed = k \varphi(n) + 1$, that is, $ed \equiv 1 \pmod{\varphi(n)}$. Then:

$$C^d \equiv (M^e)^d \equiv M^{ed} \equiv M^{k \varphi(n) + 1} \equiv M \pmod{n}$$

And this is why it works. You are choosing $e$ and $d$ multiplicative inverses of one another modulo $\varphi(n)$ precisely so that their product is congruent to $1$ modulo $\varphi(n)$, and Euler's theorem does the rest. If you are observant you will notice the rule $(M^e)^d = M^{ed}$ really is what makes RSA work as a public key scheme by separating $e$ and $d$, and this is exploited in Diffie-Hellman and some other public key schemes as well.

This doesn't however work if you had chosen $ed \equiv 1 \pmod{n}$, because $kn + 1$ doesn't actually mean anything modulo $\varphi(n)$. There is no structure to be exploited here, and you will just get an arbitrary number that won't help you decrypt $C$. In the same way, multiplicative inverses modulo $n$ do not "carry over" modulo $\varphi(n)$. There is a relationship between integers modulo $n$ and integers modulo $\varphi(n)$, but it is not that simple (I just described that relationship above), and you have to work with that relationship to make your algorithm work.

So the answer to your question is really "because this is how arithmetic works out modulo $n$" :)

* in fact RSA "works" even when the plaintext is a multiple of $p$ or $q$, but never mind that now.

* in practice, $\varphi(n)$ is sufficient but not necessary, and we use $\lambda(n) = \mathrm{lcm}(p - 1, q - 1)$ (the Carmichael function) which is basically $\varphi(n)$ with any prime factors shared between $p - 1$ and $q - 1$ left out - this means we still have all the nice properties that we require for RSA, but with the numbers involved as small as possible (but still secure, of course - knowledge of either $\varphi(n)$ or $\lambda(n)$ is polynomial-time reducible to factoring $n$, so knowing one is equivalent to knowing the other).