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

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?

• Would you prefer key sizes of 818 bits, 1935 bits, 4144 bits? There is no cryptographic advantage, but using nice round numbers allows them to be more efficiently implemented and stored. It is also simpler, convention, and just makes more sense than apparently arbitrarily chosen key sizes. Also, 9000-bit RSA is overkill, people using such large keys are just wasting CPU cycles (and it's not "over 9000" anyway, so it fails in this respect as well ^^). Mar 28, 2013 at 6:48
• maybe it has to do with being the powers of 2? Mar 28, 2013 at 9:13

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.

• "But the difficulty of computing the RSA public and private functions grows largely stepwise as n increases" Exponentiation by squaring, right? Mar 28, 2013 at 11:14
• @Joe Zeng: That's not what I meant. In my original answer, the "later" you quote referred to considerations on word/storage unit size. This creates much more marked steps than the (relatively smooth) addition of an extra squaring step, because the later depends on the number of bits in the exponent, which is not bound to be a multiple of something, and is typically a little less than $n$.
– fgrieu
Mar 28, 2013 at 16:45
• @fgrieu do you have any references that can help explain the theory behind that public modulus length equation? Feb 18, 2020 at 18:18
• @Liam Kelly: if by "equation" you mean $n=c\cdot2^k$ with $c$ small, I'm afraid that no, I have no reference with an explanation. Number of this form abound in computer science, because that's the number of bits in $c$ RAM chips with $n$ address bits, or equivalently in $c$ computer words with $2^n$ bits. Correspondingly one can store $N$ in binary with precisely this amount of RAM, or this many computer words.
– fgrieu
Feb 18, 2020 at 18:28

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

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.

• Nit: FIPS186 though -2 (the doc you link) required DSA p a multiple of 64 bits (from 512 to 1024). And the changes to 1k,2k,3k, as you say for both DSA and RSA, were in -3 in 2009. And an update: in 2019-10 draft -5 drops DSA entirely, and makes RSA min 2k but drops the 'only 1k 2k 3k' requirement. It also adds optional deterministic k to ECDSA, and adds EdDSA. Dec 4, 2019 at 8:26

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 );
}

• The first check makes sure you aren't using a dangerously small keysize. The second check is only for DSA, since the most recent standard sets 3072 as the maximum size. The third check is for performance reasons (as mentioned in other answers), and the final check is for FIPS compliance. Jul 15, 2018 at 3:42
• Whoever downvoted this is wrong, and the comments are wrong too, and the selected "best answers" are also wrong. I have personally hand-coded all the the bigmath code needed to perform RSA - performance is directly related the the count of the number of "1" bits, and has nothing whatsoever to do with the total number of bits. Sep 5, 2018 at 11:17
• You are thinking of the performance impact of large exponents, where the bit population count matters. For a large modulus, using a power of two just makes it easier to use fast modular exponentiation algorithms. Dec 13, 2018 at 1:02
• That code is GPG only, and as forest noted one part DSA only. OpenSSL requires only min 512 and multiple of 64 for DSA (corresponding to the original '186-0'), and only min 512 for RSA (although it won't use >16k for pubkey operations, which limits their utility). OpenSSH generates only 1k for DSA (apparently the intersection of 186-0 and the OpenSSH people's security requirements, or maybe just 186-2cn1), but any length 1k up for RSA. Java restricts DSA sizes, and annoyingly also DH, but not RSA (all using same BigInteger internally). Dec 4, 2019 at 8:54