Questions and Answers: Shamir's Factoring Device and RSA
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.
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.
Building the device would involve a fair amount of opto-electronic engineering, but it is likely to be feasible. Actually, such competitions can and have been applied to RSA. Since several years before RSA started the
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.
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.
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. |