Offensive Security Researcher & Quantum Cryptography Analyst

Merkle-Hellman Knapsack Algorithm: Working, Explanation, and Cryptanalysis

Abdul Wahab Junaid
Merkle-Hellman algorithm and working of this algorithm

Merkle-Hellman algorithm and working of this algorithm

I consider the Merkle-Hellman knapsack cryptosystem to be one of the founding constructions of public-key cryptography, published in the same period as RSA and built on a completely different hard problem — the subset-sum (knapsack) problem — rather than integer factorization. I find studying it valuable not because it is still secure (it is not; it was broken in 1982), but because it teaches me the fundamental “trapdoor” design pattern that recurs throughout cryptography: take an easy version of a hard problem, disguise it using a transformation only the key-holder can undo, and publish the disguised version as the public key.

History and Background

I trace the Merkle-Hellman cryptosystem to Ralph Merkle and Martin Hellman’s 1978 paper, “Hiding Information and Signatures in Trapdoor Knapsacks,” published shortly after Hellman’s earlier collaboration with Whitfield Diffie introduced the concept of public-key cryptography itself in 1976. At the time, Merkle-Hellman was seen as an exciting, computationally efficient alternative to RSA, since its encryption and decryption relied only on additions and simple modular arithmetic rather than expensive modular exponentiation. That excitement was short-lived: in 1982, Adi Shamir published a polynomial-time attack showing that the basic single-iteration Merkle-Hellman scheme could be broken without solving the underlying general subset-sum problem at all, by directly recovering an equivalent trapdoor from the public key. Later work using the LLL lattice-basis-reduction algorithm (Lenstra, Lenstra, Lovász, 1982) further generalized attacks against knapsack cryptosystems, including multi-iteration variants of Merkle-Hellman. I see this history as an important lesson: an NP-hard problem in general does not guarantee that a specific instance-generation method used to build a cryptosystem is itself secure.

Problem Statement

I want a public-key encryption scheme based on the subset-sum problem: given a set of positive integers and a target sum, determine which subset sums to that target. This problem is NP-hard in general. I want to construct a private version that is efficiently solvable (a superincreasing sequence, letting me use a simple greedy algorithm) and disguise it, using modular multiplication, into a public sequence that appears to be a generic, hard subset-sum instance to anyone without the private key.

Core Concepts

How It Works

I break the algorithm into key generation, encryption, and decryption:

  1. Key generation: Choose a superincreasing sequence $b_1, \dots, b_n$, typically by picking $b_1$ randomly and setting each subsequent term to slightly more than double the running sum (e.g., $b_i = 2\sum_{j<i} b_j + 1$ or similar), guaranteeing the superincreasing property.
  2. Choose a modulus $M$ strictly greater than $\sum_{i=1}^n b_i$.
  3. Choose a multiplier $W$ such that $\gcd(W, M) = 1$, so $W^{-1} \bmod M$ exists.
  4. Compute the public sequence: $a_i = (W b_i) \bmod M$ for each $i$.
  5. Publish $(a_1, \dots, a_n)$ as the public key; keep $(b_1, \dots, b_n, W, M)$ private.
  6. Encryption: Represent the plaintext as an $n$-bit vector $x_1, \dots, x_n$, and compute the ciphertext $c = \sum_{i=1}^n x_i a_i$.
  7. Decryption: Compute $c’ = W^{-1} c \bmod M$, which equals $\sum_i x_i b_i$ (since this sum is guaranteed to be less than $M$).
  8. Solve the resulting superincreasing subset-sum problem greedily to recover the original bits.

Working Principle

I understand the core mechanism as identical in spirit to the general knapsack cryptosystem family: modular multiplication by $W$ acts as a “scrambling” transformation that destroys the ordering relationships that make the private sequence easy to solve. To anyone without $W^{-1}$ and $M$, the public sequence $a_i$ looks like an arbitrary set of numbers with no special structure, and finding a subset summing to a given ciphertext appears to require solving a generally NP-hard subset-sum instance. The legitimate receiver, holding the private trapdoor, can reverse the modular scaling in constant “one-shot” arithmetic and then exploit the superincreasing structure to solve the now-easy version instantly. Shamir’s attack works precisely because this specific way of disguising the knapsack (a single modular multiplication of a superincreasing sequence) leaves detectable structural fingerprints, letting an attacker efficiently search for values behaving like $W$ and $M$ without ever needing the receiver’s actual private key.

Mathematical Foundation

I define the superincreasing private sequence with the recurrence:

$$ b_i > \sum_{j=1}^{i-1} b_j \quad \text{for all } i $$

I select:

$$ M > \sum_{i=1}^{n} b_i, \qquad \gcd(W, M) = 1 $$

The public key is:

$$ a_i = (W \cdot b_i) \bmod M $$

Encryption computes:

$$ c = \sum_{i=1}^{n} x_i a_i \pmod{\text{no reduction needed if design is correct}} $$

Decryption reverses the scaling:

$$ c’ = W^{-1} c \bmod M $$

Since $c = \sum_i x_i a_i \equiv \sum_i x_i W b_i \equiv W \sum_i x_i b_i \pmod M$, multiplying by $W^{-1}$ gives:

$$ c’ \equiv \sum_{i=1}^n x_i b_i \pmod M $$

And because $\sum_i x_i b_i < M$ by the choice of $M$, this congruence is in fact an equality:

$$ c’ = \sum_{i=1}^n x_i b_i $$

which I solve greedily using the superincreasing property, checking $b_n, b_{n-1}, \dots, b_1$ in turn. Shamir’s attack exploits the fact that for many valid choices of $(W’, M’)$ other than the true $(W, M)$, the transformation $a_i \mapsto (W’)^{-1} a_i \bmod M’$ still yields a superincreasing-looking sequence, letting an attacker search a structured space (using the theory of simultaneous Diophantine approximation) for a working “equivalent trapdoor” without brute-forcing the subset-sum problem itself.

Diagrams

flowchart TD
    K1[Generate superincreasing sequence b_i] --> K2[Choose M greater than sum of b_i]
    K2 --> K3[Choose W coprime to M]
    K3 --> K4[Public key: a_i = W*b_i mod M]
    K4 --> E1[Message bits x_i select which a_i to sum]
    E1 --> E2[Ciphertext c = sum of selected a_i]
    E2 --> D1[Compute c' = W^-1 * c mod M]
    D1 --> D2[Greedy solve on superincreasing b_i]
    D2 --> D3[Recover message bits x_i]
sequenceDiagram
    participant S as Sender
    participant R as Receiver
    R->>S: Public sequence a_1..a_n
    S->>S: Encode message as bits, compute c = sum(x_i * a_i)
    S->>R: Send ciphertext c
    R->>R: Compute c' = W^-1 * c mod M
    R->>R: Greedy solve superincreasing subset-sum on b_i
    R->>R: Recover original message bits

Pseudocode

Function MerkleHellmanKeyGen(n):
    b[1] = randomInt(1, 10)
    sum = b[1]
    for i in 2..n:
        b[i] = 2 * sum + randomInt(1, 5)   // ensures strict superincreasing property
        sum = sum + b[i]

    M = sum + randomInt(1, sum)
    W = randomCoprimeTo(M)

    for i in 1..n:
        a[i] = (W * b[i]) mod M

    publicKey = a[1..n]
    privateKey = (b[1..n], W, M)
    return (publicKey, privateKey)

Function MerkleHellmanEncrypt(bits[1..n], a[1..n]):
    c = 0
    for i in 1..n:
        if bits[i] == 1:
            c = c + a[i]
    return c

Function MerkleHellmanDecrypt(c, privateKey):
    (b[1..n], W, M) = privateKey
    Winv = modInverse(W, M)
    cPrime = (Winv * c) mod M

    bits = array of n zeros
    for i in n downTo 1:
        if b[i] <= cPrime:
            bits[i] = 1
            cPrime = cPrime - b[i]
    return bits

Step-by-Step Example

I build a private superincreasing sequence $b = (2, 3, 7, 14, 30)$ (each term exceeds the sum of all previous: $3>2$, $7>2+3=5$, $14>2+3+7=12$, $30>2+3+7+14=26$). The total sum is $56$, so I choose $M = 61$ (a prime greater than 56) and $W = 17$ (coprime to 61). Computing the public key: $a_1 = 17\cdot2 \bmod 61 = 34$, $a_2 = 17\cdot3 \bmod 61 = 51$, $a_3 = 17\cdot7 \bmod 61 = 58$, $a_4 = 17\cdot14 \bmod 61 = 26$, $a_5 = 17\cdot30 \bmod 61 = 40$. Suppose I want to encrypt the message $10110$: I sum $a_1 + a_3 + a_4 = 34 + 58 + 26 = 118$. To decrypt, I compute $W^{-1} \bmod 61$: since $17 \times 18 = 306 = 5\cdot61 + 1$, $W^{-1} = 18$. Then $c’ = 18 \times 118 \bmod 61 = 2124 \bmod 61 = 23$. Solving greedily against $(2,3,7,14,30)$ from largest down: $30 > 23$, skip; $14 \leq 23$, take it, remainder $9$; $7 \leq 9$, take it, remainder $2$; $3 > 2$, skip; $2 \leq 2$, take it, remainder $0$. This recovers $b_4, b_3, b_1$ selected, i.e., bits $10110$, matching my original message exactly.

Time Complexity

I evaluate encryption, decryption, and key generation in terms of sequence length $n$. Encryption sums up to $n$ values:

$$ T_{\text{encrypt}} = O(n) $$

Decryption performs one modular multiplication and one greedy pass over $n$ terms:

$$ T_{\text{decrypt}} = O(n) $$

Key generation, building the superincreasing sequence and computing $n$ modular products, is also:

$$ T_{\text{keygen}} = O(n) $$

(all ignoring big-integer arithmetic cost, which scales with $\log M$).

Space Complexity

I store $n$ private terms, $n$ public terms, plus $W$ and $M$:

$$ S = O(n) $$

integers of bit-length $O(\log M)$, giving total bit-space $O(n \log M)$.

Correctness Analysis

I consider the scheme correct because the transformation $a_i = W b_i \bmod M$ is a group homomorphism under addition modulo $M$ (since $W$ has a well-defined multiplicative inverse), so summing selected $a_i$ values and then multiplying by $W^{-1} \bmod M$ exactly reconstructs the sum of the corresponding $b_i$ values modulo $M$. Because key generation ensures $\sum_i x_i b_i < M$ for any valid $n$-bit message, this modular sum equals the true integer sum with no wraparound, and the superincreasing property guarantees the greedy decoder recovers the unique correct subset. So, under honest key generation, decryption always succeeds. The scheme’s cryptographic correctness assumption — that the public sequence is hard to invert without the private key — is what fails, as shown by Shamir’s attack.

Advantages

Disadvantages

Applications

Implementation in C

#include <stdio.h>
#include <stdlib.h>

#define N 5

long long b[N], a[N];
long long W, M;

long long ext_gcd(long long x1, long long y1, long long *x, long long *y) {
    if (y1 == 0) { *x = 1; *y = 0; return x1; }
    long long xx, yy;
    long long g = ext_gcd(y1, x1 % y1, &xx, &yy);
    *x = yy;
    *y = xx - (x1 / y1) * yy;
    return g;
}

long long mod_inverse(long long val, long long mod) {
    long long x, y;
    ext_gcd(val, mod, &x, &y);
    return ((x % mod) + mod) % mod;
}

int main() {
    /* Private superincreasing sequence */
    long long initial[N] = {2, 3, 7, 14, 30};
    for (int i = 0; i < N; i++) b[i] = initial[i];

    M = 61;
    W = 17;

    for (int i = 0; i < N; i++) {
        a[i] = (W * b[i]) % M;
    }

    printf("Private sequence b: ");
    for (int i = 0; i < N; i++) printf("%lld ", b[i]);
    printf("\nPublic sequence a: ");
    for (int i = 0; i < N; i++) printf("%lld ", a[i]);
    printf("\n");

    /* Encryption of bits 1 0 1 1 0 */
    int bits[N] = {1, 0, 1, 1, 0};
    long long c = 0;
    for (int i = 0; i < N; i++) {
        if (bits[i]) c += a[i];
    }
    printf("Ciphertext c = %lld\n", c);

    /* Decryption */
    long long Winv = mod_inverse(W, M);
    long long cPrime = (Winv * c) % M;

    int decoded[N] = {0};
    for (int i = N - 1; i >= 0; i--) {
        if (b[i] <= cPrime) {
            decoded[i] = 1;
            cPrime -= b[i];
        }
    }

    printf("Decoded bits: ");
    for (int i = 0; i < N; i++) printf("%d ", decoded[i]);
    printf("\n");

    return 0;
}

Sample Input and Output

Private sequence b: 2 3 7 14 30
Public sequence a: 34 51 58 26 40
Ciphertext c = 118
Decoded bits: 1 0 1 1 0

This matches my hand-worked example exactly.

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version