1
$\begingroup$

I was told that you can determine the private key of an RSA encryption with the public key.

I thought the point of a public key was to avoid letting people find the private key, but anyway, they said I could find it by simply factoring the public key modulus? Were they joshing me or can it be done? If so, how would I do that (need to acquire $p,q$ somehow?)?

So with with example Public Key $( e, n ) = ( 13, 119 )$ or any other valid key you want to use...

Improve this question
$\endgroup$
1
  • $\begingroup$ Note that solving a Sudoku is also considered a hard problem, given large enough dimensions of the Sudoku. Hard problems are not impossible problems; they are just hard to solve for large enough puzzles. $\endgroup$
    – Maarten Bodewes ♦
    Oct 21 '19 at 14:26
2
$\begingroup$

I was told that you can determine the private key of an RSA encryption with the public key. Were they joshing me or can it be done?

Yes, it can be done. What you have not been told is that to factor a public key (usually hundreds of digits) to find the private key, requires a time exponential in the length of the public key, therefore even a supercomputer could take years, if not centuries. Factorization is believed to be a Hard Problem. On the other hand, if you already know the private key, you can get the plaintext in very few CPU's cicles. This is the general principle underlying asymmetric cryptography:

Improve this answer
$\endgroup$
12
  • $\begingroup$ There are known subexponential (but superpolynomial) factoring algorithms. $\endgroup$
    – Maeher
    Oct 21 '19 at 14:07
  • $\begingroup$ A "second" is a specific amount of time. Maybe you could think of another term? (My brain has trouble to come up with a good synonym, I must admit.) Um, "almost instantly" or" directly" would present themselves. $\endgroup$
    – Maarten Bodewes ♦
    Oct 21 '19 at 14:08
  • $\begingroup$ @MaartenBodewes what about "in very few CPU cycles"? If it fits better, I change the answer. $\endgroup$
    – Yamar69
    Oct 21 '19 at 14:12
  • $\begingroup$ @Maeher I know but assuming basic knowledge from the OP I didn't want to complicate things for him. $\endgroup$
    – Yamar69
    Oct 21 '19 at 14:14
  • 2
    $\begingroup$ @Anan 7354943 it's a RIDICULOUSLY small number ... RSA public keys can have 1000+ digits. $\endgroup$
    – Yamar69
    Oct 21 '19 at 14:27

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.