Does larger key size mean larger data size in asymmetric encryption?

Question

I'm new to cryptography. I know the larger the key size (like 128-bit vs 1024-bit) the harder the ciphertext is to crack, generally. But assuming everything else being equal, does a larger key size increase the data size compared to the original data in asymmetric encryption? I know AES doesn't increase the data size, but what about RSA?

I've been Googling my question, but I haven't found a straight answer. I just hope the answer is not "it depends", thus I added "assuming everything else being equal".

Answer 1

In addition to kelalaka's answer, keep in mind that the amount of data that can be encrypted with RSA is relatively small (keysize+padding/8), so most schemes use hybrid encryption to use RSA to encrypt a symmetric key and some other critical information and most data is encrypted using the symmetric key.

Answer 2

Yes, for the RSA larger modulus $n = p \cdot q$ means that you can encrypt larger plaintexts. The modulus determines the size of the plaintext space.

Keep in mind that, for proper RSA encryption (which is not textbook RSA), you need padding schemes like PKCS#1 v1.5 or OAEP padding schemes to be secure against attacks.

The padding schemes will reduce your message space.

The overhead of PKCS#1 v1.5 padding is at least 11 bytes. See this asnwer

and for OAEP sizes see this answer

Answer 3

But assuming everything else being equal, does a larger key size increase the data size compared to the original data in asymmetric encryption?

Yes. The ciphertext will somehow have to include some kind of result that is related to the asymmetric algorithm. And the size of that result commonly depends on the key size.

---

So for instance for RSA encryption the modulus defines the key size as well as the size of the output. The growth of the ciphertext compared to the plaintext on the other hand depends on how much padding is used. So the overhead is a fixed number per encryption, however the data storage capacity grows if the key size grows. So you could say that the relative overhead decreases for larger key sizes. This is true for PKCS#1 v1.5 padding as well as the newer OAEP padding (which is more secure but has more overhead as well).

---

Generally however these kind of schemes are used together with symmetric encryption. In that case RSA is just used to encrypt the symmetric key. Even an (insecure) 512 bit RSA is plenty to encrypt a 128 bit / 16 byte AES key. In that case you've got an encrypted key (with a larger size) and an identically sized ciphertexts created using that symmetric key. So the increase in asymmetric key size just makes the ciphertext larger.

Of course with hybrid encryption the symmetric key will handle the data, so the overhead is just the length of the plaintext + a constant for each key size (and maybe some additional overhead). For instance, for RSA-OAEP + CTR mode the minimum ciphertext size would just be the asymmetric key size + the plain text size, and that's it.

If you're using a hybrid scheme like ECIES or RSA-KEM - those schemes derive the symmetric key rather than calculating it - then the same idea applies: the size of the parameters that need to be send with the ciphertext will grow with the asymmetric key size. The actual ciphertext created using the symmetric key remains the same size. So overall it is an increase.

Answer 4

Be careful when comparing key sizes. Different algorithms require different sized keys to achieve equivalent security. There are significant differences between symmetric block cipher key sizes and asymmetric (public/private) key sizes; and among asymmetric algorithms there are big differences, too.

Symmetric ciphers, such as AES, DES, Blowfish, etc., have key lengths that are usually directly equivalent to brute force efforts. To guess an AES 128 bit key requires an average of 2^127 guesses. To guess a 56 bit DES key requires an average of 2^54 guesses. An algorithm that doesn’t hold true to this is considered weak, and shouldn’t be used.

Asymmetric ciphers are based on different types of math problems. RSA is based on factoring the product of two prime numbers. Factoring algorithms are much more efficient than trying every possible number. For example, you wouldn’t try any even numbers, because they’re all divisible by 2. You wouldn’t try any number ending in 0 or 5, because they’re all divisible by 5. So to get the equivalent protection of 80 bits of guessing, mathematicians have calculated that your RSA key needs to be about 1024 bits long.

Similarly, Elliptic Curve Cryptography uses a different hard math problem: finding the intersection of points on a curve. The numbers required to achieve similar results are smaller than RSA factors, but larger than brute force. It may take an ECC key of about 160 bits to equate to the security of an 80 bit symmetric key.

Also, these difficulty factors are probabilities determined by mathematicians based on what they know today. Tomorrow, someone may come up with a new, more efficient factoring algorithm, rendering these key sizes obsolete.

So to reiterate: a 1024 bit RSA key is much, much weaker than a 128 bit AES key.

Within a single algorithm, yes, larger key sizes are harder to crack. This is where you use published information to understand the expected brute force capabilities, and select a key size that is resistant, but not so large that it drags down performance. An 8192 bit RSA key is not going to be brute forced any time soon, but do you really want to build a server farm just to do TLS key exchanges?