Which cryptographic attack here is feasible on RSA?

Sir Muffington

3/19/24, 7:32 PM

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)

0 + 3

key-recovery

fgrieu

3/19/24, 8:37 PM

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.

dave_thompson_085

3/19/24, 11:52 PM

@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.)

fgrieu

3/20/24, 6:01 AM

@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.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Which cryptographic attack here is feasible on RSA?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.