[Monotone-devel] Fwd: 307 digit number factored

[Jack Lloyd]

[Article summary: 307 digit = 1019 bit integer of special form
factored by Lenstra. It took 11 months on a very large cluster (exact
size not mentioned)]

While of course most/all Monotone keys are not high value enough to be
worth this kind of effort, it may be worthwhile to either increase the
default keysize and/or allow the user to specify a different size,
since this will only get easier (eg factoring projections for 2020
show 1024-bit keys being trivially weak), key lifetimes are measured
in years, and (hopefully!) Monotone will become more widely used over
time. Eventually the two values, current cost of factoring a key of
this size and the value of factoring a particular key (eg the key of a
lead developer on a major project) will cross, at which point badness
becomes increasingly likely.

Obviously the date of there being any real risk here is a number of
years off, but I thought it would be of interest.

Are there any provisions for key rollover ATM? (Either due to
factoring or more likely events like machine compromise)

-Jack

----- Forwarded message from "Perry E. Metzger" <address@hidden> -----

From: "Perry E. Metzger" <address@hidden>
To: address@hidden
Date: Mon, 21 May 2007 14:44:28 -0400
Subject: 307 digit number factored

Quoting the original article:

   A mighty number falls

   Mathematicians and number buffs have their records. And today, an
   international team has broken a long-standing one in an impressive
   feat of calculation.

   On March 6, computer clusters from three institutions \u2013 the
   EPFL, the University of Bonn and NTT in Japan -- reached the end of
   eleven months of strenuous calculation, churning out the prime
   factors of a well-known, hard-to-factor number that is a whopping
   307 digits long.

   "This is the largest 'special' hard-to-factor number factored to
   date," explains EPFL cryptology professor Arjen Lenstra. (The
   number is 'special' because it has a special mathematical form --
   it is close to a power of two.) The news of this feat will grab the
   attention of information security experts and may eventually lead
   to changes in encryption techniques.


http://www.physorg.com/news98962171.html

My take: clearly, 1024 bits is no longer sufficient for RSA use for
high value applications, though this has been on the horizon for some
time. Presumably, it would be a good idea to use longer keys for all
applications, including "low value" ones, provided that the slowdown
isn't prohibitive. As always, I think the right rule is "encrypt until
it hurts, then back off until it stops hurting"...

-- 
Perry E. Metzger                address@hidden

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to address@hidden

----- End forwarded message -----