Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
2  
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 ^^). –  Thomas Mar 28 '13 at 6:48
    
maybe it has to do with being the powers of 2? –  midhunhk Mar 28 '13 at 9:13

2 Answers 2

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.

share|improve this answer
    
"But the difficulty of computing the RSA public and private functions grows largely stepwise as n increases (more on why later)." Exponentiation by squaring, right? –  Joe Z. Mar 28 '13 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 '13 at 16:45

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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