Pack Your Knapsack For Some Secret Messages — Difficult to Pack/Easy to Unpack

RSA is just one way of doing public key encryption. Knapsack is a good alternative where we can create a public key and a private one:

The knapsack problem defines a problem where we have a number of weights and then must pack our knapsack with the minimum number of weights that will make it a given weight. In general, the problem is:

• Given a set of numbers A and a number b.
• Find a subset of A which sums to b (or gets nearest to it).

So imagine you have a set of weights of 1, 4, 6, 8 and 15, and we want to get a weight of 28, we could thus use 1, 4, 8 and 15 (1+4+8+15=28).

So our code would become 11011 (represented by ‘1’, ‘4’, no ‘6’, ‘8’ and ‘15’).

Then if our plain text is 11011, with a knapsack of 1, 4, 6, 8, 15, we have a cipher text of 1+4+8+15 which gives us 28.

A plain text of 00001 will give us a cipher text of 15.

With public key cryptography, we have two knapsack problems. One of which is easy to solve (private key), and the other difficult (public key).