Patents

The Pohlig-Hellman algorithm is patented in the United States [722] and also in Canada. PKP licenses the patent, along with other public-key cryptography patents (see Section 25.5).

19.5 Rabin

Rabin’s scheme [1283,1601] gets its security from the difficulty of finding square roots modulo a composite number. This problem is equivalent to factoring. Here is one implementation of this scheme.

First choose two primes, p and q, both congruent to 3 mod 4. These primes are the private key; the product n = pq is the public key.

To encrypt a message, M (M must be less than n), simply compute

C = M² mod n

Decrypting the message is just as easy, but slightly more annoying. Since the receiver knows p and q, he can solve the two congruences using the Chinese remainder theorem. Compute

m₁ = C^{(p + 1)/4} mod p

m₂ = (p - C^{(p+ 1)/4}) mod p

m₃ = C^{(q + 1)/4} mod q

m₄ = (q - C^{(q + 1)/4}) mod q

Then choose an integer a = q(q^-1 mod p) and a integer b = p(p^-1 mod q). The four possible solutions are:

M₁ = (am₁ + bm₃) mod n

M₂ = (am₁ + bm₄) mod n

M₃ = (am₂ + bm₃) mod n

M₄ = (am₂ + bm₄) mod n

One of those four results, M₁, M₂, M₃, or M₄, equals M. If the message is English text, it should be easy to choose the correct M_i. On the other hand, if the message is a random-bit stream (say, for key generation or a digital signature), there is no way to determine which M_i is correct. One way to solve this problem is to add a known header to the message before encrypting.

Williams

Hugh Williams redefined Rabin’s schemes to eliminate these shortcomings [1601]. In his scheme, p and q are selected such that

p ≡ 3 mod 8

q ≡ 7 mod 8

and

N = pq

Also, there is a small integer, S, such that J(S,N) = -1. (J is the Jacobi symbol—see Section 11.3). N and S are public. The secret key is k, such that

k = 1/2 * (1/4 * (p - 1) * (q - 1) + 1)

To encrypt a message M, compute c₁ such that J(M,N) = (-1)^c1. Then, compute M’ = (S^c1 * M) mod N. Like Rabin’s scheme, C = M’² mod N. And c₂ = M’ mod 2. The final ciphertext message is the triple:

(C, c₁, c₂)

To decrypt C, the receiver computes M" using

C^k ≡ ±M" (mod N)

The proper sign of M" is given by c₂. Finally,

M = (S^c1 * (-1)^c1 * M") mod N

Williams refined this scheme further in [1603, 1604, 1605]. Instead of squaring the plaintext message, cube it. The large primes must be congruent to 1 mod 3; otherwise the public and private keys are the same. Even better, there is only one unique decryption for each encryption.

Both Rabin and Williams have an advantage over RSA in that they are provably as secure as factoring. However, they are completely insecure against a chosen-ciphertext attack. If you are going to use these schemes in instances where an attacker can mount this attack (for example, as a digital signature algorithm where an attacker can choose messages to be signed), be sure to use a one-way hash function before signing. Rabin suggested another way of defeating this attack: Append a different random string to each message before hashing and signing. Unfortunately, once you add a one-way hash function to the system it is no longer provably as secure as factoring [628], although adding hashing cannot weaken the system in any practical sense.

Other Rabin variants are [972, 909, 696, 697, 1439, 989]. A two-dimensional variant is in [866, 889].

19.6 ElGamal

The ElGamal scheme [518,519] can be used for both digital signatures and encryption; it gets its security from the difficulty of calculating discrete logarithms in a finite field.

To generate a key pair, first choose a prime, p, and two random numbers, g and x, such that both g and x are less than p. Then calculate

y = g^x mod p

The public key is y, g, and p. Both g and p can be shared among a group of users. The private key is x.

ElGamal Signatures

To sign a message, M, first choose a random number, k, such that k is relatively prime to p - 1. Then compute

a = g^k mod p

and use the extended Euclidean algorithm to solve for b in the following equation:

M = (xa + kb) mod (p - 1)

The signature is the pair: a and b. The random value, k, must be kept secret.

To verify a signature, confirm that

y^aa^b mod p = g^M mod p

Each ElGamal signature or encryption requires a new value of k, and that value must be chosen randomly. If Eve ever recovers a k that Alice used, she can recover Alice’s private key, x. If Eve ever gets two messages signed or encrypted using the same k, even if she doesn’t know what it is, she can recover x.

This is summarized in Table 19.5.

For example, choose p = 11 and g = 2. Choose private key x = 8. Calculate

y = g^x mod p = 2⁸ mod 11 = 3

The public key is y = 3, g = 2, and p = 11.

To authenticate M = 5, first choose a random number k = 9. Confirm that gcd(9, 10) = 1. Compute

a = g^k mod p = 2⁹ mod 11 = 6

and use the extended Euclidean algorithm to solve for b:

M = (ax + kb) mod (p - 1)

5 = (8 * 6 + 9 * b) mod 10