2048-bit RSA keys

[John Gilmore]

> 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 majordomo at metzdowd.com