What are Key Size requirements (rather than modulus size) for different Asymmetric Algorithms for 112-bit security?

Question

A lot of writeups, books & webpages say that to get 112 bit security (i.e $2^{112}$ steps), you need to use RSA or DH with 2048 key size or ECDH with 224 key size. In reality, I think what is meant in most of these cases is modulus size or group size rather than key size, but for some reason it's always referred to as key size?

I think the modulus size requirements are thus for 112 bit security

• RSA - 2048 bits
• DH - 2048 bits
• ECDH - 224 bits

What are the corresponding key sizes required? Keeping the modulus size at what is required, will increasing key size increase security? Can we lower modulus size requirement by increasing key size?

Answer 1

What are the corresponding key sizes required?

Well, for RSA, we always refer to the modulus size as the key size; a 2048 bit RSA key has a 2048 bit modulus (that is, one between $2^{2047}$ and $2^{2048}-1$) by definition.

If you're talking about how many bytes we use to transport the RSA public key, well, that's a bit more; we obviously need to send the modulus (2048 bits in this case), the public exponent (which is typically small); we generally use a BER or DER representation, which might require another dozen or so bytes. Of course, there are some nonstandard tricks you could use to reduce the size of the transmitted RSA public key by close to a factor of two (without affecting security); however we never use those.

As for DH, well, if we do static DH (that is, one where we have a public $g^x \bmod p$ value that other people use as a public key), well, $g^x \bmod p$ is effectively a random value between 0 and $p-1$; hence the size of the public key is the same as the size of the modulus $p$.

As for ECDH, well, that has the public value being the point $xG$. The straight-forward (x,y) representation of that point would give a public key that's twice is the size of the modulus (actually, the field size - it's not unknown to do ECDH in an extension field, and in that case, the term 'modulus' doesn't apply). On the other hand, ECDH works if we only transmit the $x$ coordinate; if we do that, then that public key is the field size.

If you go through the above answers, you'll see that the answers to your further question:

Keeping the modulus size at what is required, will increasing key size increase security? Can we lower modulus size requirement by increasing key size?

Doesn't make sense; in all cases, the public key size is pretty much the modulus size; changing them independently doesn't work.

And, if you're asking about the private key size, that doesn't work either; in all three cases, the private value (private exponent in the case of RSA) is an integer that is effectively modulo something close to the modulus size; we can pick a larger integer, however that is exactly equivalent to some smaller integer, and hence can't increase security.