Merkle-Hellman

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. The Merkle-Hellman system 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-complete; however, there are some 'easy' instances which can be solved efficiently. The Merkle-Hellman scheme is based on transforming an easy instance into a difficult instance, and back again. However, the scheme was broken by Adi Shamir, not by attacking the knapsack problem, but rather by breaking the conversion from an easy knapsack to a hard one.

Contents

1 Description 1.1 Key generation 1.2 Encryption 1.3 Decryption 2 References

Description

Key generation

To encrypt n-bit messages, choose a superincreasing sequence

w = (w₁, w₂, ..., w_n)

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, eg {1, 2, 4, 8, 16} ) Pick a random integer q, such that

q ≥<math>\sum_{i = 1}^n w_i<math>,

and a random integer, r, such that gcd(r,q) == 1.

q must be chosen as such to ensure the uniqueness of the encrypted message, after modular arithmatic. If it is any smaller, more than one message (in plaintext) will encrypt to the same cryptotext, making decoding functionally impossible. r must be coprime to q or else it will not have an inverse mod q. The existence of the inverse of r is necessary so that decryption is possible.

Now calculate the sequence

β = (β₁, β₂, ..., β_n)

where β_i = rw_i (mod q). The public key is β, while the private key is (w, q, r).

Encryption

To encrypt an n-bit message

α = (α₁, α₂, ..., α_n),

where α_i is the i-th bit of the message and α_i <math> \boldsymbol{\in}<math> {0, 1}, calculate

<math>c = \sum_{i = 1}^n \alpha_i \beta_i<math>.

The cryptogram then is c.

Decryption

The key to decryption lies in somehow determining s = r^-1 (mod q). s is the private key in this cryptosystem. You can now convert the NP-hard problem, extrapolating α from c (using an essentially randomly-filled knapsack), into the easy problem of extrapolating α using a super-increasing knapsack, which is solvable in linear time.

The steps of decryption require that you calculate c' = c*s (mod q) and w = β*s (mod q).

c' is still an encrypted form of α, but the knapsack which encrypts it is simply the super-increasing sequence, w. The super-increasing knapsack problem is easy to solve because of the structure of a super-increasing sequence. Take the largest element in w, say w_k. If w_k > c', then α_k = 0, if w_k≤c', then α_k = 1. Then, subtract w_k * α_k from c', and repeat these steps until you have figured out α.

When q is very large, it is very difficult to calculate s (it can take a long time, but the algorithm merely makes use of simple modular multiplication). The difficulty of determining s is why this was thought to be such an impossible cryptosystem to break.

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 (http://dsns.csie.nctu.edu.tw/research/crypto/HTML/PDF/C82/279.PDF))de:Merkle-Hellman-Kryptosystem