# RSA keys are multiplicative inverse in mod phi(n), but also in mod n?

I understand that the RSA keys $pk$ and $sk$ are choosen such that one is the multiplicative inverse of the other, in $\mod \phi(n)$

But for the encryption and decryption to work, in other words, that

${m^{pk}}^{sk} \mod n = m$

holds, $pk$ and $sk$ must also be multiplicative inverse to each other in $\mod n$, right?

• Why do you think this must be the case? – fkraiem Apr 6 '17 at 14:07
• (Of course, this is obviously false; just generate a keypair and you will see that decryption works even though the keys are not inverse modulo $n$.) – fkraiem Apr 6 '17 at 14:10

I understand that the RSA keys $pk$ and $sk$ are chosen such that one is the multiplicative inverse of the other, in $\bmod \phi(n)$

Mostly correct. Actually, they're always multiplicative inverses modulo $\lambda(n) = \phi(n) / \gcd(n)$; selecting them as inverses modulo $\phi(n)$ does work (they will encrypt and decrypt properly), but using the smaller $\lambda(n)$ also works, and yields smaller key values.

$pk$ and $sk$ must also be multiplicative inverse to each other in $\bmod n$, right?

That is wrong; $pk \cdot sk \bmod n$ need not be any specific value; there's no reason it needs to be 1. One trivial example is $n = 85, e = 5, d = 13$; in this case, $e$ is not relatively prime to $n$, hence it doesn't have a multiplicative inverse.

After all, when you look at ${m^{pk}}^{sk} \bmod n$, you're not multiplying by $pk$ or $sk$; you're raising $m$ to the power of $pk, sk$; those are different operations.

• Hmm it looks like I am still misunderstanding something crucial. I mean..${m^{pk}}^{sk}$ is the same as $m^{sk*pk}$, and that must be $m^1$, so $pk * sk$ must be 1, right?This is why I thought pk must be the inverse of sk. – user66875 Apr 6 '17 at 14:25
• @user66875: yes, however $m ^ {pk \cdot sk} = m ^ {pk \cdot sk \bmod \lambda(n)}$, and so the idea that they are inverses modulo $\lambda(n)$ already captures that notion... – poncho Apr 6 '17 at 14:27

Theorem. Let $a$ be an element of a finite group $G$ and $b,c$ be integers. Then $a^b = a^c$ in $G$ if and only if $b$ and $c$ are congruent modulo the order of $a$ in $G$ (that is, the smallest positive integer $k$ such that $a^k = 1$).

In the special case where $G$ is the multiplicative groups of integers modulo $n$, the order of $a$ is a divisor of $\varphi(n)$ (the order of the group), thus in order to have $(a^\mathrm{pk})^\mathrm{sk} = a^{\mathrm{pk}\cdot\mathrm{sk}} = a$ it is sufficient to have $\mathrm{pk}\cdot\mathrm{sk} \equiv 1 \pmod{\varphi(n)}$. This does not imply anything about how congruent they are modulo $n$.