I'm new to cryptography, so please don't bash me.

I'm trying to learn to recover a RSA private key. As you can see from my profile I'm a cybersecurity professional, which is only now trying to learn some cryptography..

Let's assume we have 5 message and public keys derived from the same string message. It is short (the string content and keys), 1024-bit public key and a public exponent of either 5 or 65537 is being used for ALL the public keys.

How would you approach this problem?

I read that this falls either under too small or too big public exponent category and hence the owiener package on PyPi should be ideal for it.

I tried Garner's formula, Owiener package on PyPi and CRT and none of them worked apparently :( I mostly got division by zero errors.

I am a hands-on person that tried this in practice - I used openssl for producing the keys and content. I would appreciate some guidance in the right direction.

I have the following:

  • ciphertext
  • 5 moduli from the key
  • 5 public exponents from the keys (I think I found a bug in OpenSSL though, that's why two exponents and this is all for learning anyways)
  • $\begingroup$ I strongly suspect that 1) It's actually given as many ciphertexts as there are moduli. 2) The actual goal is not to "recover a RSA private key", and correspondingly the question is tagged incorrectly; but rather the goal is to decipher a common plaintext that was encrypted using textbook RSA. 3) The openssl command line tool won't let one make that mistake, other than perhaps deliberately. If I'm wrong, leave a comment. $\endgroup$
    – fgrieu
    Mar 19 at 20:37
  • 2
    $\begingroup$ @fgrieu+ openssl rsautl -encrypt -raw does 'textbook' (unpadded) RSA encryption, subject to Hastad's attack. The officially obsolete but still widely recommended and used openssl genrsa to generate an RSA keypair uses e = 65537 (aka F4, the Fermat prime $2^{2^4}+1$) or 3, but not 5. (Commandline on versions below 3.0 also generates (FF)DH parameters with generator aka base, not exponent, 2 or 5.) $\endgroup$ Mar 19 at 23:52
  • $\begingroup$ @dave_thompson_085: That -raw option had went under my radar. At least, it's use falls under the "deliberately" umbrella, and happens to match the OP's need. I guess it has a few other uses, like a building block for ad hoc implementation of ISO/IEC 9796-2 signature or other padding. $\endgroup$
    – fgrieu
    Mar 20 at 6:01


Browse other questions tagged or ask your own question.