3.6.8 What are some other public-key cryptosystems?
The ElGamal system [Elg85] is a public-key cryptosystem based on the discrete logarithm problem. It consists of both encryption and signature variants. The encryption algorithm is similar in nature to the Diffie-Hellman key agreement protocol (see Question 3.6.1).
The system parameters for the ElGamal cryptosystem are a prime p and an integer g, whose powers modulo p generate a large number of elements (it is not necessary for g to be a generator of the group Z*p; however, it is ideal). Alice has a private key a and a public key y, where y = ga mod p. Suppose Bob wishes to send a message m to Alice. Bob first generates a random number k less than p. He then computes
y1 = gk mod p and y2 = yk m mod p.
Bob sends (y1, y2) to Alice. Upon receiving the ciphertext, Alice computes y1-a y2 mod p. This is equal to m, because
y1-ay2 º g-ak yk m º y-k yk m º m mod p.
The ElGamal signature algorithm is similar to the encryption algorithm in that the public key and private key have the same form. However, encryption is not the same as signature verification, nor is decryption the same as signature creation as in the RSA system (see Question 3.1.1). DSA, The Digital Signature Algorithm (see Section 3.4), is based in part on the ElGamal signature algorithm.
Analysis based on the best available algorithms for both factoring and discrete logarithms show that the RSA system and the ElGamal system have similar security for equivalent key lengths. The main disadvantage of the ElGamal system is the need for randomness, and its slower speed (especially for signing). Another potential disadvantage of the ElGamal system is that message expansion by a factor of two takes place during encryption. However, such message expansion is generally unimportant if the cryptosystem is used only for exchange of secret keys.
The Merkle-Hellman knapsack cryptosystem [MH78] is a public-key cryptosystem first published in 1978. It is commonly referred to as the knapsack cryptosystem. It is based on the subset sum problem in combinatorics. The problem involves selecting a number of objects with given weights from a large set such that the sum of the weights is equal to a pre-specified weight. This is considered to be a difficult problem to solve in general, but certain special cases of the problem are relatively easy to solve, which serve as the ``trapdoor'' of the system. Shamir broke the single iteration knapsack cryptosystem introduced in 1978 [Sha84]. Merkle then published the multiple-iteration knapsack problem broken by Brickell [Bri85]. Merkle offered from his own pocket a $100 reward for anybody able to crack the single iteration knapsack and a $1000 reward for anybody able to crack the multiple iteration cipher. When they were cracked, he promptly paid up.
The Chor-Rivest knapsack cryptosystem was first published in 1984, followed by a revised version in 1988 [CR88]. It is the only knapsack-like cryptosystem that does not use modular multiplication. It was also the only knapsack-like cryptosystem that was secure for any extended period of time. Eventually, Schnorr and Hörner [SH95] developed an attack on the Chor-Rivest cryptosystem using improved lattice reduction which reduced to hours the amount of time needed to crack the cryptosystem for certain parameter values (though not for those recommended by Chor and Rivest). They also showed how the attack could be extended to attack Damgård's knapsack hash function [Dam90].
LUC is a public-key cryptosystem [SS95] developed by a group of researchers in Australia and New Zealand. The cipher implements the analogs of the ElGamal system (see Question 3.6.9), the Diffie-Hellman key agreement protocol (see Question 3.6.1), and the RSA system (see Section 3.1) over Lucas sequences. LUCELG is the Lucas sequence analog of ElGamal, while LUCDIF and LUCRSA are the Diffie-Hellman and RSA analogs, respectively. Lucas sequences used in the cryptosystem are the general second-order linear recurrence relation defined by
tn = ptn-1 - qtn-2,
where p and q are relatively prime integers. The encryption of the message is computed by iterating the recurrence, instead of by exponentiation as in the RSA system and the Diffie-Hellman protocol.
A paper by Bleichenbacher et al. [BBL95] shows that many of the supposed security advantages of LUC over cryptosystems based on modular exponentiation are either not present, or not as substantial as claimed.
The McEliece cryptosystem [Mce78] is a public-key encryption algorithm based on algebraic coding theory. The system uses a class of error-correcting codes known as the Goppa codes, for which fast decoding algorithms exist. The basic idea is to construct a Goppa code as the private key and disguise it as a general linear code, which is the public key. The general linear code cannot be easily decoded unless the corresponding private matrix is known. The McEliece cryptosystem has a number of drawbacks. These include large public key size (around half a megabit), substantial expansion of data, and possibly a certain similarity to the knapsack cryptosystem. Gabidulin, Paramonov, and Tretjakov [GPT91] proposed a modification of the McEliece cryptosystem by replacing Goppa codes with a different algebraic code and claimed the new version was more secure than the original system. However, Gibson [Gib93] later showed there was not really any advantage to the new version.