The Merkle-Hellman Knapsack Cryptosystem

The Merkle-Hellman Knapsack Cryptosystem

Introduction

Imagine a list of numbers and a target sum. Your job is to find which numbers add up to the target. If the list is chosen cleverly, this is trivial. If the list looks random, it is believed to be very hard. The Merkle-Hellman knapsack cryptosystem builds a public key from this contrast. The private key is an easy list, and the public key is the same list in disguise.

It was one of the first public-key cryptosystems, and it is now a standard example of a scheme that was broken. Its story is useful for two reasons. It shows how a trapdoor can be built from a hard problem. It also shows that a problem can be hard in general, while the special instances that a scheme actually uses are easy. This guide covers the scheme and a real attack, with the attack running on a key of 16 bits and on keys of up to 100 bits.

Table of Contents

• History and Standards
• Superincreasing Sequences
• Key Generation
• Encryption
• Decryption
• Interactive Visualizer
• A Worked Example
• Breaking It with Lattice Reduction
• Python Implementation
• Security Status
• FAQ
• References

History and Standards

Ralph Merkle and Martin Hellman published the cryptosystem in 1978, in a paper titled “Hiding Information and Signatures in Trapdoor Knapsacks”. Whitfield Diffie and Martin Hellman had introduced the idea of public-key cryptography in 1976. RSA came in 1977, and Merkle-Hellman in 1978, so it is among the earliest examples.

The scheme did not last. Adi Shamir presented a polynomial-time attack in 1982, and the journal version appeared in 1984. According to Wikipedia, the cryptosystem is now considered insecure. It was never a standard, and it is not used. It remains in textbooks as a warning, and the attacks that broke it are still studied.

Superincreasing Sequences

The subset sum problem, also called the knapsack problem in this form, is this: given a list of integers and a target c, find a subset of the list that adds up to c. The problem is NP-complete in general, which means that no fast algorithm is known for the hardest instances.

A sequence W = (w1, w2, ..., wn) is superincreasing when every number is larger than the sum of all the numbers before it. For example, 2, 7, 11, 21, 42, 89, 180, 354 is superincreasing, because 7 is larger than 2, 11 is larger than 2 + 7, 21 is larger than 2 + 7 + 11, and so on. For such a sequence, the subset sum problem is easy. Look at the largest number. If it is not larger than the target, it must be in the subset, because the numbers before it cannot reach the target without it. Subtract it and repeat. This greedy method takes n steps.

Key Generation

Choose a block size n, so that messages of n bits can be encrypted, and follow these four steps:

1. Choose a superincreasing sequence W of n positive integers. This is the easy list.
2. Choose a modulus q that is larger than the sum of all numbers in W.
3. Choose a multiplier r between 1 and q - 1 that has no common factor with q.
4. Compute the public key B = (b1, ..., bn), where bi = r * wi mod q.

The private key is (W, q, r). The public key is B. Multiplying by r modulo q scrambles the list, so that B no longer looks superincreasing. The two keys are not interchangeable: the private key cannot be used for encryption.

Encryption

Write the message as n bits, m1 m2 ... mn, with the highest bit first. The ciphertext is the sum of the public numbers whose bits are 1:

c = m1 * b1 + m2 * b2 + ... + mn * bn

Anyone can compute this. To decrypt, an attacker would have to solve a subset sum problem for the list B, which looks like a hard one.

Decryption

The receiver knows r and q, so the receiver can turn the hard problem back into the easy one. Compute the inverse r' of r modulo q, which exists because r has no common factor with q. The ciphertext is then multiplied by it:

c' = c * r' mod q

Why does this give the easy problem? Each bi is r * wi mod q, so the sum c equals r times the sum of the chosen wi, modulo q. Multiplying by r' cancels the r, so c' is the sum of the chosen wi, modulo q. Because q is larger than the sum of all of W, that sum is already smaller than q, so c' is exactly the sum of the chosen numbers. The receiver now solves a subset sum problem for the superincreasing sequence W with the greedy method, and the chosen positions are the bits of the message.

Interactive Visualizer

The visualizer above runs these exact steps, with small numbers. The first variant takes a superincreasing list W, the numbers q and r, and a message of one bit for each number of W. It shows every number of the public key, every step of the encryption, the inverse of r, and every step of the greedy decryption. The second variant breaks a ciphertext without the private key. Enter a public key and a ciphertext, and click the button. The log shows the density of the knapsack, the lattice, the LLL reduction, the short vector that it finds, and the check that the bits add up to the ciphertext.

A Worked Example

This is the example that the Wikipedia article uses. The private list is W = (2, 7, 11, 21, 42, 89, 180, 354). Its sum is 706, so the modulus q = 881 is large enough. The multiplier is r = 588.

The public key. Each public number is r * wi mod q:

(2 * 588) mod 881 = 295
(7 * 588) mod 881 = 592
(11 * 588) mod 881 = 301
(21 * 588) mod 881 = 14
(42 * 588) mod 881 = 28
(89 * 588) mod 881 = 353
(180 * 588) mod 881 = 120
(354 * 588) mod 881 = 236

The public key is therefore B = (295, 592, 301, 14, 28, 353, 120, 236).

Encryption. The message is the byte 97, which is 01100001 in binary. The bits that are 1 select b2, b3, b8, and the ciphertext is 592 + 301 + 236 = 1129.

Decryption. The inverse of r modulo q is r' = 442, because 588 * 442 mod 881 = 1. The next number is c' = 1129 * 442 mod 881 = 372. The greedy method works from the largest number down:

w8 = 354 fits, 372 - 354 = 18
w7 = 180 is too big
w6 = 89 is too big
w5 = 42 is too big
w4 = 21 is too big
w3 = 11 fits, 18 - 11 = 7
w2 = 7 fits, 7 - 7 = 0
w1 = 2 is too big

The chosen positions are 2, 3, and 8, which gives the bits 01100001. This is the original message. All 256 possible messages give 256 different ciphertexts for this key, so decryption is always unambiguous.

Breaking It with Lattice Reduction

A lattice is the set of all integer combinations of some basis vectors. The LLL algorithm of Lenstra, Lenstra, and Lovasz takes a basis and returns a new basis of the same lattice, with short and nearly perpendicular vectors. It runs in polynomial time. A basis is LLL-reduced when two conditions hold. Each vector is nearly perpendicular to the ones before it, which is called size-reduction, with every Gram-Schmidt coefficient at most 1/2 in absolute value. And each vector is not much shorter than the one before it after the Gram-Schmidt step, which is the Lovasz condition with the parameter 3/4.

In 1985, Lagarias and Odlyzko showed how to turn a subset sum problem into a short vector problem. Coster and others improved the method. For the public key B and the ciphertext c, build a lattice with n + 1 rows of n + 1 numbers. To keep every number a whole number, the version in this guide doubles the coordinates:

row i  = (0, ..., 0, 2, 0, ..., 0, 2 * N * b_i)     for i = 1 to n   (the 2 is in place i)
last   = (1, 1, ..., 1, 2 * N * c)

N is a small whole number. Now take the message bits x_i. The sum of x_i times row i, minus the last row, has the entries 2 * x_i - 1 in the first n places. In the last place it has 2 * N * (sum of x_i * b_i - c), which is 0, because the message adds up to the ciphertext. So the lattice contains a vector with entries +1 and -1, and a 0 at the end. Its length is only the square root of n. Other lattice vectors are usually much longer, because of the large last coordinate. When the knapsack has a low density, which is n / log2(max b), this short vector is the shortest one by a wide margin, and LLL finds it.

The method has known limits on the density. According to the introduction of the 2025 paper of Bi and others, the original method of Lagarias and Odlyzko works only when the density is below 0.6463, and the improvement by Coster and others raised the limit to 0.9408. For densities close to 1, no efficient lattice method is known. Merkle-Hellman keys have a low density. For keys chosen as in the code of this guide, it is about 0.5, and that is why the attack works.

An attack on a 16-bit key. The private key has W = (4184, 29717, 54165, 131948, 284587, 565665, 1134137, 2205870, 4433755, 8885316, 17744422, 35501136, 71020899, 141999381, 284019710, 568051008), q = 1136071353, and r = 1087465132. The public key, with density 0.53, is:

1124414876, 651691559, 657435789, 765210530, 106178401, 360883341, 612666695, 1364811, 115988833, 435977526, 168949396, 443761938, 948313650, 521126409, 759067598, 624565983

The message is 1010100110111001, and the ciphertext is 4190973677. The attacker knows only B and c. The lattice has 17 rows, with N = 6. LLL needs 235 swaps of two rows. Among the reduced rows there is one with a last entry of 0 and all other entries +1 or -1:

-1 +1 -1 +1 -1 +1 +1 -1 -1 +1 -1 -1 -1 +1 +1 -1

Changing all signs and mapping +1 to the bit 1 and -1 to the bit 0 gives 1010100110111001, which is the message. The bits that are 1 select numbers of B that add up to 4190973677, which is the ciphertext. The attack worked on the first setting.

Larger keys. The attack was run on random Merkle-Hellman keys of several sizes, with 20 random messages for each size. It tries up to three settings of the LLL parameter and of N, and it stops at the first success. The times are for a single message in pure Python on the machine that built this page:

Message bits n	Messages recovered	Time per message
16	20 of 20	0.00 s
32	20 of 20	0.01 s
48	20 of 20	0.04 s
64	20 of 20	0.08 s
80	18 of 20	0.35 s
100	16 of 20	0.62 s

Not every message is recovered for the larger sizes. This basic version of the attack uses only the standard LLL algorithm with a few settings, and it loses reliability as n grows. A likely reason is that LLL finds only an approximation of the shortest vector, but I did not test this. I also did not try stronger reduction methods such as BKZ. The point is that a key with 100 bits falls in less than a second. For contrast, the same code was run on random knapsacks with a density of about 1. The result was: n = 40: 10 of 10 failed; n = 60: 10 of 10 failed; n = 80: 10 of 10 failed.

Shamir’s attack and later work. Shamir’s attack of 1982 is different. It does not look at a ciphertext. It analyses the public key alone and finds numbers u and m such that u * bi mod m is a superincreasing sequence. This pair works as a private key, even if it differs from the real one. According to Wikipedia, this attack works in polynomial time even if the numbers of the public key are shuffled. Shuffling is a step that the usual description of the cryptosystem leaves out, and the code of this guide does not shuffle. In 2025, Bi and others presented an improved attack that uses the LLL algorithm on a lattice of small dimension and recovers the plaintext in less than one second on a laptop for typical parameters.

Python Implementation

This is a complete Merkle-Hellman cryptosystem, with the lattice attack. The first file is the cryptosystem and the attack. The second file is the LLL algorithm, in the integral form of Cohen, which uses only whole numbers, so there is no rounding error.

# mh.py
#
# The Merkle-Hellman knapsack cryptosystem (1978), and a lattice attack on it.
# The private key is a superincreasing sequence W, a modulus q that is larger
# than the sum of W, and a multiplier r that has no common factor with q. The
# public key is B = (r * w_i mod q). A message is a string of n bits, and its
# ciphertext is the sum of the b_i for the bits that are 1. The attack is the
# lattice method of Lagarias and Odlyzko, in the form of Coster, Joux,
# LaMacchia, Odlyzko, Schnorr and Stern, with the LLL algorithm of lll.py.

import math
import random
from math import gcd

from lll import lll_reduce


def is_superincreasing(w):
    total = 0
    for x in w:
        if x <= total:
            return False
        total += x
    return True


def check_private_key(w, q, r):
    if not w or not is_superincreasing(w):
        raise ValueError("W must be superincreasing: every number is larger than the sum of the ones before it")
    if q <= sum(w):
        raise ValueError("q must be larger than the sum of W")
    if not 1 <= r < q or gcd(r, q) != 1:
        raise ValueError("r must be between 1 and q - 1, with no common factor with q")


def public_key(w, q, r):
    check_private_key(w, q, r)
    return [r * x % q for x in w]


def random_private_key(n, rng):
    """A random key for n-bit messages: a superincreasing W, a q above its sum, and an r coprime to q.

    Keys made this way have a density of about 0.5, which is the range where the lattice attack works.
    """
    w, total = [], 0
    for _ in range(n):
        x = total + rng.randrange(1, 2**n)
        w.append(x)
        total += x
    q = total + rng.randrange(1, 2**n)
    r = rng.randrange(2, q - 1)
    while gcd(r, q) != 1:
        r = rng.randrange(2, q - 1)
    return w, q, r


def bits_of(m, n):
    """The n bits of m, highest bit first."""
    return [(m >> (n - 1 - i)) & 1 for i in range(n)]


def encrypt(bits, b):
    if len(bits) != len(b) or any(x not in (0, 1) for x in bits):
        raise ValueError("the message must be one bit for each number of the public key")
    return sum(x * y for x, y in zip(bits, b))


def decrypt(c, w, q, r, trace=None):
    """The bits of the message. c' = c / r mod q is a sum of some w_i, which the greedy method finds."""
    r_inv = pow(r, -1, q)
    cp = c * r_inv % q
    bits = [0] * len(w)
    rest = cp
    for i in range(len(w) - 1, -1, -1):
        if w[i] <= rest:
            bits[i] = 1
            rest -= w[i]
    if rest != 0:
        raise ValueError("the ciphertext is not a sum of numbers of the public key")
    if trace is not None:
        trace.update({"r_inv": r_inv, "cp": cp})
    return bits


def density(b):
    return len(b) / math.log2(max(b))


def lattice_attack(b, c, settings=((3, 4, 2), (99, 100, 2), (99, 100, 6))):
    """Recover the bits of a message from the public key and the ciphertext, without the private key.

    Lattice (all numbers doubled so that they are whole): n rows (2 e_i, 2 N b_i), and a last row
    (1, ..., 1, 2 N c). The message gives a short vector with entries +1 or -1 and last entry 0.
    Each setting is (delta numerator, delta denominator, extra for N); the next one is tried when
    the vector is not found. Returns (bits or None, the reduced basis, the number of swaps, settings used).
    """
    n = len(b)
    swaps_total = 0
    reduced = []
    for used, (num, den, extra) in enumerate(settings, 1):
        big_n = math.isqrt(n) + extra
        basis = []
        for i in range(n):
            row = [0] * (n + 1)
            row[i] = 2
            row[n] = 2 * big_n * b[i]
            basis.append(row)
        basis.append([1] * n + [2 * big_n * c])
        reduced, swaps = lll_reduce(basis, num, den)
        swaps_total += swaps
        for row in reduced:
            if row[n] == 0 and all(abs(x) == 1 for x in row[:n]):
                for sign in (1, -1):
                    bits = [(sign * x + 1) // 2 for x in row[:n]]
                    if encrypt(bits, b) == c:
                        return bits, reduced, swaps_total, used
    return None, reduced, swaps_total, len(settings)


if __name__ == "__main__":
    # the example of the Wikipedia article
    w = [2, 7, 11, 21, 42, 89, 180, 354]
    q, r = 881, 588
    b = public_key(w, q, r)
    bits = bits_of(97, 8)
    c = encrypt(bits, b)
    print("Public key B: " + ", ".join(str(x) for x in b))
    print("Message 97 = " + "".join(str(x) for x in bits) + ", ciphertext " + str(c))
    print("Decrypted: " + "".join(str(x) for x in decrypt(c, w, q, r)))
    # a larger key, and the lattice attack, which does not use the private key
    rng = random.Random(1978)
    n = 32
    w, q, r = random_private_key(n, rng)
    b = public_key(w, q, r)
    message = rng.getrandbits(n)
    c = encrypt(bits_of(message, n), b)
    found, _, swaps, used = lattice_attack(b, c)
    print("n = %d, density %.2f: attack %s after %d swaps" % (n, density(b), "recovered the message" if found == bits_of(message, n) else "failed", swaps))

# lll.py
#
# The LLL lattice basis reduction algorithm of Lenstra, Lenstra and Lovasz,
# in the integral form of Cohen (Algorithm 2.6.7 of "A Course in
# Computational Algebraic Number Theory"). All numbers are whole numbers, so
# there is no rounding error. The basis is a list of rows of integers.


def dot(a, b):
    return sum(x * y for x, y in zip(a, b))


def lll_reduce(basis, delta_num=3, delta_den=4):
    """Return an LLL-reduced copy of the basis (parameter 3/4 by default) and the number of swaps."""
    b = [list(row) for row in basis]
    n = len(b)
    if n == 0:
        return b, 0
    swaps = 0
    # d[i] = the product of the squared Gram-Schmidt norms of the first i vectors (d[0] = 1)
    d = [1] + [0] * n
    lam = [[0] * n for _ in range(n)]  # lam[i][j] for j < i: the integer d[j+1] * mu[i][j]
    d[1] = dot(b[0], b[0])
    k, kmax = 1, 0

    def reduce(k, l):
        # make |mu[k][l]| <= 1/2
        if 2 * abs(lam[k][l]) > d[l + 1]:
            q = (2 * lam[k][l] + d[l + 1]) // (2 * d[l + 1])
            b[k] = [x - q * y for x, y in zip(b[k], b[l])]
            lam[k][l] -= q * d[l + 1]
            for i in range(l):
                lam[k][i] -= q * lam[l][i]

    def swap(k):
        nonlocal swaps
        swaps += 1
        b[k], b[k - 1] = b[k - 1], b[k]
        for j in range(k - 1):
            lam[k][j], lam[k - 1][j] = lam[k - 1][j], lam[k][j]
        lmb = lam[k][k - 1]
        big_b = (d[k - 1] * d[k + 1] + lmb * lmb) // d[k]
        for i in range(k + 1, kmax + 1):
            t = lam[i][k]
            lam[i][k] = (d[k + 1] * lam[i][k - 1] - lmb * t) // d[k]
            lam[i][k - 1] = (big_b * t + lmb * lam[i][k]) // d[k + 1]
        d[k] = big_b

    while k < n:
        if k > kmax:
            kmax = k
            for j in range(k + 1):
                u = dot(b[k], b[j])
                for i in range(j):
                    u = (d[i + 1] * u - lam[k][i] * lam[j][i]) // d[i]
                if j < k:
                    lam[k][j] = u
                else:
                    d[k + 1] = u
                    if u == 0:
                        raise ValueError("the vectors are linearly dependent")
        reduce(k, k - 1)
        # Lovasz condition: |b*_k|^2 >= (delta - mu^2) |b*_(k-1)|^2, in integers
        if delta_den * d[k + 1] * d[k - 1] < delta_num * d[k] * d[k] - delta_den * lam[k][k - 1] ** 2:
            swap(k)
            k = max(1, k - 1)
        else:
            for l in range(k - 2, -1, -1):
                reduce(k, l)
            k += 1
    return b, swaps

Running the first file produces this output:

Public key B: 295, 592, 301, 14, 28, 353, 120, 236
Message 97 = 01100001, ciphertext 1129
Decrypted: 01100001
n = 32, density 0.52: attack recovered the message after 493 swaps

I checked this code in several ways before writing it up. It reproduces every number of the example in the Wikipedia article: the public key, the ciphertext 1129, the inverse 442, and c' equal to 372. For that key, all 256 messages decrypt, with 256 different ciphertexts. Random keys of 8 to 100 bits encrypt and decrypt correctly. The LLL code was checked with an independent test that uses exact fractions. On 33 random bases of 2 to 12 dimensions, every output was size-reduced, satisfied the Lovasz condition, had the same volume, and spanned the same lattice as the input. The attack was run on random keys, and each recovered message was checked against the ciphertext. Merkle-Hellman has no official test vectors, so these are mathematical checks, and the Wikipedia example is the only published one.

Security Status

The Merkle-Hellman cryptosystem is broken. Shamir’s polynomial-time attack finds an equivalent private key from the public key alone. Lattice methods recover a message from the public key and the ciphertext when the knapsack has low density, and Merkle-Hellman knapsacks have low density. The 2025 work of Bi and others shows that the attack remains practical on a laptop.

The lesson is that the NP-completeness of the subset sum problem does not protect a scheme. NP-completeness is about the worst case, and the keys of this scheme are special instances that are not hard. A scheme is only as strong as the problem that the attacker actually has to solve.

Lattice-based cryptosystems also rest on lattice problems, but they use those problems on purpose, with parameters chosen so that the best known algorithms, including LLL and its improvements, fail. Lattices appear in post-quantum standards today, and lattice reduction is also the main tool for attacking them.

FAQ

Why must the sequence be superincreasing?

It makes the private problem easy. With a superincreasing list, the greedy method finds the unique subset in n steps. It also guarantees that each message has its own ciphertext, so decryption has one answer.

Why must q be larger than the sum of W?

Otherwise the sum of the chosen wi could be as large as q or more, and then c' would be that sum modulo q, which loses information. With q larger than the sum, c' is exactly the sum, and the greedy method works.

What is the density of a knapsack?

It is the number of items divided by the size of the largest item in bits, n / log2(max b). A low density means that few subsets share a sum, so the right subset is easy to single out with lattice methods. For the keys of this guide, the density is about 0.5.

Can Merkle-Hellman be used for signatures?

It cannot be used directly. The Wikipedia article explains that the private key cannot be used for encryption, so the system does not give signatures in the way RSA does. Shamir published a signature variant in a 1978 technical memorandum of MIT, titled “A Fast Signature Scheme”.

Is subset sum still a good basis for cryptography?

For worst-case instances, the problem is hard. But a scheme must give the attacker a typical instance of the scheme, and those have so far been easy. Lattice-based cryptography is the modern way of using hard lattice problems with careful parameters.

References

1. Merkle, Ralph C. and Hellman, Martin E. “Hiding Information and Signatures in Trapdoor Knapsacks.” IEEE Transactions on Information Theory 24(5), 1978, pages 525 to 530.

2. Shamir, A. “A Polynomial-Time Algorithm for Breaking the Basic Merkle-Hellman Cryptosystem.” IEEE Transactions on Information Theory 30(5), 1984, pages 699 to 704. Presented at FOCS 1982.

3. Lagarias, Jeffrey C. and Odlyzko, Andrew M. “Solving Low-Density Subset Sum Problems.” Journal of the ACM 32(1), 1985, pages 229 to 246.

4. Bi, J., Su, L., Peng, H., and Wang, L. “A simple and efficient attack on the Merkle-Hellman knapsack cryptosystem.” PLoS One 20(5), 2025. Available at: https://doi.org/10.1371/journal.pone.0322726

5. Lenstra, Arjen K., Lenstra, Hendrik W., and Lovasz, Laszlo. “Factoring Polynomials with Rational Coefficients.” Mathematische Annalen 261, 1982, pages 515 to 534.

6. Cohen, H. “A Course in Computational Algebraic Number Theory.” Springer, 1993, Algorithm 2.6.7.

7. Shamir, Adi. “A Fast Signature Scheme.” MIT Laboratory for Computer Science, Technical Memorandum TM-107, July 1978.

8. Wikipedia. “Merkle-Hellman knapsack cryptosystem.” Available at: https://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsack_cryptosystem