I’m not getting out of bed for a meeting" featuring: Rob Cowsill, Craig Lucas, Tom Woods and Dan Wray

What you need to know about…..

KNAPSACK ENCRYPTION

Knapsack encryption was the first practical public key encryption method.

The Merkle-Hellman knapsack encryption scheme was the first of these encryption schemes and, despite proposals for many other schemes since, most have been proven to be insecure.

The mathematical principles behind knapsack encryption have been the basis for numerous other encryption methods since, specifically those using a public-private key system (such as RSA). The understanding of the principles behind knapsack encryption help enormously with the understanding of other, more complex and more secure systems.

Knapsack encryption relies on the principles of a concept known as the subset-sum problem.

The problem is this:

Given a set of numbers, n, find a subset that sums to a given number, T.

An example:

Find a subset of {4, 8, 10, 13, 16} that adds up to 27.

An algorithm to find the subset does not exist in polynomial time so this problem is hard to solve without a non-deterministic Turing machine (and such things only exist in theory).

"I pity the fool who can only

solve the subset-sum problem

with a non-deterministic

turing machine"

Now consider the same problem except with a slightly different example:Find a subset of {1, 3, 6, 12, 25} that adds up to 19.

Notice that each number in this particular set is greater than the sum of all the numbers before it, this set is what we call super-increasing.

We can solve this problem linearly quite simply by starting at the end and working backwards:

25 obviously can't be in the subset because it's greater than 19.

• 12 must be in the set because, in this case, the numbers below can't possibly add up to 19 on their own so subtract the newly found 12 from the target (19 - 12 = 7). We now have to make 7 from the remaining numbers.
• 6 must be in the set because 1 and 3 can't add up to 7 on their own so subtract 6 from the target (7 - 6 = 1).
• 1 is obviously the remaining number missing.
• 12 + 6 + 1 = 19, we have found our solution, and in linear time. This particular variation on the problem was easy to solve because the original set was super-increasing.

"The subset-sum problem

can also be solved if our

original set is super-increasing"

First we have to choose a super-increasing knapsack (to use as the private key) with which to encrypt our data. To keep it simple, in my knapsack, I have objects of the following weights: {1, 7, 9, 18, 50, 86 }

Now I pick a modulus, m, which is bigger than the sum of all the elements. With my knapsack, the total weight is 171, so 175 would be a suitable value, so m=175.

I then pick a number, n, that is less than, and relatively prime to (that is, sharing no factors beside 1 with) m. I will take n=27.

I then multiply each element in my knapsack by n mod m. This gives me:

1* 27 mod 175 = 27

7 * 27 mod 175 = 14

9 * 27 mod 175 = 68

18 * 27 mod 175 = 136

50 * 27 mod 175 = 125

86 * 27 mod 175 = 47

This creates the knapsack { 27, 14, 68, 136, 125, 47 }. This will be our public key because, as the subset-sum problem demonstrates, solving this will be hard because it is not super-increasing.

Now we need something to encrypt. For example 01010101 11001100 00100101

First we break it up into blocks that are the length of our knapsack, so: 010101 011100 110000 100101

If we look at the first block (010101), there are 1’s in the second, fourth and sixth positions. This means that we take the second, fourth and sixth numbers in our public key, and add them together:

14+136+47 = 197

Repeating this for the other 3 blocks gives us:

011100 = 14 + 68 + 136 = 218

110000 = 27 + 14 = 41

100101 = 27 + 136 + 47 = 210

This gives us the encrypted version of 01010101 11001100 00100101 as {197, 218, 41, 210}. This encrypted data would then be transmitted to the recipient.

We know that the subset-sum problem is easy to solve using a super-increasing set and since our private key is super-increasing we can send them this along with m and n (as chosen earlier), to enable them to decrypt the message.

Decrypting the message is the same as solving the subset-sum problem with the original, decrypted message as our target. First we need to solve:

(x * 27) mod 175 = 1 so that we can move from the hard non-super-increasing set to the easy super-increasing set.

In this case, x = 13.

We can then do

(13 * 197) mod 175 = 111 to translate the target of the hard to solve problem to the target of the easy to solve problem. If we look at the private key ( {1, 7, 9, 18, 50, 86 } ), we can easily see that 111 is made up of 86 + 18 + 7. Since these correspond to the second, fourth and sixth values in the key, we can convert this to 010101. Repeating this with the other parts of the encrypted data will reveal the whole message.