RSA Encryption Time with Different Block Sizes

Question

I was working on encrypting a few files on my computer and I was using OAEP for padding with RSA. I noticed that it was taking a long time to encrypt some of my files with a small block size, so I tried to encrypt the same files with a much larger block size and it finished encrypting incredibly fast. I was thinking that the number of encryption cycles since there were so many blocks and/or the amount of padding used could be the reasons why it was so much lower when I tried to encrypt the files with small block sizes. Does the number of encryption cycles and/or amount of padding used from smaller block sizes compared to large block sizes impact the time. If so, why is this? If there are other reasons too as to why RSA with OAEP encrypts files much faster with larger block sizes compared to smaller block sizes, I would love to learn more about that!

Disclaimer: I completely understand that RSA is NOT meant for file encryption, I am just trying stuff.

Thank you in advance for any logic behind this that you can provide.

Answer 1

The maximum payload for each encryption using RSA OAEP is displayed here. For any message up to that size a complete RSA operation needs to be performed. Of course, if you encrypt each byte separately then you won't get much performance, and your ciphertext will expand enormously. You need to make sure that you use the entire possible payload for each encryption.

Encryption for RSA is a relatively fast operation compared to decryption. The RSA public exponent is generally kept small (and to a specific value with just two bits set, 65537 or 0x10001 in hexadecimals, often called F4). So encryption may still be pretty fast even with larger key sizes. Key generation and decryption however will take much more time. As the relative OAEP padidng overhead is also much lower for larger key sizes, I'd expect the encryption speed to initially grow and then quickly degrade again when the RSA modulus start to get really large. Decryption speed will have degraded long before that in all likelihood. For generation of 16,384 bit key pairs I definitely suggest to use a fast CPU....