2
$\begingroup$

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?

$\endgroup$
  • 4
    $\begingroup$ The attacker doesn't know $\varphi(n)$ $\endgroup$ – CodesInChaos Dec 25 '17 at 18:17
  • $\begingroup$ But CodesinChaos the attacker can calculate φ(n) right ? They is a lot of website help calculate it online , huh ? $\endgroup$ – user9119852 Dec 25 '17 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$ – SEJPM Dec 25 '17 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$ – SEJPM Dec 26 '17 at 11:16
  • $\begingroup$ Yeah thank you @SEJPM ! I accidentally create one for mobile one for computer , thanks ! $\endgroup$ – AlphaBetA Dec 26 '17 at 15:15
5
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.