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

More about distributed computing...

[BillGodfrey]

Stuff to read...

A primer on distributed computing [bacchae.co.uk]

Re:Still safe for a while

[Ckwop]

Wow nice random word generator.. Can I have a go?

Seriosuly, It's utter rubbish. I mean please explain to me how you stack an S-box into a corner of a cryptographic chamber..

It's just a substitution you muppet.. And cryptography isn't all hardware speed.. I mean WEP [berkeley.edu]

was broken with trivial computing power!

Simon.

If anyone wants...

[Phidoux]

... to waste 3 months and 100 computers trying to read my RSA-576 encrypted information, they are welcome

Re:Still safe for a while

[thedanc]

Bear in mind, using bits to exponentially increase cryptographic strength only works until you reach the Berenstein factor, which is a practical limit on the number of S-boxes that can be stacked in any particular corner of the cryptographic chamber. After a certain point, which varies according to the chamber ceiling, it is possible albiet less space efficient to take advantage of parallel stacking to some extent.

Mods -- how could you let this get modded up? First, S-boxes are in DES, not RSA. Next, even if the random reference was to the correct cryptographic algorithm, the rest of the comment still makes no sense at all.

C'mon people, post if you have a clue, and only if you have a clue.

Re:Still safe for a while

[Anonymous Coward]

You complete idiot. Linearity in the _length_ of the key vs. year means _exponentially_ faster-running factoring over time. But if you couldn't figure that out for yourself, you could at least look up your screen a couple of inches where they state:

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

At any rate, time to go buy a G5 I think, they are supposed to have pretty fast memory.

Re:Factoring in advance

[RupW]

Not true, because if you can factorise the modulus in the public key (which is generally easy to get), you can generate the private key.

Yeah, that was misleading - I was just trying to say you need a target for your arbitrary factor effort. In my mind I'd figured you'd have to have the encrypted message to know what private key it was encrypted for - although I realise now that's not necessarily true (and neither's the reverse). But it could be for real tinfoil-hat types :-)

There's no good reason, either, why a public key can't be kept as confidential as a private key or a symmetric cipher key - it's just that once you publish it to a few people there are more points of failure. And if you don't have the public key (in GPG's implementation at least) you don't have anything to try and factorise because it's not bundled with the encrypted data.

Re:So, has any Slashdot reader checked the results

[Ant2]

Yes. They are correct.

BigInteger p1 = new BigInteger("39807508642406493739712550055038649119 9064362342526708406385189575946388957261768583317" );
BigInteger p2 = new BigInteger("47277214610743530253622307197304822463 2914695302097116459852171130520711256363590397527" );
BigInteger p = p1.multiply(p2);
System.out.println(p);

188198812920607963838697239461650439807163563379 41 73827007633564229888597152346654853190606065047430 45317388011303396716199692321205734031879550656996 221305168759307650257059

See also dmaxwell's correction

[Beryllium Sphere(tm)]

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

Re:Security

[ConsumedByTV]

While I agree with the sentiment of this remark, I have to disagree with some implementations.

Yes, it's not going to be difficult to attack the users passphrase if it's stupid. However you make an assumption that most people who encrypt their harddrive keep their keys on the laptop.

I don't.

With loop-aes, you have pretty good abstraction.

So you can have a set of gpg keys, a file encrypted to a given public key, and the data to be decrypted, all in different places.

In theory, it can be done over a network, a usb keychain, a serial cable, whatever you want.

In the end, if they have all three, yes, the password is the last link obviously.

The key is to make sure that those three aren't in the same place at the same time, once the system is on, the keys are loaded into memory and aren't needed. Remove the usb key with your gpg secret key. Remove the usb key or detach from the server that has the actual encrypted gpg file that holds the actual disk encryption keys.

You need all three to attack the users password at that point. Assuming that you decide it's not worth cracking the gpg encrypted file (4096bit), that it's not worth cracking the passphrase (war and peace in leet speak), you can attack the disk file itself.

Each encrypted partition has 64 different keys that are all
61 different characters long.
Example:
kd11Zki1oKre4iSwXaMX+C/wH+t7RXBtG 3Q0rog5pYAHHVm0tb CWDYp0MgII

So yea, it's possible to crack that, but I highly doubt that you will.

So stealing my laptop takes away my hardware, and my encrypted disks. It doesn't mean you have an easy way into my data.

Check out the loop-aes [sf.net] project for practical examples of this in Gnu/Linux.

It's not perfect, but it's better than the stupid cryptoloop crap where you can't ever change your password because that requires writing all the data to the disk again (with the new key).