0
$\begingroup$

I mean, $n$ can also be easily used to find the factors $p$ and $q$ right?

$\endgroup$
1

1 Answer 1

5
$\begingroup$

No, it is not easy! RSA is based on the difficulty of factoring the product $n=pq$ of two large prime numbers. But if you know $\varphi(n)$ for plain RSA you can compute the secret exponent $d=e^{-1}\bmod \varphi(n);\;$ and you can factor $n$ from the two equations $n=pq,\;\varphi(n)=(p-1)(q-1)$.

$\endgroup$
1
  • $\begingroup$ In general, it is easy to find the prime factors of any numbers. But here, p and q are taken so large (at least 512 bits) that it takes an veery long time. And thus we talk about the hardness of factoring the product of (very) large primes. $\endgroup$
    – aguellie
    Commented Apr 26, 2016 at 11:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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