RSA-129

148 views
Skip to first unread message

Derek Atkins

unread,
Apr 27, 1994, 12:06:25 AM4/27/94
to
We are happy to announce that

RSA-129 = 1143816257578888676692357799761466120102182967212423625625618429\
35706935245733897830597123563958705058989075147599290026879543541
= 3490529510847650949147849619903898133417764638493387843990820577 *
32769132993266709549961988190834461413177642967992942539798288533


The encoded message published was

968696137546220614771409222543558829057599911245743198746951209308162\
98225145708356931476622883989628013391990551829945157815154

This number came from an RSA encryption of the `secret' message using the
public exponent 9007. When decrypted with he `secret' exponent

106698614368578024442868771328920154780709906633937862801226224496631\
063125911774470873340168597462306553968544513277109053606095

this becomes

200805001301070903002315180419000118050019172105011309190800151919090\
618010705

Using the decoding scheme 01=A, 02=B, ..., 26=Z, and 00 a space between
words, the decoded message reads

THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE

To find the factorization of RSA-129, we used the double large prime
variation of the multiple polynomial quadratic sieve factoring method.
The sieving step took approximately 5000 mips years, and was carried
out in 8 months by about 600 volunteers from more than 20 countries,
on all continents except Antarctica. Combining the partial relations
produced a sparse matrix of 569466 rows and 524338 columns. This matrix
was reduced to a dense matrix of 188614 rows and 188160 columns using
structured Gaussian elimination. Ordinary Gaussian elimination on this
matrix, consisting of 35489610240 bits (4.13 gigabyte), took 45 hours
on a 16K MasPar MP-1 massively parallel computer. The first three
dependencies all turned out to be `unlucky' and produced the trivial
factor RSA-129. The fourth dependency produced the above factorization.

We would like to thank everyone who contributed their time and effort
to this project. Without your help this would not have been possible.

Derek Atkins
Michael Graff
Arjen Lenstra
Paul Leyland
--
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
war...@MIT.EDU PP-ASEL N1NWH PGP key available

Rob U.S.M.

unread,
Apr 27, 1994, 5:04:25 AM4/27/94
to
war...@MIT.EDU (Derek Atkins) writes:
>We are happy to announce that
>
>RSA-129 = 1143816257578888676692357799761466120102182967212423625625618429\
> 35706935245733897830597123563958705058989075147599290026879543541
> = 3490529510847650949147849619903898133417764638493387843990820577 *
> 32769132993266709549961988190834461413177642967992942539798288533
>
>[etc]

I used Franc,ois Morain's ECPP software to prove that the factors are
indeed prime. Of course that was virtually certain, but the pedant in
me wanted proof...

Rob

David Sternlight

unread,
Apr 27, 1994, 12:27:59 PM4/27/94
to
In article <WARLORD.94...@incommunicado.mit.edu>,

Derek Atkins <war...@MIT.EDU> wrote:
>We are happy to announce that
>
>RSA-129 = 1143816257578888676692357799761466120102182967212423625625618429\
> 35706935245733897830597123563958705058989075147599290026879543541
> = 3490529510847650949147849619903898133417764638493387843990820577 *
> 32769132993266709549961988190834461413177642967992942539798288533

Congratulations, indeed.

Is there some sort of prize from RSADSI for this?

How long do you estimate the job would have taken if it were all done on a
single 64,000 processor Connection Machine such as the one delivered to DOD
a while ago, at processor speeds of that machine.

Given the answer to the question just above, how long would it take to crack
a 512bit key of the sort used by Apple in the AOCE signer? A 1024 bit key of
the sort people are now moving to for PGP and RIPEM, making no further
assumptions about mathematical or technological breakthroughs beyond what's
known about the Connection Machine?

David

Phil Karn

unread,
Apr 27, 1994, 5:08:54 PM4/27/94
to
In article <WARLORD.94...@incommunicado.mit.edu>,
Derek Atkins <war...@MIT.EDU> wrote:
>We are happy to announce that
>
>RSA-129 = 1143816257578888676692357799761466120102182967212423625625618429\
> 35706935245733897830597123563958705058989075147599290026879543541
> = 3490529510847650949147849619903898133417764638493387843990820577 *
> 32769132993266709549961988190834461413177642967992942539798288533
^^ ^^

Indeed! Given that the specs called for just being able to factor
42=6x9 in 5 billion years, I'd say this exceeded the manufacturer's
expectations by a comfortable margin.

Will the next job take the full 7.5 million years to run? :-)

In article <strnlghtC...@netcom.com>, strn...@netcom.com (David Sternlight) writes:

|> Given the answer to the question just above, how long would it take to crack
|> a 512bit key of the sort used by Apple in the AOCE signer? A 1024 bit key of
|> the sort people are now moving to for PGP and RIPEM, making no further
|> assumptions about mathematical or technological breakthroughs beyond what's
|> known about the Connection Machine?

According to p 212 of Schneier, the Number Field Sieve algorithm has a
time complexity on the order of

exp( (ln n)**1/3 * (ln (ln(n)))**2/3)

Given the now-known effort for RSA129 (about 429 bits) you should be able
to compute the answers to your questions.

Phil

John Jack Repenning

unread,
Apr 27, 1994, 5:09:37 PM4/27/94
to

In article <WARLORD.94...@incommunicado.mit.edu>, war...@MIT.EDU writes:
> We are happy to announce that
>
> RSA-129 = 1143816257578888676692357799761466120102182967212423625625618429\
> 35706935245733897830597123563958705058989075147599290026879543541
> = 3490529510847650949147849619903898133417764638493387843990820577 *
> 32769132993266709549961988190834461413177642967992942539798288533

There was an article in the San Francisco Chronicle today about this
(I believe it was over a Knight-Ridder byline, so others may have seen
it as well). At least in the Chron, the headline and other teaser
text made great play of the claim that the cracking was far easier
than anyone had expected. Is there any meaning to that suggestion?

Neither the article text, nor the discussions I've seen here in News
seem to suggest any such thing. The closest approach to that was the
observation that Lotus Notes uses a key-size not much larger than
this; perhaps they really meant "Lotus is placed right on the edge of
current crackability"?


Jack Repenning M/S 1-875 ja...@wpd.sgi.com
Silicon Graphics, Inc. x3-3027 Off:(415) 390-3027
Visual Magic Division Fax:(415) 390-6056

Tony Austin

unread,
Apr 27, 1994, 6:03:52 PM4/27/94
to
For us lower forms of life, "Lets talk story."
Does this mean the RSA used in PGP is now de facto cracked?

I was just about to pay for a copy of PGP too. RATS!

Tony Austin
--
___________________________________________________________________________
"Art appreciation, like love, cannot be done by proxy." Robert Henri-artist
___________________________________________________________________________

Curt Howland

unread,
Apr 27, 1994, 7:39:57 PM4/27/94
to
In article <austinCo...@netcom.com>, aus...@netcom.com (Tony Austin) writes:
|> For us lower forms of life, "Lets talk story."
|> Does this mean the RSA used in PGP is now de facto cracked?
|>
|> I was just about to pay for a copy of PGP too. RATS!
|>
|> Tony Austin

What this means, is that *one* *single* *possible*
RSA key of some 429 bits has been factored. If someone
expended this effort yet again, they could crack
*one* other possible RSA key of some 429 bits.

RSA can use innumerable different keys. One medium one
has been broken. Do your self a favor and do not put
in "429" when PGP asks how long you want your key to
be. That way, it won't somehow pick one that's been
factored.

The algorythem is still working, and secure.

*sheesh.*

---
Curt Howland how...@nsipo.nasa.gov
The above does not constitute an official
statement of NASA or anyone else.

Jered Floyd

unread,
Apr 27, 1994, 9:21:02 PM4/27/94
to
David Sternlight (strn...@netcom.com) wrote:
: In article <WARLORD.94...@incommunicado.mit.edu>,

: Derek Atkins <war...@MIT.EDU> wrote:
: >We are happy to announce that
: >
: >RSA-129 = 1143816257578888676692357799761466120102182967212423625625618429\
: > 35706935245733897830597123563958705058989075147599290026879543541
: > = 3490529510847650949147849619903898133417764638493387843990820577 *
: > 32769132993266709549961988190834461413177642967992942539798288533

: Congratulations, indeed.

: Is there some sort of prize from RSADSI for this?

Yes, they get $100, which they are donating to the FSF.

: Given the answer to the question just above, how long would it take to crack


: a 512bit key of the sort used by Apple in the AOCE signer? A 1024 bit key of
: the sort people are now moving to for PGP and RIPEM, making no further
: assumptions about mathematical or technological breakthroughs beyond what's
: known about the Connection Machine?

Well, RSA-129 is about 428 bits. That's significantlly less that 512,
and a hack of a way from 1024.


--
Jered Floyd
jjf...@vela.acs.oakland.edu
GAT d? -p+ c++++ l+ u++ e*@ m++ s/-- n--- h++ f? g- w++ t+++ r++
PGP Public key available by finger."

Michael Graff

unread,
Apr 27, 1994, 9:32:38 PM4/27/94
to
In <2pmt4d$4...@news.arc.nasa.gov> how...@noc.arc.nasa.gov (Curt Howland) writes:

>|> Does this mean the RSA used in PGP is now de facto cracked?

>What this means, is that *one* *single* *possible*

>RSA key of some 429 bits has been factored. If someone
>expended this effort yet again, they could crack
>*one* other possible RSA key of some 429 bits.

>RSA can use innumerable different keys. One medium one
>has been broken. Do your self a favor and do not put
>in "429" when PGP asks how long you want your key to
>be. That way, it won't somehow pick one that's been
>factored.

>The algorythem is still working, and secure.

What this means is that keys of 429 bits or slightly larger *can* be broken by
a team of internet hackers with people who are willing to donate cpu time.
This means I'd put 1024 in where pgp asks for a key size. I sure as hell did.
:)

--Michael, one of the RSA-129 coordinators.

--
Michael Graff <expl...@iastate.edu> Speaking for myself, not
Project Vincent Voice: (515)294-4994 for ISU or the ISUCC
Iowa State Univ Comp Center Fax: (515)294-1717
Ames, IA 50011
--
Michael Graff <expl...@iastate.edu> Speaking for myself, not
Project Vincent Voice: (515)294-4994 for ISU or the ISUCC
Iowa State Univ Comp Center Fax: (515)294-1717
Ames, IA 50011

William Unruh

unread,
Apr 27, 1994, 7:44:22 PM4/27/94
to
aus...@netcom.com (Tony Austin) writes:

>For us lower forms of life, "Lets talk story."
>Does this mean the RSA used in PGP is now de facto cracked?

No, it means that if you use a 430 or so bit key, it will take someone
a conceivable amount of time to crack it. ( a year or so with 600
workstations working part time- say a few hours to days on the best
thing available) a 1024 bit key however would take a fair amount of time
longer.


>I was just about to pay for a copy of PGP too. RATS!

WEll I guess you get what you pay for.

--
Bill Unruh
un...@physics.ubc.ca

John K. Taber

unread,
Apr 27, 1994, 8:56:44 PM4/27/94
to
Tony Austin (aus...@netcom.com) wrote:
: For us lower forms of life, "Lets talk story."

No, no. This was the original RSA challenge cipher that appeared in
Scientific American ages ago. There was not that much research in
factoring at that time, and R, S, and A must have thought that a 129
digit modulus was reasonably secure. And so it has been for years.

Get PGP by all means, just don't use 129 digit PQs.

Congratulations!
--
John K. Taber jkt...@netcom.com
========================================================================
Avoid taking a definite stand on great public issues either in the Senate
or before the people. Bend your energies towards making friends of key
men in all classes of voters. -- advice to Cicero from his brother and
campaign manager, Quintus.

Magnus Y Alvestad

unread,
Apr 27, 1994, 10:27:25 PM4/27/94
to
Bill> someone a conceivable amount of time to crack it. ( a year or so
Bill> with 600 workstations working part time- say a few hours to days
Bill> on the best thing available) a 1024 bit key however would take a

Not unless the best thing available has become a lot better since I
last checked. I'd say at least a month.

-Magnus

Jeff Gostin

unread,
Apr 27, 1994, 11:13:47 PM4/27/94
to
In article <austinCo...@netcom.com> aus...@netcom.com (Tony Austin)
writes:

> For us lower forms of life, "Lets talk story."
> Does this mean the RSA used in PGP is now de facto cracked?

No. It means that _one possible prime number used in key generation_
has been cracked. We have now "cracked" the factoring of RSA-129, a 129
digit number. This is not the only prime possible to use, and probably
does little to weaken the algorithm's strength.

--Jeff
--
====== ====== +-----------...@eternal.pha.pa.us----------------+
== == | The new, improved, environmentally safe, bigger, better,|
== == -= | faster, hypo-allergenic, AND politically correct .sig. |
==== ====== | Now with a new fresh lemon scent! |
PGP Key Available +---------------------------------------------------------+

Donald T. Davis

unread,
Apr 28, 1994, 12:57:53 AM4/28/94
to
In article jjf...@vela.acs.oakland.edu (Jered Floyd) writes:
>: Given the answer to the question just above, how long would it take to crack
>: a 512bit key of the sort used by Apple in the AOCE signer?
>
>Well, RSA-129 is about 428 bits. That's significantlly less that 512,
>and a hack of a way from 1024.
>
using the quadratic seive, it takes roughly a factor of 10 more
computing resources (disks & cycles, if not keyboards) to factor
each additional 10 digits. further, that factor of ten becomes
available in off-the-shelf workstations every 2-5 years. in
practice, the biggest factorable number has been growing by about
10 digits per year, thanks in part to algorithmic improvements.
i (and others) figure 512 bits will become inadequate by the late
'90's. at the crypto '93 conference, where rsa-120's demise was
announced (it took 1/6 as much resources), people were already
recommending the move to 768-bit or 1024-bit rsa keys.

it's not yet possible to guess at what it would take to crack
a 1024-bit key, because the general number field sieve, which
will eventualy/soon replace the quadratic seive as the fastest
factoring algorithm, has unknown constants in its complexity-
growth curve. once gnfs sees some use, those constants will get
pinned down a little, and such predictions will then be more
possible. here, i'm paraphrasing what i heard last year at crypto.

-don davis, openvision

Peter T. Wang

unread,
Apr 28, 1994, 3:23:56 AM4/28/94
to
aus...@netcom.com (Tony Austin) writes:

No, RSA is fundamentally "secure" in the sense that the computational power
needed to factor the product of two large primes is far greater than that
required to find these two primes. Until an efficient mathematical method
for factoring numbers is discovered (if it exists), RSA in general cannot
be cracked.

Peter Wang

David Sternlight

unread,
Apr 28, 1994, 2:44:55 AM4/28/94
to
-----BEGIN PRIVACY-ENHANCED MESSAGE-----
Proc-Type: 4,MIC-CLEAR
Content-Domain: RFC822
Originator-ID-Asymmetric:
ME0xCzAJBgNVBAYTAlVTMSAwHgYDVQQKExdSU0EgRGF0YSBTZWN1cml0eSwgSW5j
LjEcMBoGA1UECxMTUGVyc29uYSBDZXJ0aWZpY2F0ZQ==,B7
MIC-Info: RSA-MD5,RSA,
cDU5NnZ5+1ID5sNORhZT+6kTtzj0ROugXTgDMDrBZb4SfjPSWNdLMd8gCgoCxoWE
Isl8omYuTkQpGUVzdUYFzkkYSHjakC5RaEGTXnREypDjuWi7ZOkdRdPWG4xxFhak
31REua7LQ2fIWmyAzLVJO5LMHUBfus6u5lOSfskXPzM=

"Do your self a favor and do not putin "429" when PGP asks how long you want
your key to be."

Chuckle of the day.

David
-----END PRIVACY-ENHANCED MESSAGE-----
Created with RIPEM Mac.

David Sternlight

unread,
Apr 28, 1994, 2:49:47 AM4/28/94
to
In article <MAGNUS.94A...@svartbak.ii.uib.no>,

I don't think so. For the same key length, the 64,000 processor Connection
Machine DOD is said to have bought should take a lot less than 4 days,
depending on what the ratio of average time spent per day on the
workstations is compared with full time on the Connection machine.

And if a 64,000 processor machine is one we know about, what do you suppose
they have that we don't know about?

David

David Harwood

unread,
Apr 28, 1994, 9:22:18 AM4/28/94
to
In article <MAGNUS.94A...@svartbak.ii.uib.no>,
Magnus Y Alvestad <mag...@ii.uib.no> wrote:
\\\\
In my field we have to use supercomputers such as the CM-5. However
if we really want speed for special applications, we design VLSI
devices which are much more efficient. Moreover, this technology
has advanced to the point that our government and some European consortiums
have factories that can produce these chips very quickly from a design.
The computers that broke RSA-129, no matter what they are, are not
very fast at all compared to what is easily (and cheaply) built for
special purposes. Just to put this is discussion in some better
perspective about what is feasible computationally now. (Keep in mind
that the best general-purpose supercomputer chess programs are much less
efficient than custom VLSI designs (by a large factor).
D.H.

Heinz-Bernd Eggenstein (LS2)

unread,
Apr 28, 1994, 10:17:28 AM4/28/94
to
In <WARLORD.94...@incommunicado.mit.edu> ,
expl...@iastate.edu (Michael Graff) writes [on the RSA-129 success]:

>What this means is that keys of 429 bits or slightly larger *can* be broken by
>a team of internet hackers with people who are willing to donate cpu time.

^^^^^^^
At least in theory, I think it's also possible to speculate about a distributed
cryptographic attack by people *not willing* to do this, e.g. by hiding
the algorithm inside an operating system or application program and stealing
CPU cycles from the user ("parasitic cryptanalysis", if you like).

Feedback of results to the author of the program could be established thru e-mail
or "maintenance messages" ("malfunction, send this number ... to ...". Even
better: "You broke the hi-score and won 100 $!! call ... ").

Heinz-Bernd Eggenstein

P.S.: This should be great stuff for conspiracy fans: Imagine: "Tetris wasn't a
game at all, it was a distributed factoring program by the KGB" ;----)

Michael Graff

unread,
Apr 28, 1994, 11:34:11 AM4/28/94
to

>In <WARLORD.94...@incommunicado.mit.edu> ,
>expl...@iastate.edu (Michael Graff) writes [on the RSA-129 success]:

>At least in theory, I think it's also possible to speculate about a

>distributed cryptographic attack by people *not willing* to do this, e.g. by
>hiding the algorithm inside an operating system or application program and
>stealing CPU cycles from the user ("parasitic cryptanalysis", if you like).

Most users would feel 8M of core sliding in and out when playing a game. :)

Someone suggested we make an After Dark module and let all those Mac's factor
when the screen is being saved :)

Stainless Steel Rat

unread,
Apr 28, 1994, 8:16:18 AM4/28/94
to
>>>>> "Heinz-Bernd" == Heinz-Bernd Eggenstein (LS2)
>>>>> <egge...@cantor.informatik.uni-dortmund.de> writes:

Heinz-Bernd> P.S.: This should be great stuff for conspiracy fans: Imagine:
Heinz-Bernd> "Tetris wasn't a game at all, it was a distributed factoring
Heinz-Bernd> program by the KGB" ;----)

But... but... but it is!!! :)

[Followups to alt.consipracy only, please]

\||| | | | | | | | | | | | | | | | | | | | | | | |||/
== Rat <rat...@ccs.neu.edu> WWW Page: http://www.ccs.neu.edu/home/ratinox ==
== Democracy is four wolves and a lamb voting on what to have for lunch. ==
/||| | | | | | | | | | | | | | | | | | | | | | | |||\

Stainless Steel Rat

unread,
Apr 28, 1994, 8:18:38 AM4/28/94
to
>>>>> "John" == John Jack Repenning <ja...@dblues.wpd.sgi.com> writes:

John> At least in the Chron, the headline and other teaser text made great
John> play of the claim that the cracking was far easier than anyone had
John> expected. Is there any meaning to that suggestion?

Probably just that the first couple of factorizations were "unlucky" and
were the correct ones, rather than having to scan through the whole list of
factorizations to find the right one. So the search took a couple of
seconds instead of a couple of hours.

\||| | | | | | | | | | | | | | | | | | | | | | | |||/
== Rat <rat...@ccs.neu.edu> WWW Page: http://www.ccs.neu.edu/home/ratinox ==

== When sub-culture becomes pop-culture, ==
== it's time to move on to something new. --Dana Carvey ==
/||| | | | | | | | | | | | | | | | | | | | | | | |||\

Rogier Wolff

unread,
Apr 28, 1994, 12:30:35 PM4/28/94
to
Curt Howland (how...@noc.arc.nasa.gov) wrote:

: In article <austinCo...@netcom.com>, aus...@netcom.com (Tony Austin) writes:
: |> For us lower forms of life, "Lets talk story."
: |> Does this mean the RSA used in PGP is now de facto cracked?
: |>
: |> I was just about to pay for a copy of PGP too. RATS!
: |>
: |> Tony Austin

: RSA can use innumerable different keys. One medium one


: has been broken. Do your self a favor and do not put
: in "429" when PGP asks how long you want your key to
: be. That way, it won't somehow pick one that's been
: factored.

429 bits reduces to prime factors of about 69 decimal digits:

There are around 10^69 numbers of length 69. Of those around 0.7% to 1.0%
is prime. This gives you around 0.5 * 10^138 possible keys. The chances
are quite small :-) that you'd get the one that has already been cracked.

Roger.


--
* As a protest against the recent bunch proposed anti-cryptography *
* laws, this message has been doubly encryted using the rot13 algorithm. *
EMail: wo...@dutecai.et.tudelft.nl ** Tel +31-15-783643 or +31-15-142371

Rogier Wolff

unread,
Apr 28, 1994, 12:37:44 PM4/28/94
to
Michael Graff (expl...@iastate.edu) wrote:

: What this means is that keys of 429 bits or slightly larger *can* be broken by


: a team of internet hackers with people who are willing to donate cpu time.
: This means I'd put 1024 in where pgp asks for a key size. I sure as hell did.
: :)

An internet CRACKER could find 250000 hosts on the internet "willing" to
contribute and perform part of the task in less than a day..... :-(
(He's then left with a 138000x138000 matrix that needs a little postprocessing
to actually crack a key....)

John Jack Repenning

unread,
Apr 28, 1994, 2:29:28 PM4/28/94
to

> How long do you estimate the job would have taken if it were all done on a
> single 64,000 processor Connection Machine such as the one delivered to DOD
> a while ago, at processor speeds of that machine.

Does it have half a terabyte of RAM? Speaking only as one of the
people who provided cycles to the effort, it seems that the program
uses, quite thoroughly and constantly, around 8 megabytes per process;
a CM isn't prepared to feed that hunger for all its many minds, is it?

Eric Weaver

unread,
Apr 28, 1994, 2:30:59 PM4/28/94
to

[Corrected the size of the effort for RSA-129]

In article <2pmk96$2...@qualcomm.com>, ka...@unix.ka9q.ampr.org (Phil Karn) writes:
|> According to p 212 of Schneier, the Number Field Sieve algorithm has a
|> time complexity on the order of
|>
|> exp( (ln n)**1/3 * (ln (ln(n)))**2/3)
|>
|> Given the now-known effort for RSA129 (about 429 bits) you should be able
|> to compute the answers to your questions.


If I've done the math right, and using 5000 MIPS-years for the recent effort,
a 1024-bit key comes out to 109 million MIPS-years.

Time for a new new algorithm if somebody's gonna crack the certificate
authority key... B-]


--
Eric Weaver Sony AVTC 3300 Zanker Road, MS 4B1 SJ CA 95134 408 955-4904
& Chief Engineer, KFJC 89.7 Foothill College Los Altos Hills, CA 94022
... Home of the Radio Devil Network / Live at SXSW '94!

John Jack Repenning

unread,
Apr 28, 1994, 2:37:19 PM4/28/94
to

In article <2pmkah$m...@fido.asd.sgi.com>, ja...@dblues.wpd.sgi.com writes:

> There was an article in the San Francisco Chronicle today about this
> (I believe it was over a Knight-Ridder byline, so others may have seen
> it as well).

Well, I really botched that one: it was the San Jose Mercury News,
and it was their very own byline. Which naturally explains any errors
of fact or orientation encountered.

It was MYST that was reviewed in the Chron over a Knight-Ridder
byline. They got that part all right! ;-)

Steve Tate

unread,
Apr 28, 1994, 2:59:25 PM4/28/94
to
John Jack Repenning (ja...@dblues.wpd.sgi.com) wrote:

> > How long do you estimate the job would have taken if it were all done on a
> > single 64,000 processor Connection Machine such as the one delivered to DOD
> > a while ago, at processor speeds of that machine.

> Does it have half a terabyte of RAM? Speaking only as one of the
> people who provided cycles to the effort, it seems that the program
> uses, quite thoroughly and constantly, around 8 megabytes per process;
> a CM isn't prepared to feed that hunger for all its many minds, is it?

I didn't think the CM-5 could get larger than 16k nodes... perhaps the
figure for "64k processors" refers to 64k vector units, of which there are
four per node (so there would be 64k in a 16k node machine). I don't know
the source of the information about the DOD machine though, so I can
only speculate. Anyway, assuming a 16k node machine, the CM-5 has 32 Meg
of RAM per node, which gives the whopping figure of half a terabyte of
memory (exactly! did you know this before you asked your question?).

Now the real question is: I have worked on a 32 node CM-5 doing some
testing of parallel algorithms. The 32 node CM-5 seems to have problems
staying up for more than a few days or before a processor dies, or whatever
(I think they've been through quite a few processor boards). Has anyone
worked on a larger machine? If the processor boards blow as fast on
a 16k node machine, it seems like it would be damned hard to have the
machine running for more than an hour at a time....

--
Steve Tate --- s...@cs.unt.edu | "Nationalism is an infantile sickness.
Dept. of Computer Sciences | It is the measles of the human race."
University of North Texas | -- A. Einstein
Denton, TX 76201 |

Geoff Kuenning

unread,
Apr 28, 1994, 2:31:26 PM4/28/94
to
In article <2pmk96$2...@qualcomm.com> ka...@servo.qualcomm.com writes:

> exp( (ln n)**1/3 * (ln (ln(n)))**2/3)
>
> Given the now-known effort for RSA129 (about 429 bits) you should be able
> to compute the answers to your questions.

I just wrote the following little ugly program to try this out:

#include <stdio.h>
#include <math.h>

extern double exp ();
extern double pow ();
extern double log ();

double complxty();
extern double atof ();

int main (argc, argv)
int argc;
char *argv[];
{
double base = complxty (429.0);

while (--argc > 0)
{
++argv;
printf ("%d: %g\n",
atoi (argv[0]), complxty ((double) atoi (argv[0])) / base);
}
return 0;
}

double complxty(n)
double n;
{
return exp(pow(log(n),0.3333)*pow(log(log(n)),0.66667));
}

Running it with arguments "429 512 1024 2048 4096 8192 16384" gave the
following frightening results:

429: 1
512: 1.05647
1024: 1.29931
2048: 1.57926
4096: 1.90026
8192: 2.26656
16384: 2.68272

Given predictable increases in processor speed and power, this seems
to say that RSA is crackable now for 512-bit keys and soon for even
very long keys. Somebody please tell me I made a mistake somewhere!
--
Geoff Kuenning ge...@ficus.cs.ucla.edu ge...@ITcorp.com

Geoff Kuenning

unread,
Apr 28, 1994, 3:46:57 PM4/28/94
to
In article <1994Apr28.1...@cs.ucla.edu> I write:

> Somebody please tell me I made a mistake somewhere!

Eric Wong straightened me out. The formula posted was for factoring
the number N, not for factoring N digits. So I had an extra log in my
program. The correct relative difficulties, after correcting this,
are:

429: 1
512: 7.66719
1024: 105473
2048: 2.9718e+10
4096: 4.28061e+17
8192: 1.02939e+27
16384: 1.90839e+39

So 512 bits would take over 3 years, and 1024 bits are still pretty
much impossible to factor. I'm *much* happier now.

Martin Brown

unread,
Apr 28, 1994, 3:07:51 PM4/28/94
to
> To find the factorization of RSA-129, we used the double large prime
> variation of the multiple polynomial quadratic sieve factoring method.
> The sieving step took approximately 5000 mips years, and was carried
> out in 8 months by about 600 volunteers from more than 20 countries...

Let's see... 5000 mips years, that's uh... how much in NSA mips time?

a day?
an hour?
a minute, maybe?

Clearly, the security provided by 428 bits has been vastly overrated.
And it gives one pause even for the larger bit sizes.

What's that sound...
ahh, the sound of assholes puckering up across the world. ;)

--

- mjb -

m...@netcom.com

David Harwood

unread,
Apr 28, 1994, 5:03:22 PM4/28/94
to
In article <2pova8$m...@fido.asd.sgi.com>,

John Jack Repenning <ja...@dblues.wpd.sgi.com> wrote:
>
>In article <strnlghtC...@netcom.com>, strn...@netcom.com writes:
>
>> How long do you estimate the job would have taken if it were all done on a
>> single 64,000 processor Connection Machine such as the one delivered to DOD
>> a while ago, at processor speeds of that machine.
>
>Does it have half a terabyte of RAM? Speaking only as one of the
>people who provided cycles to the effort, it seems that the program
>uses, quite thoroughly and constantly, around 8 megabytes per process;
>a CM isn't prepared to feed that hunger for all its many minds, is it?
>
\\\\\\
Our CM-5 has 32 MBytes per processor.

Again, serious code breakers probably will use VLSI and not general
purpose computers. And custom VLSI designs are much, much faster than
any commercial CPU for their function. (A VLSI chip was designed for
one of my algorithms and ran as fast as 8000 (slow) CM-2 processors;
I'm not saying this is representative, although the CM-2 was well suited
for the processing and the code was hand optimized.)


Rob U.S.M.

unread,
Apr 28, 1994, 6:17:04 PM4/28/94
to
ge...@ficus.cs.ucla.edu (Geoff Kuenning) writes:
>In article <2pmk96$2...@qualcomm.com> ka...@servo.qualcomm.com writes:
>
>> exp( (ln n)**1/3 * (ln (ln(n)))**2/3)
>>
>> Given the now-known effort for RSA129 (about 429 bits) you should be able
>> to compute the answers to your questions.
>
>I just wrote the following little ugly program to try this out:
>
>[...]

>Running it with arguments "429 512 1024 2048 4096 8192 16384" gave the
>following frightening results:
>
> 429: 1

>[...]


> 16384: 2.68272
>
>Given predictable increases in processor speed and power, this seems
>to say that RSA is crackable now for 512-bit keys and soon for even
>very long keys. Somebody please tell me I made a mistake somewhere!

OK: you made a mistake somewhere. First of all the formula is really:

O( exp( ln(n)^(1/3) * ln(ln(n))^(2/3) * ((64/9)^(1/3)+o(1)) )

Second of all, we are not talking about factoring 429, but 429-bit numbers.
Your "complxty" functions should be something like:

/*--complxty----------------------------------------------------------------*/

double complxty(double n) {
double l, c;

l = n/log(2);
c = pow(64.0/9.0, 1.0/3.0);

return exp(pow(l,1.0/3.0)*pow(log(l),2.0/3.0)*c);
} /* end complexity */

/*--------------------------------------------------------------------------*/

and that's just ignoring the o(1). Then the results are:

429: 1
512: 93.499
1024: 1.52007e+11
2048: 1.97327e+23
4096: 1.53709e+39
8192: 9.75511e+59
16384: 1.46726e+87

So 512 will soon be in reach. 1024 won't, with current algorithms.

Rob
--
email: {robert@vlsi,rjh@csvax,rjharley@cco}.cs.caltech.edu
www: http://cs.caltech.edu/~rjh/rjh.html Hi Kibo!
__ __
__/\_\ "r4P3 M3. r4P3 M3, MY PHR13ND. /_/\__
/_/\/_/ r4P3 M3. r4P3 M3, 4G41N." -- B1FF c0B41N \_\/\_\
\_\/_/\ /\_\/_/
\_\/ If you're offended, tough shit. \/_/

Michael Graff

unread,
Apr 28, 1994, 6:44:29 PM4/28/94
to
In <RATINOX.94...@delphi.ccs.neu.edu> rat...@ccs.neu.edu (Stainless Steel Rat) writes:

>Probably just that the first couple of factorizations were "unlucky" and
>were the correct ones, rather than having to scan through the whole list of
>factorizations to find the right one. So the search took a couple of
>seconds instead of a couple of hours.

They prolly mean the difference between 40 quadrillion years as the Sci.
American article printed and the real-life 8 months.

--Michael

Derek Atkins

unread,
Apr 28, 1994, 8:11:00 PM4/28/94
to
In article <explorer....@tbird.cc.iastate.edu> expl...@iastate.edu (Michael Graff) writes:

Someone suggested we make an After Dark module and let all those Mac's factor
when the screen is being saved :)

Hey, that was my suggestion (actually, a friend of mine).. At least
give credit where credit is due. ;-)

But to answer everyone's question, in a single sentence:

The RSA Crypto System has **NOT** been broken, only a single
RSA KeyPair has been broken. What is does mean is that a group of
users with a similar amount of computation time could break any one
key of comparible length in about the same amount of time.

-derek
(one of the)RSA-129 Project Coordinator/Programmer
--
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
war...@MIT.EDU PP-ASEL N1NWH PGP key available

Message has been deleted

Robert D. Silverman

unread,
Apr 28, 1994, 9:39:28 PM4/28/94
to
In article <1994Apr2...@kuttner.sfc.sony.com> wea...@kuttner.sfc.sony.com (Eric Weaver) writes:
:
:[Corrected the size of the effort for RSA-129]

:
:In article <2pmk96$2...@qualcomm.com>, ka...@unix.ka9q.ampr.org (Phil Karn) writes:
:|> According to p 212 of Schneier, the Number Field Sieve algorithm has a
:|> time complexity on the order of
:|>
:|> exp( (ln n)**1/3 * (ln (ln(n)))**2/3)
:|>
:|> Given the now-known effort for RSA129 (about 429 bits) you should be able
:|> to compute the answers to your questions.
:
:
:If I've done the math right, and using 5000 MIPS-years for the recent effort,
:a 1024-bit key comes out to 109 million MIPS-years.
:
(1) I do not know whether Mr. Schneier was misquoted, but if the above
quote is accurate, then the asymptotic estimate he gave was wrong.

The time complexity function should be:

exp( (c + o(1)) (log N)^1/3 (loglog N)^2/3)

For the special number field sieve, c is about 1.5. Forthe general version
c is about 1.92. And noone has published any estimates as to how fast
o(1) goes to zero, or what its value is for numbers that have been factored.

Any extrapolations based on this function would have to be viewed very
skeptically.

--
Bob Silverman
These are my opinions and not MITRE's.
Mitre Corporation, Bedford, MA 01730
"You can lead a horse's ass to knowledge, but you can't make him think"

Curt Howland

unread,
Apr 28, 1994, 10:51:25 PM4/28/94