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 think 1024 bit RSA keys were considered secure ~5 years ago, but I assume that's not true anymore. Can 2048 or 4096 keys still be relied upon, or have we gained too much computing power in the meanwhile?

Edit: Lets assume an appropriate padding strategy. Also, I'm asking both about security of signatures and security of data encryption.

share|improve this question
add comment

5 Answers 5

up vote 42 down vote accepted

In the first decade of the 21th century, and counting, on a given $Year$, no RSA key bigger than $(Year-2000)\cdot 32+512$ bits has been openly factored other than by exploitation of a flaw of the key generator. This linear estimate of academic factoring progress should be used neither for long-term predictions (after 2016 or 1024-bits) nor for choosing a key length.

The current factoring record is 768 bits, by the end of 2009, and quoting this:

it is not unreasonable to expect that 1024-bit RSA moduli can be factored well within the next decade by an academic effort.

Update: I emphasize that the above is about attacks by academics. So far, hackers have always been some years behind (see below). On the other hand, it is quite conceivable that well funded government agencies are many years ahead in the factoring game. They have the hardware and CPU time. And there are so many 1024-bit keys around that it is likely a worthwhile technique to be in a position to break these. It is one of the most credible explanation for claims of cryptanalytic breakthrough by the NSA.

By 2012, the main practical threat to systems using 1024-bit RSA to protect commercial assets is usually not factorization of their key (often, that is penetration of the IT infrastructure by other means). With 2048 bits or more we are safe from that factorization threat for perhaps two decades, with fair (but not absolute) confidence. For varying estimates on how big is safe enough, see this site on keylength.

Update 2: Factorization progress is best shown on a graph (to get at the the raw data e.g. to make a better graph, edit this answer)

Graph of academic RSA factorization records

This also shows the linear approximation at the beginning of this answer, which actually is a conjecture at even odds for the [2000-2016] period that I made privately circa 2002, and committed publicly in 2004 (in French). Also pictured are the three single events that I know of hostile factorization of an RSA key (other than copycats of these events or by exploitation of a flaw of the key generator):

  • The Blacknet PGP Key in 1995. Alec Muffett, Paul Leyland, Arjen Lenstra and Jim Gillogly covertly factored a 384-bit RSA key that was used to PGP-encipher "the BlackNet message" spammed over many usenet newsgroup. There was no monetary loss.

  • The French "YesCard" circa 1998. An individual factored the 321-bit key then used (even though it was clearly much too short) in issuer certificates for French debit/credit bank Smart Cards. By proxy of a lawyer, he contacted the card issuing authority, trying to monetize his work. In order to prove his point, he made a handful of counterfeit Smart Cards and actually used them in metro tickets vending machine(s). He was caught and got a 10 months suspended sentence (judgment in French). In 2000 the factorization of the same key was posted (in French) and soon after, counterfeit Smart Cards burgeoned. These worked with any PIN, hence the name YesCard (in French). For a while, they caused real monetary loss in vending machines.

  • The TI-83 Plus OS Signing Key in 2009. An individual factored the 512-bit key used to sign downloadable firmware in this calculator, easing installation of custom OS, thus making him a hero among enthusiasts of the machine. There was no direct monetary loss, but the manufacturer was apparently less than amused. Following that, many 512-bit keys (including that of other calculators) have been factored.

Update 3: Definitely, 512-bit RSA is no longer providing sizable security. Despite that, reportedly, certificates with this key size have been recently issued by official Certification Authorities, and used to sign malware, possibly by mean of an hostile factorization.

share|improve this answer
    
Thought you'd be interested to know I submitted this question to be promoted on the Stack Exchange social media outlets - also, question - because you've edited the answer so many times its turned into "community wiki" i.e. the edit bar is lower and you get no rep for upvotes. Want me to turn it back? It's an auto feature designed to credit multiple authors (which there aren't in this case), but if a mod reverts the CW conversion, it'll stay reverted forever. –  Ninefingers Apr 3 '12 at 9:57
    
@Ninefingers: I'm OK with this being a CW. Sent a longer answer by email some days ago. –  fgrieu Apr 7 '12 at 14:07
    
also a consideration - factoring is being done more and more on GPU rather than CPU systems, which offer higher parallelization and shorter crack times (at least on symmetric systems) –  warren Apr 10 '12 at 22:39
    
@warren: do you have a link describing sieving or linear algebra (the bottlenecks for GNFS) on GPU? –  fgrieu Apr 11 '12 at 7:49
    
@fgrieu - some of the more detailed references off Jeff Atwood's recent blog post on hashing may have some of those details –  warren Apr 11 '12 at 18:26
show 4 more comments

You might want to look at NIST SP800-57, section 5.2. As of 2011, new RSA keys generated by unclassified applications used by the U.S. Federal Government, should have a moduli of at least bit size 2048, equivalent to 112 bits of security. If you are not asking on behalf of the U.S. Federal Government, or a supplier of unclassified software applications to the U.S. Federal Government, other rules might of course apply.

However, at the very least, these figures indicate what the U.S. Federal Government thinks about the computational resources of it's adversaries, and presuming they know what they are talking about and have no interest in deliberately disclosing their own sensitive information, it should give some hint about the state of the art.

share|improve this answer
add comment

The simplest answer would be to look at the keylength.com site, and if you don't trust that, to the linked papers, particularly by NIST and ECRYPT II. Bare in mind that you may have additional restrictions and - if you are brave or stupid - relaxations depending on the use case.

share|improve this answer
add comment

Another way of determining the key size that offers 'adequate security' and was presented initially by Lenstra is the equivalence between symmetric and asymmetric key lengths where two systems offer cost-equivalent security if at a given time accessing the hardware that allows a successful attack in a certain fixed amount of time, costs the same amount of money for both systems. Adequate security was defined as the security offered by DES in 1982.

There are several factors that influence the choice of the key length, for example the life span of the data you want to protect, the estimation of the computational resources (consider Moore's law) and the cryptanalytic advances through the years (Integer factorisation). According to Lenstra, by 2013 a symmetric key size of 80 bits and an asymmetric key size of at least 1184 bits is considered to offer adequate security.

A more recent method of determining adequate key sizes again by Lenstra ("Using the cloud to determine key strengths") is by using cloud services to estimate the computational cost required to factor keys assuming that the fastest way is the Number Field Sieve algorithm. He used Amazon's cloud services to develop his cost based model. Note that the Number Field Sieve algorithm is over 20 years old and since 1989 in this area there have been no major advances besides small tweaks.

In recent surveys it has been observed that people tend to move towards 2048-bit keys although certificates holding 1024-bit keys have no reason to be revoked as long they are not expired.

share|improve this answer
add comment

On my website, I have describes why I personally have chosen a 10kbit RSA key:

share|improve this answer
1  
While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference. Link-only answers can become invalid if the linked page changes. –  Stephen Touset Jun 20 at 0:40
    
The "do not cost significant performance penalty" depends very much on context. For email that may be true since you usually don't receive several emails per second. For many other contexts, such as SSL, several hundred milliseconds of decryption time for a single handshake are not acceptable. The other big problem is that many RSA implementations do not support such large keys. –  CodesInChaos Jun 20 at 9:55
    
It does not change the two overall conclusions: The penalty is solely paid by the key holder - not by the communication partner and measure before you assume 10kbit keys will be a problem. –  Ole Tange Jun 20 at 18:29
    
“measure before you assume“ – For the fun of it, I just did and as a result noticed that your claims are build on faulty conclusions. Skipping potential discussions about your somewhat naive benchmark strategy, I would like to point out that the numbers on your site are wrong. For example: you state CPU performance 4kbit --encrypt = <0.001-0.004 secs and CPU performance 10kbit --encrypt = 0.004-0.012 secs, but you come to the conclusion that Additional cost for --encrypt = 0 secs? Also, in one case you even claim 4kbit to be slower than 10kbit… I hope you notice what’s wrong with that! –  e-sushi Jun 20 at 20:25
    
The additional cost is 0 seconds rounded to 0 decimals. It makes sense to round to 0 decimals, when the measuring uncertainty is greater than the number (in this case the uncertainty is around 0.008 and the difference is less than 0.008). I have tried figuring out which case you are talking about, and have been unable to find it. Also I do not claim: I measure and report the measurements. Will you care to share the numbers you got when when you re-did the tests on your systems? –  Ole Tange Jun 20 at 22:57
add comment

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.