Why are RSA key sizes almost always a power of two?

Question

I know that other bit sizes are possible, e.g. this HTTPS server seems to have a 9000 bit key https://www.ssllabs.com/ssltest/analyze.html?d=qqq.gg, but it's very rare that one sees a key not of size 1024, 2048, 4096, etc. bits in common usage - what is the reason for this? Is it just customary, or is there a cryptographic advantage?

Answer 1

In RSA, the bit size $n$ of the public modulus $N$ is often of the form $n=c\cdot2^k$ with $c$ a small odd integer. $c=1$ ($n=512$, $1024$, $2048$, $4096$.. bit) is most common, but $c=3$ ($n=768$, $1536$, $3072$.. bit) and $c=5$ ($n=1280$..) are common. One reason for this is simply to limit the number of possibilities, and similar progressions are found everywhere in cryptography, and often in computers where binary rules (e.g. size of RAM).

The difficulty of factoring (thus, as far as we know, the security of RSA in the absence of side-channel and padding attacks) grows smoothly with $n$. But the difficulty of computing the RSA public and private functions grows largely stepwise as $n$ increases (more on why in the next paragraph). The values of $n$ just below a step is thus more attractive than the value just above a step: they are about as secure, but the later is more difficult/slow in actual use. And, not coincidentally, the common RSA modulus sizes are just below such steps.

One major factor creating a step is when one more word/storage unit becomes required to store a number. When the storage unit is $b$-bit, there is such step every $b$ bits for the RSA public function $x\mapsto x^e\bmod N$; and a step every $r\cdot b$ bits for the RSA private function $x\mapsto x^d\bmod N$, with $r=1$ for the naïve implementation, and $r$ equal to the number of factors of $N$ when using the CRT with factors of equal bit size (most usually $r=2$, but I have heard of plans up to $r=8$). On any modern general-purpose CPU suitable for RSA, $b$ is a power of two and at the very least $2^5$, creating a strong incentive that $n$ is at least a multiple of $2^6$ ($r=2$ is common, and the only reasonable choice for $n$ below about a thousand).
_{Note: $n=1984=31\cdot2^6$ is not unseen in the field of Smart Cards, because the next multiple of $2^6$ would break the equivalent of a sound barrier in a common transport protocol, ISO/IEC 7816-3 T=0. For a list of common RSA modulus size in this field, search LENGTH_RSA_1984.}

As an aside, it is significantly simpler to code quotient estimation in Euclidian division (something much used in RSA) when the number of bits of the divisor is known in advance. This creates an incentive to reduce the number of possible bit sizes for the modulus. The two simplest cases are when the number of bits is a multiple of $b$, and one more than a multiple of $b$; the former won.

Answer 2

Using powers of two is traditional. It also has a few implementation benefits for very constrained architectures: it saves a few instructions. This indirectly implies that some implementations are not able to process RSA keys whose size is not a multiple of 32 or 64, meaning that if you want maximum interoperability, you should not use other key sizes as well (even if your code is not that limited).

(I have seen RSA keys of size 1152 bits and 1536 bits used in the wild, so there is no absolute limitation to powers of two only.)

Answer 3

There is no cryptographic advantage in picking any particular alignment for RSA key sizes, whether it's powers of 2, multiples of 64, multiples of 2, ... The difficulty of cryptographic attacks pretty much grows with the number of bits. As already noted by fgrieu, there is a slight advantage to the defender in working with sizes that are a multiple of 32 or 64, because most bignum operations cost the same in practice whether you run them on a 2017-bit number of a 2048-bit number.

There is however an occasional practical advantage in using “standard” sizes — at least multiples of 32, and more generally numbers of the form $(2^k+1)2^m$ with small $k$. The advantage is that the implementations your key will be used with have a better chance of having been tested at these sizes. RSA calculations involve operations on the sizes and may include mistakes that are only apparent on “non-round” sizes (e.g. sizes that are not a multiple of the word size). Some implementations may even forbid the use of key sizes that have not been tested, so they would only support a few sizes.

For DSA, the FIPS 186 standard originally specified that the key size should be a multiple of 32 between 512 and 1024. The current version specifies that the key size must be 1024, 2048 or 3072, and specifies that these same key sizes are the only valid ones for government use for RSA. Restricting key sizes to a few values improves interoperability, and improves security by reducing implementation complexity and increasing test coverage.

Answer 4

It is just customary, and enforced by products like GPG and OpenSSL which include code to block you choosing your own exact bitlength (they enforce padding or rounding, for no particular reason). Here is the GPG code that enforces this, for example:

 if( nbits < 768)
   {
     nbits = 2048;
     log_info(_("Keysize invalid; using %u bits\n"), nbits );
   }
 else if(nbits>3072)
   {
     nbits = 3072;
     log_info(_("Keysize invalid; using %u bits\n"), nbits );
   }

 if(nbits % 64)
   {
     nbits = ((nbits + 63) / 64) * 64;
     log_info(_("keysize rounded up to %u bits\n"), nbits );
   }


 /* To comply with FIPS rules we round up to the next value unless
    in expert mode.  */

 if (!opt.expert && nbits > 1024 && (nbits % 1024))
   {
     nbits = ((nbits + 1023) / 1024) * 1024;
     log_info (_("keysize rounded up to %u bits\n"), nbits );
   }