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

Lots of hardware...

[basil montreal]

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.

Re:It has to be asked...

[lewko]

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

Security

[nuclear305]

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

Re:Lots of hardware...

[Chilliwilli]

I'm sorry but factorisation problems and SETI really infuriate me. Firstly we can calculate how long something will take to compute with ease using simple the simple CS complexity analysis we all learnt at university.. then theres the SETI people.. not that I don't want to know whether there's life on other planets but to be honest there is so much we don't understand on our own planet that could have far greater reward for us all. Things I'm talking about might be research into climate, new fuels, medicines. The only distributed task I contribute to is folding@home because all others don't seem worth the extra energy and heat my PC will put out.

Re:Factoring in advance

[RupW]

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.

Factoring what? You won't know the number you need factored until you intercept or steal the encrypted data.

You could, I suppose, start multiplying every pair of primes together and try and organise a database of the results but the storage - even if you just store some sort of clue to the primes used - would be staggering, even for just 1024-bit RSA.

Re:It has to be asked...

[RupW]

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.

Safe from whom?

[dcavanaugh]

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.

Re:Still safe for a while

[cortana]

For each specific algorithm, the progress follows Moore's law that states that the speed of computers double every 18 months.

Sorry for sounding like a dick, but Moore's Law states that the number of transistors per unit area doubles every eighteen months. This does not directly correspond to an increase in computer "speed".

Re:Factoring in advance

[tadmas]

You won't know the number you need factored until you intercept or steal the encrypted data.

You don't have to steal anything. The number to factor (the modulus) is given away as part of the public key.

organise a database of the results but the storage - even if you just store some sort of clue to the primes used - would be staggering, even for just 1024-bit RSA.

For 1024-bit numbers, the factors will be on the order of 512-bits. The density of primes is rougly 1/ln(n), and ln(2^512) is about 355, so you should expect around every 355 numbers to be prime. That's only 3e151 numbers, not to mention that you'd have to figure every product of the two, which is 0.5*(3e151)^2, or 7e302 numbers.

Staggering doesn't begin to describe how many of these things you'd have to store.

Re:Virginia Tech

[Chexum]

Uh, oh, someone is bad at math...

I don't think VA's unknown numbered G5 park is about 2^448th more powerful than 100 PC(?) nodes. I don't think it's possible.

Or, I simply have been trolled :)

On the other hand, let me check my sig again...

soooo....

[MasTRE]

It took longer for them to come up with the press release than it did for their code to be broken. Lookin' good, RSA!

Re:It has to be asked...

[StarfishOne]

IMHO projects like Folding@Home, TSC, United Devices, Lifemapper or ClimatePrediction.net are far more important then breaking a piece of encrypted material.

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!

Goes to show

[BCW2]

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