0

I am working on the following exercise on the RSA algorithm:

Suppose that Eve has a magic box which creates decryption exponents for $(n, e)$ for a fixed modulus $n$ and for a large number of different public exponents $e$. Let $n = 225022969$. Eve’s magic box gives her the following three encryption/decryption pairs for $n$: $(e_1, d_1) = (70583995, 4911157)$, $(e_2, d_2) = (173111957, 7346999)$, $(e_3, d_3) = (180311381, 29597249)$. Use this information to factor $n$.

My train of thought: we should have the following equations:

$e_1 d_1 = k\phi(n) + 1, \quad k \in \mathbb{Z}$

$e_2 d_2 = s\phi(n) + 1, \quad s \in \mathbb{Z}$

$e_3 d_3 = r\phi(n) + 1, \quad r \in \mathbb{Z}$

Therefore, we can guess $\phi(n)$ and then solve a quadratic equation for $p$ and $q$, where $n = pq$, $\phi(n) = (p-1)(q-1)$.

However, when I factorize $n$ in Wolfram Mathematica, I get that $n = 10867 \cdot 20707$, so none of the equations above is satisfied!

Could you please tell me where I am wrong?

tar_sova
  • 1
  • Are you sure that you're supposed to use Euler's totient $\phi(n)$ rather than Carmichael's totient $λ(n)$? Because all your equations seem to hold for $λ$ – Fotis Jun 04 '23 at 14:48
  • @Fotis, thank you for your comment. Indeed, it is said in my textbook that the Euler's totient function should be used here. – tar_sova Jun 04 '23 at 14:56
  • 1
    Interesting, well, then probably there's a mistake in the exercise, since like you pointed out, none of the three equations have solutions for φ(n) – Fotis Jun 04 '23 at 15:17

0 Answers0