Cryptography: Theory and Practice by Douglas Stinson CRC Press, CRC Press LLC ISBN: 0849385210 Pub Date: 03/17/95 |
Previous | Table of Contents | Next |
A more efficient variation has been found by Menezes and Vanstone. In this variation, the elliptic curve is used for masking, and plaintexts and ciphertexts are allowed to be arbitrary ordered pairs of (nonzero) field elements (i.e., they are not required to be points on E). This yields a message expansion factor of two, the same as in the original ElGamal Cryptosystem. The Menezes-Vanstone Cryptosystem is presented in Figure 5.10.
If we return to the curve y2 = x3 + x + 6 over , we see that the Menezes-Vanstone Cryptosystem allows 10 × 10 = 100 plaintexts, as compared to 13 in the original system. We illustrate encryption and decryption in this system using this same curve.
Example 5.9
As in the previous example, suppose that α = (2, 7) and Bobs secret exponent is a = 7, so
Suppose Alice wants to encrypt the plaintext
(note that x is not a point on E), and she chooses the random value k = 6. First, she computes
and
so c1 = 8 and c2 =3.
Next, she calculates
and
Figure 5.10 Menezes-Vanstone Elliptic Curve Cryptosystem
The ciphertext she sends to Bob is
When Bob receives the ciphertext y, he first computes
and then
Figure 5.11 Subset summ problem
Hence, the decryption yields thee correct plaintext.
The well-known Merkle-Hellman Knapsack Cryptosytem was first described by Merkle and Hellman in 1978. Although this cryptosystem, and several variants of it, were broken in the early 1980s, it is still worth studying for its conceptual elegance and for the underlying design technique.
The term knapsack is actually a misnomer2.; the system is based on the Subset Sum problem which is presented in Figure 5.11.
2The Knapsack problem, as it is usually defined, is a problem involving selecting objects with given weights and profits in such a way that a specified capacity is not exceeded and a specified target profit is attained
The Subset Sum problem, as phrased in Figure 5.11, is a decision problem (i.e., we are required only to answer yes or no). If we rephrase the problem slightly, so that in any instance where the answer is "yes" we are required to find the desired vector x (which may not be unique), then we have a search problem.
Figure 5.12 Algorithm for solving a superincreasing instance of the subset sum problem
The Subset Sum (decision) problem is one of the so-called NP-complete problems. Among other things, this means that there is no known polynomial-time algorithm that solves it. This is also the case for the Subset Sum search problem. But even if a problem has no polynomial-time algorithm to solve it in general, this does not rule out the possibility that certain special cases can be solved in polynomial time. This is indeed the situation with the Subset Sum problem.
We define a list of sizes, (s1, . . . , sn) to be superincreasing if
for 2 ≤ j ≤ n. If the list of sizes is superincreasing, then the search version of the Subset Sum problem can be solved very easily in time O(n), and a solution x (if it exists) must be unique. The algorithm to do this is presented in Figure 5.12.
Suppose s = (s1, . . . , sn) is superincreasing, and consider the function
defined by the rule
Is es a possible candidate for an encryption rule? Since s is superincreasing, es is an injection, and the algorithm presented in Figure 5.12 would be the corresponding decryption algorithm. However, such a system would be completely insecure since anyone (including Oscar) can decrypt a message that is encrypted in this way.
The strategy therefore is to transform the list of sizes in such a way that it is no longer superincreasing. Bob will be able to apply an inverse transformation to restore the superincreasing list of sizes. On the other hand Oscar, who does not know the transformation that was applied, is faced with what looks like a general, apparently difficult, instance of the subset sum problem when he tries to decrypt a ciphertext.
One suitable type of transformation is a modular transformation. That is, a prime modulus p is chosen such that
as well as a multiplier a, where 1 ≤ a ≤ p - 1. Then we define
1 ≤ i ≤ n. The list of sizes t = (t1,...,tn) will be the public key used for encryption. The values a, p used to define the modular transformation are secret. The complete description of the Merkle-Hellman Knapsack Cryptosystem is given in Figure 5.13.
The following small example illustrates the encryption and decryption operations in the Merkle-Hellman Cryptosystem.
Example 5.10
Suppose
is the secret superincreasing list of sizes. Suppose p = 2003 and a = 1289. Then the public list of sizes is
Now, if Alice wants to encrypt the plaintext x = (1, 0, 1, 1, 0, 0, 1, 1, 1), she computes
When Bob receives the ciphertext y, he first computes
Then Bob solves the instance I = (s, z) of the Subset Sum problem using the algorithm presented in Figure 5.12. The plaintext (1, 0, 1, 1, 0, 0, 1, 1, 1) is obtained.
Figure 5.13 Merkle-Hellman Knapsack Cryptosystem
By the early 1980s, the Merkle-Hellman Knapsack Cryptosystem had been broken by Shamir. Shamir was able to use an integer programming algorithm of Lenstra to break the system. This allows Bobs trapdoor (or an equivalent trapdoor) to be discovered by Oscar, the cryptanalyst. Then Oscar can decrypt messages exactly as Bob does.
Previous | Table of Contents | Next |
Copyright © CRC Press LLC