RSA Laboratories Key-Size Directive Reaffirmed at Technical Conference

Related documents:

Questions and Answers: Shamir's Factoring Device and RSA

An Analysis of Shamir's Factoring Device
- Robert D. Silverman, RSA Laboratories

SAN MATEO, CA and PRAGUE, THE CZECH REPUBLIC, May 4, 1999 -- A recommendation by RSA Laboratories, RSA Data Security, Inc.'s research arm, to use 768-bit and 1024-bit keys as the minimum for achieving reliable security was reaffirmed today when the design for a potential hardware-based threat to RSA keys was revealed in a research paper presented today at a technical conference in Europe.  The design for the theoretical hardware device was discussed by RSA co-inventor Adi Shamir at the Eurocrypt '99 conference being held in Prague, Czech Republic.

In his research result, Shamir describes better ways of using known factorization methods, including one based on the work of John M. Pollard, one of the recipients of the 1999 RSA Award.  According to Shamir's result, a specially-designed hardware device could do as much work as one hundred to one thousand desktop workstations in its part of the process of factoring a large number.  However, the device still faces practical limitations in fabrication and implementation.

"Though the new device, if built, would place 512-bit RSA keys at much greater risk, it would have no effective impact on 1024-bit RSA," said Shamir, a professor at the Weizmann Institute in Israel.

"This theoretical device reinforces what RSA has been advising its customers for several years," said Burt Kaliski, chief scientist of RSA Laboratories.  "A key size of 512 bits is not enough for real security, and 768 bits should be considered the acceptable minimum key length for protecting critical data."  Current industry standards for the RSA algorithm, such as the ANSI X9.31 banking standard for RSA signatures, require a minimum of 1024 bits for an additional level of security.

As was pointed out at the 1999 RSA Conference, special purpose hardware devices are good for collecting lots of equations and then extracting the required information to break the key. But with larger key sizes, the number of equations reaches into the billions, resulting in a RAM storage requirement of many Terabytes (TB) -- millions of millions of bytes that need to be in memory at once to achieve productive speeds.

According to scientists at RSA Laboratories, the speed or the computational horsepower of a hardware device used to aid in the attack of the key is not the only issue.  Also important is the amount of computer memory required to process all the equations.  RSA researchers noted that while this device shortens part of the process, the overall impact on the security of the RSA public key algorithm also depends on the ability to process all the equations, which for adequate key sizes requires more memory than any computer has now or will have in the foreseeable future.  This is in addition to the length of time it would take to collect and process all the equations for adequate key sizes, even with special hardware. To RSA's knowledge, no one has yet successfully managed to handle these equations using massively parallel computation the way Shamir's device handles its part of the factoring problem.

RSA Laboratories published its key size recommendation in the summer of 1995 issue of CryptoBytes, RSA Laboratories' technical newsletter, which is available on RSA's Web site.  In this document, RSA Laboratories recommended that the minimum key length for protecting critical user data should be 768 bits; for enterprise data and enterprise certificate authorities, a minimum key length of of 1024 bits is recommended.  A technical summary about the practical impact of Shamir's result on the security of the RSA public key algorithm can also be found on RSA's Web site,

RSA Data Security, Inc

RSA Data Security, Inc., a wholly owned subsidiary of Security Dynamics Technologies, Inc. (NASDAQ: SDTI), is a leading supplier of software components that secure electronic data, with more than 400 million copies of RSA encryption and authentication technologies installed worldwide. RSA technologies are part of existing and proposed standards for the Internet and World Wide Web, ISO, ITU-T, ANSI, IEEE and are in use in business, financial and electronic commerce networks around the globe. RSA develops and markets platform-independent security components and related developer kits, and provides comprehensive cryptographic consulting services. RSA can be reached at