### 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^{3})
steps, and key generation takes O(k^{4}) 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.