# Why is RSA considered safe?

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?

• The attacker doesn't know $\varphi(n)$ – CodesInChaos Dec 25 '17 at 18:17
• But CodesinChaos the attacker can calculate φ(n) right ? They is a lot of website help calculate it online , huh ? – user9119852 Dec 25 '17 at 18:59
• 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$. – SEJPM Dec 25 '17 at 19:27
• @user9119852 It seems you have created two accounts, you might want to get them merged. Have a look at our help center. – SEJPM Dec 26 '17 at 11:16
• Yeah thank you @SEJPM ! I accidentally create one for mobile one for computer , thanks ! – AlphaBetA Dec 26 '17 at 15:15

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