Why is RSA safe, using this algorithm to calculate $d$ as the private key? $$e\cdot d \equiv 1 \pmod{\varphi(n)},$$ where $e$ is part of the public key and $n$ is also part of the public key, so there is only one variable the attacker doesn't know, and that is $d$? Why can't they can use the extended Euclidean algorithm to calculate it? Even if they can't, why is it considered safe?
$\begingroup$
$\endgroup$
5
-
4$\begingroup$ The attacker doesn't know $\varphi(n)$ $\endgroup$– CodesInChaosCommented Dec 25, 2017 at 18:17
-
$\begingroup$ But CodesinChaos the attacker can calculate φ(n) right ? They is a lot of website help calculate it online , huh ? $\endgroup$– user9119852Commented Dec 25, 2017 at 18:59
-
4$\begingroup$ Calculating $\varphi(n)$ is equivalent (-> as hard as) factoring $n$, which is "easy" for small values of $n$ (so websites can do it), but infeasible for cryptographically relevant values of $n$. $\endgroup$– SEJPMCommented Dec 25, 2017 at 19:27
-
$\begingroup$ @user9119852 It seems you have created two accounts, you might want to get them merged. Have a look at our help center. $\endgroup$– SEJPMCommented Dec 26, 2017 at 11:16
-
$\begingroup$ Yeah thank you @SEJPM ! I accidentally create one for mobile one for computer , thanks ! $\endgroup$– AlphaBetACommented Dec 26, 2017 at 15:15
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Yes, theoretically anyone can compute $\varphi(n)$ from $n$ and thus recover $d$ from $e$. This should be read as "given any $n$, it takes a finite amount of time to compute $\varphi(n)$".
More practically, "computing $\varphi(n)$ given $n$" and "factoring $n$" are equivalently hard. That is, if you can efficiently compute $\varphi(n)$ you can also efficiently factor $n$ and vice versa.
Now, if $n$ is sufficiently small, we can easily factor it and thus compute $\varphi(n)$ (which is what websites do), but as $n$ reaches cryptographically relevant values, it becomes infeasible (using current technology) to factor $n$ and thus to recover $\varphi(n)$.
