Merkle-Hellman (MH) was one of the earliest public key cryptosystems invented by Ralph Merkle and Martin Hellman in 1978. 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.
Description
Key generation
To encrypt n-bit messages, choose a superincreasing sequence
- w = (w1, w2, ..., wn)
of n natural numbers (excluding zero). (A superincreasing sequence is a sequence in which every element is greater than the sum of all previous elements.) Pick a random integer q, such that q > wn, and a random integer r coprime to q. Now calculate the sequence
- β = (β1, β2, ..., βn)
where βi = rwi (mod q). The public key is β, while the private key is (w, q, r).
Encryption
To encrypt an n-bit message
- α = (α1, α2, ..., αn) ,
where αi is the i-th bit of the message, calculate
- .
The cryptogram then is c.
Decryption
Calculate s = r-1 (mod q), and c' = c*s (mod q). The super-increasing knapsack problem (w, c) can be solved in linear time.
References
- Ralph Merkle and Martin Hellman, Hiding Information and Signatures in Trapdoor Knapsacks, IEEE Trans. Information Theory, 24(5), September 1978, pp525–530.
- Adi Shamir, A Polynomial Time Algorithm for Breaking the Basic Merkle-Hellman Cryptosystem. CRYPTO 1982, pp279–288. (PDF)