RSA, a public key cryptography algorithm, relies for its security on the fact that factorizing a number that is the product of two large primes is hard. Very hard.

A group of computer science researchers, mostly from Europe, have just factored the number RSA-768:

RSA-768 = 12301866845301177551304949583849627207728535695953347921973224521517264005
 07263657518745202199786469389956474942774063845925192557326303453731548268
 50791702612214291346167042921431160222124047927473779408066535141959745985
 6902143413

It's 768 bits long (or 232 decimal digits) and is the product of two 116 decimal digit numbers. If you know anything about public key cryptography and how it's used in SSL (the underlying tech for secure web sites like your bank), you may be feeling a little alarmed at this; after all the researchers in their paper estimate that factoring a 1024-bit product of two primes is only about one thousand times harder and many people are using 1024-bit RSA.

However, let's just see what was involved in completing this feat. They used the number field sieve method (not something I've ever heard of, to be clear). First of all they used 80 processors for 6 months on polynomial selection (presumably part of the sieve algorithm). After that they performed the main task known as sieving, "which was done on many hundreds of machines and took almost two years." So after two and a half years of continuous processing on 80 and then "several hundred" machines, they factorized RSA-768. They admit that on a single 2.2GHz AMD Opteron processor with 2GB of RAM sieving would have taken 1500 years.

Although a formidable feat -- and believe you me, I am in awe -- this is still brute force. No doubt, the techniques and code they used will be refined in the future (and they do say that their estimate is 10 years before RSA-1024 is factored), but it's still not a "knock it out in an afternoon" type break. I'd say we're safe for a while yet.

Oh, by the way, the result they found is that

RSA-768 = 33478071698956898786044169848212690817704794983713768568912431388982883793
 878002287614711652531743087737814467999489
 × 36746043666799590428244633799627952632279158164343087642676032283815739666
 511279233373417143396810270092798736308917

Posted via email from Julian's posterous

 

Posts on similar topics...

• Someone is wrong on the internet — the lock-free stack edition
• I have PCPlus Mail
• JavaScript for C# programmers: object inheritance (part 2)