Merkle–Hellman knapsack cryptosystem. 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.

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

Description
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  and an integer , find a subset of  which sums to . In general, this problem is known to be NP-complete. However, if  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 , which is actually a "disguised" version of . The private key also contains some "trapdoor" information that can be used to transform a hard knapsack problem using  into an easy knapsack problem using .

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.

Key generation
1. Choose a block size . Integers up to  bits in length can be encrypted with this key.

2. Choose a random superincreasing sequence of  positive integers

The superincreasing requirement means that , for .

3. Choose a random integer  such that
 

4. Choose a random integer  such that  (that is,  and  are coprime).

5. Calculate the sequence

where .

The public key is  and the private key is .

Encryption
Let  be an -bit message consisting of bits , with  the highest order bit. Select each  for which  is nonzero, and add them together. Equivalently, calculate
.
The ciphertext is .

Decryption
To decrypt a ciphertext , we must find the subset of  which sums to . We do this by transforming the problem into one of finding a subset of . That problem can be solved in polynomial time since  is superincreasing.

1. Calculate the modular inverse of  modulo  using the Extended Euclidean algorithm. The inverse will exist since  is coprime to .

The computation of  is independent of the message, and can be done just once when the private key is generated.

2. Calculate

3. Solve the subset sum problem for  using the superincreasing sequence , by the simple greedy algorithm described below. Let  be the resulting list of indexes of the elements of  which sum to . (That is, .)

4. Construct the message  with a 1 in each  bit position and a 0 in all other bit positions:

Solving the subset sum problem
This simple greedy algorithm finds the subset of a superincreasing sequence  which sums to , in polynomial time:

1. Initialize  to an empty list.

2. Find the largest element in  which is less than or equal to , say .

3. Subtract: .

4. Append  to the list .

5. Remove  from the superincreasing sequence 

6. If  is greater than zero, return to step 2.

Example

Key generation
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 :
.
Choose  to be coprime to : 
.

Construct the public key  by multiplying each element in  by  modulo :

Hence .

Encryption
Let the 8-bit message be . We multiply each bit by the corresponding number in  and add the results:
   0 * 295
 + 1 * 592
 + 1 * 301
 + 0 * 14
 + 0 * 28
 + 0 * 353
 + 0 * 120
 + 1 * 236
     = 1129
The ciphertext  is 1129.

Decryption
To decrypt 1129, first use the Extended Euclidean Algorithm to find the modular inverse of  mod :
. 

Compute . 

Use the greedy algorithm to decompose 372 into a sum of  values:

Thus , and the list of indexes is . The message can now be computed as
.

Cryptanalysis

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.  The attack analyzes the public key  and searches for a pair of numbers  and  such that  is a superincreasing sequence. The  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.

References

Public-key encryption schemes
Broken cryptography algorithms