768-bit RSA modulus factorized

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

2 Responses

#1Dew Drop – January 8, 2010 | Alvin Ashcraft's Morning Dew said...
08-Jan-10 6:50 AM

Pingback from Dew Drop – January 8, 2010 | Alvin Ashcraft's Morning Dew

#2hari E said...
01-Nov-10 5:32 AM

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

•  Emphasize with italics: surround word with underscores `_emphasis_`
•  Emphasize strongly: surround word with double-asterisks `**strong**`
•  Link: surround text with square brackets, url with parentheses `[text](url)`
•  Inline code: surround text with backticks ``IEnumerable``
•  Unordered list: start each line with an asterisk, space `* an item`
•  Ordered list: start each line with a digit, period, space `1. an item`
•  Insert code block: start each line with four spaces
•  Insert blockquote: start each line with right-angle-bracket, space `> Now is the time...`