Public-Key encryption: Knapsack algorithms.

Let us consider a Knapsack problem with N different items. The weights if the items are: W₁, W₂, W₃, ..., W_N. And their prices are the same as their weights. You can think of them as if you had a stock of golden bars of different sizes. We also have a total weight limit of S. So, the problem is to find coefficients b_i such that

Let's consider an example: we have 6 items with weights (and prices) set as: 1, 5, 6, 11, 14, 20, and 47. We also have a knapsack that can handle up to 69 pounds of load. We'll get the best amount if we take items with the weights 5, 6, 11, and 47.

Now, let me illustrate how we can use it to do the encryption. Assume we have a letter 'T' we would like to encrypt. The ASCII code for the letter is 84 which is 1010100 in binary. We will use the bits from the binary representation for the letter as the coefficients for the knapsack problem solution. Thus, the encryption for the letter 'T' would be:

If we know the key we encrypted the text width (the weights from the knapsack problem) we can certainly decrypt the text, but the problem is that the knapsack problem is so called NP-complete problem, which means that it cannot be solved for polynomial time. In other words, the only known algorithm provides us with exponentially growing time. This, in particular, means that adding one more item to the set of items doubles the time required for the algorithm to complete. Thus, is we take a set of about 250-300 items, then the time for decryption will take years and the price for the encrypted information will be zero by then.

This approach, though, has a big drawback: we know that bad goys have to spent a lot of time decrypting the message, but so do we. What can be done about it?

Super increasing Knapsack

If we have a super increasing sequence of weights, then we can solve the knapsack problem quite easily. Super increasing means that the weight of every next item is bigger than the sum of weights for all items in front on it. For example, the sequence 1, 3, 6, 13, 27, 52, 106 is a super increasing sequence. (3>1, 6>1+3, 13>1+3+6, etc). This kind of sequences give us a pretty simple problems to solve because we can apply the greedy algorithm and it will work, even if it doesn't for general knapsack problem.

If we use a super increasing sequence we run into another problem, though, if it's easy to decode for use it would be as easy for anybody else. What do we do about it?

Creating the Public and Private Keys

The solution to this is, we will create two sequences one would be a super increasing one (for private use) and another would be a normal knapsack sequence, which we will give away. These two sequences called the private and public keys. The only problem we need to solve is how to make these two sequences match each other. In other words, we would like to be able to use the private (easy) sequence to decrypt messages ciphered with the public (hard) sequence.

The following algorithm does the job:

1. We will need two numbers n and m: the number m (called modulus) should be bigger than the sum of all numbers in the sequence, and the number n (called multiplier) should not have any common factors with the modulus.
2. To create the public sequence from the private sequence, we need to multiply each number from the super increasing sequence by n and evaluate the residual if we divide the product by m. In other words, we need to compute W_i*n mod m

Now, if we have a message to encrypt, we use the public key to do it. That is, we make our public key available for every one, and if someone wants to send us a secret message he/she should use the public key we provided to cipher the text. Let's encrypt the message "My message":

Symbol	ASCII	Encryption process	Cipher text
M	77	59+137+123+164	483
y	121	59+177+144+137+164	681
	32	177	177
m	109	59+177+137+123+164	660
e	101	59+177+123+164	523
s	115	59+177+144+128+164	672
s	115	59+177+144+128+164	672
a	97	59+177+164	400
g	103	59+177+123+128+164	651
e	101	59+177+123+164	523

Once we received the cipher text we need to decrypt it. We definitely do not want to solve the hard knapsack problem, but in order to use our private key we first need to do some computations. We need to apply a process similar to the one we used to create a public key out of the private one to the message. We will use the same modulus m, but instead of the multiplier n we need to find a number reciprocal to the number n by modulus m. That is, we need to find a number k such that k*n mod m = 1. Number 89 is such a number for multiplier n=59. Thus, process of decoding will be:

Cipher text	Adjusted value	Process	Decoded (binary)	Decoded ASCII
483	147	= 1+13+27+106	1001101	77
681	129	= 1+3+6+13+106	1111001	121
177	3	= 3	0100000	32
660	150	= 1+3+13+27+106	1101101	109
523	137	= 1+3+27+106	1100101	101
672	168	= 1+3+6+52+106	1110011	115
672	168	= 1+3+6+52+106	1110011	115
400	110	= 1+3+106	1100001	97
651	189	= 1+3+27+52+106	1100111	103
523	137	= 1+3+27+106	1100101	101

Note that the process of solving knapsack problem on our end is much easier since we are using the super increasing sequence and as consequence the greedy algorithm.

If you want to implement this algorithm in practice, you need to use much longer knapsack sequence. Real knapsack should contain at least 250 items and the value for each item in the suseincreasing knapsack should be somewhere between 200 and 400 bits long, and the modulus should be somewhere between 100 and 200 bits long. Please note, though, that this algorith is not used in real life anymore because it turned out to have a weakness and can be broken. Please refer to Applied Cryptography by Bruce Schneier.