The Merkle–Hellman knapsack cryptosystem was one of the earliest public key cryptosystems. 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.

The concept of public key cryptography was introduced by Whitfield Diffie and Martin Hellman in 1976. 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.

Merkle–Hellman is a public key cryptosystem, meaning that two keys are used, a public key for encryption and a private key for decryption. It is based on the subset sum problem (a special case of the knapsack problem). The problem is as follows: given a set of integers ${\displaystyle A}$ and an integer ${\displaystyle c}$, find a subset of ${\displaystyle A}$ which sums to ${\displaystyle c}$. In general, this problem is known to be NP-complete. However, if ${\displaystyle A}$ 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 ${\displaystyle W}$, and the public key contains a non-superincreasing list of numbers ${\displaystyle B}$, which is actually a "disguised" version of ${\displaystyle W}$. The private key also contains some "trapdoor" information that can be used to transform a hard knapsack problem using ${\displaystyle B}$ into an easy knapsack problem using ${\displaystyle W}$.

Unlike some other public key cryptosystems such as RSA, the two keys in Merkle-Hellman are not interchangeable; the private key cannot be used for encryption. Thus Merkle-Hellman is not directly usable for authentication by cryptographic signing, although Shamir published a variant that can be used for signing.

1. Choose a block size ${\displaystyle n}$. Integers up to ${\displaystyle n}$ bits in length can be encrypted with this key.

2. Choose a random superincreasing sequence of ${\displaystyle n}$ positive integers

3. Choose a random integer ${\displaystyle q}$ such that