Slashdot Mirror
RSA-576 Factorization Officially Announced
product byproduct writes "RSA Security finally has a news item about the December 2003 factorization of RSA-576. (See earlier Slashdot coverage). We now know what the computational cost was: the 174-digit number was factored "using approximately 100 workstations in a little more than three months"."
That's a ton of computer hardware to use on factoring... I wonder why they didn't just use a distributed system (like seti@home) to do this... at least it's free.
What does this tell us? That if you throw enough machines and/or money at a solvable cryptographic challenge you'll solve it?
Try not. Do or do not, there is no try.
-- Dr. Spock, stardate 2822-3.
We should still be reasonably safe using the RSA-algorithm for a while more since the number is the equivalent of a 576-bit key. Most cryptography programs support upto 4096-bit keys, and the strength of a key increases exponentially for every bit if my memory does not fail me (correct me if it does).
:)
Safe, that is unless someone invents quantum computers and makes them easy to produce..
Couldn't agree more.. but from what I see they didn't use a distributed client.
Cure cancer.. and stuff! www.team45.info
No.
It tells us HOW MANY machines we need to throw at the challenge.
The whole key to protecting information is to make it cost more to recover the information than it is worth.
For example, if information is going to need to be kept secret for twenty years, projects like this help you learn based on current technology, how much crypto is sufficent (or overkill).
Do you or your partner snore? - Visit www.snoring.com.au
Of course, the whole idea behind key strength is rather moot if the user gets careless with his keys/passphrase.
Unfortunately, crypto is only as strong as the user(weakest link)
While it's not always comforting to know these things can be factored, at least we can take comfort in knowing that *most* hackers/spooks don't exactly have a 100 node server farm laying around just dying to crack your keys.
Of course, unless you're the NSA and measure their servers by acres...
A primer on distributed computing
I encrypt everything on my hard-drive using one-way compact encryption, it only cost me $100 and converts every file into 0 bytes that can't be de-crypted by anyone... not even me. Now THAT is proper security.
I previously used 2^(10e20) bit encryption which would have taken several universes to crack. Unfortunately it took one earth life to encrypt a 1 Mb file so I had to revert to the super-secure method above.
And Yes I do have a tin-foil hat... why do you ask ? Oh and the application that does the one way encryption. Well I work on Windows but I get this Unix utility called Cygwin and the guy sold me a program that does the encryption. I had a look at what was in encrypt.sh and what it says is
cat
Amazing how simple UNIX makes encryption... but then I use Windows so its all beyond me.
An Eye for an Eye will make the whole world blind - Gandhi
That makes it 240000 computer hours ... too cheap ..
Think about this :
...
It's a weekend job if I can sneak this in as along with the next upgrade.
:)
"Toy Story 2" had about 800,000 computer hours worth of rendering.
"The Hulk" had 2.5 Million computer hours
My office has nearly 400 fast machines , imagine this running them makes it 25 days . Running that every weekend makes it 12 weeks or 3 months
DDoS time is over with all networks being careful about... the next big windows worm will be a distributed processing program
Quidquid latine dictum sit, altum videtur
Surely a complexity calculation would suffice? After running a few iterations of the solver surely they could just calculate how long the key space would take to cover and divide by two.. why the need to run it until completion?
Cure cancer.. and stuff! www.team45.info
If you knew that factoring big numbers was important to breaking encryption, and would be for quite a long time wouldn't you simply have started a huge factoring effort decades ago? I know I would have.
It begs the question, how many workstations, for how many months, would it take to find out
How many licks does it take to get to the center of a Tootsie Pop?
I'm afraid the world will never know.
-Patrick
"They never stop thinking about new ways to harm our country and our people, and neither do we."
9/11 Eyewitnesses to Explosive WTC Demolition 1 of 2
... to waste 3 months and 100 computers trying to read my RSA-576 encrypted information, they are welcome
Free Firefox news reader.
I remember an article written some time ago
from a Dutch (I think) guy. He was stating that
for symmetric cryptography (i.e not RSA,
Diffie-Hellmann and the likes) a 128 bit long
key is enough. He was making the assumption
that cracking a 128 bits key (again, for a
symmetric algorithm) would produce, even with
processors 1000 more efficient heat-dissipation
wise than current chips, so much heat that the
Netherlands would be under sea level due to ice
melting.
However, I cannot remember where I read it, and
can't find it with Google. Can someone please
provide a pointer for this article? Now that
I'm more savvy with cryptography, I'd like to
double check if the paper indeed make sense or
if it is just a bunch of BS.
If we all remember our RSA encryption methods, or in fact any encryption method, they are all breakable, it's just a matter of enough computing power to do it. With RSA all you have to do is factor the big prime number pq into p and q and then you know phi = (p-1)(q-1) and from there you can get the decryption exponent no problem.
Encryption was designed to be just unbreakable enough, not totally unbreakable. 576-bits is a small one compared to what is often used for critical data these days, and every RSA factorization prize will be taken. But trust me it will be a lang time before you see the next ones show up, since eachadditional bit makes the problem a much harder one.
It'll be like this at least until quantum computing makes it all obsolete :) Every so often you will see that another RSA
Insert witty comment here
Surely a complexity calculation would suffice? After running a few iterations of the solver
Because there's no motive to optimise the solver. Open up the project, offer a prize and you'll get many eyes looking for the absolute best solution - then you can study the complexity of that.
OK, it took 1000 machines and 3 months for this particular example. The task is not impossible, and there are people who really can get their hands on 1000 machines.
If the goal is personal security, I agree that the average credit card hacker is not going to make the investment. On the other hand, the NSA has the hardware resources to attack on a grand scale, with perhaps even better algorithms.
It will be a while before RIAA and MPAA can hijack NSA resources to pursue P2P users, so I guess we ARE still safe for a while.
If you think about it, this means that VA could do 1024 bit in 1month. Gotta love the G5 supercomputer!
artlu
-------
artlu.net
I think that distributed computing is wonderful. It allows us to divide and conquer which is what the developed world should be about.
I agree that the analysis could just as effectively be done using bif-O notation and all that, but I still dont think we should knock it.
If you have a problem with people factoring RSA keys, then just dont take interest - go somewhere else.
Personally, I would like to distributed computing used to find out more about the origins of our universe etc..
There's a far easier way to crack the the key
open4free (c) (R) (tm)
factor the big prime number pq into p and q
Well, as Bill Gates has told us, that would indeed an tremendous mathmatical advance.
I have a solution right now, assuming the big prime pq where p != 1: p = pq, q = 1.
Sorry. I'm sure you just mistyped it, but I couldn't resist.
Not entirely true. The article states that three of the contributors were part of NFSNET which does have a distributed client.
Paul
Lasciate ogne speranza, voi ch'intrate
Does anyone know what the predicted lifetime of the 576 bit key was?
I mean, when they say that we should be using 4096bit keys today, how long do they predict that it will take to crack that key? (taking into account Moores law and perhaps linear growth over time of the number of clients contributing CPU cycles). Is it possible to guestimate?
I happen to know him a little, as one of my friends is his student, and another one was. If you think mathematicians are crazy, Franke is more than that. When you talk to him, he will usually just continue to stare at the piece of paper he has directly in front of his eyes (Nobody knows why he isn't wearing glasses.) and think of that as a normal way of communicating. His office consists of 3 huge desks (plus a computer desk); on each of them there is huge bunch of completely unorganized papers lying around, mixed with empty yoghurt cans.
His mathematical skill is enormous, he has done research in quite a lot of different areas of mathematics (analysis, algebraic geometry, algebraic topology, category theory), but he never bothers at all with making his results well-known. (In fact, at least one time he actually had to be persuaded to even publish his result, which got immediately accepted in Inventionaes, the most highly regarded journal in pure mathematics.) He even couldn't be bothered to apply for a much better-payed position at another university in Germany when he was almost urged to do so.
Anyone who knows him will burst out laughing when he reads that he supposedly said "I'm very proud of all these individuals from around the world and their efforts to solve this first factoring challenge." and all this other stuff in that paragraph of the article. I bet the author of this press release desperately tried to get some phrases longer than 5 words out of his mouth, gave up, and then decided to just make up all the quotes.
Now with his mathematical skills, number factoring is (in his own opinion) a rather dull activity. The reason he is doing this is that he expects an economic breakdown soon, and he thinks of his knowledge in number-factoring as an assurance against the coming job crisis. (Of course, his position is guaranteed by the German state until his retirement.)
But if you manage to get along with him, he is actually quite nice and extremely helpful.
I *believe* that they are O(k*n^2) or possiblely worst-case O(k*n^3) boolean variables for SAT.
For n = 640 bits, n^3 = 262'144'000 boolean variables, you will need a cheap little-expensive 64-bit supercomputer like Opteron 148 with a lot of RAM!!!.
open4free (c) (R) (tm)
RC5-64 is so solved, they are solving how to crack RC5-72.
RC5-72:http://www.distributed.net/rc5/
open4free (c) (tm) (R)
They say that Google is preparing an IPO, but sometimes I wonder what they need the money for. They already had enough money for 10,000-100,000 servers, after all. If they doubled or quintupled that acreage of computer-farm, would your search-results come to you down the Internet pipe so much faster that you'd be glad the did?
And they had the money to hire the experts needed to manage that cluster like a single supercomputer. Sure, they probably got some of that initial funding from ordinary venture capitalists, but what if some Govt. outfit helped, on the grounds of requesting access for occasional factoring purposes? After that IPO gets invested in a bigger farm, not even 2048-bit keys may be safe.
And I'd like to also add "petty."
Does the numeral posted here actually equal the product of the numerals posted here?
:-)
The last digit looks OK, anyway.
No, don't bother to flame me for laziness... I already know...
There was a time when I would have tried to do that on paper by hand, just to keep in practice. These days, not only am I too lazy to try that, but I don't currently have any software system at hand that implements indefinite-sized integer arithmetic... and I'm too lazy to implement one.
"How to Do Nothing," kids activities, back in print!
It took longer for them to come up with the press release than it did for their code to be broken. Lookin' good, RSA!
Must-not-watch TV!
java does this. It works on most platforms. See java.math.BigInteger
Rhymes that keep their secrets will unfold behind the clouds.There upon the rainbow is the answer to a neverending story
Like RC5 for example. If you break the RC5-64 key, everyone is happy. Then they want to break the RC-72 key.
Wow.. it takes ages and ages.. and what does it *really* proof?
Yes, it is breakable too.. wow. I'd rather have a few new medicins available, thank you :)
What I'm trying to say: there is plenty of computer power available on this world.. but not nearly near enough! There are far more important and interesting things to do with it then breaking some non-sense line of text!
bc and dc are Unix utilities that compute arbitrarily precise integers, basically limited by your memory and patience. (Obviously, they can't do the same thing for real numbers). The GNU versions, I believe, are based on the GNU MP (multiple precision) library, which is an incompatible replacement for the original Berkeley MP library.
:)
Anyway, as for using it, bc is probably easier to use, as it implements a standard calculator interface. See man bc for details. I usually use bc -l when I want to work with fractional values. dc is the original utility, but it uses reverse polish notation (RPN), so it may or may not be intuitive to you. I believe bc is usually implemented as a frontend to dc.
If you're stuck with Windows or Mac, a quick Google will turn up some applications that implement arbitrary precision math. You can also probably find a Java applet to do it, since big number support is built righti n.
As to why I would know all this, multiplying really big numbers with exact integer precision is something that comes up often enough to warrant a little informal searching.
My Stuff: pspChess and foobar2000 plugins
http://www.google.com/search?sourceid=navclient&ie =UTF-8&oe=UTF-8&q=39807508642406493739712550055038 64911990643623425267084063851895759463889572617685 83317+%2A+4727721461074353025362230719730482246329 14695302097116459852171130520711256363590397527
And google confirms the first few numbers...
Cracking RC5 has nothing to do with factorization.
RC5 is a symetric crypto algorithm and winning the challenge is not a matter of smart algorithms like in the factorization case but of brute force, because one "just gave to" try all keys (statistically speaking you're likely to try about half of them, i.e. 2^71 keys) until one decipher the challenge in something meaningful. (in the case at hand recognizing something meaningful is easy as part of the text in the message is already known, in the real world it is not always the case). This is a really easy problem to distribute (just allocate some key space to each volunteer and have them report back once they're done if they found it or not), unlike the GNFS algorithm where you must have a big computer with very fast RAM to hold a giant matrix in the last phase, something you can't get at Best Buy.
Please go chase some car on the highway, it'll clean the gene pool.
Yes. They are correct.
9 9064362342526708406385189575946388957261768583317" );3 2914695302097116459852171130520711256363590397527" );
9 41 73827007633564229888597152346654853190606065047430 45317388011303396716199692321205734031879550656996 221305168759307650257059
BigInteger p1 = new BigInteger("3980750864240649373971255005503864911
BigInteger p2 = new BigInteger("4727721461074353025362230719730482246
BigInteger p = p1.multiply(p2);
System.out.println(p);
18819881292060796383869723946165043980716356337
It just took some time to get to the marketoid...
Factorization of RSA-576
import java.math.BigInteger;
5 26708406385189575946388957261768583317";0 97116459852171130520711256363590397527";
t or));
public class biginteger
{
public static void main(String[] args)
{
String num1 = "398075086424064937397125500550386491199064362342
String num2 = "472772146107435302536223071973048224632914695302
BigInteger firstfactor = new BigInteger(num1);
BigInteger secondfactor = new BigInteger(num2);
System.out.println(firstfactor.multiply(secondfac
}
}
this should do it..
There is very little info to the article.
My summary: they used about 100 workstations and it took 3 months. General credits to those involved.
That's it. Oh yeah, and a quote.
My interest is in how an individual's effort would have compared to their's. 100 machines is a little too vague - and is only really useful in the initial sieving process anyway. The last stage hasn't been implemented in a distributed fashion yet, so it can only be done on one.
Perhaps an estimate that can be roughly referenced by other computers. Does anyone have a link to this info or a better article (preferably in english)?
Maybe I'm asking for too much. Or maybe it'll be another four and a half months before we see any real detail.
This is not my sig.
- CPU speed has been doubling pretty fast, every 1.5-2 years.
- Memory size (or at least, size/price ratio) has been growing pretty fast.
- Disk capacity has been booming faster than CPU speed, though disk seek times have been changing much more slowly.
- Memory speed has been lagging - I forget the exact numbers, but some of the hashcash folks did some research and found the speed doubled every N years, maybe 3-4. Certainly not the same curve as CPU speed.
If the real constraint in GNFS is storing and retrieving data, not multiplication speed, then you could easily get an environment where memory speed increases are the gating factor for your Moore's Law growth, no CPU speed increases, so your K-bit key is good for 2-3 times as many years as you'd expect.On the other hand, factoring is a problem where the increases in Algorithm Speed have been just as critical as increases in Computer Speed. So maybe GNFS has reached the point where it's computer-speed-bound, but next year's Super-Duper-Number-Field-Sieve may be several times more efficient than GNFS, just like GNFS was several times more efficient than NFS in the ranges that are now interesting. Sometimes this happens just because mathematicians keep doing new work, and sometimes it happens because computer capacity (e.g. memory size) grows enough from Moore's Law that algorithms which weren't practical in the past become practical. There were factoring tools that weren't useful when most computers had 128MB of RAM, but work fine now, and there may be tools that aren't practical when most computers have less than 4GB of RAM, but five years from now your SonyNintendo box will have enough RAM to run Sieve@Home.
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
>Most cryptography programs support upto 4096-bit keys, and the strength of a key increases exponentially for every bit if my memory does not fail me (correct me if it does).
First, adding one bit to the size of a number only doubles the range of possible numbers.
Second, even that doesn't apply to RSA because not every number is a possible key (not even close!). A key is the product of two large primes. Numbers like that are thin on the ground.
Third, there's no value in making your crypto harder to crack until you've made the rest of your system as secure as your crypto. Ask yourself which is cheaper -- brute-forcing a DES key, or breaking into your home and training a hidden camera on your screen?
9/11 Eyewitnesses to Explosive WTC Demolition 1 of 2
Yes it does.
Use Pari/GP. It's even GLP.
>The whole key to protecting information is to make it cost more to recover the information than it is worth.
That post deserved its +5 Insightful but here's a quibble anyway.
The idea of making information more expensive to crack than it's worth depends on your being attacked by people with economic motives.
If the attackers are true hackers they'll do it for the challenge. The more elaborate and clever your security, the harder they'll work. The "solve a puzzle-win a prize" motivation pulls people harder than the prize does.
Yes, there are in fact precisely 640 variables (a320,...,a0 and b320,...,b0 where a0=b0=1, and a*b=n). There are of course 36,869 carry terms and a huge number of intermediate terms, but each of these can be expressed as a function of the bits that comprise the two 321 bit factors.
9/11 Eyewitnesses to Explosive WTC Demolition 1 of 2
ANSI X9F1 -- the influential working group that develops US standards for the financial services industry on data security -- has reportedly decided, at least informally, that 2010 will be the year at which they will require an upgrade from 80-bit to 112-bit crypto security.
NIST generally follows the lead of X9 in these matters.
80-bit ciphers are generally understood, on the basis of equivalent resistance to brute force attacks -- the state of the art, as measured by the results in RSA Security's industry-defining crypto contests for both symmetric and RSA public key cryptosystems, and Certicom's ECC equivalents -- to encompass 1024-bit RSA (and DSA), as well as SHA1, Skipjack, and 160-bit ECC.
112-bit crypto strength is understood to be found in three-key triple-DES, SHA-224, RSA-2048, 224-bit ECC, and other standard cryptosystems with even longer keys.
This means that any data encrypted today, which must remain secure beyond 2010, should be using at least 112-bit crypto.
(While there are obviously levels of cryptographic security that lie between these 80-bit and 112-bit ciphers, ANSI X9 and NIST are trying to structure the technical debate in order to simplify their ultimate recommendations on effective security measures.)
_AraratThat any key can be cracked if enough computing power is thrown at it. Remember NSA does this as their job, now how many keys have been cracked? All or real close to it.
Professional Politicians are not the solution, they ARE the problem.
Too bad your post wasn't modded up, I was about to re-type what you said. They make a BC version for windows as well. Can't find the link right now but search for "BC.exe". Also, PHP has a "bc" function.
We now know what the computational cost was...
We also could have spared ourselves the computer-months of CPU time and just computed the computational cost using a few miliseconds of calculator time.
The only time such an exercise is successful is when a new code-breaking technique is developed to solve the problem, not when brute force wins.
But the universe refuses to maintain the 'state' in which it was in and several factors were conspiring against that estimate from the start. The estimate was based on a single processor running at a single speed with a single algorythm. Unfortunately, the evolution of the hardware, the creation of stable multi processor systems and cheap clusters, and the development of new algorythms have all conspired to have that estimate drop like a rock until it has now hit zero!
What's more important in IMHO is the life of the information protected by the key. As long as the information needs to be kept secret the key's factorial combinations should remain incalculable. In the mean time we can only say that the key's ability to protect the data is 'less than X,' where X is the current time it takes to calculate the factors of the key.
"Can there be a Klein bottle that is an efficient and effective beer pitcher?"
According to the marketroid article, RSA Labs announced it "today". So are you saying that the RSA marketroids are both slow and lying?
Jose T Oliveira Jr.
I understand what you are saying, however it's besides the point. In protecting anything you need to assess what (or who) exactly the threat is, including their motivation, be it social, political or financial for example. Even if, in your scenario, its a bunch of challenge-happy hackers, then you merely protect your information according to this different threat. This may or may not involve crypto.
My reference to making information "more expensive" could also have be phrased: "making protected information way too much bother to crack before people lost interest and chased poodles with puffy tails instead while someone beat the information out of you".
Do you or your partner snore? - Visit www.snoring.com.au