3
$\begingroup$

The question is what is an appropriate public/private key length in order to encrypt a 256-bit or 512-bit AES key without wasting bytes, and whether long public/private keys provide meaningful increase in security simply from being longer.

I'm encrypting a 256-bit AES key using a public key from a 2048-bit private key. The maximum allowed message length is longer, making me concerned that I'm encrypting with too many bits for the size of the data.

  • Does a 2048-bit key waste bytes when encrypting exactly 32 bytes with a public key?

  • If bytes are wasted and a lower size public/private key were chosen (e.g. 1024 bits), is there a reduction in security? Or is the public/private key size solely about the size of the data to be encrypted, and the remaining bytes are just wasted (padding needlessly encrypted)?

  • Is there a rule of thumb about what size data can be encrypted with a given public/private key size?

$\endgroup$

1 Answer 1

8
$\begingroup$

The question is what is an appropriate public/private key length in order to encrypt a 256-bit or 512-bit AES key without wasting bytes, and whether long public/private keys provide meaningful increase in security simply from being longer.

That's a bit of a hard question, as 512 bit AES doesn't exist. AES is the Rijndael algorithm with a block size of 128 bits and a key size of 128, 192 or 256 bits.

And no, public / private keys are longer, but they are not more secure. You can reach 256 bit security, but for RSA that means a key size of 15K. And that security is against classical computing; a large quantum computer may still break large keys in the future while it should not be able to break 256 bit AES. You can see a good comparison between key size and key strength at https://keylength.com.

Does a 2048-bit key waste bytes when encrypting exactly 32 bytes with a public key?

No, a 2048 bit key has a key strength of about 112 bits, lower than a 128 bit AES key and much lower than a 256 bit AES key. For symmetric algorithms the key strength is generally close to the key size.

If bytes are wasted and a lower size public/private key were chosen (e.g. 1024 bits), is there a reduction in security?

Yes, a 1024 bit RSA key has a key strength of about 80 bits. That's not considered very secure anymore, although it still considered out of reach for most organizations.

Or is the public/private key size solely about the size of the data to be encrypted, and the remaining bytes are just wasted (padding needlessly encrypted)?

Padding is an absolute necessity for direct encryption or key wrapping with RSA. Without such padding encryption or key wrapping is not secure, although it is possible to securely encapsulate a secret with about the same size as the RSA modulus / the key size (RSA-KEM).

Is there a rule of thumb about what size data can be encrypted with a given public/private key size?

Better, for a single encrypt with an RSA key you can look at the key sizes for PKCS#1 v1.5 padding or OAEP padding.

Raw RSA can encrypt messages of the same size as the modulus (they are converted to a number in the range [0, N) before modular exponentiation). So your 2048 bit key can encrypt slightly more than 2047 bits. However, as indicated above, that's not secure. For arguments sake we'll take 2048 / 8 = 256 bytes as maximum message size after one of the following padding algorithms is applied.

For PKCS#1 v15 padding the minimum padding size is about 11 bytes for 8 randomized bytes, although you should really have at least 16 of those bytes for 19 bytes of overhead. So that would give you a maximum message or key of 256 - 19 = 237 bytes. For the more secure OAEP padding things get more complicated so I've created this handy table.

$\endgroup$
6
  • $\begingroup$ More answer than I could have hoped for, thank you! $\endgroup$
    – Per
    Commented Dec 8, 2022 at 8:52
  • $\begingroup$ Is it worth adding a comment about EC keys, where the key length is much closer to the security level? $\endgroup$ Commented Dec 8, 2022 at 16:19
  • $\begingroup$ I think you just did. Yes, the security strength is about half of the key size for ECC. However you cannot directly encrypt with ECC, for that you need ECIES (basically ephemeral-static key agreement, key derivation followed by symmetric cryptography). But maybe that's a bit much for the current question, and the strength is mentioned at keylength.com. $\endgroup$
    – Maarten Bodewes
    Commented Dec 8, 2022 at 17:42
  • $\begingroup$ So to understand, is it even worth using any symmetric AES over 128 bits if the public key is encrypting it with fewer bits of security? It seems that no matter how high a quality the symmetric key is, the public key encryption becomes the limit on security. Is this a correct way to think about it? $\endgroup$
    – Per
    Commented Dec 13, 2022 at 18:42
  • $\begingroup$ It's certainly one way to think about it yes. With TLS 1.3 the sometimes very unbalanced security between the various algorithms has been diminished somewhat. On the other hand: AES is very fast, especially if the CPU has hardware acceleration. You would not really notice the difference between AES-128 and AES-256. I'd be more worried about RSA or ECDSA security though, especially if you count in quantum computing. And any worry about algorithm choice and strength is dwarfed by worries about bad configuration, out of date software and key management issues. $\endgroup$
    – Maarten Bodewes
    Commented Dec 13, 2022 at 20:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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