knapsack algorithm (thing)

Merkle-Hellman's Knapsack algorithm is based on the NP-class "knapsack" problem, in which a series of items with different weights are put into a knapsack capable of holding a certain weight S. As an example, take the objects of weight 1, 4, 6, 11, 17, and 29 where the S can be equal to 11 (1+4+6, or just 11) and not 13. The time necessary to solve this problem increases exponentially as the number of items increase, as the only conventional method being exhaustive search, and is easily solvable with 5 objects but not 1000.

To encrypt text which such a method, begin by converting a message into a string of binary numbers, five bits per number, starting with A=00000, B=00001, C=0010 (in base ten, A=0, B=1, C=2...). In relation to the knapsack problem, indicates the absence of one of the items, 1 the presence. Such an alphabet will have 32 (binary: 11111) characters. Now in binary, the string will be broken into n bits, making a block x={x₁, x₂, ... x_n}. Take public key a ={a₁, a₂, a₃ ... a_n} (the weights of the pile of objects), and take the dot product of x and a, which means multiplying object x₁ by a₁, adding this to x₂*a₂, resulting in C=a₁x₁ + a₂x₂+...+ a_nx_n.

The public-key a can be developed from the concept of the knapsack problem. In all cases but one, the weights used to equal S can only be determined by exhaustive search. The solvable situation is the case of superincreasing weights, where each successive value in the key is more than all the previous values added together. Such a case of solvability is called a trapdoor, and does not occur in all NP problems. For example, the values adding to S=70 out of the set {2,3,6,13,27}, are all smaller than S minus the previous values, starting from the largest number. All the numbers without 27 cannot add to 30, so 27 is an object in the sack, leaving 3 pounds left for the sack and therefore necessarily discluding 27, 13, 6, 2, but not 3. To convert this superincreasing sack into a normal, less solvable knapsack, multiply all the numbers in the sequence by a value k, then mod m, where k has no common factors with the sack values and m is greater than the largest value. Have k=31 and m=56, making the first value in the knapsack (2*31) mod 56, or 6. In this fashion, the knapsack set, or a, is {6,37,18,11,53}.

Modular arithmetic obfuscates information further by destroying the appearance of pattern, in this case, the superincreasing nature of the set. The value of integer x mod integer y is the remainder left when y divides x. This function also limits the largest value under the modulus to y.

Now with the public key a={6,37,18,11,53}, the blocks 10101 01110 01000 00011 ('void', in binary) can be encrypted. The first block, the dot product equals 6*1 + 37*0 + 1*18 + 0*11 + 1*53, or 77. In this fashion, the others equal 66, 37, 64. The ciphertext, C = {77,66,37,64}. The receiver of this text knows the original superincreasing sack, as well as k and m, and from this can determine the modular inverse of k; this value multiplied by k equals 1 mod m. In other words, 31 times a value that produces 56 times a constant, plus 1. In this case, inverse k is 47. The ciphertext is now multiplied by 47 mod 56, which produces the set {35,22,3,40}, and with the superincreasing knapsack set {2,3,6,13,27} 35 has respectively a 2, 6, and 27, which in binary is 10101. Similarly, the rest is decoded to the original 10101 01110 01000 00011, from there, back to VOID.