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
Loading links to posts on similar topics...
2 Responses
#1 Dew Drop – January 8, 2010 | Alvin Ashcraft's Morning Dew said...
08-Jan-10 6:50 AMPingback from Dew Drop – January 8, 2010 | Alvin Ashcraft's Morning Dew
#2 hari E said...
01-Nov-10 5:32 AMplz someone tell me how to find modulo of big number like mod (27^21667,32881) in matlab
any algorithm plz tell me it will be very helpful for my project
Leave a response
Note: some MarkDown is allowed, but HTML is not. Expand to show what's available.
_emphasis_**strong**[text](url)`IEnumerable`* an item1. an item> Now is the time...Preview of response