Why isn't RSA trivially broken using Multiplicative Inverse?

172 Views Asked by At

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.)

1

There are 1 best solutions below

0
On BEST ANSWER

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}$.