148 views

Skip to first unread message

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

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]>We are happy to announce that

>

>RSA-129 = 1143816257578888676692357799761466120102182967212423625625618429\

> 35706935245733897830597123563958705058989075147599290026879543541

> = 3490529510847650949147849619903898133417764638493387843990820577 *

> 32769132993266709549961988190834461413177642967992942539798288533

>

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

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

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

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

^^ ^^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

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

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?

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

___________________________________________________________________________

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

|> 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.

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

: 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."

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

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

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."

: 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.

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

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

Apr 27, 1994, 11:13:47 PM4/27/94

to

In article <austinCo...@netcom.com> aus...@netcom.com (Tony Austin)

writes:

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 +---------------------------------------------------------+

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?

>

>: 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>and a hack of a way from 1024.

>

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

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

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=

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.

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

Apr 28, 1994, 9:22:18 AM4/28/94

to

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.

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]:

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" ;----)

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

to

In <2pogho$6...@fbi-news.informatik.uni-dortmund.de> egge...@cantor.informatik.uni-dortmund.de (Heinz-Bernd Eggenstein (LS2)) writes:

>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 :)

Apr 28, 1994, 8:16:18 AM4/28/94

to

>>>>> "Heinz-Bernd" == Heinz-Bernd Eggenstein (LS2)

>>>>> <egge...@cantor.informatik.uni-dortmund.de> writes:

>>>>> <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. ==

/||| | | | | | | | | | | | | | | | | | | | | | | |||\

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 ==

/||| | | | | | | | | | | | | | | | | | | | | | | |||\

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

: 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

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....)

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?

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!

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

to

> 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! ;-)

Apr 28, 1994, 2:59:25 PM4/28/94

to

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?

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 |

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

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.

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...

> 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 -

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.

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.)

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:

>

>[...]>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. \/_/

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

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

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.

:

:[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"

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