0
$\begingroup$

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

$\endgroup$
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$
  • $\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$ – aguellier Apr 26 '16 at 11:17

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.