> It's worth a quote from the paper at CRYPTO '10 on factorization of a > 768-bit number:
A good paper by top academics. > Another conclusion from > our work is that we can confidently say that if we restrict ourselves to > an open community, academic effort such as ours and unless something > dramatic happens in factoring, we will not be able to factor a 1024-bit > RSA modulus within the next five years [27]. After that, all bets are off. The 768-bit team started crunching in early 2007 and completed three years later in December 2009. They used fewer than a thousand commercially available unspecialized computers, connected by commercially available interconnects. Their intermediate results fit on less than a dozen $150 2TB disk drives. And one of their results is that it's better to scale up the part of the process that scales linearly with minimal communication (sieving), to reduce the complexity of the nonlinear parts. (Given their prediction that they won't be done with a 1024-bit number within 5 years, but they will be done "well within the next decade", which 1024-bit number are they starting to factor now? I hope it's a major key that certifies big chunks of the Internet for https today, rather than one of those silly challenge keys.) Their reported time and difficulty results are great lower bounds on the capabilities of the covert or criminal -- but don't mistake them for upper bounds! No open-community academic has ever designed, built and deployed special-purpose hardware for factoring numbers of this size. Yet they have published designs that claim order-of-magnitude speedups or better on time-consuming parts of the process. EFF read similar published paper designs for DES cracking. When a few years later we built the actual device, we discovered that the basic structure of the academics' designs really did work. There are good reasons to believe that the covert community *has* built RSA cracking hardware as good or better than what's been publicly designed. And in some places covert agencies and organized crime are partners, thus merely stealing large amounts of money, as opposed to military objectives, might motivate a covert key crack. Here is Europe's consensus report on recommended key sizes, also co-authored by Lenstra: ECRYPT2 Yearly Report on Algorithms and Keysizes (2010). http://www.ecrypt.eu.org/documents/D.SPA.13.pdf For RSA, "we recommend |N| >= 1024 for legacy systems and |N| >= 2432 for new systems." A more accessible table of ECRYPT2-2010 recommendations: http://www.keylength.com/en/3/ RSA Bits Security level ---- -------------- 1008: Short-term protection against medium organizations, medium-term protection against small organizations 1248: Very short-term protection against agencies, long-term protection against small organizations Smallest general-purpose level, 1776: Legacy standard level 2432: Medium-term protection 3248: Long-term protection Generic application-independent recommendation, protection from 2009 to 2040 15424: "Foreseeable future" Good protection against quantum computers, unless Shor's algorithm applies John --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com