Cryptography General Interview Question:

How Fast is RSA?

Submitted by: Administrator

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( k3) steps, and key generation takes O(k4) 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.
Submitted by: Administrator