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

Comments

Re:It has to be asked...

[Sheetrock]

Especially in light of all the projects one could be donating computer cycles to, such as protein folding or SETI.

What does this tell us? That if you throw enough machines and/or money at a solvable cryptographic challenge you'll solve it?

Still safe for a while

[BuddieFox]

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

Re:Still safe for a while

[Ckwop]

Also remember the moore's law doesn't apply to factoring algorithms.. This is because for the GNFS the *memory* speed is what's important and that isn't growing nearly as quickly..

Not convinced? Look at the linear proportionality in this graph

Simon.

Re:Still safe for a while

[dmaxwell]

The rules are different for public key cryptography. You are correct in that every bit added to a symmetric crypto key doubles the keyspace. In public key crypto which RSA is one type of, it is necessary to add 10 bits to double the difficulty. That 10 bit number is somewhat fuzzy. It can be a little more or a little less depending on whether we are talking about elliptic curves or Diffie-Hellman and others.

Re:Still safe for a while

[andalay]

WEP had a flaw in the protocol.

The flaw made it possible to inject unauthorized packets and reduce the time/space needed for brute forcing the key.

Thanks for demonstrating a common misconception in cryptography: it is all about encryption and decryption. Its not. Its also about the algorithms and protocols you use in your applications. Encryption/decryption is a factor in the security but it is not the whole point of cryptography.

As a result, when people break SSL,WEP, it is as much a part of practical cryptography as factoring integers

Re:Lots of hardware...

[ezzzD55J]

Because it's difficult to efficiently parallelize (distribute) the factorisation algorithm, especially the final step which so far has always happened on 1 machine. In fact, if you can paralellize the final step of the GNFS (general number field sieve is generally used for these factorisations), you have yourself a PhD. thesis (in math and/or CS), I remember reading in sci.crypt.

Hundred computers * 3 months

[Gopal.V]

That makes it 240000 computer hours ... too cheap .. Think about this :

"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 ... It's a weekend job if I can sneak this in as along with the next upgrade.

DDoS time is over with all networks being careful about... the next big windows worm will be a distributed processing program :)

Re:Hundred computers * 3 months

[duffbeer703]

Think about the commercial application of cyrpto... would anyone invest Pixars IT budget to steal a few credit card numbers?

Even with military-style secrets, timing is key. If a US war plan is intercepted by a foreign intelligence service, only to be decrypted months later, that data is pretty useless.

Re:Hundred computers * 3 months

[Short Circuit]

would anyone invest Pixars IT budget to steal a few credit card numbers?

It depends on the credit limits of the cards, and whether or not the holder knows the data's been accessed..

Re:Hundred computers * 3 months

[phoenix.bam!]

I'd imagine intelligence agencies would have a lot mroe than 100 machines working on cracking the US military plans...

Factoring in advance

[Anonymous Coward]

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.

Re:Security

[CoolGopher]

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

Or if you grabbed the source for the latest windoze worm and modded it to bruteforce keys in addition to spreading...

I have a suspicion that doing that would give you a supercomputer that quite possibly ranked #1 on the supercomputer charts, and for free to boot*.

*) Comes with complimentary government provided lodging and meals.

Virginia Tech

[artlu]

If you think about it, this means that VA could do 1024 bit in 1month. Gotta love the G5 supercomputer!
artlu

Anyone know what the predicted strenght was?

[pmcevoy]

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?

Jens Franke

[greppling]

(As far as I understand, he and Thorsten Kleinjung wrote most of the software used, and did most of the work in the project, while the other institutions were rather donating computing time.)

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.

Re:Jens Franke

[Xilman]

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.

I also know Jens quite well (we are on first-name terms) and he seems sane enough to me. Perhaps I have hung around with mathematicians too much!

But if you manage to get along with him, he is actually quite nice and extremely helpful.

Seconded. Thorsten Kleinjung is also one of the good guys and very helpful.

Paul

Next Time, Hire Google

[VernonNemitz]

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.

Memory speed vs. CPU speed increases

[billstewart]

You missed his point, though perhaps he could have expressed it more clearly. Many applications are CPU-bound, some are memory-size-bound, some are memory-speed-bound.

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