True or false: "If you can compute $x = \sqrt[e]{y} \mod N$ (e-th root), then you can also factor $N = p \cdot q$."
Not proven! The reverse direction (factoring ⇒ e-th root) IS proven, but whether computing e-th roots implies you can factor has never been demonstrated.
* Factoring is sufficient to break RSA, but nobody has shown it is necessary — a hypothetical e-th-root shortcut could exist without factoring. *
What we know:
- Factoring → e-th root: ✓ Proven. If you factor $N = p \cdot q$, you compute $\varphi(N) = (p-1)(q-1)$, then $d = e^{-1} \mod \varphi(N)$, then $x = y^d \mod N$.
- e-th root → Factoring: ✗ NOT proven. There might exist a method to compute e-th roots without ever learning the factors of N.
Why this matters:
- RSA's security is often described as "relying on the hardness of factoring"
- More precisely: RSA relies on the hardness of computing e-th roots mod N
- Factoring is sufficient to break RSA, but may not be necessary
- If someone found a way to compute e-th roots without factoring, RSA would be broken even though factoring remains hard
The practical implication: because factoring breaks RSA, RSA can never be harder to break than factoring $N$. The cost of factoring is therefore an upper bound on the attack effort, and factoring records (currently ~829 bits) tell us which key sizes are definitely too small. RSA could only turn out easier, if someone found an e-th-root shortcut that avoids factoring.
Go deeper:
The RSA problem (Wikipedia) — the open question of whether the RSA problem is equivalent to factoring.