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
- Superincreasing sequence — a sequence $b_1, \dots, b_n$ where each term exceeds the sum of all previous terms: $b_i > \sum_{j<i} b_j$.
- Greedy subset-sum solver — because of the superincreasing property, I can solve subset-sum for such a sequence in $O(n)$ time by checking from the largest term down.
- Modulus $M$ — chosen larger than the sum of all $b_i$, ensuring the modular transformation does not wrap around during valid encryption.
- Multiplier $W$ — an integer coprime to $M$, used to scramble the superincreasing sequence into the public sequence.
- Public (hard) knapsack — the transformed sequence $a_i = (W b_i) \bmod M$, which no longer has the superincreasing property and appears to be a hard, general subset-sum instance.
How It Works
I break the algorithm into key generation, encryption, and decryption:
- 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.
- Choose a modulus $M$ strictly greater than $\sum_{i=1}^n b_i$.
- Choose a multiplier $W$ such that $\gcd(W, M) = 1$, so $W^{-1} \bmod M$ exists.
- Compute the public sequence: $a_i = (W b_i) \bmod M$ for each $i$.
- Publish $(a_1, \dots, a_n)$ as the public key; keep $(b_1, \dots, b_n, W, M)$ private.
- 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$.
- 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$).
- 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 bitsPseudocode
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
- Extremely fast encryption and decryption, using only additions and a small number of modular operations rather than expensive exponentiation.
- Conceptually simple to understand and implement compared to number-theoretic schemes.
- Historically significant as one of the first concrete public-key cryptosystems, helping establish public-key cryptography as a practical field.
- The subset-sum problem it is nominally based on remains NP-hard in the general case, illustrating an important distinction between problem hardness and instance-generation security.
Disadvantages
- Completely broken for the basic single-iteration version — Shamir’s 1982 attack recovers an equivalent private key in polynomial time.
- Even multi-iteration variants designed to patch the original scheme were later broken using lattice-basis-reduction techniques (LLL and its descendants).
- Provides no formal security reduction to the general (NP-hard) subset-sum problem; security depended on an informal hope that the specific superincreasing-to-scrambled transformation was hard to reverse, which turned out to be false.
- No longer used in any real-world secure system, serving today only an educational and historical role.
Applications
- Cryptography education, as a clear illustration of the “trapdoor” design pattern used across public-key cryptosystems.
- Historical case study in cryptanalysis courses, showing how structural weaknesses (not brute-force attacks) can break a cryptosystem.
- A stepping stone in the historical development that motivated stronger security definitions and formal reduction-based proofs for later cryptosystems.
- Occasionally revisited in academic papers studying lattice-based cryptanalysis techniques and their general applicability.
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
- Using big-integer libraries for realistically-sized $n$ (historically around 100 terms) and correspondingly large $M$, though this does not restore security against known attacks.
- Precomputing $W^{-1} \bmod M$ once at key generation, avoiding repeated extended-Euclidean computation during decryption.
- Iterating the modular disguise multiple times (multi-iteration Merkle-Hellman) was proposed as a defense against Shamir’s specific attack, though this too was later broken using lattice reduction.
- None of these are true “security” optimizations in the modern sense — I mention them mainly because the historical literature explored them as attempted patches.
Common Mistakes
- Believing that because subset-sum is NP-hard in general, any subset-sum-based cryptosystem is automatically secure — Shamir’s attack proves this reasoning is flawed for this specific construction.
- Choosing $M$ too close to the sum of the private sequence, risking ciphertext ambiguity or overflow past $M$.
- Failing to verify $\gcd(W, M) = 1$, breaking the existence of $W^{-1}$ and thus decryption entirely.
- Treating multi-iteration variants as “fixed” versions without recognizing they too were broken by later lattice-based cryptanalysis.
Further Reading
- Merkle, R., Hellman, M., “Hiding Information and Signatures in Trapdoor Knapsacks,” IEEE Transactions on Information Theory, 1978. https://ieeexplore.ieee.org/document/1055927
- Shamir, A., “A Polynomial Time Algorithm for Breaking the Basic Merkle-Hellman Cryptosystem,” CRYPTO 1982. https://link.springer.com/chapter/10.1007/3-540-39568-7_2
- Lenstra, A. K., Lenstra, H. W., Lovász, L., “Factoring Polynomials with Rational Coefficients,” Mathematische Annalen, 1982. https://link.springer.com/article/10.1007/BF01457454
- Odlyzko, A. M., “The Rise and Fall of Knapsack Cryptosystems,” Cryptology and Computational Number Theory, 1990. https://www.dtc.umn.edu/~odlyzko/doc/knapsack.survey.pdf
- Diffie, W., Hellman, M., “New Directions in Cryptography,” IEEE Transactions on Information Theory, 1976. https://ee.stanford.edu/~hellman/publications/24.pdf
