problem 5 using the knapsack code let w17 m31 and a 124820

problem 5: using the knapsack code , let w=17, m=31, and a\' =(1,2,4,8,20) find a, the hard knapsack

Encoding

if someone wants to send you a binary message, they first break the message into blocks of length n where n=#of items in the knapsack and since a=(6,37,18,11,53,44) we have n=6

suppose the binary message =011000110101 101110

we then split this into 6 digits pieces as follows

011000 | 110101 | 101110

using a=(6,37,18,11,53,44) we get:

011000 is encodes as 37+18= 55

110101 is encodes as 6+37+11+44=98

101110 is encodes as 6+18+11+53=88

therefore the ciphertext is 55;98;88.

Solution

Public-Key cryptography was invented in the 1970s by Whitfield Diffie, Martin Hellman and Ralph Merkle.

Public-key cryptography needs two keys. One key tells you how to encrypt (or code) a message and this is \"public\" so anyone can use it. The other key allows you to decode (or decrypt) the message. This decryption code is kept secret (or private) so only the person who knows the key can decrypt the message. It is also possible for the person with the private key to encrypt a message with the private key, then anyone holding the public key can decrypt the message, although this seems to be of little use if you are trying to keep something secret!

The First General Public-Key Algorithm used what we call the Knapsack Algorithm. Although we now know that this algorithm is not secure we can use it to look at how these types of encryption mechanisms work.

The knapsack algorithm works like this:
Imagine you have a set of different weights which you can use to make any total weight that you need by adding combinations of any of these weights together.
Let us look at an example:
Imagine you had a set of weights 1, 6, 8, 15 and 24. To pack a knapsack weighing 30, you could use weights 1, 6, 8 and 15. It would not be possible to pack a knapsack that weighs 17 but this might not matter

The Superincreasing Knapsack Problem

An easy knapsack problem is one in which the weights are in a superincreasing sequence. A superincreasing sequence is one in which the next term of the sequence is greater than the sum of all preceding terms. For example, the set {1, 2, 4, 9, 20, 38} is superincreasing, but the set {1, 2, 3, 9, 10, 24} is not because 10 < 1+2+3+9.

It is easy to solve a superincreasing knapsack. Simply take the total weight of the knapsack and compare it with the largest weight in the sequence. If the total weight is less than the number, then it is not in the knapsack. If the total weight is greater then the number, it is in the knapsack. Subtract the number from the total, and compare with the next highest number. Keep working this way until the total reaches zero. If the total doesn\'t reach zero, then there is no solution.

So, for example, if you have a knapsack that weighs 23 that has been made from the weights of the superincreasing series {1, 2, 4, 9, 20, 38} then it does not contain the weight 38 (as 38 > 23)
but it does contain the weight 20; leaving 3;
which does not contain the weight 9 still leaving 3;
which does not contain the weight 4 still leaving 3;
which contains the weight 2, leaving 1; which contains the weight 1.
The binary code is therefore 110010.

It is much harder to decrypt a non-superincreasing knapsack problem. Give a friend a non-superincreasing knapsack and a total and see why this is the case.
One algorithm that uses a superincreasing knapsack for the private (easy) key and a non-superincreasing knapsack for the public key was created by Merkle and Hellman They did this by taking a superincreasing knapsack problem and converting it into a non-superincreasing one that could be made public, using modulus arithmetic.

Making the Public Key

To produce a normal knapsack sequence, take a superincreasing sequence; e.g. {1, 2, 4, 10, 20, 40}. Multiply all the values by a number, n, modulo m. The modulus should be a number greater than the sum of all the numbers in the sequence, for example, 110. The multiplier should have no factors in common with the modulus. So let\'s choose 31. The normal knapsack sequence would be:

1×31 mod(110) = 31
2×31 mod(110) = 62
4×31 mod(110) = 14
10×31 mod(110) = 90
20×31 mod(110) = 70
40×31 mod(110) = 30

So the public key is: {31, 62, 14, 90, 70, 30} and
the private key is {1, 2, 4, 10, 20.40}.

Let\'s try to send a message that is in binary code:
100100111100101110
The knapsack contains six weights so we need to split the message into groups of six:
100100
111100
101110
This corresponds to three sets of weights with totals as follows
100100 = 31 + 90 = 121
111100 = 31+62+14+90 = 197
101110 = 31+14+90+70 =205
So the coded message is 121 197 205.

Now the receiver has to decode the message...
The person decoding must know the two numbers 110 and 31 (the modulus and the multiplier). Let\'s call the modulus \"m\" and the number you multiply by \"n\".
We need n1, which is a multiplicative inverse of n mod m, i.e. n(n1) = 1 mod m

In this case I have calculated n1 to be 71.

All you then have to do is multiply each of the codes 71 mod 110 to find the total in the knapsack which contains {1, 2, 4, 10, 20, 40} and hence to decode the message.
The coded message is 121 197 205:

121×71 mod(110) = 11 = 100100
197×71 mod(110) = 17 = 111100
205×71 mod(110) = 35 = 101110

The decoded message is:
100100111100101110.