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$ Commented Oct 23, 2021 at 19:22
  • $\begingroup$ Yes, it should be vulnerable. @poncho $\endgroup$ Commented Oct 23, 2021 at 19:49

1 Answer 1

Reset to default
2
$\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$ Commented Oct 23, 2021 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$ Commented Oct 23, 2021 at 22:32
  • $\begingroup$ ok, got it. Thank you for the detailed explanation. $\endgroup$ Commented Oct 23, 2021 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$ Commented Oct 23, 2021 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$ Commented Oct 24, 2021 at 2:42

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.