|Previous||Table of Contents||Next|
The Pohlig-Hellman algorithm is patented in the United States  and also in Canada. PKP licenses the patent, along with other public-key cryptography patents (see Section 25.5).
Rabins 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
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
Then choose an integer a = q(q-1 mod p) and a integer b = p(p-1 mod q). The four possible solutions are:
One of those four results, M1, M2, M3, or M4, equals M. If the message is English text, it should be easy to choose the correct Mi. 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 Mi is correct. One way to solve this problem is to add a known header to the message before encrypting.
Hugh Williams redefined Rabins schemes to eliminate these shortcomings . In his scheme, p and q are selected such that
Also, there is a small integer, S, such that J(S,N) = -1. (J is the Jacobi symbolsee Section 11.3). N and S are public. The secret key is k, such that
To encrypt a message M, compute c1 such that J(M,N) = (-1)c1. Then, compute M = (Sc1 * M) mod N. Like Rabins scheme, C = M2 mod N. And c2 = M mod 2. The final ciphertext message is the triple:
To decrypt C, the receiver computes M" using
The proper sign of M" is given by c2. Finally,
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 , 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].
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
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.
To sign a message, M, first choose a random number, k, such that k is relatively prime to p - 1. Then compute
and use the extended Euclidean algorithm to solve for b in the following equation:
The signature is the pair: a and b. The random value, k, must be kept secret.
To verify a signature, confirm that
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 Alices private key, x. If Eve ever gets two messages signed or encrypted using the same k, even if she doesnt 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
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
and use the extended Euclidean algorithm to solve for b:
|Previous||Table of Contents||Next|