4.5.3 Merkle-Hellman Cryptosystem

In 1976 W. Diffie and M. Hellman introduced the concept of public-key cryptography. Two years later R. Merkle and M. Hellman published a cryptosystem based on the subset sum problem [MH78]. At that time it was the only alternative cryptosystem to the existing RSA-Cryptosystem.

As described in the chapter about subset sum problems there are knapsack vectors such that a problem (A, s) is easily and efficiently solvable, for example superincreasing knapsacks. On the other hand it may be extremely difficult to get a solution for (A, s) if A is not superincreasing.
Merkle and Hellman used this fact to construct a cryptosystem based on the subset sum problem. Starting with a superincreasing knapsack vector A, a second knapsack vector B is built hiding the superincreasing property of A. The knapsack A is part of the private key whereas the knapsack B forms the public key. A message p then is encrypted by computing the sum c = pB = b₁p₁ + ... + b_np_n, with p_i representing the i-th bit of p.
Anyone being in possession of the cipher c is faced with the difficult problem (B, c). The owner of the private key however can easily determine the original message p because he knows the secret superincreasing sequence A.

Now the Merkle-Hellman Cryptosystem is explained in detail.

Key creation

A parameter n is fixed specifying the number of components in A and B respectively. Also n determines the size of the message to be encrypted.
Choose a superincreasing set A = (a₁, ..., a_n)
Choose an integer M with M > SUM_i=1...n(a_i). M is called the modulus.
Choose a mulitplier W such that gcd(M, W) = 1 and 1 <= W < M
This choice of W guarantees an inverse element U: UW = 1 (mod M)
optional: choose a permutation pi: {1,..., n} -> {1, ..., n}
To get the components b_i of the public key B, perform
b_i = a_pi(i)W mod M, i = 1 ... n

modular multiplication

B represents the public key whereas the tuple (A, M, W) is the private key.

Encryption

The length of a message to be encrypted is fixed by the parameter n. Prior to encryption, a possibly larger message p has to be divided into n-bit groups.
Let p = (p₁, p₂, ..., p_n) the message to be encrypted. The ciphertext c is obtained by computing
c = b₁p₁ + b₂p₂ + ... + b_np_n

Decryption

First compute c' = Uc mod M = W^-1c mod M
Now solve (A, c'). Because A is superincreasing, (A, c') is easily solvable. Let X = (x₁, ..., x_n) be the resulting vector. If no permutation was used, p_i = x_i and p = (p₁, ..., p_n) is the plaintext.
If a permutation was used to construct the public key, reverse the permutation: the plain bits p_i are p_i = x_pi(i)

To be a correct cryptosystem, encryption of a plaintext p followed by decryption must yield p, that is d(e(p)) = p, with d the decryption function and e the encryption function respectively.
Indeed,

c' = Uc mod M = W^-1c mod M = W^-1(pB) mod M = W^-1W(pA) mod M = pA mod M

Because both c' < M as well as SUM (a_i) < M, c' = pA = a₁p₁ + ... + a_np_n. With solving (A, c') and, if used, reversing the permutation pi the original plaintext p is received.

Start applet

Remarks

For key creation Merkle and Hellman specified as lower bounds for n, M and A

n = 100: the knapsack vectors A and B both have 100 elements
a₁ should have a bit length of 100: |a₁| = 100
|a_i| = 100 + i - 1
|M| = 202
Using this values, the resulting cipher c has a bit length of 209. A plaintext p of length 100 expands to a cipher having 209 bits, therefore the data expansion is 2.09.

In 1983 A. Shamir published an algorithm breaking the basic Merkle-Hellman Cryptosystem [SH83]. Shamir described a method of finding a so-called trapdoor-pair (M', U'). Using this trapdoor pair together with the public key B, a valid private key might be created, decrypting every messge encrypted with B.
Another attack against the Merkle-Hellman cryptosystem uses a tool called lattice base reduction. With this tool, a given ciphertext c can be decrypted to yield the plaintext p without having the corresponding private key.

Low Dense Knapsacks