3

Standing back from the details, RSA does

$m^{ed}=m \mod pq$

Where e is a constant and d is the private key.

Now $e$ and $pq$ are coprime, so $e^{-1} \mod pq$ should be easy to determine using the extended euclidean algorithm. (Note, $\mod pq$, not $\mod (p-1)(q-1)$. Then trivially

$(m^e)^{e^{-1}} = m^{ee^{-1}} = m^1 \mod pq$

Somehow I doubt that I have broken RSA, so what is wrong with this analysis?

(RSA also uses multiplicative inverses in the full algorithm, but that is not my point.)

Tuntable
  • 133
  • 13
    The pertinent congruence to solve is $ed\equiv1$ mod $\phi(pq)$, which requires that you know the value of $\phi(pq)$, which basically means you know $p$ and $q$. – Barry Cipra Jul 06 '21 at 23:54
  • You must know the prime factors in order to invert $e$, but these are hidden. – Randall Jul 07 '21 at 00:09
  • It’s not necessarily that $e$ and $pq$ are coprime (though clearly it would be a security fail if you allowed that). The quantities that must be coprime for RSA to function are $e$ and $(p-1)(q-1)$. – Erick Wong Jul 07 '21 at 00:24
  • I know how RSA works. But my alternative simply calculates $e^{-1}$ for pq which should be easy. At that point the cypher unravels. So what is wrong with this approach? – Tuntable Jul 08 '21 at 00:41
  • @Tuntable You have a misconception about how RSA works. I think the answer by Andrew Li hits the nail on the head. – Erick Wong Jul 08 '21 at 02:49
  • @Tuntable if you think your method works, you should actually try it on a few examples. – Randall Jul 08 '21 at 12:26

1 Answers1

4

In general, $a \equiv b \pmod{N}$ does not imply $c^a \equiv c^b \pmod{N}$. The error in your logic is assuming that $m^{ee^{-1}} \equiv m^1 \pmod{pq}$ is always true if $ee^{-1} \equiv 1 \pmod{pq}$ is true.

As an example, take $N = 5$, $a = 0$, $b = 5$, $c = 2$. $2^0 \equiv 1 \not\equiv 2 \equiv 2^5 \pmod{5}$.