Cryptography: Theory and Practice:Other Public-key Cryptosystems

cryptography: theory and practice 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 Bob’s 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.

5.3 The Merkle-Hellman Knapsack System

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 1980’s, 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 ≤ jn. 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 ≤ ap - 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 1980’s, 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 Bob’s 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



Cryptography. Theory and Practice
Modern Cryptography: Theory and Practice
ISBN: 0130669431
EAN: 2147483647
Year: 1995
Pages: 133
Authors: Wenbo Mao

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net