17
$\begingroup$

One can find up to date recommended key sizes for RSA at http://csrc.nist.gov/publications/nistpubs/800-131A/sp800-131A.pdf for example. In short it suggests a key size of at least 2048 bits.

Is it possible to find a history of recommended key sizes for RSA, going back to the invention of RSA?

|improve this question
$\endgroup$
  • $\begingroup$ Back in the day the government didn't use RSA, because it was patented. So I'm not sure if they would have any recommendations on its key length that far back. But I imagine they would be in line with DSA key lengths. $\endgroup$ – user13741 Oct 15 '14 at 15:11
  • 2
    $\begingroup$ Leaving as a comment because I don't have time to craft a well-written answer: en.m.wikipedia.org/wiki/Key_size provides a good starting point for some answers. $\endgroup$ – Pete Scott Oct 15 '14 at 22:29
  • 4
    $\begingroup$ One data point: the original (1974) RSA paper said: "We recommend that $n$ be about 200 digits long." That was about 664 bits. $\endgroup$ – fgrieu Oct 17 '14 at 16:37
  • 3
    $\begingroup$ @fgrieu So we have a 1974 lower bound. I wonder at what point the recommendations, such as derived in Table 1 of the paper, became explicitly linked to Moore's law, which interestingly enough was published a decade earlier. As once they became explicitly linked in any formal cryptogaphic literature, you could then just look at regular whitepapers and articles on Moore's Law for the answer. $\endgroup$ – LateralFractal Oct 17 '14 at 23:07
13
+25
$\begingroup$

512 bits (rounded down from the 664 bits or 200 digits in the patent) was recommended from its conception in 1974 and throughout the 1980s. Indeed, 463 bits was considered sufficient in the mid-1990s for the RSA-140 challenge. Whether key strengths as low as 100 digits (330 bits) were ever used in the early 1980s embedded systems is unclear; but probable given the RSA-100 challenge of 1991.

RSA's recommended key size increased to 768 (user) or 1024 (enterprise) at some point in the late 1990s1 due to academic successes in breaking bit strengths leading up to 512 bits.

Current recommendations (SP 800-572) are now 2048 or 3072 bits, depending on interoperability requirements.

In practice, these key strengths do not smoothly match Moore's Law as each new key size requires overhauling embedded systems and resolving interoperability requirements. So the trend has been to pick a key size much larger than necessary until the risk of breaching occurs, then pick another key size much larger than necessary.

A coarse stepwise increase governed by infrastructure costs and collective public perception of key strength.

1. Inferred from this RSA article and this (irritatingly uncited) Wikipedia section.
2. A sister document of the PDF cited in the question.

|improve this answer
$\endgroup$
  • $\begingroup$ @fgrieu Yes, I can well imagine that existing infrastructure could be using very low key sizes; perhaps due to design constraints. I hope they are also relying on hardware resilience of some sort, as 321 bits is well within the capability of modern GPU arrays. $\endgroup$ – LateralFractal Oct 18 '14 at 7:04
  • $\begingroup$ [reposted with correction] As of the embedded world: one of two RSA keys with 321-bit public modulus has been used by French banks as global keys for static issuing certificates of credit/debit Smart Cards, well after the end of the 20th century (but are phased out now). See references in the third bullet point of this answer. The lowest routinely used nowadays is more like 1024-bit (e.g. European tachograph cards). $\endgroup$ – fgrieu Oct 18 '14 at 7:56
  • $\begingroup$ Your "irritatingly undated" link says it's from the week of Eurocrypt '99, which was May 2-6 1999. $\endgroup$ – otus Oct 18 '14 at 8:07
  • $\begingroup$ Oop. I was too busy scanning for a non-existent byline to read the press release section. Updated probable cutover. $\endgroup$ – LateralFractal Oct 18 '14 at 9:06
  • $\begingroup$ You wouldn't expect the key sizes to match Moore's Law would you? There have been a number of improvements in factoring algorithms since 1974. It is interesting that even in 1999 they recommended 2048 bits for some purposes. $\endgroup$ – Lembik Oct 18 '14 at 18:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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