I am doing a tutorial where my lecturer (PhD) gave me an optional question to do relating to RSA.

He said: write a python function that takes as input the server’s public key and then uses that to compute the server’s private key. Print out the server’s private key to standard out.

Because according to him, 16-bit or 17-bit keys can be easily factorized on your computers.

How am I able to do this. I have searched all over and people have said RSA private keys cannot be generated by public keys.

I am asking for guidance, please.

  • $\begingroup$ Hint: Wolfram alpha can factor that very easily or the factor command in Unix. $\endgroup$ – kelalaka Nov 19 '19 at 22:27
  • $\begingroup$ Yes, but I am seeking to construct the Python function $\endgroup$ – Jermaine Hall Nov 19 '19 at 22:28
  • $\begingroup$ Did you hear sieve $\endgroup$ – kelalaka Nov 19 '19 at 22:35
  • $\begingroup$ Just use the Sagemath $\endgroup$ – Woodstock Nov 19 '19 at 22:42
  • 2
    $\begingroup$ For RSA keys of the size actually used factoring is practically impossible -- the best known algorithms would use more energy than exists, and take longer than the universe's lifetime. For 16 bits it is trivial, and in fact up to about 800 bits is currently practical, which is why 1024-bit keys, which were formerly common, have been deprecated or prohibited since about 2014 and most people today use 2048-bit. $\endgroup$ – dave_thompson_085 Nov 20 '19 at 4:57

Take the server’s public key.

Parse the modulus and public exponent.

(A public key contains the public exponent and modulus)

Factor the modulus into p and q elements.

Calculate the private key as normal.


1) calculate $$Carmichaels$$ $$totient:$$ $$\phi= lcm (p-1)(q-1) $$

2) calculate d the private key as $$d*e\equiv 1mod \phi$$

3) celebrate


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.