The Merkle–Hellman knapsack cryptosystem was one of the earliest public key cryptosystems invented by Ralph Merkle and Martin Hellman in 1978.^{[1]} Although its ideas are elegant, and far simpler than RSA, it has been broken.^{[2]}
Contents
Description
MerkleHellman is an asymmetrickey cryptosystem, meaning that for communication, two keys are required: a public key and a private key. Furthermore, unlike RSA, it is oneway  the public key is used only for encryption, and the private key is used only for decryption. Thus it is unusable for authentication by cryptographic signing.
The MerkleHellman system is based on the subset sum problem (a special case of the knapsack problem). The problem is as follows: given a set of numbers A and a number b, find a subset of A, which sums to b. In general, this problem is known to be NPcomplete. However, if the set of numbers (called the knapsack) is superincreasing — that is, each element of the set is greater than the sum of all the numbers before it — the problem is 'easy' and solvable in polynomial time with a simple greedy algorithm.
Key generation
In MerkleHellman, the keys are knapsacks. The public key is a 'hard' knapsack, and the private key is an 'easy', or superincreasing, knapsack, combined with two additional numbers, a multiplier and a modulus, which were used to convert the superincreasing knapsack into the hard knapsack. These same numbers are used to transform the sum of the subset of the hard knapsack into the sum of the subset of the easy knapsack, which is solvable in polynomial time.
Encryption
To encrypt a message, a subset of the hard knapsack is chosen by comparing it with a set of bits (the plaintext), equal in length to the key, and making each term in the public key that corresponds to a 1 in the plaintext an element of the subset, while ignoring the terms corresponding to 0 terms in the plaintext. The elements of this subset are added together, and the resulting sum is the ciphertext.
Decryption
Decryption is possible because the multiplier and modulus used to transform the easy, superincreasing knapsack into the public key can also be used to transform the number representing the ciphertext into the sum of the corresponding elements of the superincreasing knapsack. Then, using a simple greedy algorithm, the easy knapsack can be solved using O(n) arithmetic operations, which decrypts the message.
Full article ▸
