How Fast is RSA?

An "RSA operation," whether for encrypting or decrypting, signing or verifying, is essentially a modular exponentiation, which can be 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 typical modular exponentiation algorithms, public-key operations take O(k2) steps, private-key operations take O( k³) steps, and key generation takes O(k⁴) steps, where k is the number of bits in the modulus. ( O-notation refers to the upper bound on the asymptotic running time of an algorithm.) "Fast multiplication" techniques, such as FFT-based methods, require asymptotically fewer steps, though in practice they are not as common due to their great software complexity and the fact that they may actually be slower for typical key sizes.

There are many commercially available software and hardware implementations of RSA, and there are frequent announcements of newer and faster chips. On a 90 MHz Pentium, RSA Data Security's cryptographic toolkit BSAFE 3.0 (see Question 173) has a throughput for private-key operations of 21.6 Kbits per second with a 512-bit modulus and 7.4 Kbits per second with a 1024-bit modulus. The fastest RSA hardware [SV93] has a throughput greater than 300 Kbits per second with a 512-bit modulus, implying that it performs over 500 RSA private-key operations per second. (There is room in that hardware to execute two RSA 512-bit RSA operations in parallel [Sha95], hence the 600 Kbits/s speed reported in [SV93]. For 970-bit keys, the throughput is 185 Kbits/s.) It is expected that RSA speeds will reach 1 Mbits/second within a year or so.

By comparison, DES is much faster than RSA. In software, DES is generally at least 100 times as fast as RSA. In hardware, DES is between 1,000 and 10,000 times as fast, depending on the implementation. Implementations of RSA will probably narrow the gap a bit in coming years, as there are growing commercial markets, but DES will get faster as well.