# How should I address message size limits in RSA encryption?

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!

• RSA should not be used for encryption, even so, you should use it with proper padding. Otherwise, you are open to many attacks. See this or search for RSA-OAEP. If you want to use RSA, you should use it as key exchange and better use Diffie-Hellman Key exchange over Elliptic Curves. – kelalaka Jun 6 '19 at 10:53
• In addition, 512 bit RSA keys are far too small nowadays; they should be at least 2048 bits... – poncho Jun 6 '19 at 12:27

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!