AAPPENDIX PPENDIX JJ KKNAPSACK NAPSACK PPUBLICUBLIC--KKEY EY AALGORITHMLGORITHM William Stallings Copyright 2010 J.1 THE KNAPSACK PROBLEM.........................................Error! Bookmark not defined. Supplement to Cryptography and Network Security, Fifth Edition William Stallings Prentice Hall 2010 ISBN-10: 0136097049 http://williamstallings.com/Crypto/Crypto5e.htmlJ-2 A number of algorithms have been proposed for public-key cryptography. Some of these, though initially promising, turned out to be breakable. It is instructive to review the most important such scheme. J.1 THE KNAPSACK PROBLEM The most famous of the fallen contenders is the trapdoor knapsack proposed by Ralph Merkle [MERK78]. The knapsack problem deals with determining which objects are in a container, such as a knapsack. A simple example is shown if Figure J.1. The knapsack is filled with a subset of the items shown, whose weights in grams are indicated. Given the weight of the filled knapsack, 1156 grams, the problem is to determine which of the items are contained in the knapsack. (The scale is calibrated to deduct the weight of the empty knapsack.) As an exercise, the reader is encouraged to determine the contents of the knapsack by trail-and-error calculation. The problem illustrated in Figure J.1 is relatively simple but generally becomes computationally formidable when there are, say, 100 items rather than the 10 of this example. Merkle's contribution was to show (1) how to turn the knapsack problem into a scheme for encryption and decryption, and (2) how to incorporate trapdoor information that would enable a person to quickly solve the knapsack problem. J.2 THE KNAPSACK CRYPTOSYSTEM First, let us state the general approach for encryption/decryption using the knapsack problem. Suppose we wish to send messages in blocks of n bits. Then, define: cargo vector a = (a1, a2, …, an) ai integer plaintext message block x = (x1, x2, …, xn) xi binary corresponding ciphertext ! S = a • x = ai" xi( )i=1n#J-3 Consider the cargo vector a to be a list of potential elements to be put in the knapsack, with each vector element in a equal to the weight of the corresponding cargo element. And consider the plaintext message block x to be a selection of elements from the cargo vector, with xi = 1 for each cargo element ai that is selected for inclusion in the knapsack. Thus each unique plaintext message block corresponds to a unique selection of items from the cargo vector. The vector product S is simply the sum of the selected items, which is the weight of the knapsack. For encryption, a is the public key. If Bob wishes to send a confidential message x to Alice, Bob encrypts the message using Alice's public key a. Bob performs S = a • x and transmits S. For decryption, the Alice must recover x, given S and a. This public-key scheme must satisfy two requirements. The first requirement is that there be a unique inverse for each value of S. For example, consider the following: a = (1, 3, 2, 5) S = 3 This problem has two solutions: x = 1010 and x = 0100. Thus, the elements of a must be chosen such that each combination of elements yields a unique value. The second requirement is that decryption is hard in general but easy if special knowledge is available. (In the preceding example, the special knowledge would function as Alice's private key.) Certainly, for large values of n, the knapsack problem is hard in general. But, under special circumstances, the problem is easy to solve. Suppose we impose the condition that each element of a is larger than the sum of the preceding elements: ! ai> ajj=1i"1#1 < i $ n (J.1) This is known as a superincreasing vector. In this case, the solution is easy. For example, consider the vector a' = (171, 197, 459, 1191, 2410)J-4 which satisfies inequality (J.1). Suppose we have S' = a' • x' = 3798. Because 3798 > 2410, a5 must be included (x5 = 1), because without a5 the other elements cannot contribute enough to add up to 3798. Now consider 3798 – 2410 = 1388. Because 1388 > 1191, a4 must also be included (x4 = 1). Continuing in this fashion, we find that x3 = 0, x2 = 1, and x1 = 0. Thus, in this example, given the public key a' and the encrypted message S', it is possible to decrypt the message without access to a private key. What Merkle did was find a way to tie an easy superincreasing knapsack problem to a difficult general knapsack problem. Suppose we choose at random an easy superincreasing knapsack vector ! " a =" a 1," a 2,…" a n( ), with n elements. Also select two integers m and w, such that m is greater than the sum of the elements of a' and w is relatively prime to m. That is: ! m >" a i1=1n# gcd(w, m) = 1 Now, we construct a hard knapsack vector a by multiplying the easy vector a' by w, modulo m: a = wa' mod m The vector a will, in general, not be superincreasing and can therefore be used to construct hard knapsack problems. However, knowledge of w and m enables the conversions of this hard knapsack problem to an easy one. To see this, first observe that because w and m are relatively prime, there exists a unique multiplicative inverse w–1, modulo m. Therefore, w–1a ! a' (mod m) We are now ready to define the knapsack scheme. The ingredients are the following:J-5 a', a superincreasing vector (private, chosen) m, an integer larger than ! " a i1=1n# (private, chosen) w, an integer relatively prime to m (private, chosen) w–1, the inverse of w, modulo m (private, calculated) a, equal to wa'mod m (public, calculated) The private key consists of the triple (w–1, m, a'). The public key is a. Suppose that Alice has published her public key a and that Bob wishes to send the message x to Alice. Bob calculates the sum: S = a • x The determination of x given S and a is difficult, so this is a secure transmission. On receipt, Alice is able to decrypt easily. Define S' = w–1S mod m. We have: S = a • x = wa' • x S' = w–1S mod m S' = w–1wa' • x mod m S' = a' • x Therefore, we have converted the hard problem of finding x given S and a to the easy problem of finding x given S' and a'. The knapsack algorithm was hailed as an unbreakable system. Merkle, confident though not rich, offered a reward of $100 to anyone who could break it. It took four years, but Adi Shamir, one of the inventors of RSA, broke the system and collected the $100 [SHAM82].