The Merkle-Hellman Knapsack Cipher

In this cipher-implementation of the knapsack problem, the public key is a hard knapsack, and the private key is an easy superincreasing knapsack along with two numbers, a multiplier and a modulus. The multiplier and modulus of the private key is used to convert the hard knapsacks subset (which corresponds to the goal weight) into the subset of the easy knapsack, and can therefore be decrypted with the greedy algorithm.

In order to encrypt with the public key, the plaintext is converted into a long string of binaries and then sliced up so they’re as long as the key. A 1 in the plaintext corresponds to the element of the public key at that position, the result is a subset of elements which are then added together as the encrypted message. In order to decrypt we use our multiplier and modulus to convert it into an easy problem and can use the greedy algorithm to gain the plaintext.