4
$\begingroup$

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".

$\endgroup$
  • $\begingroup$ Two questions here - the first is in the title, the second is about the data size of the resulting encrypted content. $\endgroup$ – Kieveli Jul 19 at 18:10
  • $\begingroup$ Is it? I'm just asking one question. Does larger key size mean larger data size of the resulting encrypted content in asymmetric encryption? $\endgroup$ – worisi24 Jul 19 at 19:06
  • $\begingroup$ Asymmetric encryption increases the data size by 1/3 during encryption. Symmetric encryption does not increase the size of the data. The maximum asymmetric data size is 11 bytes less than the size of the key. You can split and chain encrypted packets, but with the extra space it takes, why would you. $\endgroup$ – Kieveli Jul 22 at 13:00
  • $\begingroup$ And a quick test shows that a 15 byte file encrypts twice as large with an asymmetric key of 4096 vs 2048. Encrypted data becomes the size of the key. $\endgroup$ – Kieveli Jul 22 at 13:03
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You shouldn't put this as addition to the other answer, it is the actually correct answer: Use hybrid encryption, don't use RSA directly (or actually, try to avoid RSA in general). $\endgroup$ – tylo Jul 19 at 15:28
  • 1
    $\begingroup$ Did you mean minus padding/8 ? $\endgroup$ – Kieveli Jul 19 at 18:03
  • $\begingroup$ Besides that, even with a minus, I've got some doubts that the formula works for e.g. OAEP padding. Probably best to simply point out the formulas within PKCS#1 or, indeed, one of my answers about calculating the payload size for RSA. $\endgroup$ – Maarten Bodewes Jul 20 at 1:37
  • $\begingroup$ @Swashbuckler You mean I can't encrypt say large dictionary of 10MB in size? and hybrid encryption here means I use say AES to encrypt my secret message and then use RSA to encrypt my AES key? $\endgroup$ – worisi24 Jul 20 at 4:54
  • 1
    $\begingroup$ Yeah, mean minus $\endgroup$ – Swashbuckler Jul 20 at 18:10
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Sorry, can you explain in plain English? So the answer is yes? Larger key size means larger data size in asymmetric encryption, right? $\endgroup$ – worisi24 Jul 19 at 19:04
  • $\begingroup$ @worisi24 yes, when you increase the modulus you will have larger message space. Note that one increases the modulus size to mitigate the attacks not for having larger message sizes. The larger the modulus the higher computation cost. Keep in mind that as Swashbuckler said use hybrid encryption. RSA mostly used for digital signature. $\endgroup$ – kelalaka Jul 19 at 19:11
  • $\begingroup$ I'm assuming modulus means key size right? $\endgroup$ – worisi24 Jul 20 at 4:51
  • $\begingroup$ In RSA, the public modulus $e$ is chosen 3, 17, 65537 etc. so they are already small. However, when you calculate the private exponent you need the inverse of $e \cdot d = 1 \pmod \lambda(n)$ (or $\varphi(n)$), therefore your private key is will be bigger. $\endgroup$ – kelalaka Jul 20 at 8:49
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ OK, this really requires some pictures, but I'll have to find a program to create them. $\endgroup$ – Maarten Bodewes Jul 21 at 19:07
0
$\begingroup$

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?

$\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.