Questions and Answers: Shamir's Factoring Device and RSA

Also available:

RSA Press Release

An Analysis of Shamir's Factoring Device
 - Robert Silverman, RSA Labs

What is RSA announcing?

At the Eurocrypt '99 conference this week in Prague, Adi Shamir, a coinventor of the RSA public-key algorithm and a professor at the Weizmann Institute in Israel, is presenting a design for a special hardware device that would speed up the first part of the process of factoring a large number. The design, called TWINKLE, which stands for "The Weizmann INstitute Key Locating Engine," is based on opto-electronics. Shamir estimates that the device would be as powerful as about 100 to 1,000 PCs in the factoring process called "sieving," and would cost only about $5,000 in quantity.

Does this mean that RSA can be cracked?

No. Shamir's device offers the possibility of recovering keys less expensively than with a network of PCs, but does not crack RSA in the sense of making it easy to recover keys of any size. Rather, the device  speeds up the "sieving" step of known methods of factoring large numbers, which are the primary avenues for attacking the RSA public-key algorithm. The design confirms what was previously expected about the appropriateness of certain RSA key sizes, including 512 bits. Larger RSA key sizes are still out of reach, one of the obstacles being the amount of work and storage involved in the rest of the process of factoring a large number.

What would it take to build the new device?

Building the device would involve a fair amount of opto-electronic engineering, but it is likely to be feasible.

RSA sponsors competitions that demonstrate that DES can be cracked by a group of determined computer enthusiasts using networked computers. Why can't this be applied to RSA?

Actually, such competitions can and have been applied to RSA. Since several years before RSA started the DES Challenges, which offer prizes for successful recovery of a 56-bit DES key, RSA has been awarding prizes for successful factorizations of large numbers, including many RSA numbers. Very few of the RSA numbers have been factored so far, however, the largest one being about 450 bits long, still short of the 512-bit mark targeted by the new device.

Perhaps the new device, if built, may figure into future cracking efforts around the 512-bit level, just as the Electronic Frontier Foundation's Deep Crack device has facilitated the last two cracking efforts for DES.

What can developers do to safeguard their products against advances due to the new device?

One of the benefits of the RSA public-key algorithm is that it has a variable key size, so, in effect, it has variable strength. This is in contrast to DES, which has a fixed, 56-bit key size and is difficult to safeguard if the key size is found to be insufficient. Products based on RSA can be protected against the new device and other developments in factoring technology with appropriate key sizes.

In the 1980s, the "default" key size for many RSA implementations was 512 bits, which even as of this writing has not been broken. Several years ago, recognizing that 512-bit keys might be at risk in the near future, RSA Laboratories recommended that developers choose a minimum key size of 768 bits for user keys and 1024 bits for enterprise keys. (The recommendation for certificate authority "root" keys was 2048 bits.) Products following these recommendations are safe against the new threat, and products that support a variable key size can be safeguarded through the deployment of longer keys.

Last week, RSA issued a bulletin about a weakness in the ISO 9796 signature format. Today, you're disclosing that it is possible to break RSA.  Is RSA's encryption technology still secure?

Yes, RSA's encryption technology is still secure. Last week's announcement was about a weakness in an alternative format for preparing messages for RSA signatures that is not supported by RSA's products. The weakness was related to the format, and not the RSA public-key algorithm itself. Today's announcement is about a clever design for a hardware device that speeds up known methods of factoring large numbers, not a new method of attacking the RSA public-key algorithm. In both cases, the strength of the methods supported in RSA's products and of the key sizes recommended by RSA Laboratories have been confirmed.

RSA Laboratories will continue to report on these and similar developments.