How should I address message size limits in RSA encryption?

Question

I am making an end-to-end encryption software program in Java using RSA. I am using BigIntegers and its number theory methods. (I know this is a very slow approach, but I just want to learn to the concept of encryption through this). I have a lot of questions, feel free to only answer as many as you'd like.
I have most of the encryption done already but I have questions about the size limitations of RSA and its technical details.

Say I generate primes p and q for my RSA which are of bit length 256 and 257. According to my intuition on the number theory behind it (using modulus) and a lot of test cases, I should be able to safely encrypt and decrypt any number with bit lengths L < 513 (256+257) without losing information. Is this correct and will work 100% of the time? Also if L happens to be a 5-bit number, its encrypted version will still be around ~512 bits long?

I want to abstract my BigInteger (Java class) encryption to encrypting any byte[] of data. My plan is to split the byte[] into 512-bit (64-byte) chunks and encrypt those chunks by converting them to a BigInteger and then encrypting them. Is this a good idea? How is it done in industry?

Should I make the bit length of p and q smaller/larger and make the encryption chunks size smaller/larger to optimize performance?

Also, after I encrypt a number, the encrypted version ranges anywhere between 0 and 512 bits. How should I added padding to this byte[], in order to keep them of uniform size, for easy decrypting? Should I just add 0's to the most significant bit side and pad until it is always 512 bits?

Thank you so much for the help in advance!

Answer 1

I should be able to safely encrypt and decrypt any number with bit lengths L < 513 (256+257) without losing information. Is this correct[?]

No. The RSA operation $x \mapsto x^e \bmod n$ is unfit to ‘encrypt’ even short messages directly.

Here is what you should do:

• Pick a hash function $H$ up front, like SHA-256 or SHAKE128, and bake it into your program. (Don't let users pick it—users have even less of an idea of what's up.)
• Pick a symmetric-key authenticated cipher up front, like AES-GCM or NaCl crypto_secretbox_xsalsa20poly1305, and bake it into your program. (Again, don't let users pick it.)
• To encrypt a message $m$, which is a bit string of arbitrary length, for public key $n$:
  1. Choose an integer $x$ with $0 \leq x < n$ uniformly at random.
  2. Compute $y = x^3 \bmod n$.
  3. Compute $k = H(x)$, where $x$ is encoded as a bit or octet string in some standard way, e.g. little-endian.
  4. Encrypt $m$ using your authenticated cipher under the key $k$, giving a ciphertext $c$.
  5. Send $y$ and $c$. $y$ is called the encapsulation of the key $k$.
• To decrypt a ciphertext $c$ with key encapsulation $y$:
  1. Solve $y \equiv x^3 \pmod n$ for $x$. (E.g., compute $x = y^d \bmod n$ where $d$ solves $e d \equiv 1 \pmod{\phi(n)}$, or compute $x_p = y^{d_p} \bmod p$ and $x_q = y^{d_q} \bmod q$, and then combine using the Chinese remainder theorem, etc.)
  2. Compute $k = H(x)$.
  3. Decrypt $c$ using your authenticated cipher under the key $k$.
     • If decryption fails, drop it all on the floor and stop here. (If you skip this step, you are setting yourself up for efailure.)
     • Otherwise, it returns a message $m$, which is the plaintext message you return in the end.

This system—generating a symmetric key $k = H(x)$ for uniform random $x$ and concealing it as $x^3 \bmod n$—is called RSA-KEM, and it is an example of a public-key key encapsulation mechanism, which can be generically composed with an authenticated cipher to get public-key (anonymous) encryption.

Also if L happens to be a 5-bit number, its encrypted version will still be around ~512 bits long?

With the system above, the ciphertext overhead is 128 bits for the authenticated cipher (or more, if it's a particularly inefficient authenticated cipher), plus the size of your modulus $n$, no matter how long the message is.

You should not use 512-bit moduli. They have been breakable in practice by the public for decades. You should use at least 2048-bit moduli. More details.

Alternatively: Just use NaCl crypto_box, or libsodium crypto_box_seal. Faster, smaller, safer than RSA!