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)
openssl rsautl -encrypt -rawdoes 'textbook' (unpadded) RSA encryption, subject to Hastad's attack. The officially obsolete but still widely recommended and usedopenssl genrsato 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$-rawoption 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$