What are the Alternatives to RSA?

Many other public-key cryptosystems have been proposed, as a look through the proceedings of the annual Crypto, Eurocrypt, and Asiacrypt conferences quickly reveals. Some of the public-key cryptosystems will be discussed in Question 24 through Question 44.

A mathematical problem called the knapsack problem was the basis for several systems (see Question 32), but these have lost favor because several versions were broken. Another system, designed by ElGamal (see Question 29), is based on the discrete logarithm problem. The ElGamal system was, in part, the basis for several later signature methods, including one by Schnorr [Sch90], which in turn was the basis for DSS, the Digital Signature Standard (see Question 26).The ElGamal system has been used successfully in applications; it is slower for encryption and verification than RSA and its signatures are larger than RSA signatures.

In 1976, before RSA, Diffie and Hellman proposed a system for key exchange only (see Question 24); it permits secure exchange of keys in an otherwise conventional secret-key system. This system is in use today.

Cryptosystems based on mathematical operations on elliptic curves have also been proposed (see Question 31), as have cryptosystems based on discrete exponentiation in the finite field GF(2ⁿ ). The latter are very fast in hardware. There are also some probabilistic encryption methods (see Question 36), which have the attraction of being resistant to a guessed ciphertext attack (see Question 10), but with possible data expansion.

For digital signatures, Rabin (see Question 37) proposed a system which is provably equivalent to factoring; this is an advantage over RSA, where one may still have a lingering worry about an attack unrelated to factoring. Rabin's method is susceptible to a chosen message attack, however, in which the attacker tricks the user into signing messages of a special form. Another signature scheme, by Fiat and Shamir [FS87], is based on interactive zero-knowledge protocols (see Question 107), but can be adapted for signatures. It is faster than RSA and is provably equivalent to factoring, but the signatures are much larger than RSA signatures. Other variations, however, lessen the necessary signature length; see [BDB92] for references. A system is "equivalent to factoring" if recovering the private key is provably as hard as factoring; forgery may be easier than factoring in some of the systems.

Advantages of RSA over other public-key cryptosystems include the fact that it can be used for both encryption and authentication, and that it has been around for many years and has successfully withstood much scrutiny. RSA has received far more attention, study, and actual use than any other public-key cryptosystem, and thus RSA has more empirical evidence of its security than more recent and less scrutinized systems. In fact, a large number of public-key cryptosystems which at first appeared secure were later broken; see [BO88] for some case histories.