512-bit RSA Key Cracked.

Alec Muffett writes " On Thursday, a small team of people (including myself) announced the world's first factorisation of a 512-bit RSA encryption key (aka: RSA-155) - considerably bigger than the RSA-129 challenge of several years ago, and this time performed by a small cabal of numbercrunchers, just to see if it could be done in secret. There are press releases and announcements available, as well as considerable discussion in sci.crypt. " Read on for what Alec has to say on the matter. This is a significant advance because such 512-bit length keys are routinely used in (possibly ill-advised?) transaction protocols for some important financial institutions (read: some serious $$$$$$$ may be at risk in the near future) - and moreover, as a factoring contributor, I can state that I personally have now been offered the use of additional hardware which could take the 6 or 7 months spent sieving for results, and reduce the time by a factor of some 40% to 60%.

Comments

More Info...Comments

[Rolan]

More info is here from CWI. It took them between 3.5 ad 3.7 months (I've seen both numbers). But here's the stats on what the used:

"Sieving was done on about 160 175-400 MHz SGI and Sun workstations, on 8 300 MHz SGI Origin 2000 processors, on about 120 300-450 MHz Pentium II PCs, and on 4 500 MHz Digital/Compaq boxes. The total amount of CPU-time spent on sieving was 35.7 CPU years estimated to be equivalent to approximately 8000 mips years. Calendar time for sieving was 3 1/2 months."

"(L: using lattice sieving code from Arjen K. Lenstra C: using line sieving code from CWI)

20.1 % (3057 CPU days) Alec Muffett (L at Sun Microsystems Professional Services, Camberley, UK)
17.5 % (2092 CPU days) Paul Leyland (L,C at Microsoft, Cambridge, UK)
14.6 % (1819) Peter L. Montgomery, Stefania Cavallar (C,L at CWI, Amsterdam)
13.6 % (2222) Bruce Dodson (L,C at Lehigh University, Bethlehem, PA, USA)
13.0 % (1801) Francois Morain and Gerard Guillerm (L,C at Ecole Polytechnique, Palaiseau, France)
6.4 % (576) Joel Marchand (L,C at Ecole Polytechnique/CNRS, Palaiseau, France)
5.0 % (737) Arjen K. Lenstra (L at Citibank, Parsippany, NJ, USA and Univ. of Sydney, Australia)
4.5 % (252) Paul Zimmermann (C at Inria Lorraine and Loria, Nancy, France)
4.0 % (366) Jeff Gilchrist (L at Entrust Technologies Ltd., Ottawa, Canada)
0.65 % (62) Karen Aardal (L at Utrecht University, The Netherlands)
0.56 % (47) Chris and Craig Putnam (L at ?)

Calendar time for the sieving was 3.7 months.
The relations were collected at CWI and required 3.7 Gbytes of disk space."

Quoted material from the link provided at the begining.

Time for Civil Disobediance? Think Carefully...

[Baldrson]

When a "former" NSA employee forbade me, in 1982, from continuing my work to incorporate RSA's public key algorithm in the home shopping and banking capabilities of the Western Electric videotex terminal that was to be deployed in the Viewtron service a few years later, I knew it was going to be a long haul before the potential of this technology could be realized. (I believe my comment to him was "The NSA contracted with IBM to report on the security of its 56 bit DES, and many independent experts believe this was more than a mere conflict of interest." His response was something like, "I'm a former NSA employee. You will stop work on RSA and use DES.")

Seymour Cray's final product involved the fastest switching technology ever activated in a super computer, which was then coupled into a massively parallel computing system. The Cray-3/Super Scalable System had a revolutionary GaAs control processor with potentially tens of millions of computing memory elements. This system (an adaptation of the original GaAs Cray-3) was financed by the NSA. Seymour Cray accepted this funding in a last-ditch effort to save his company and when I visited the Colorado Springs office, I was actually given the impression by one of their executives that they had a working model and would consider commercial sale of the device. Cray Computer Corporation went bankrupt shortly thereafter in the first business failure of Cray's phenomenal career. About a year later, Cray was killed in a jeeping accident. Having cut my teeth on his machines at the CDC/Urbana PLATO project, I knew Cray was unhappy with the direction his technology had been taken by "the spook shops" from before the day he left CDC to found Cray Research on his farm in in Wisconsin.

Recent revelations of RSA's vulnerability come as no surprise. The NSA, despite the fact that it is run by unaccountable bureaucrats embedded in a dough ball of Federal funding, is probably far beyond a cabal of private hackers in their capabilities.

Lest hackers and civil libertarians get the idea that now is the time for civil disobedience in protest of regulations against unlimited key sizes, you should probably be aware that Federal officials are so embolden by their lack of accountability that some of them have slipped up and are explicitly threatening suspects with prisoner gang rape. Given the prevalence of HIV infection in the prison systems, and the efficiency with which the virus is transmitted during gang rape, such threats amount to murderous sexual sadism as punishment for civil disobedience. In one of the most outrageous examples, Assistant U.S. attorney Gordon Zubrod from Harrisburg, PA made the following statement in a broadcast statement to 3 suspects who fled to Canada (this statement was captured for the public record during a Canadian Broadcasting Corporation interview):

"You're going to be the boyfriend of a very bad man if you wait out your extradition."

If you think the use of murderous sexual sadism against protesters who engage in civil disobedience is unrealistic, or somehow so low risk as to be inconsequential, you should read Torture In The American Gulag before taking any personal risks.