1994-04-27 - Re: RSA-129…what’s the big deal?

Header Data

From: Derek Atkins <warlord@ATHENA.MIT.EDU>
To: tcmay@netcom.com (Timothy C. May)
Message Hash: cac8b1ff48c5f9f90f4a739981d7338899640a18c0d7be9d61b5ad81f84dd5f3
Message ID: <199404270533.BAA04222@charon.MIT.EDU>
Reply To: <199404270516.WAA18438@netcom.com>
UTC Datetime: 1994-04-27 05:34:22 UTC
Raw Date: Tue, 26 Apr 94 22:34:22 PDT

Raw message

From: Derek Atkins <warlord@ATHENA.MIT.EDU>
Date: Tue, 26 Apr 94 22:34:22 PDT
To: tcmay@netcom.com (Timothy C. May)
Subject: Re: RSA-129...what's the big deal?
In-Reply-To: <199404270516.WAA18438@netcom.com>
Message-ID: <199404270533.BAA04222@charon.MIT.EDU>
MIME-Version: 1.0
Content-Type: text/plain

[stuff deleted]
> That is, it took MMA only 0.066 second, mostly overhead, to multiply
> your two factors to the product you gave.
[more stuff deleted]
> So, this took slightly longer, 4194 seconds, or a bit over an hour,
> but MMA had no problem factoring this number. Why such a big deal?

Cute, Tim!  (Uhh, you're about 3 weeks too late for this ;-)

Actually, the *first* thing I did when I received these factors was
fire up a trusty mathematics package and verify the product: bc. :-)

Although I admit that RSA-129 dprobably does not have any cosmic
significance with regards to protecting any vital data, it is a data
point: it is the largest number of its type to ever have been
factored.  As a result, it tells us that 425-bit keys are not secure,
and keys not much bigger are not secure, either, today!

But you are right, we are learning alot about factoring and
distributed problems as a result of this exercise (at least I feel
that I have learned alot).


         Derek Atkins, SB '93 MIT EE, G MIT Media Laboratory
       Member, MIT Student Information Processing Board (SIPB)
    Home page: http://www.mit.edu:8001/people/warlord/home_page.html
       warlord@MIT.EDU    PP-ASEL     N1NWH    PGP key available