Textbook RSA security for fully random message

Jakub Rogacz

3/16/24, 9:58 PM

I am asking this since I can't find definite answer.

Is it secure if I use textbook RSA provided all my data is 2048 bits ( or any N <=2048 for 2048 bit key ) and it is random ( using Secure Random in Java for example) ?

Or should I figure out maximal key length under padding scheme and use padding anyway ?

1 + 2

zero-knowledge-proofs

padding

bk2204

3/17/24, 12:26 AM

You're going to be better off using padding with something like a 256-bit key (or a secure hash algorithm for signing). Any larger key is overkill and it's a lot easier to securely use a normal cryptographic library with padding than to try to securely do it without.

fgrieu

3/17/24, 6:44 AM

Notice that you can not encipher then successfully decipher any 2048-bit bitstring using RSA and a 2048-bit public modulus (slightly improperly: 2048-bit key). Problem is, the integer encrypted must be (strictly) lower than the public modulus $n$. For example, the all-ones bitstring would decipher to $2^{2048}-n-1$.

Score:2

Crypto

Maarten Bodewes

3/17/24, 3:34 AM

Your description of the algorithm looks a lot like RSA-KEM, which is considered secure. However, note that the (b) argument of the security proof indicates that "the input is independent of the keying data so the result of the RSA decryption operation is not directly available to an adversary."

So if you use this as RSA-KEM, i.e. follow it up with a non-invertible function like a key derivation function which is secured against side channel analysis, then yes, it is assumed to be secure.

You might as well study RSA-KEM and specify RSA-KEM as your algorithm in that case.

+ 1

Maarten Bodewes

3/17/24, 3:34 AM

PS I've got a little algorithm called [RNG-BC](https://github.com/owlstead/RNG-BC) which is really efficient calculating a random between 0 and N. It's especially useful in cases where N is not a special number that has most of the significant bits set to 1, e.g. RSA-KEM where the modulus is randomized. Use it if your RNG is slow and you don't want to use any big integer operations.

Elon Musk

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

EN: Textbook RSA security for fully random message

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.