RSA-129
Derek Atkins
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.
>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
David Sternlight
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
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
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
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
|> 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
: 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
>|> 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
>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
: 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
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
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
>: 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?
>
>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
Peter T. Wang
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
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
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
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)
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
>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
>>>>> <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
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
: 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
: 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
> 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
[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
> 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
> 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 |
Geoff Kuenning
> 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
> 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
> 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 -
David Harwood
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.
>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
>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
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
Robert D. Silverman
:
:[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
|> Someone suggested we make an After Dark module and let all those Mac's factor
|> when the screen is being saved :)
So Sorry, Maxfactor is a copywrited name....
:^>
Ken Pizzini
David Sternlight <da...@sternlight.com> wrote:
>In article <1994Apr2...@kuttner.sfc.sony.com>,
>Eric Weaver <wea...@kuttner.sfc.sony.com> wrote:
>>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.
>
>correctly,
[...]
>It certainly doesn't make arguments with respect to current key sizes that
>wave the number of atoms in the universe in the air as palatable as they at
>first seemed.
[...]
>Someone please tell me I've got the quantitative consequences wrong.
>Otherwise security is an illusion, and the best we can do is keep the bulk
>of the not-so-vastly-rich out of our traffic. (Not that that's a bad
>outcome--it's just not the high security outcome many here have been
>trumpeting.) At a minimum, 1024 bit keys may not be nearly as strong as some
>think, and we may have to got to bigger keys a lot sooner than some expect.
>Let's hope widely available machines are cheap enough and fast enough that
>the exponential increase to crack argument wins over the slower to encrypt
>and decrypt argument.
The basic assumption here (that the math was done right) doesn't seem
to match up. My understanding is that the complexity of the current
best factoring algorithm is:
O( exp( ln(n)^(1/3) * ln(ln(n))^(2/3) * ((64/9)^(1/3)+o(1)) ) )
(where n is the number being factored; i.e. log(n) is the number of digits).
This gives an expected running time for a 1024 bit modulus to be almost
171 billion times longer than for the 427 bit modulus that is rsa-129.
Given the estimate above of "5000 MIPS-years" for rsa-129, that comes
out to 853 trillion MIPS-years for a 1024 bit modulus. For a 1 million
1000 MIPS processors, this requires 853 millenia. For those made
uncomfortable by this low number, square your running time by using a
2048 bit modulus and increase the factoring running time by a factor of
another couple trillion. Of course, if you want real security (barring
breakthroughs in factoring, which are harder to predict) you might want
to go with a 8192 bit modulus and require the advisary to expend
5 vingintillion MIPS-years...
--Ken Pizzini
P.S. for our non-US readers: in this posting I use the American
numerology where 1 billion = 1000 million, etc.; not the
European 1 billion = 1 million million form. For ease of translation,
here is a conversion table:
name exponent of 10 European name
million 6 million
billion 9 milliard
trillion 12 billion
vingintillion 63 thousand decillion
Chris Thompson
(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.
This shows some miscomprehension on someone's part. Each linear relation
over GF(2) that comes out of the last part of MPQS produces a factorisation
of N. If N is the product of two primes p.q (as the RSA-129 number was "known"
to be) then there is a 50% chance that you get N.1 and a 50% chance that you
get p.q, and the chances for each new relation are (heuristically, anyway)
independant. So three false drops before the success was indeed (mildly)
unlucky. With the methods used there would have been no problem keeping up
the supply of new linear relations for a long time.
By the way, all this *was* done with (state of the art) MPQS, so those posters
who are scaling up to larger numbers using the formulae for NFS are making
unwarranted assumptions (quite apart from the fact that using only the
assymptotic complexity can give seriously misleading results in practical
ranges). NFS for general numbers has not yet been proved to be a practical
method, despite the claims that it will be Real Soon Now.
Chris Thompson
Internet: ce...@phx.cam.ac.uk
JANET: ce...@uk.ac.cam.phx
Paul C Leyland
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-]
yes, your math looks ok. Your assumptions suck though 8-)
We used ppmpqs for rsa-129; you are assuming that the gnfs will take exactly
as long to do rsa-129. We estimate that current versions of gnfs will only
take about 1/3 the time that ppmpqs took.
You also (implicitly) assume that our 5000 figure is good to 3 significant
digits. In reality, MIPS is a rather fuzzy unit. It all depends on
what an instruction does and how you measure it. The real computing effort
probably lies between 4000 and 6000 mips years, though I wouldn't swear
under oath that it definitely lies in those bounds.
Nonetheless, a 1024-bit key is a lot harder than a 429-bitter. 20 thousand
times is about the right ball park.
Paul
--
Paul Leyland <p...@black.ox.ac.uk> | Hanging on in quiet desperation is
Oxford University Computing Services | the English way.
13 Banbury Road, Oxford, OX2 6NN, UK | The time is gone, the song is over.
Tel: +44-865-273200 Fax: +44-865-273275 | Thought I'd something more to say.
Finger p...@black.ox.ac.uk for PGP key |
Steve Wildstrom
>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?
A prize was offered when the original challenge was published in
Scientific American in 1977. I think it's $100. If it's distributed among
all the folks who contributed cycles, they might get a penny apiece.
--
----------------------------------------------------------------------
Steve Wildstrom Business Week Washington Bureau wi...@access.digex.net
"These opinions aren't necessarily mine or anyone else's."
-----------------------------------------------------------------------
Barry Margolin
>
>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?
Yes, it looks like it might be beyond the capabilities of a CM2/CM200
models, like the one strnlght refers to. Each of these 64K processors is a
relatively slow, 1-bit processor. It's generally better to consider them
from the viewpoint of the floating point accelerators (we call this
"slicewise" mode), which are 1 FPA for every 32 processors, so this is more
like a 2K-processor machine.
However, the newer, CM5 models have enough processing power (each node is a
SPARC processor with optional vector units -- up to 120 MIPS/processor) and
memory (8 MB/node is the minimum configuration). If 100% parallelism
efficiency were achievable, someone here estimated that the largest CM5
we've sold (1K nodes with VU's) could solve RSA-129 in about two weeks of
continuous processing (based on the estimated number of MIPS-years that
were used by the distributed project).
--
Barry Margolin
System Manager, Thinking Machines Corp.
bar...@think.com {uunet,harvard}!think!barmar
Perry E. Metzger
>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.
Even better, one could pick a 1024 bit key instead.
--
Perry Metzger pe...@imsi.com
--
Are American citizens really so neurotically uptight about deviant
sexual behavior that we will allow our entire information
infrastructure to be dictated by the existence of pedophiles?
-- Bruce Sterling
Steve Atkins
|> strn...@netcom.com (David Sternlight) writes:
|>
|> >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?
|>
|> A prize was offered when the original challenge was published in
|> Scientific American in 1977. I think it's $100. If it's distributed among
|> all the folks who contributed cycles, they might get a penny apiece.
|>
--
Steve Atkins <atk...@inmos.co.uk> +44 454 611439
The magic words are `SQUEAMISH OSSIFRAGE'
David Sternlight
Ken Pizzini <k...@chinook.halcyon.com> wrote:
>
>This gives an expected running time for a 1024 bit modulus to be almost
>171 billion times longer than for the 427 bit modulus that is rsa-129.
>Given the estimate above of "5000 MIPS-years" for rsa-129, that comes
>out to 853 trillion MIPS-years for a 1024 bit modulus. For a 1 million
>1000 MIPS processors, this requires 853 millenia. For those made
>uncomfortable by this low number, square your running time by using a
>2048 bit modulus and increase the factoring running time by a factor of
>another couple trillion. Of course, if you want real security (barring
>breakthroughs in factoring, which are harder to predict) you might want
>to go with a 8192 bit modulus and require the advisary to expend
>5 vingintillion MIPS-years...
Planting tongue firmly in cheek:
Let's see--if we scale the above by a correction factor equal to the number
of years since the Scientific American Article that RSA-129 fell, divided by
the number of years the experts in the article thought it would take for it
to fall, what do we get?
Hm, hm, di-diddle, (I like to sing when I sew), dumty di....
(Number left to readers).
:-)
David
John Jack Repenning
In article <mjbCoz...@netcom.com>, m...@netcom.com writes:
>
> 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.
By no means has it been "vastly overrated," even at your ... creative
... "NSA to real-world" conversion ratios. I have this tremendous
sense of disconnect here; I was advised (am I the only one who ever
read or heard this?) that a 384-bit key was merely "casual" security,
512 was "commercial" grade, and 1024 was "military." I think the
present factoring fits those characterizations quite well - I would
never expect anything called "casual" to defend against the concerted
might of a US Government organization - that would take something more
like "military," which even by the most pessimistic estimates posted
in this discussion is still proof against the NSA chimera for a while
longer.
Ken Pizzini
>Ken Pizzini <k...@chinook.halcyon.com> wrote:
>>This gives an expected running time for a 1024 bit modulus to be almost
>>171 billion times longer than for the 427 bit modulus that is rsa-129.
>
>Planting tongue firmly in cheek:
noted...
>Let's see--if we scale the above by a correction factor equal to the number
>of years since the Scientific American Article that RSA-129 fell, divided by
>the number of years the experts in the article thought it would take for it
>to fall, what do we get?
Two comments: one I made no prediction as to how many years it would
take, just how much computational resources it would take (i.e. MIPS-years).
Second, I am making the questionable assumption that the same
factoring algorithm continues to be used. My points (and I did
get carried away) was that the original work estimate quoted for
a 1024 bit modulus was quite a bit low, and 1024 bits is not the
be-all end-all of security offered by RSA.
(I also wonder what disclaimers may have been in the old Sci Am article
that are being ignored, such as perhaps: "given current computers and
factoring algorithms", and a forgotten "on one computer".)
--Ken Pizzini
Shiraz J. Cupala
: A prize was offered when the original challenge was published in
: Scientific American in 1977. I think it's $100. If it's distributed among
: all the folks who contributed cycles, they might get a penny apiece.
Actually, just roughly counting the number of workstations which
contributed to the project each would get about sixteen cents. A little
better than a penny. :)
Shiraz
David Sternlight
Paul C Leyland <p...@foo.oucs.ox.ac.uk> wrote:
>
>Nonetheless, a 1024-bit key is a lot harder than a 429-bitter. 20 thousand
>times is about the right ball park.
That's not very comforting, Paul.
Suppose the NSA has the ability to put 100 times as many parallel processors
on the job, in the form of a Connection Machine type of hardware. Not an
unreasonable assumption.
Suppose they have 10 times the CPU speed. Based on today's technology, not
an unreasonable assumption.
Suppose they spend 10 times more (in hours per day)--since your participants
apparently were computing part time, and perhaps at lower effective speed if
the work stations were doing other things as well. This one is a bit
shaky--I don't have the data on the usage efficiency of all those volunteer
workstations.
Then we're down to only twice as time-consuming to do a 1024 bit key.
Now suppose they have algorithms that are just a little better...
You can see why I'm not sanguine about the security of 1024 bit keys against
rich and powerful adversaries, given the RSA-129 result.
Especially given the expert forecasts in the same Scientific American
article on how long it would take for RSA-129 to fall.
Am I missing something here?
David
Austin Lobo
Steve Wildstrom <wi...@access1.digex.net> wrote:
>strn...@netcom.com (David Sternlight) writes:
>
>>In article <WARLORD.94...@incommunicado.mit.edu>,
>>Derek Atkins <war...@MIT.EDU> wrote:
>>>We are happy to announce that
>
>Scientific American in 1977. I think it's $100. If it's distributed among
>all the folks who contributed cycles, they might get a penny apiece.
>
>--
Yesterday (4/28) Arjen Lenstra spoke at our Dept. Colloquium. One of his
slides was a photocopy of the $100 check.
Austin
Dave Kinkley
: In article <PCL.94Ap...@foo.oucs.ox.ac.uk>,
: Paul C Leyland <p...@foo.oucs.ox.ac.uk> wrote:
: >
: >Nonetheless, a 1024-bit key is a lot harder than a 429-bitter. 20 thousand
: >times is about the right ball park.
: That's not very comforting, Paul.
: Suppose the NSA has the ability to put 100 times as many parallel processors
: on the job, in the form of a Connection Machine type of hardware. Not an
: unreasonable assumption.
: Suppose they have 10 times the CPU speed. Based on today's technology, not
: an unreasonable assumption.
: Suppose they spend 10 times more (in hours per day)--since your participants
: apparently were computing part time, and perhaps at lower effective speed if
: the work stations were doing other things as well. This one is a bit
: shaky--I don't have the data on the usage efficiency of all those volunteer
: workstations.
Suppose they recruit help from aliens in Andromeda to help in the effort.
Suppose they promise everyone a big chocolate chip cookie if they work
extra hard on the problem.
Pleeeeeease! This string is out of control. I guess everybody and their
sister is sending email that the NSA deems valuable enough to spend
millions of dollars to crack.
RSA is extensible. Figure out how valuable your data is, who might want it,
how much they would spend to get it, and how far in the future it needs to
remain confidential. Then pick the appropriate key length.
-dave kinkley
Peter T. Wang
>David
All of that doesn't matter. One must always remember that RSA gives the
"code-maker" a huge advantage over the "code-breaker." The most dedicated
government, the fastest computers, and the best algorithms known to humanity
can never factor a number in a time interval comparable to the time it took
to find it. If 1024 bits isn't enough, then go for 2048. If that's not
enough, then use more. In the end, the ones who try to crack RSA are the
ones who will always lose.
That is, until some mathematical theorem about factoring numbers is
discovered and makes factoring a relatively simple task. (If that ever
happens.)
Peter Wang
Alan Lovejoy
Bits: Relative Time
> 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.
> --
> Geoff Kuenning ge...@ficus.cs.ucla.edu ge...@ITcorp.com
Don't forget that computer power doubles every year and a half. Taking that
into account, we have (assuming NO algorithmic improvements):
Bits Relative Times
Year: 1994 x64 2003 x128 2021 x128 2039 x128 2057
429: 1.0 -------------------------------------------------------
512: 7.66719e+0 1.197998e-1 ----------------------------------------
1024: 1.05473e+5 1.648016e+3 1.287512e+1 1.005869e-1 ------------
2048: 2.9718e+10 4.643438e+8 3.627686e+6 2.834130e+4 2.214164e+2
4094: 4.28061e+17 6.688453e+15 5.225354e+13 4.082308e+11 3.189303e+9
8192: 1.02939e+27 1.608422e+25 1.256580e+23 9.817031e+20 7.669555e+18
16384: 1.90839e+39 3.095061e+37 2.418016e+35 1.889075e+33 1.475840e+31
Another factor to be considered is the economic motivation for breaking RSA
keys. It's not just the economic incentive for cracking your own key that
you need to consider, but rather the economic incentive for cracking any
key. If cracking your 1024-bit key is worth $50,000, but cracking someone
else's 1024-bit key is worth $50 billion, and cracking all 1024-bit keys
is worth $2 trillion, then you should assume that some significant fraction
of $2 trillion could be spent cracking you key (as a side effect).
For exmaple, if "the rich" (i.e., the taxpayers) start using Chaumian digital
cash transactions to evade the income tax, the economic incentives to break RSA
keys could become huge. Normally, the U.S. could not afford to spend several
hundred billion dollars per year on computer hardware for factoring large
numbers. But if yearly income tax receipts on the order of a trillion dollars
were at stake, then the money might well be spent. Large sums could also be
spent on improving factoring algorithms.
On the other hand, it would not take many years of severe shortfalls in tax
recipts to bankrupt any effort to break RSA keys by spending hundreds of
billions on hardware.
Conclusions:
1) Taking all factors into consideration, 4094-bit keys appear unimpeachably
safe, and 2048-bit keys can be considered secure for the next thirty years
or so.
2) 1024-bit keys should be secure from all but governments, and even from them
for the next 5 to 10 years.
3) The next century will see significant declines in state power.
--
--
Alan Lovejoy | INTERNET: love...@netcom.com | Smalltalk-80 Consultant
"Do not go gentle into that good night. Old age should burn and rave
at the closing of the day. Rage, rage at the dying of the light!"
Barry Margolin
>In article <PCL.94Ap...@foo.oucs.ox.ac.uk>,
>Paul C Leyland <p...@foo.oucs.ox.ac.uk> wrote:
>>Nonetheless, a 1024-bit key is a lot harder than a 429-bitter. 20 thousand
>>times is about the right ball park.
>
>That's not very comforting, Paul.
>
>Suppose the NSA has the ability to put 100 times as many parallel processors
>on the job, in the form of a Connection Machine type of hardware. Not an
>unreasonable assumption.
The biggest CM-5 sold to date has 1K processing nodes, while the RSA-129
project made use of about 600 computers. Our current CM-5 design only
scales up to 16K PNs, but I don't think anyone (even the NSA) could afford
to buy one (and it would take us quite a bit of time to manufacture such a
beast).
I know you weren't referring specifically the CM-5, but just MPP systems in
general. But I think the CM-5 is representative of the state of the art.
Over the next few years I think we'll mostly see improvements in the power
of the individual PN's and the network, but not much larger machines. A
60K-processor machine seems unlikely for a while (note that in the
64K-processor CM's that Thinking Machines used to sell, the individual
processors were extremely simple).
>Suppose they have 10 times the CPU speed. Based on today's technology, not
>an unreasonable assumption.
That's reasonable. Processor speeds increase ten-fold about every three
years, although it's not clear how long that will continue (but that's what
they said a decade ago).
>Suppose they spend 10 times more (in hours per day)
...
>Then we're down to only twice as time-consuming to do a 1024 bit key.
>Now suppose they have algorithms that are just a little better...
>
>You can see why I'm not sanguine about the security of 1024 bit keys against
>rich and powerful adversaries, given the RSA-129 result.
It took the better part of a year for the RSA-129 volunteers to do one
factorization. So even with all your assumptions about improvements
available to the NSA, it will still take them just as long to crack one
1K-bit key. A codebreaker that monopolizes the supercomputer resources of
the NSA and still takes several months to run isn't something I would worry
too much about. How many supercomputers like the one you describe do you
think the NSA could have? And compare that to the number of people whose
codes they would like to break.
Michael Levy
Dave Kinkley <kin...@hpindav.cup.hp.com> wrote:
>
>Suppose they recruit help from aliens in Andromeda to help in the effort.
>
>Suppose they promise everyone a big chocolate chip cookie if they work
>extra hard on the problem.
>
A chocolate chip cookie?!! Where?!! What do I have to factor??
Jim Grubs, W8GRT
The maximum it MIGHT take. Doesn't mean they won't do it sooner
by sheer, dumb luck. Then, again, maybe RSA-129 was sheer, dumb
luck, too.
-----BEGIN PGP PUBLIC KEY BLOCK-----
Version: 2.3a
mQCNAi05314AAAEEAO/haRSJnlweN7yJ6tpetnM/31k0+XBX2y6UNQf6hc7HdmFU
tCjYu52cikNhjxN9WEZX5anyLMCTa9PrZpdpUFuvZwmNc4zCNxWEkvYjv+eSGzkQ
oV9uOzWVCK3RjdHGSVfu3Zs1BHmzCf2gW7tjicZhvIHOxo5PiMmzkeX3rfUNAAUR
tCVKaW0gR3J1YnMgPGpncnVic0B2b3hib3gubm9yZGVuMS5jb20+iQCVAgUQLbnZ
Jk9J4/ZiAE2bAQHSIgQAhirtYWmuKWBHi0oRVNVU1zMlGdCdfCIACxrIqutV7TQ7
8dCET+A9cKZ2WTcO5mb52u2NeVTIrE1iXmc82EPnlCclZeyiYhvvfynIKcETAK2M
oojwyjvB5OViQVXqhXfzFSqrT8pEAz2OX/XkeZxvCx6Cjvkd/frHumCjC+KO3OC0
H0ppbSBHcnVicywgVzhHUlQgPFBlcnNvbmFsIEtleT60GEppbSBHcnVicyA8UGVy
c29uYWwgS2V5Pg==
=oak0
-----END PGP PUBLIC KEY BLOCK-----
/----------------------------------------------------------------------\
| Jim Grubs, W8GRT Voxbox Enterprises Tel.: 419/882-2697 |
| jgr...@voxbox.norden1.com 6817 Maplewood Ave. |
| Fido: 1:234/1.0 Sylvania, Ohio 43560 |
\-+--------------------------------------------------------------------/
Matthew Dillon
Not to nitpick, but even giving the NSA the benefit of the doubt, with all
the information they monitor they are unlikely to spend a days worth of
resources on a key used by law abiding users like us when other more
important matters need the cpu time.
Hey, now there is an idea... instead of using an encryption the
government has the secret key for, how about an encryption that takes
the government a week to crack if they really want to? This protects
privacy in a reasonable fashion by limiting the bandwidth of the cracked
data. The government can hardly monitor all the terrabytes of encrypted
information flowing through the NSA each day, but they can still crack
things for some criminal investigation or other. After all, investigations
takes a long time anyway (Cuckoo's Egg), a week to crack something would
not effect it at all.
That was only semi-serious... if it came down to one or the other I'd take
the latter, but I'd much rather use something that couldn't be cracked
at all.
-Matt
--
Matthew Dillon dil...@apollo.west.oic.com
1005 Apollo Way
Incline Village, NV. 89451 ham: KC6LVW (no mail drop)
USA Sandel-Avery Engineering (702)831-8000
[always include a portion of the original email in any response!]
Dik T. Winter
> The maximum it MIGHT take. Doesn't mean they won't do it sooner
> by sheer, dumb luck. Then, again, maybe RSA-129 was sheer, dumb
> luck, too.
>
workstations for eight months on a fishing expedition. (Although I know
people who exploit a Cray C-90 for 100 hours on a fishing expedition ;-).)
Using mpqs and its derivates you are able after a short running time the
total time it will take to factor.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924098
home: bovenover 215, 1025 jn amsterdam, nederland; e-mail: d...@cwi.nl
T. M. Cuffel
Peter T. Wang <pet...@cco.caltech.edu> wrote:
[RSA is safe]
>That is, until some mathematical theorem about factoring numbers is
>discovered and makes factoring a relatively simple task. (If that ever
>happens.)
Changing the subject a bit, is this statement strictly true?
It can be shown that RSA can be broken by factoring the appropriate
number. But can it be shown that this is the best way to break
RSA?
Peter T. Wang
>[RSA is safe]
According to the original authors of the RSA encryption system, there are
several (in theory) ways to find the decryption code. However, they emphasize
that none of these alternatives are of any use, because if they were
successful then it would immediately reveal the factors of n. However,
since all known methods of factoring numbers are extremely inefficient,
they assure us that alternative methods of finding the decryption key is
just as difficult (if not more so) than factoring n. They continue in
mentioning how the NSA has worked many, many years on finding alternate
means of finding an unknown decryption key but to no avail.
In a nutshell, there are other ways of breaking RSA. But each one is
theoretically equivalent to factoring n.
Peter Wang
P.S. If anyone is interested, I may post the original article by the
creators of RSA.
Louis K. Scheffer
>In article <PCL.94Ap...@foo.oucs.ox.ac.uk>,
>Paul C Leyland <p...@foo.oucs.ox.ac.uk> wrote:
>>Nonetheless, a 1024-bit key is a lot harder than a 429-bitter. 20 thousand
>>times is about the right ball park.
>That's not very comforting, Paul.
> [Could use 100 times as many processors]
> [Could be 10 times faster...]
> [Could be 24 hours/day instead of 2.4]
>Then we're down to only twice as time-consuming to do a 1024 bit key.
>Now suppose they have algorithms that are just a little better...
>You can see why I'm not sanguine about the security of 1024 bit keys against
>rich and powerful adversaries, given the RSA-129 result.
>Am I missing something here?
Yes - the economics. Suppose a 33 mips workstation lasts 3 years and costs $3000.
You get 100 Mips-years for $3000, or $30/mips-year. This is assuming 24 hour/day
use.
The 5000 mip-years = 5000/100*$3000 = $150,000 to crack a 429 bit key. This implies
$3,000,000,000 to crack a single 1024 bit key, if the factor is 20,000 as claimed
above. This is not impossible for a very rich adversary, but they won't do it
casually. It's a lot more money than cracking DES by brute force.
Note that parallel processing does not help this. Conventional computers are cheaper
per MIP than parallel processors, because the parallel processors do not have the
volume production and competition that conventional computers have.
Dedicated factoring hardware would help, but not very much. Unless you have a large
staff continuously turning out new hardware, advances in conventional computers will
swamp the factor of 10 or so you can usually get this way.
The time/day/machine does not matter if you calculate $, not hours.
Faster computers help the encryptors more than the attackers. As you use a bigger
modulus, the cracking cost/encrypting cost goes up, and faster machines make bigger
moduli practical.
The only real danger here is from better algorithms, and as differential analysis of
DES has shown, that is a problem with *any* encryption, not just mathematical ones.
And here, we have the advantage that a lot more brain-years have been put into
factoring, as opposed to breaking schemes such as Clipper (whatever it is).
-Lou Scheffer
Leo Bicknell
>The biggest CM-5 sold to date has 1K processing nodes, while the RSA-129
>project made use of about 600 computers. Our current CM-5 design only
>scales up to 16K PNs, but I don't think anyone (even the NSA) could afford
>to buy one (and it would take us quite a bit of time to manufacture such a
>beast).
I'm no expert in the supercomputer area, but there are a lot
of other, _new_ offerings that are just now becomming usable machines.
For instance I am working now on an Intel Paragon. While still a little
experimental it's getting better. It's already been scaled up to
2K Processors at Sandia, and Intel is thinking about some minor redesigns
to allow it to go to more. From my own trials, each processor can be run
like an individual machine, and a 600 processor Paragon (to achieve the
speed of the RSA group) would not be that hard to get.
I would also like to point out the RSA group only used IDLE
time on those 600 computers. On some of those computers that might
have only have been a couple of hours a day. Given 600 computers
full time I would venture the time would have at least been cut in
half.
I have seen several new Pentium PC's being offered, one with
4 processors (SMP) in it for $20K. Get 100 of them ($20 Mil), network
them, and run a network solution (like the RSA group) and you have
a relatively inexpensive, and fast, solution.
I think as long as there are machines like the Sandia Paragon
with 2K processors that are used for testing and benchmarks we need
to worry. What if someone wanted to benchmark it by breaking
RSA-129 in a continuous run on all processors? A week later we
might have the answer. While the NSA might not be able to afford
the latest in computer hardware, the developers have it around,
and who knows what some over-stressed tester might do...
--
Leo Bicknell - bick...@ussenterprise.async.vt.edu | Make a little birdhouse
bick...@csugrad.cs.vt.edu | in your soul......
ab...@freenet.buffalo.edu | They Might
the...@toz.buffalo.ny.us | Be Giants
Adrian V Mariano
>>[RSA is safe]
Is this last statement true? When I studied RSA last year, I was told
that nobody had shown that breaking RSA allowed one to factor n.
David Harwood
Louis K. Scheffer <l...@Cadence.COM> wrote:
[ re economics of computing ...]
>Note that parallel processing does not help this. Conventional computers are cheaper
>per MIP than parallel processors, because the parallel processors do not have the
>volume production and competition that conventional computers have.
>
>Dedicated factoring hardware would help, but not very much. Unless you have a large
\\\\\
Maybe, maybe not. As a matter of fact, the CPU chips/componets of commericial
computers cost far less than you suggest, and custom assembly of these
for special prupose is quite inexpensive. (I had a graduate student who
built a powerful general purpose supercomputer from transputers.) Moreover
the advantage of dedicated (VLSI) design is in being able to readily
exploit parallelism of special algorithms which a conventional computer
cannot. It is not simply a matter of faster hardware. And DARPA once
created a factory for automated fabrication of VLSI designs (with quick
turnaround); there are some in Europe too.
I really don't care about this discussion. I just don't believe an
government agencies are as technologically backward as my Sparcstation 10
for the purpose of factoring numbers. (I seem to recall reading that some
mathematician home-built special hardware for doing certain number-theoretic
calculations faster than supercomputers; if he do it, so can professionals.)
No more from me about this- I don't have anything worth encrypting ;-)
D.H.
Robert D. Silverman
stuff deleted....
: I have seen several new Pentium PC's being offered, one with
:4 processors (SMP) in it for $20K. Get 100 of them ($20 Mil), network
:them, and run a network solution (like the RSA group) and you have
:a relatively inexpensive, and fast, solution.
No! No! No! Multiprocessor computers such as you describe are LOUSY
for sieving algorithms unless each processor has its own separate
cache, its own separate memory, and its own separate bus to that memory.
Sieve-based factoring algorithms are STRONGLY constrained by memory
cycle time and memory bandwidth, and NOT by processor speed. Bus
contention becomes a big problem on such machines, as well as cache
contention.
I wish people would stop making all these ridiculous claims until after
they have coded and run a sieving algorithm on a wide variety of platforms.
After you have done so, you might have the necessary knowledge base for
an intelligent discussion on the subject. But not before.
: I think as long as there are machines like the Sandia Paragon
:with 2K processors that are used for testing and benchmarks we need
:to worry. What if someone wanted to benchmark it by breaking
Worry about what? A 2K processor Paragon, running full time would take
6-8 weeks to factor RSA-129. Now ask yourself what the COST of that would
be. How many of these machines do you think are floating around anyway?
Would people please stop and look at the ECONOMICS of what they are proposing?
Noone who has factored 100+ digit integers by QS denies that 512-bit numbers
are feasible to do. The issue is the cost.
--
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"
David Sternlight
>All of that doesn't matter. One must always remember that RSA gives the
>"code-maker" a huge advantage over the "code-breaker." The most dedicated
>government, the fastest computers, and the best algorithms known to humanity
>can never factor a number in a time interval comparable to the time it took
>to find it. If 1024 bits isn't enough, then go for 2048. If that's not
>enough, then use more. In the end, the ones who try to crack RSA are the
>ones who will always lose.
It's not that simple. It's a function of the encryption and decryption times
for longer keys as well. Though the users have a cracking time advantage,
the rich and smart crackers have a monetary advantage and can afford faster
and better hardware.
Thus a careful analysis, taking account of the encryption and decrytion
times for any key length at any state of the art for the wide base of user
machines, and the cutting edge, high speed, massively parallel cracking
machines a rich adversary wuld have at the same period is needed.
Some incomplete attempts at such an analysis have been made by Rivest, for
example, but they don't take into account user encryption/decryption times
that I've seen.
David
Michael Graff
>The maximum it MIGHT take. Doesn't mean they won't do it sooner
>by sheer, dumb luck. Then, again, maybe RSA-129 was sheer, dumb
>luck, too.
Dumb luck? Oh no, I assure you, nothing we did relied on ``dumb luck'' or
luck of any other type.
--
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
Mike Oliver
>Dumb luck? Oh no, I assure you, nothing we did relied on ``dumb luck'' or
>luck of any other type.
One thing I've been curious about: How much did you rely on the reliability
of the people doing the distributed computing and the channels used to send
their results to you? Suppose, for example, that a few people trying to
defeat the project had decided to send you bogus relations. How many would
it have taken to have caused you a serious problem?
Leo Bicknell
>Worry about what? A 2K processor Paragon, running full time would take
>6-8 weeks to factor RSA-129. Now ask yourself what the COST of that would
>be. How many of these machines do you think are floating around anyway?
Really? Here's my math. 600 machines on the net working
4 hours a day, is the same as 100 machines on the net working
24 hours a day. Each processor is the speed of the average workstation
in a paragon (40 MFLOP's per processor on the paragon...that's in
the workstation range). So, 100 processors could do it in 6 months
(I think that's how long it took, and 2048 could do it in 1.2 weeks,
or a little over 8 days. That's a lot different then 6-8 weeks.
Not to mention the last ranking I saw showed 14 machines
faster than that paragon, the fastest was 4 times faster, that
would (theoretically) crank it out in 2 days.
Sure, it would be expensive. If we went to a state of war
or something and the NSA took over big computer, they could easily
be breaking RSA-129 codes in a day I think.
With the exponential growth in computing power per dollar
I don't think it's unreasonable to expect to see a lot of groups
able to break codes of this order in under two years.
Yes, the cost now is high, it will drop rapidly, and deep
pockets (like the governments) will be able to purchase these
machines soon. It is also not all that unlikely that someone
hasn't devised a hardware model for breaking these codes that
is 100 times more efficient than a standard microprocessor.
John Scholes
av...@crux4.cit.cornell.edu "Adrian V Mariano" writes:
>
> :In a nutshell, there are other ways of breaking RSA. But each one is
> :theoretically equivalent to factoring n.
>
> Is this last statement true? When I studied RSA last year, I was told
> that nobody had shown that breaking RSA allowed one to factor n.
>
I agree with you. Suppose we have N=p*q, e, d with e*d=1 mod (p-1)(q-1).
The public key is N,e; the private key is d. Encryption is by c=m^e mod N,
where m is a block of plain text, c is the cipher text. Decryption is
by m=c^d mod N. The usual attack is to factor N to get p and q, hence
get d.
It has been shown that if one has d, then one can get p and q. But one
might also proceed directly to extract e-th roots mod N. As far
as I know this has not been shown to lead to a knowledge of d. Remember
that e is often small in practice (eg 3).
This is confirmed by the RSA FAQ (prepared by RSA Laboratories) recently
posted to sci.crypt and alt.security.ripem.
--
John Scholes
Mitchell N. Perilstein
Derek Atkins
We did not rely on the reliability of the users. One of the neat
things about how the factoring process works is that while it takes a
lot of time to generate the data used to factor the number, it takes
virtually no time at all to *verify* the data.
To use the metaphor that Arjen used, its like finding 8.2 million
needles in a giant haystack. However once we have a "needle", it is
very easy to check and see that it is really a needle as opposed to
another piece of hay!
Does this make it clearer?
-derek
--
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
Cornelis van der Laan
> Someone suggested we make an After Dark module and let all those
> Mac's factor when the screen is being saved :)
Ever thought of all these Postscript Printer RISC engines wasting
their time with plenty of RAM installed? How about using those idlers
for doing something useful?
Nils
--
-----------------------------------------------------------------------
Cornelis van der Laan --- ni...@ims.uni-stuttgart.de
IMS Universitaet Stuttgart --- ni...@guru.stgt.sub.org
#echo "Knusper Knusper Knaeuschen" > /etc/nologin
Magnus Y Alvestad
Leo> RSA group) would not be that hard to get.
No no. 600 people, at least 1200 machines - including several Maspars
(massive parallel computers with 8k or 16k processors). Our MP2, for
example, rated at 60,000 MIPS (64bit integer operations).
Jim Grubs, W8GRT
> In <aHckLc...@voxbox.norden1.com> jgr...@voxbox.norden1.com (Jim Grubs, W8
>
> >The maximum it MIGHT take. Doesn't mean they won't do it sooner
> >by sheer, dumb luck. Then, again, maybe RSA-129 was sheer, dumb
> >luck, too.
>
> Dumb luck? Oh no, I assure you, nothing we did relied on ``dumb luck'' or
> luck of any other type.
I apologize for the poor choice of words. What I had reference
to was that even if you attack a cipher in a logical progression
of n=1 to umpty steps, the successful step might be closer to 1
than to umpty.
Or is that an unsound premise?
Robert D. Silverman
They don't matter at all. They get found as a matter of course (and rejected)
while preparing the final matrix for processing.
If there were sufficiently many bogus results it would only mean doing a
little more sieving to get the required number of correct results. But finding
bogus results is trivial. It is a non-problem.
Robert D. Silverman
:expl...@iastate.edu (Michael Graff) writes:
:
:> In <aHckLc...@voxbox.norden1.com> jgr...@voxbox.norden1.com (Jim Grubs, W8
:>
:> >The maximum it MIGHT take. Doesn't mean they won't do it sooner
:> >by sheer, dumb luck. Then, again, maybe RSA-129 was sheer, dumb
:> >luck, too.
:>
:> Dumb luck? Oh no, I assure you, nothing we did relied on ``dumb luck'' or
:> luck of any other type.
:
:I apologize for the poor choice of words. What I had reference
:to was that even if you attack a cipher in a logical progression
:of n=1 to umpty steps, the successful step might be closer to 1
:than to umpty.
:
:Or is that an unsound premise?
I wish people would stop shooting their mouths off about this when they don't
know what they are talking about.
Why don't you try READING about the algorithms involved before making
such pronouncements.
The run time for QS depends only on the size of the number being factored
andalso in how rich that number is in small quadratic residues (the latter
makes a difference of up to a factor of about 2 in run time). The worst
case for this algorithm is the same as the average case. You sieve
until you collect a sufficient number of relations. The rate at which you
produce relations depends on the size of the number and the size of the chosen
factor base. I knew (and had publically stated) 4 years ago that RSA-129
would take 5000 MIPS-years to do.
Serge Vaudenay
As is a recent discussion in sci.math, it is equivalent to factor n than to
get a secret key (the inverse of the public key mod phi(n)).
However, breaking RSA is not known to be equivalent than giving the secret key.
--Serge
scott johnson
i
Breaking RSA would indeed produce the secret primes p and q, which would indeed
be the factorization of n. However, this only provides a way for factoring
n, when n is a product of two primes. If n is the product of multiple primes,
(as are most numbers), it is doubtful that this will work....
So, breaking RSA =/=> factoring n (in the general case.)
/sj/
Alfred Steele
>strn...@netcom.com (David Sternlight) writes:
>
>>Derek Atkins <war...@MIT.EDU> wrote:
>>>We are happy to announce that
>>>
>>>RSA-129 = 1143816257578888676692357799761466120102182967212423625625618429\
>>> 35706935245733897830597123563958705058989075147599290026879543541
>>> = 3490529510847650949147849619903898133417764638493387843990820577 *
>>> 32769132993266709549961988190834461413177642967992942539798288533
>
>[snip..]
>A prize was offered when the original challenge was published in
>Scientific American in 1977. I think it's $100. If it's distributed among
>[snip...]
I read the original artical. I believe that there was also text to decode
using the rsa-129 as a key. Has anyone decoded it?
Lewis McCarthy
$ I read the original artical. I believe that there was also text to decode
$ using the rsa-129 as a key. Has anyone decoded it?
Yes, it was published in the N.Y. Times a few days ago. I don't remember the
exact phrasing, but it's something like "The magic words are _____ ossifrage"
-Lewis
================================
"Ja, ja. Waldheim for President" -Mark Line [in soc.culture.austria]
(mark...@henson.cc.wwu.edu)
scott johnson
Alan Lovejoy <love...@netcom.com> wrote:
[stuff deleted]
>
>The strategic situation is defined by three facts:
>
>1) Computer power increases by a factor of 2 every 1.5 years (on average).
>2) Encryption/decryption time increases by a factor of 4 as the bit-length
>of the RSA key is doubled. So the largest practical RSA key doubles every
>three years.
A minor quibble. While it is true that the time to perform modular
exponentiation increases with the square of the input size (when done in
hardware), the total encoding time increases only linearily. This is because
doubling the bit size halves the number of exponentiations which need be
performed for a given message. Encrypting a 1024-bit message with a 1024-bit
key is equivalent to encrypting TWO 512-bit messages with a 512-bit key.
Thus, throughput varies with the inverse of key size, NOT the square of the
inverse.
/sj/
Iolo Davidson
b...@gauss.mitre.org "Robert D. Silverman" writes:
> I wish people would stop shooting their mouths off about this when they don't
> know what they are talking about.
Perhaps if the people who do know what they are talking about had not
used the word "unlucky" in their original announcement, there would be
less comment about how much luck was involved.
--
Iolo Davidson
(no club, lone wolf)
Paul L. Allen
strn...@netcom.com (David Sternlight) writes:
> In article <lovejoyaC...@netcom.com>,
> Alan Lovejoy <love...@netcom.com> wrote:
>
> >Any and all economic advantages of code crackes must inexorably become
> >irrelevant in a relatively short time, if they aren't already. By the year
> >2000, computers will be 16 times more powerful, the largest practical bit
> >length will be 4 times today's, and the relative cracking difficulty of the
> >largest practical RSA keys will be many powers of ten greater than that
> >required for those of today.
> >
> >Checkmate.
>
> Nope. You omitted the costs of cracking machines, vis-a-vis the costs of
> users' machines. Users machines are now, for all practical purposes so cheap
> that all users can afford them. But the cost of computing power, continuing
> to fall dramatically, makes cracking machines ever cheaper, or to a fixed
> budget ever more powerful.
>
> Thus it ain't as simple as deponent sayeth, and a horseback analysis won't
> suffice--a detailed analysis is needed.
Much as it pains me to take David's side in an argument (:-) ), I also
have concerns about the analysis. The problem is not staying ahead of the
game but of being able to ensure that your key remains uncrackable for the
lifetime of the data. In some situations data is sensitive only for weeks.
In other situations the statute of limitations might be a more appropriate
span. In other cases the relevant interval might be 80 years (human life
span). If you belong to a persecuted minority, then hiding your membership
of said minority might be important to several generations of your
descendants.
So the question is not will our (much longer) keys 20 years hence be safe
from attack but will the keys we use today (1024-bit if you have any sense)
be safe 20 years from now given the doubling of CPU power every 1 or 2 years?
40? 60? 80?
Of course, there are other considerations. As a law-abiding citizen I'm not
*too* concerned if GCHQ/NSA/whoever break my key and read my e-mail, although
I wouldn't like it. Someone who cheats on his wife may be less happy with
the possibility - it leaves him open to blackmail. These are not matters of
universal consequence though, and the sheer number of users provides some
cover - if it takes finite time to crack a single key it will take some
multiple of that finite time to get around to mine. Even if the fears of
the anti-Clipper crowd come true and the US becomes a police state, the NSA
still have a lot of potential keys to examine before they find one belonging
to a dissident (assuming PGP usage continues to increase and it is not made
illegal). There *is* safety in numbers, even if the NSA can today crack a
1024-bit key in a week.
Hence I agree with David - we *do* need a detailed analysis. OTOH, I can
retain my untarnished reputation for disagreeing with David (:-) ) because I
want one for different reasons.
--Paul
Robert D. Silverman
:In article <2pv3au$o...@linus.mitre.org>,
:Robert D. Silverman <b...@gauss.mitre.org> wrote:
:>until you collect a sufficient number of relations. The rate at which you
:>produce relations depends on the size of the number and the size of the chosen
:>factor base. I knew (and had publically stated) 4 years ago that RSA-129
:>would take 5000 MIPS-years to do.
:Since you seem to know what you are talking about, and nobody has yet done
:the parametric analysis I've been suggesting since before RSA-129 fell, how
:about a simplified pair of result points?
:
:How long would it take to crack a 512k bit key RSA, and a 1024 bit key, under
512 bits would be about 25 times more difficult than RSA-129.
Noone really knows how long 1024 bits would take. There are some problems
involved.
(1) The factor base would need to be MUCH larger. The final matrix reduction
would be a big problem.
(2) The large factor base would mean the sieving program would not fit on an
8 Meg machine. Many of the machines used for RSA-129 were 8meg. It
would probably require 32 meg/machine.
(3) Noone knows how the o(1) term in the run time behaves up near 1024 bits.
Projections would only be rough ballpark figures.
That said, it would take between 10^4 and 10^5 times as long to do 1024
bits as 512 bits. One would want to use more than 2 large primes on each
side.
Chris Thompson
|>
|> We did not rely on the reliability of the users. One of the neat
|> things about how the factoring process works is that while it takes a
|> lot of time to generate the data used to factor the number, it takes
|> virtually no time at all to *verify* the data.
As a matter of interest: did you verify the relations on receipt, or only
later on in the process? And how many bad ones did you receive?
Chris Thompson
Internet: ce...@phx.cam.ac.uk
JANET: ce...@uk.ac.cam.phx
Jim Grubs, W8GRT
> In article <iuamLc...@voxbox.norden1.com> jgr...@voxbox.norden1.com (Jim G
> :expl...@iastate.edu (Michael Graff) writes:
> :
> :> In <aHckLc...@voxbox.norden1.com> jgr...@voxbox.norden1.com (Jim Grubs,
> :>
> :> >The maximum it MIGHT take. Doesn't mean they won't do it sooner
> :> >by sheer, dumb luck. Then, again, maybe RSA-129 was sheer, dumb
> :> >luck, too.
> :>
> :> Dumb luck? Oh no, I assure you, nothing we did relied on ``dumb luck'' or
> :> luck of any other type.
> :
> :I apologize for the poor choice of words. What I had reference
> :to was that even if you attack a cipher in a logical progression
> :of n=1 to umpty steps, the successful step might be closer to 1
> :than to umpty.
> :
> :Or is that an unsound premise?
>
> I wish people would stop shooting their mouths off about this when they don't
> know what they are talking about.
>
> Why don't you try READING about the algorithms involved before making
> such pronouncements.
>
> The run time for QS depends only on the size of the number being factored
> andalso in how rich that number is in small quadratic residues (the latter
> makes a difference of up to a factor of about 2 in run time). The worst
> case for this algorithm is the same as the average case. You sieve
> until you collect a sufficient number of relations. The rate at which you
> produce relations depends on the size of the number and the size of the chose
> factor base. I knew (and had publically stated) 4 years ago that RSA-129
> would take 5000 MIPS-years to do.
There, you answered my question. Wasn't that easy? The smartass
remarks weren't necessary, were they?
C44...@mizzou1.missouri.edu
>an adversary couldn't do everybody's keys. But we should be looking at the
>point of maximum leverage on the part of a determined adversary, since
>that's probably what such an adversary would do.
I agree that this kind of thinking is flawed, for two reasons:
1. By breaking the keys of key-distribution centers or key certifiers
(or simply people who've issued lots of key certificates), someone
who can crack just five keys per year can use those five keys to
do some serious active attacks. Once I know how to issue highly-
trusted key-certificates, I simply (carefully) choose peoples'
communications I wish to compromise, and then substitute in
an RSA public key *I* generated for both parties' public keys,
certifying them myself. Both parties send things only I can read,
and I sit in the middle, decrypting and re-encrypting everything.
2. More importantly, we're trying to get digital signatures accepted
in courts and among most people, so that electronic business
transactions are trustworthy. *One* well-publicized case where
it was proved that a digital signature had been forged would make
*every* digital contract ripe for being questioned in court.
We need to make sure that users of digital signature and crypto
schemes understand when they're using keys that might be compromised,
but are convenient (like using a 512-bit RSA key in a smartcard, for
transactions under $1,000 per month), versus when they're using keys
that we believe won't be compromised within the lifetime of anyone
now living (ie, 3000-bit RSA keys used for signing 50-year contracts
digitally.)
>David
--John Kelsey, c44...@mizzou1.missouri.edu
Andrew Haley
: jsch...@kalva.demon.co.uk (John Scholes) writes:
: > It has been shown that if one has d, then one can get p and q. But one
: > might also proceed directly to extract e-th roots mod N. As far
: > as I know this has not been shown to lead to a knowledge of d. Remember
: > that e is often small in practice (eg 3).
: Eh? Schneier claims that using low values of e is insecure.... "Hastad
: demonstrated a successful attack against RSA with a low encryption key.
: ... Moral: Choose large values for e and d." This is in Applied
: Cryptography p. 287. There's a reference to a paper in the CRYPTO '85
: proceedings, so this can't be anything recent. Have I missed something?
I've heard several people saying this recently; now I know where they
got the idea from! In fact, Hastad said nothing of the sort. The use
of RSA with small exponents is secure, but is subject to what is known
as the small exponent protocol failure. This occurs when the _same
message_ (or very similar messages; it's not sufficient simply to add
timestamps to make them different) is sent to M users, with M >= e,
the exponent used for encryption. The Chinese remainder theorem can
then be used to extract the message. The easy solution to this is not
to encrypt the actual message to be sent, but instead to encrypt a
randomly generated key to be used in a conventional cryptosystem. As
this is exactly what small exponent RSA is commonly used for, there
isn't any real problem.
Andrew.
Ref: J. Hastad, "On using RSA with low exponent in a public key
network," Proceedings of CRYPTO '85 pp. 403-408.
--
"Always keep an open mind, but not so open that your brain falls out."
Robert D. Silverman
stuff deleted...
I had posted some remarks about mouthing off when the prior poster was
totally ignorant of the subject......
>There, you answered my question. Wasn't that easy? The smartass
>remarks weren't necessary, were they?
Yes, they were necessary because there are simply TOO MANY people who
know nothing about this subject who are now making pronouncements
about it.
When you make ridiculous remarks in a *public* forum about a subject in which
you haven't even bothered to read the rudiments, such remarks are called
for.
If you are going to make ignorant statements without bothering to do
ANY studying of your subject matter, such "smartass" answers should
be expected.
There is a little saying: RTFM.
Robert D. Silverman
stuff deleted....
> We need to make sure that users of digital signature and crypto
>schemes understand when they're using keys that might be compromised,
>but are convenient (like using a 512-bit RSA key in a smartcard, for
>transactions under $1,000 per month), versus when they're using keys
>that we believe won't be compromised within the lifetime of anyone
>now living (ie, 3000-bit RSA keys used for signing 50-year contracts
I would not trust anyone who made the claim that 3000-bit keys won't
be broken even during the next 20 years. One can never predict when
a new algorithm might make factoring *easy*. If we could prove that
factoring is hard it would be a different story. But no such proof
is known.
With current algorithms, 1024 bits will be safe for 25 years. No conceivable
increase in computer power will let one factor a 1-24-bit number in that
time frame. Within (say) 25 to 35 years it might be possible to pull together
enough hardware to do it, but doing ONE such number would be a massive effort.
I can't see 2048 bits being done in the next 100 years with existing algorithms.
New factoring algorithms have come along about every 5 years since 1970.
1970 - CFRAC
1975 - Pollard P-1
1980 - QS
1985 - MPQS and variants
1985 - ECM
1990 - NFS
(dates are approximate; within a year of actual publication/release)
Barry Margolin
> Really? Here's my math. 600 machines on the net working
>4 hours a day, is the same as 100 machines on the net working
>24 hours a day.
There were more than 600 machines. 600 is the number of volunteers, but
many of them used several machines. At least one of them used an MPP
machine (someone wrote me to tell me that they used an MP2).
> Each processor is the speed of the average workstation
>in a paragon (40 MFLOP's per processor on the paragon...that's in
>the workstation range). So, 100 processors could do it in 6 months
>(I think that's how long it took, and 2048 could do it in 1.2 weeks,
>or a little over 8 days. That's a lot different then 6-8 weeks.
Given the above, 1.2 weeks should be multipled by the average number of
machines each volunteer used.
> Not to mention the last ranking I saw showed 14 machines
>faster than that paragon, the fastest was 4 times faster, that
>would (theoretically) crank it out in 2 days.
I think the machine that currently heads the MFLOP list isn't a general
purpose computer. I think it's a machine specialized for certain
simulations (wind tunnels spring to mind, but I might be mixing up two
things).
> Sure, it would be expensive. If we went to a state of war
>or something and the NSA took over big computer, they could easily
>be breaking RSA-129 codes in a day I think.
There's a big difference between that and worrying about day-to-day
encryption of email. The government could also send troups to fire on my
house, but I don't put up blast shields to protect me against this
eventuality.
> With the exponential growth in computing power per dollar
>I don't think it's unreasonable to expect to see a lot of groups
>able to break codes of this order in under two years.
But that same exponential growth also applies to the encryptors, so they
can afford to increase key lengths accordingly. So it should always
require a billion-dollar supercomputer a few weeks to break the code that a
$5K computer can encrypt with.
Machines available in a couple of years will be able to crack today's codes
pretty easily. But decrypting messages several years old isn't a very
interesting project.
--
Barry Margolin
System Manager, Thinking Machines Corp.
bar...@think.com {uunet,harvard}!think!barmar
Barry Margolin
>Barry Margolin <bar...@think.com> wrote:
>> If 100% parallelism
>>efficiency were achievable, someone here estimated that the largest CM5
>>we've sold (1K nodes with VU's) could solve RSA-129 in about two weeks of
>>continuous processing (based on the estimated number of MIPS-years that
>>were used by the distributed project).
...
>Given the assumptions in the last paragraph, leading to the conclusion that
>it would have taken the machine in question two weeks to do RSA-129, how
>long would it take for an IPRA key of 1024 bits to fall? 2048?
I think others have posted that a 1Kbit key requires 20,000 more work to
crack than RSA-129. So it would take 40,000 weeks, or 800 years. So even
if and when compute power increases by a factor of 100 it will still take
years for a supercomputer to crack it. But a distributed project like that
mounted against RSA-129 should be able to crack it in a comparable amount
of time.
>Corollary: Such a machine would likely be justified by the benefits of its
>use--i.e. the direct and indirect gains from cracking any particular key, as
>has been pointed out by another.
>
>Corollary question: What would such a machine cost?
I'm just guessing (I don't know our prices precisely), but I think a
1K-processor CM-5 is in the neighborhood of $50M.
David Sternlight
>
>512 bits would be about 25 times more difficult than RSA-129.
>
posts, is both non-responsive and unhelpful.
I don't want to know how much harder it is. I want to know how long it will
take an adversary with particular capabilities to do it.
There are many inefficiencies in the RSA-129 exercise. Slower machines than
an adversary of the sort I mention would have were used. They were used only
a small part of the elapsed calendar time. They were not custom
state-of-the-art for the task.
Thus it's no use for me to hear that it's "x" times harder. If you tell me
the NSA, GCHQ, the Japanes or French, with the hardware I specified, could
break a 512 bit key in "y" months, or a 1024 bit key in "z" years, THAT's
what I need to know to assess my risk.
I'm afraid what I'm seeing so far are bald assertions, supported by "off the
cuff" easy calculations as a real-time typing response to a message, rather
than the kind of detailed analysis needed to know where we stand.
Unfortunately I'm not expert enough in this area to do the number crunching
myself, but my hope is that any smart engineer or cryptologist knowledgeable
in these matters could knock the analysis out in a fairly short time.
Let's hope any further responses answer the question asked, rather than
looking for the key down the block from where it was lost because the light
is better there.
Nothing personal--your contributions have been quite useful as far as they
go.
David
Dik T. Winter
> Hence I agree with David - we *do* need a detailed analysis. OTOH, I can
> retain my untarnished reputation for disagreeing with David (:-) ) because I
> want one for different reasons.
>
a lot of analysis about the cracking go along the lines of: in so many
years computers will be so much more powerful, it takes so much more
time to crack a number of so many digits...
This analysis fails with current knowledge. Not only should the speed
of the processors itself scale, also memory should become faster by a
similar scale and also larger at the same time. As Bob Silverman already
noted: memory is becoming the bottleneck, not processor speed. And do not
expect many cache hits from the cracking process.
The algorithm used for RSA-129 goes in two distinctive steps. The first
step is most time consuming but is trivially distributable. That is
the sieving part of (pp)mpqs. A simplified explanation: starting with
a parametrized polynomial (depending on a single parameter) you note for
what parameter values it is divisible by some "small" primes. As these
parameter values are equi-distant, this is easy to fill in when you
start with a large array for possible parameter values. Going on until
all "small" primes are exhausted you look for what parameter values the
polynomial value is completely factored. Where it is, you have found a
relation. For standard mpqs you looked only for these. For pmpqs you
allowed also places were a single large prime is left in the remainder,
for ppmpqs you also allow two large primes left in the remainder. This
all does nearly not require pure processor speed, but large, fast memory.
Only for ppmpqs some better processor speed is required to determine
whether there are two primes left (but also this kind of work could
be relegated to another machine). You do all this work for multiple
polynomials (hence the 'm' in the name), and it is along the polynomials
that you distribute the work.
Good, that was step 1. In step 2 you build an nxn matrix where n is
the number of "small" primes you allow. Each row is a relation, in
a column you note a 1 when that prime occurs an odd number of times
in the relation, otherwise you note 0. (I omit the processing of
large primes.) If the number of rows (relations) is larger than the
number of columns ("small" primes) there must be dependencies. In
this step you try to find such dependencies (all over GF(2)). Each
dependency gives a factorization, but it may be the trivial 1.N
factorization. The probabiblity of that was 1/2 in this case.
For this step you need much memory, and as numbers increase in
size, you need more memory, because the number of "small" primes
used (the factor base) increases with the size of the number to
crack. For this step you use essentially Gaussian elimination over
GF(2). Gaussian elimination does not benefit overly much of caches,
all is essentially from memory.
From this you can conclude the following. Faster processors can be
less useful in step 1 than slower processors. E.g. a 10000 MIPS
processor with 1kb memory will be useless, while a 1 MIPS processor
with 1Gb memory with scaled speed is very useful. The second step
can not really be implemented unless the matrix fits in memory, and
here RSA-129 is currently approximately at the limits.
* This all modulo some of the tricks implemented in the current
algorithm, but those only imply that you get beyond the limits
a bit later.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924098
home: bovenover 215, 1025 jn amsterdam, nederland; e-mail: d...@cwi.nl
Michael Graff
>I apologize for the poor choice of words. What I had reference
>to was that even if you attack a cipher in a logical progression
>of n=1 to umpty steps, the successful step might be closer to 1
>than to umpty.
In the method we used, each tidbit of info we collect is much more important
in later steps than in early steps. While any one tidbit is just a small
clue, they begin to form groups (cycles) which give us real clues.
So, all along, we knew how many cycles we needed. We just had a guess (which
came out close I may add :) to how many tidbits we would need.
--M
--
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
>One thing I've been curious about: How much did you rely on the reliability
>of the people doing the distributed computing and the channels used to send
>their results to you? Suppose, for example, that a few people trying to
>defeat the project had decided to send you bogus relations. How many would
>it have taken to have caused you a serious problem?
That's the beauty of this whole thing. :)
If someone sent in faked (or mail-mangled, or bad data in general) the
collection machine would have caught them and disposed of them in the nightly
processing. It is hard (read: time consuming) to find the relations we were
collecting, but a snap to verify them once they are found.
Also, each relation is roughly equal to any other, so if one is skipped or a
worker machine doesn't complete the particular task it was given, it doesn't
matter much at all.
David Sternlight
Robert D. Silverman <b...@gauss.mitre.org> wrote:
>
>With current algorithms, 1024 bits will be safe for 25 years. No conceivable
>increase in computer power will let one factor a 1-24-bit number in that
>time frame.
Demonstration, please. Recall that we're talking not only about fast, but
also about massively parallel special purpose machines.
Thanks;
David
Michael Graff
>As a matter of interest: did you verify the relations on receipt, or only
>later on in the process? And how many bad ones did you receive?
Yes, we verified them. :)
We received about 150k of bad data, or so. Most of them were simply tossed
and forgotten.
Not a bad percentage -- 150k bad of 2G+ ;)