Merkle–Hellman Knapsack — Hiding Messages in a Backpack

1 2 3 4 5 6 7

difficulty levels — click green to claim

> MERKLE–HELLMAN KNAPSACK CIPHER

merkle difficulty: 4–7 field: public-key cryptography

The idea in plain English: Imagine you have a set of items with different weights. The subset sum problem asks: can you pick a subset of items that adds up to a specific target weight? For a general set, this is very hard (exponential time). But if you construct the weights in a special way (called a superincreasing sequence — each weight is bigger than the sum of all previous ones), the problem becomes trivial. This cipher converts each letter's ASCII code into a subset sum target, and you need to figure out which items were selected.

Why this really exists: Merkle-Hellman was one of the FIRST public-key cryptosystems ever invented (1978, right after RSA). It worked by having a "hidden" superincreasing sequence that the owner knew, and a "public" scrambled version that everyone else saw. While it was eventually broken (using lattice reduction), it's a beautiful example of how simple math problems can create powerful encryption. Modern lattice cryptography (like Kyber, the NIST post-quantum standard) is a direct intellectual descendant.

▸ Concrete Example

Superincreasing sequence: [2, 3, 6, 13, 27]. Target sum = 18.

Greedy algorithm (works because it's superincreasing):
Start from the heaviest weight (27): 27 > 18 → skip
13 ≤ 18 → take it. Remaining: 18-13 = 5
6 > 5 → skip
3 ≤ 5 → take it. Remaining: 5-3 = 2
2 ≤ 2 → take it. Remaining: 0 ✓

Selected: [2, 3, 13] (weights at positions 0, 1, 3)
Binary: 1 1 0 1 0 (1=taken, 0=not taken)
Binary 11010 = 26 → not a printable ASCII yet — the puzzle provides the mapping

Each ASCII character is encoded as a subset sum. The greedy algorithm (start from heaviest, take if it fits) efficiently solves the superincreasing case.

▸ How to Solve (Step by Step)

1. Get the knapsack weights and the target sums from puzzle data

2. For each target sum, use the greedy algorithm on the superincreasing sequence

3. Record which items are taken (1) or not (0) as a binary number

4. Convert binary to decimal → ASCII character

5. Join all characters → the answer word

def decode_subset_sum(weights, target):
  bits = [0] * len(weights)
  remaining = target
  for i in range(len(weights)-1, -1, -1):
    if weights[i] <= remaining:
      bits[i] = 1
      remaining -= weights[i]
  return int(''.join(str(b) for b in bits), 2)

word = ''.join(chr(decode_subset_sum(w, t)) for t in targets)

▸ Real-World Applications

First public-key crypto: The first system after RSA, proved the concept of knapsack-based encryption
Lattice reduction: Modern post-quantum crypto (Kyber) uses lattice math that grew from knapsack research
Supply chain: Real-world knapsack problems appear in logistics (which boxes fit in a truck)
Resource allocation: How to pick projects with limited budget — the knapsack problem

← Back to all ciphers