An international team of cryptographic researchers demonstrated last week that the 512-bit RSA key, used to secure many e-commerce transactions, can be broken.
A group affiliated with the National Research Institute for Mathematics and Computer Science (CWI) in Amsterdam won first place in a cryptography competition by factoring a 512-bit or 155-digit number of the type used for public key cryptography.
RSA Data Security Inc of San Mateo, California, sponsored the RSA Factoring Challenge to gauge the strength of security provided by various encryption key lengths. The company announced last week that it took the team seven months to determine the two prime numbers used to generate a single 512-bit RSA key. That information could be used to decode encrypted information. RSA issued a statement that the result "reconfirms RSA's ongoing recommendation for using 768-bit keys as the minimum for achieving reliable security".
Bruce Schneier, president of Counterpane Systems, a Minneapolis computer security and cryptography consulting firm, said there are no implications for e-commerce that were not already true before the announcement. "512-bit keys are not suddenly risky," said Schneier. "They have been risky for the better part of a decade; anyone who has studied the issue knows that."
According to RSA, the team used 292 individual computers at 11 different sites around the world. Machines used included 160 SGI and Sun workstations and 120 Pentium II PCs.
Schneier pointed out that this same problem could be solved in about a week by networking a number of machines over the Internet similar to one of the strategies used to crack the Data Encryption Standard (DES). Factoring a 512-bit number in this fashion would be 50 times easier than cracking DES, noted Schneier. He said this shows that other organisations could already be regularly breaking e-commerce keys.
"Factoring e-commerce keys is definitely very practical, and will become even more so in the future years," said Schneier. "This is not a theoretical break."