1
$\begingroup$


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!

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – kelalaka Jun 6 at 10:53
  • 2
    $\begingroup$ In addition, 512 bit RSA keys are far too small nowadays; they should be at least 2048 bits... $\endgroup$ – poncho Jun 6 at 12:27
3
$\begingroup$

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!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.