Merkle-Hellman (MH) was one of the earliest public key cryptosystems. Although its ideas are elegant, and far simpler than RSA, it has been broken. MH is based on the subset sum problem (a special case of the knapsack problem): given a list of numbers and a third number, which is the sum of a subset of these numbers, determine the subset. In general, this problem is known to be NP-hard; however, there are some 'easy' instances which can be solved efficiently. The Merkle-Hellman is based on transforming an easy instance into a difficult instance, and back again. It was broken by Shamir, not by attacking the knapsack problem, but rather by breaking the conversion from an easy knapsack to a hard one. The algorithm is as follows:
KEY GENERATION - To encrypt n-bit messages, choose a superincreasing sequence
- w = (w1, w2, ..., wn)
- β = (β1, β2, ..., βn)
ENCRYPTION - To encrypt an n-bit message
- α = (α1, α2, ..., αn) ,
- .
DECRYPTION - Calculate s = r-1 (mod q), and c' = c*s (mod q). The knapsack problem (w, c') can be solved in linear time.