Why is RSA encryption key based on modulo $\varphi(n)$ rather than modulo $n$?

Question

While calculating RSA encryption key we take modulo $\varphi(n)$ rather than modulo $n$. I can’t understand why it’s done this way.

Answer 1

Firstly, a number theory textbook might well help here. I own An Introduction to the theory of numbers which will give you a grounding in this and many other number theory topics which crop up in crypto. It's not my favourite book notation-wise, but in terms of topics covered it is very thorough.

Now, on to what you need help with. There exists a theorem called the division theorem that says any number $n = pq + r$, with the constraints that $n > q > r \geq 0$. In plain words, any number $n$ may be represented by a quotient $q$ (possibly multiplied by a number $p$) and a remainder $r$. An example would be to say that $13 = 7 + 6$ - you recognise this in that $13/7$ could be written as "$1$ remainder $6$".

Modular arithmetic is related - let's start off with $13 \equiv 6 \mod 7$. Intuitively, modular arithmetic is often explained as "you take the remainder and that is the result" which isn't far from the truth - what we actually say is that $7$ and $13$ are part of the same congruence class - that is, $q$ and $r$ ($7$ and $6$) remain the same and the congruence class is made up of all the $n$ for all the $p$ possible. So for $p=2$, $n = 2*7 + 5 = 19$. So $19\equiv 5 \mod 7$ (feel free to check it!).

So, you're concerned with the use of $\mod \phi(n)$ in RSA - well the expression usually given is $de = 1 \mod \phi(n)$. We can re-write that in division-theorem form as $de = k\phi(n) + 1$ - where $k$ is $p$ from the previous example, but renamed so as not to be confused with the prime $p$ that forms $n$.

Now observe what you may have learnt about exponents - that $x^{a+b} = x^ax^b$ and that $x^{ab} = (x^a)^b)$ If you're not convinced, pick numeric examples. Now, a message $m$ raised to the power $de$ is $m^{de}$ - but we have a different expression for $de$ already - that is - $m^{de} = m^{k\phi(n) + 1}$. This can then be written as $(m^{\phi(n)})^k \times m^1$.

There is a very good reason for this form being desirable - namely the Euler-Fermat generalisation to Fermat's Little Theorem, which states that:

$$a^{\phi(n)} = 1 \mod n$$.

Hopefully you should see that our manipulating the algebra to get $m^{\phi(n)}$ in it is not an accident at all - since under $\mod n$, $(m^{\phi(n)})^k \times m^1$ becomes $1^k \times m^1 = m$. This is what makes RSA work the way it does.

I'd also like to address the point fgrieu has raised in his comment, since it is important. The requirement is for the private key is such that $de = 1 \mod \phi(n)$ - or $de = 1 + k\phi(n)$. Clearly, $k$ can be any number we like - any congruence class for which this relation holds will work.

The lowest common multiple of two numbers is the smallest possible number such that both these numbers divide it - for example, the lowest common multiple of $4$ and $6$ is $12$. n this case we observe $4$ divides $12$, as does $6$. Now, the lowest common multiple of $p-1, q-1$ is a number such that both $p-1$ and $q-1$ divide it - well $\phi(n)$ is one such number, for starters! However, (thanks to Poncho), we can say that it is not the smallest possible number. To explain this, consider that $p$ is an odd number and that odd numbers can all be written of the form $2k+1$ for some $k$. If we subtract one, we are left with an even number which will have at least one factor of $2$. Therefore, since $p-1$ and $q-1$ are both even and both have a factor of two, their product ($\phi(pq)$) will have two factors of $2$ at the least, which is 2x what is necessary (at the minimum). More generally, the definition of a lowest common multiple uses the fundamental theorem of arithmetic to demonstrate that the lcm is in fact equal to the product of the maximum power each prime is raised to in each number's prime expansion - eurgh, yes? Well, let's look at that. I chose $4$ and $6$ before - now the prime expansions are $4 = 2^2$ and $6=2\times 3$. Taking the maximum exponentiation of each prime, $2^2 \times 3 = 12$. However, if we did $4\times6 = 2^2 \times 2 \times 3 = 2^3 \times 3$ we see we have gained an extra, unnecessary factor of $2$.

It turns out the Euler-Fermat generalisation can be generalised again - to the Carmichael theorem which states that:

$$a^{\lambda(n)} = 1 \mod n$$

Where $\lambda(n)$ is the smallest such integer where this expression is true. A slight detour - $\phi(pq)=\phi(p)\phi(q)$ and since $\phi(p) = p-1$ that is how we end up with our definition of $\phi(pq)=(p-1)(q-1)$. Now, in the general case, it turns out that $\lambda(pq) = lcm(\lambda(p), \lambda(q)) = lcm(p-1, q-1)$. By the same reasoning as the case with $\phi(pq)$, $de = 1 \mod \lambda(pq)$ allows us to invert $m^e$ back to $m$ under $\mod n$.

fgrieu has used the term "Rings" - if you're interested in those, I highly recommend Rings, Fields and Groups which is possibly the best Maths textbook I have ever read. It's about (abstract) algebra and also covers some of the number theoretic points, but not as many as a pure number-theory textbook does.

Answer 2

In RSA, the public key is $e$ and private key is $d$, if:

$ed=1 \mod{\phi (n)} $

To rearrange:

$d=e^{-1} \mod{\phi (n)}$

In an public key system, it should be the case that one cannot compute the private key from the public key. Therefore, at least one of the variables should be kept private. In the above equation, everyone knows $e$, everyone can compute inverses, and if you were to use $n$ as the modulus, that would be known as well, allowing anyone to compute $d$.

The reason $\phi (n)$ is used as the modulus is that it is assumed to be hard to compute $\phi (n)$ given only $n$, but it is easy to compute if you know $p$ and $q$ such that $n=pq$: $\phi(n)=(p-1)(q-1)$. Essentially, the easiest way to compute $\phi (n)$ is to factor $n$ into $p$ and $q$, and then compute it.

There are deeper reasons why it is specifically $\phi (n)$ but this should get you started.

Answer 3

One usually wants to get back the plain text by decrypting the cipher text obtained by encrypting the plain text.

This works for RSA only by taking $d = e^{-1} \bmod \varphi(n)$ and NOT with $d = e^{-1} \bmod n$.

Security issues don't matter if the method does not work.

Answer 4

Better to view $ed \equiv 1 \pmod{\varphi (N)}$ as $ed=1 + k\varphi (N)$, then when we exponent message as $m^{ed}$ it becomes $m^{1 + k\varphi (N)}$, where $k\varphi (N)$ part strips out because of Euler's theorem $a^{\varphi(n)} \equiv 1 \pmod {n}$, so we get $\space m(m^{\varphi (N)})^k \equiv m$.

So if you use $ed \equiv 1 \pmod{N}$ it will be $ed=1 + kN$ which will make Euler's theorem not applicable.

Answer 5

I understand the question as follows:

Why don't we compute the private key modulo $n$ instead of modulo $\varphi(n)$?

The other answers already imply this, but here in short:

As Someone's answer states, the decryption wouldn't work: $x \neq (x^e \mod n)^{e_{n}^{-1}}$, where $e_{n}^{-1}$ is the inverse of $e$ modulo $n$ (the secret key).

From Euler's theorem: $a^{\varphi(n)} \equiv 1 \mod n$ we know $a^{e\mod\varphi(n)} \equiv a^e\mod n$.

But $a^{e\mod n} \not\equiv a^e\mod n$ (generally).

Therefore, $a^{ee_{\varphi(n)}^{-1}} \equiv a \mod n$, but $a^{ee_{n}^{-1}} \not\equiv a \mod n$.