0
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ $(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? $\endgroup$
    – poncho
    Oct 23 '21 at 19:22
  • $\begingroup$ Yes, it should be vulnerable. @poncho $\endgroup$
    – Cryptomathician
    Oct 23 '21 at 19:49
1
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ 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? $\endgroup$
    – Cryptomathician
    Oct 23 '21 at 19:56
  • 1
    $\begingroup$ @Cryptomathician: well, if $e$ and $n$ are not relatively prime, then $e^{-1} \bmod (n \cdot \phi(n))$ wouldn't exist. $\endgroup$
    – poncho
    Oct 23 '21 at 22:32
  • $\begingroup$ ok, got it. Thank you for the detailed explanation. $\endgroup$
    – Cryptomathician
    Oct 23 '21 at 22:46
  • $\begingroup$ 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 $\endgroup$
    – Cryptomathician
    Oct 23 '21 at 23:33
  • 1
    $\begingroup$ @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)}$ $\endgroup$
    – poncho
    Oct 24 '21 at 2:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.