# RSA: why $( e^{-1} ~\text{mod}~ n \cdot \varphi(n)) ~\text{mod}~ \varphi(n) = e^{-1} ~\text{mod}~ \varphi(n)$ holds for a specific setting of RSA

Let $$p,q$$ are primes and $$n = pq$$ as in every RSA setting and now use a random $$e$$ that holds the following properties

• $$gcd(e, \phi(n)) \neq 1$$
• $$(e^{-1} ~\text{mod} ~\phi(n))^{4}\cdot3 < n$$
• $$e^{-1} ~\text{mod} ~\phi(n) < \sqrt[3]{n}$$ (integer square root), where $$\sqrt[3]{n} \in \mathbb{Z}$$

where $$\phi$$ is euler's totient function. This $$e$$ is used as the public exponent for the public key and $$d$$ is the private exponent for the private key.

Remember that $$\phi(n) | ed - 1$$, as $$ed = 1 + k \cdot \phi(n)$$ holds for $$k \in \mathbb{Z}$$. The question is, why it holds that $$(e^{-1} ~\text{mod}~ n \cdot \phi(n)) ~\text{mod}~ \ \phi(n) = e^{-1} ~\text{mod}~ \phi(n)\text{?}$$ Could someone explain it mathematically or give a proof why that holds?

A related question regarding multiple of $$\phi(n)$$ is asked in this question. Unfortunately, I don't understand the relation between the multiple of $$\phi(n)$$, the $$gcd$$ and why this equation $$ed = 1 ~\text{mod}~ k \cdot \phi(n)$$ holds $$ed = 1 ~\text{mod}~ \phi(n)$$ for $$k \in \mathbb{Z}$$.

Additionally it would be nice to read a proof for the related question regarding the multiple of $$\phi(n)$$, if someone knows why that holds.

• $(e^{-1} \bmod \phi(n))^4 \cdot 3 < n$ is certainly not standard with RSA, and I probably yields an RSA public key that is vulnerable to attack. Are you modelling such a weak RSA key? Oct 23 '21 at 19:22
• Yes, it should be vulnerable. @poncho Oct 23 '21 at 19:49

The question is, why it holds that $$(e^{−1} \bmod n \cdot \phi(n)) \bmod \phi(n)=e%{−1} \bmod \phi(n)$$?

Actually, we have the more general identity $$(A \bmod BC) \bmod C \equiv A \bmod C$$, for any integers $$A, B, C$$. In your specific case, we have $$A = e^{-1} \bmod \phi(n)$$, $$B = n$$, and $$C = \phi(n)$$

This more general identity can be easily be seen from two facts:

$$X \bmod Y = X + k \cdot Y$$ for some integer $$k$$ (which may be negative)

$$X \bmod Y = Z \bmod Y$$ if and only if $$X - Z = k'\cdot Y$$ for some integer $$k'$$.

From the first fact, we can see that $$A \bmod BC = A + kBC$$ (for some integer $$k$$ - we don't care what that integer is)

From the second fact, we see that $$(A + kBC) \bmod C = A \bmod C$$ holds if we have $$A + kBC - A = k'C$$ for some integer $$k'$$; we can immediately see that this holds for the integer $$k' = kB$$, hence this is true.

Since the general identity holds in all cases, it also holds in your specific case.

• thank you. I am wondering where the gcd plays a role like it is mentioned in the "correct" answer of the related question on the mathoverflow stackexchange. Should be e and n coprime ($gcd(e,n)$) to hold that identity? Oct 23 '21 at 19:56
• @Cryptomathician: well, if $e$ and $n$ are not relatively prime, then $e^{-1} \bmod (n \cdot \phi(n))$ wouldn't exist. Oct 23 '21 at 22:32
• ok, got it. Thank you for the detailed explanation. Oct 23 '21 at 22:46
• is it a different question when I want to know when $y = x^{-1} ~(\text{mod}~ k \cdot \phi(n))$ holds, so that also $xy \equiv 1 ~(\text{mod}~ \phi(n))$ holds for some $k \in \mathbb{Z}$ ? I was trying to figuring out when this holds, too. @poncho Oct 23 '21 at 23:33
• @Cryptomathician: actually, it holds for all $k \in \mathbb{Z}$; same sort of logic: $y = x^{-1} \pmod{k \phi(n)}$ means there is a $k' \in \mathbb{Z}$ with $yx = 1 + k'( k \phi(n))$; this implies that there is a $k''$ with $yx = 1 + k'' \phi(n)$, that is, $yz \equiv 1 \pmod{\phi(n)}$ Oct 24 '21 at 2:42