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).