3.1.2 How fast is the RSA algorithm?
An "RSA operation," whether encrypting, decrypting, signing, or verifying is essentially a modular exponentiation. This computation is performed by a series of modular multiplications.
In practical applications, it is common to choose a small public exponent for the public key. In fact, entire groups of users can use the same public exponent, each with a different modulus. (There are some restrictions on the prime factors of the modulus when the public exponent is fixed.) This makes encryption faster than decryption and verification faster than signing. With the typical modular exponentiation algorithms used to implement the RSA algorithm, public key operations take O(k2) steps, private key operations take O(k3) steps, and key generation takes O(k4) steps, where k is the number of bits in the modulus. ``Fast multiplication'' techniques, such as methods based on the Fast Fourier Transform (FFT), require asymptotically fewer steps. In practice, however, they are not as common due to their greater software complexity and the fact that they may actually be slower for typical key sizes.
The speed and efficiency of the many commercially available software and hardware implementations of the RSA algorithm are increasing rapidly; see http://www.rsasecurity.com/ for the latest figures.
By comparison, DES (see Section 3.2) and other block ciphers are much faster than the RSA algorithm. DES is generally at least 100 times as fast in software and between 1,000 and 10,000 times as fast in hardware, depending on the implementation. Implementations of the RSA algorithm will probably narrow the gap a bit in coming years, due to high demand, but block ciphers will get faster as well.
For a detailed report on high-speed RSA algorithm implementations, see [Koç94].