How to calculate RSA Key Size correctly starting from 384 bits to 15360 bits or beyond 15360 bits

Question

Hello fellow experts here, I am new to cryptography.

Recently I looked into RSA Key Size (Microsoft RSA library), it actually describes that the minimal key length required is 384 bits and maximum key length accepted was 15360 bits.

I really do have question here is that how can I properly calculate the key size that is between the range of 384 bits to 15360 bits easily without little to no error?

For example, currently from what i know, the possible key length in between 384 bits and 15360 bits contains the common key length of 1024, 2048, 3072 bits.

Is there any formula or calculations that other people used to know these key length? If yes, does this specific formula can be applied to calculate all possible key length between the minimal key length and maximum key length?

Answer 1

Oh, that one is simple: any key size is possible. The key size for RSA is set to the size of the modulus. The modulus in turn is the multiplication of two (or more) large primes. Of course, multiplication means that all prime sizes are added together (give or take a bit).

However, not every implementation will allow any key size. Since computers are byte oriented, in general the key size needs to be a multiple of 8. That makes encoding the key values easier, for starters. Quite often the numbers are calculated using words, so a 32 bit of 64 bit increment is also not uncommon. Finally, if just to avoid over-extensive testing, an implementation may also decide to just allow some specific key sizes.

Generally there is also some lower limit, if just to avoid completely insecure choices like 128 or 256 bit RSA. Creating an upper limit also makes sense, because key pair generation of 16Kib RSA keys or higher is nothing to sneeze at (and, not counting quantum cryptography, that provides a 256 bit security margin anyway).

If I remember correctly Microsoft's native RSA implementation uses 32 bit increments for the key sizes, although there are of course multiple API's and implementations of these API's (managed and unmanaged). But in the end you have to look it up, and even then changes may happen (such as upping the minimum bound or allowing more key sizes).

For common key sizes, try 2048 (on the small side), 3072 (2048 + 1024) and 4096 bits. Almost all implementations will support those key sizes and there is really not much need to choose an intermediate value, except for niche purposes (smart cards). RSA with bit size 1024 is not recommended anymore and may well be prohibited by some implementations.