Manual implementation RSA java. Padding ideas

Question

I am implementing RSA manually on java (yes i know not the best idea but it is for university purposes). My algorithm is working good enough with small texts but when big texts come into consideration the algorithm breaks as the number of bits is superior than my key.

I am looking into the possibility to implement a padding scheme in order to fragment my plain text into small ones and then encrypt them.

Is there any suggestion on how to the padding?

Thanks in advance.

Answer 1

I'm sorry that I'm writing an answer that contains basically the same information as divanov's answer, but an edit to add all the little details that I think are important would be a complete rewrite of the answer.

Generally you don't want to asymmetrically encrypt your data directly, but instead use RSA to exchange a symmetric key that is used to encrypt your data symmetrically. You can do it like this (idea taken from "Cryptography Engineering" by Ferguson, Kohno and Schneier, a book I can wholeheartedly recommend):

1. Assuming that l is the bit length of your modulus n, generate an l-1 bit long random number r. Encrypt r with the RSA public key.
2. Use a cryptographic hash function to generate the symmetric key k out of r. I would advise the use of sha256: k=sha256(r)
3. Encrypt you data with a block cipher like AES256 using a proper "mode" like CBC.

The advantage of this procedure is that you do not have to care about RSA paddings at all (and there is a lot of stuff that can go wrong with them). Please don't check the structure of r after decrypting, though, and just stuff if into the hash function as you otherwise might open yourself up to padding oracle attacks (akin to this one) that are beyond the scope of my answer though.

Note that for a real world scenario you have to care about authenticity of the data, too. The only common use case where encryption is mostly enough is "data at rest", i.e. if no data is transmitted over the network and you only care about physical theft of your data.

Answer 2

When one needs to encrypt longer plain text than a assymetric key typically random symmetric cipher block key is generated, for example, AES128 and then it is used to encrypt the data. At the end of a process symmetric key is encrypted with RSA public key and saved along with the cipher text.

A decryption consists of recovering symmetric key with a private RSA key and then using the former to decrypt the long message.

One of the reasons to do so is that RSA is much slower than, for example, AES. Another one is that block cipher has no limitation for a size of a message.