It was published by Ralph Merkle and Martin Hellman in 1978.
A polynomial time attack was published by Adi Shamir in 1984.
As a result, the cryptosystem is now considered insecure.
[1]: 465 [2]: 190 The concept of public key cryptography was introduced by Whitfield Diffie and Martin Hellman in 1976.
[3] At that time they proposed the general concept of a "trap-door one-way function", a function whose inverse is computationally infeasible to calculate without some secret "trap-door information"; but they had not yet found a practical example of such a function.
Several specific public-key cryptosystems were then proposed by other researchers over the next few years, such as RSA in 1977 and Merkle-Hellman in 1978.
is superincreasing, meaning that each element of the set is greater than the sum of all the numbers in the set lesser than it, the problem is "easy" and solvable in polynomial time with a simple greedy algorithm.
In Merkle–Hellman, decrypting a message requires solving an apparently "hard" knapsack problem.
The private key contains a superincreasing list of numbers
, and the public key contains a non-superincreasing list of numbers
The private key also contains some "trapdoor" information that can be used to transform a hard knapsack problem using
Thus Merkle-Hellman is not directly usable for authentication by cryptographic signing, although Shamir published a variant that can be used for signing.
bits in length can be encrypted with this key.
Choose a random superincreasing sequence of
Calculate the sequence The public key is
We do this by transforming the problem into one of finding a subset of
That problem can be solved in polynomial time since
Solve the subset sum problem for
be the resulting list of indexes of the elements of
bit position and a 0 in all other bit positions: This simple greedy algorithm finds the subset of a superincreasing sequence
, in polynomial time: Create a key to encrypt 8-bit numbers by creating a random superincreasing sequence of 8 values: The sum of these is 706, so select a larger value for
To decrypt 1129, first use the Extended Euclidean Algorithm to find the modular inverse of
Use the greedy algorithm to decompose 372 into a sum of
The message can now be computed as In 1984 Adi Shamir published an attack on the Merkle-Hellman cryptosystem which can decrypt encrypted messages in polynomial time without using the private key.
[7] The attack analyzes the public key
pair found by the attack may not be equal to
in the private key, but like that pair it can be used to transform a hard knapsack problem using
into an easy problem using a superincreasing sequence.
The attack operates solely on the public key; no access to encrypted messages is necessary.
Shamir's attack on the Merkle-Hellman cryptosystem works in polynomial time even if the numbers in the public key are randomly shuffled, a step which is usually not included in the description of the cryptosystem, but can be helpful against some more primitive attacks.