I want to start with the knapsack cryptosystem because it holds a special place in my understanding of cryptographic history — it was one of the very first attempts at building a public-key cryptosystem after RSA appeared, and it was built on a completely different hard problem: the subset-sum (knapsack) problem instead of integer factorization. When I studied it, what struck me most is that it is simple enough to compute by hand, yet it was also the first major public-key scheme to be broken in the open literature. I find that duality — elegant simplicity paired with a famous, spectacular failure — makes it one of the best teaching examples in all of cryptography.
History and Background
I trace the origin of this algorithm to 1978, when Ralph Merkle and Martin Hellman published their paper “Hiding Information and Signatures in Trapdoor Knapsacks.” At the time, RSA had just been published a year earlier, and the cryptographic community was hungry for alternative public-key constructions, partly because nobody wanted to put all their trust in a single hard problem (factoring). Merkle and Hellman turned to the subset-sum problem, which is NP-complete in its general form, and tried to build a trapdoor version of it.
The scheme became known as the Merkle-Hellman Knapsack Cryptosystem, and for a few years it was considered a promising RSA alternative. Then, in 1982, Adi Shamir showed that the basic single-iteration version could be broken in polynomial time using lattice-basis-reduction-like techniques rooted in the structure of the “superincreasing” sequence used to build the trapdoor. Later, Ernst Brickell broke even the iterated (multiple-iteration) versions in 1984. I think this history is important because it taught the field a hard lesson: a problem being NP-complete in general does not mean every instance you construct from it is hard — the specific instances generated by the trapdoor construction turned out to have exploitable structure.
Problem Statement
The algorithm tries to solve the general public-key encryption problem: how can two parties who have never met establish secure communication using a publicly known key, where only the intended recipient (holding a private key) can decrypt the message? Merkle and Hellman’s specific approach was to base the “hard direction” of encryption on the subset-sum problem: given a set of numbers and a target sum, find the subset that adds up to that target. This problem is NP-complete for arbitrary sets, so on paper it looked like a solid foundation for a trapdoor function.
Core Concepts
Before I explain the mechanism, I want to lay out the vocabulary I rely on throughout:
- Subset-sum / knapsack problem – given a set of positive integers and a target value, determine whether a subset of the integers sums exactly to the target.
- Superincreasing sequence – a sequence of numbers where each element is greater than the sum of all the previous elements. This special sequence is easy to solve for subset-sum in linear time (I explain why below), and it forms my private key.
- Trapdoor – a piece of secret information that turns a hard problem into an easy one. Here, the trapdoor is the pair of numbers used to transform the easy superincreasing sequence into a hard-looking general sequence.
- Modular multiplication transform – I take the easy superincreasing sequence and multiply each term by a secret multiplier modulo a secret modulus, which scrambles it into what looks like a “general” hard knapsack sequence — this becomes my public key.
How It Works
I generate my keys in these stages:
- I choose a superincreasing sequence of
npositive integers:w1, w2, ..., wn, where eachwi > sum(w1...w(i-1)). - I pick a modulus
mthat is larger than the sum of all elements in my superincreasing sequence. - I pick a multiplier
asuch thatgcd(a, m) = 1(so thatahas a modular inverse modm). - I compute my public key as
bi = (a * wi) mod mfor eachi. The sequenceb1, ..., bnis what I publish; it no longer looks superincreasing to an outside observer. - To encrypt, a sender takes their plaintext, breaks it into blocks of
nbits, and for each block computes the sum of thebivalues whose corresponding bit is 1. That sum is the ciphertext for that block. - To decrypt, I compute the modular inverse
a^-1 mod m, multiply the ciphertext by it modulom, and this recovers the original superincreasing sum, which I can then solve very quickly because superincreasing sequences are trivial to invert.
Working Principle
The internal trick that makes this work is that solving subset-sum on a superincreasing sequence is easy: I start from the largest weight and work backwards. If the target sum is greater than or equal to the largest weight, that weight must be part of the solution (because even summing all the smaller weights together could never reach it, by the very definition of superincreasing). I subtract it and move to the next-largest weight, repeating until the target reaches zero.
The public sequence, by contrast, has no such structure to an attacker, since the modular multiplication mixes the terms and hides their superincreasing relationship — unless the attacker knows the secret a and m to reverse the transformation. Decryption, then, is really just “undo the disguise, then solve the easy version.”
Mathematical Foundation
The superincreasing condition is expressed as:
$$w_i > \sum_{j=1}^{i-1} w_j \quad \text{for all } i = 2, \dots, n$$
Public key generation:
$$b_i = (a \cdot w_i) \bmod m, \quad \gcd(a, m) = 1$$
Encryption of an n-bit block $x_1 x_2 \dots x_n$:
$$C = \sum_{i=1}^{n} x_i \cdot b_i$$
Decryption using the modular inverse $a^{-1}$ of $a$ modulo $m$:
$$C’ = (a^{-1} \cdot C) \bmod m = \sum_{i=1}^{n} x_i \cdot w_i$$
Once I have $C’$, I solve the superincreasing subset-sum problem for $C’$ against $w_1, \dots, w_n$ using the greedy backward algorithm to recover the bits $x_1, \dots, x_n$.
Diagrams
flowchart TD
A["Choose a superincreasing sequence"] --> B["Choose a modulus larger than the sequence sum"]
B --> C["Choose a multiplier that is relatively prime to the modulus"]
C --> D["Compute the public key"]
D --> E["Publish the public key"]
E --> F["Encrypt the plaintext"]
F --> G["Compute the transformed ciphertext"]
G --> H["Solve the subset sum"]
H --> I["Recover the plaintext"]sequenceDiagram
participant S as Sender
participant R as Receiver
R->>R: Generate w (private), a, m (private)
R->>S: Publish b_i = a*w_i mod m
S->>S: Encode message as bits x_i
S->>R: Send C = sum(x_i * b_i)
R->>R: Compute C' = a^-1 * C mod m
R->>R: Greedily solve superincreasing sum
R->>R: Recover plaintext bitsPseudocode
// Key Generation
function generate_keys(n):
w = generate_superincreasing_sequence(n)
m = random_integer_greater_than(sum(w))
a = random_integer_coprime_to(m)
b = []
for i in 1..n:
b[i] = (a * w[i]) mod m
return public_key = b, private_key = (w, a, m)
// Encryption
function encrypt(plaintext_bits, b):
ciphertext_blocks = []
for each block of n bits in plaintext_bits:
sum = 0
for i in 1..n:
if block[i] == 1:
sum = sum + b[i]
ciphertext_blocks.append(sum)
return ciphertext_blocks
// Decryption
function decrypt(ciphertext_blocks, w, a, m):
a_inv = modular_inverse(a, m)
plaintext_bits = []
for C in ciphertext_blocks:
C_prime = (C * a_inv) mod m
bits = solve_superincreasing(C_prime, w)
plaintext_bits.append(bits)
return plaintext_bits
// Solving a superincreasing subset-sum
function solve_superincreasing(target, w):
n = length(w)
bits = array of size n filled with 0
for i from n down to 1:
if target >= w[i]:
bits[i] = 1
target = target - w[i]
return bits
Step-by-Step Example
I will walk through a small example with n = 5.
- I choose a superincreasing sequence:
w = [2, 3, 6, 13, 27](each term exceeds the sum of all before it: 3>2, 6>2+3=5, 13>2+3+6=11, 27>2+3+6+13=24). - I choose
m = 60(greater than the total sum 51). - I choose
a = 7(sincegcd(7, 60) = 1). - I compute the public key:
b1 = (7*2) mod 60 = 14b2 = (7*3) mod 60 = 21b3 = (7*6) mod 60 = 42b4 = (7*13) mod 60 = 31b5 = (7*27) mod 60 = 9- Public key:
b = [14, 21, 42, 31, 9]
- Suppose the sender wants to encrypt the 5-bit block
10101(bits for positions 1,3,5 are 1).C = b1 + b3 + b5 = 14 + 42 + 9 = 65
- On my side, I compute
a^-1 mod 60. Since7 * 43 = 301 = 5*60 + 1, the inverse is43.C' = (65 * 43) mod 60 = 2795 mod 60 = 35
- I solve the superincreasing problem for target
35againstw = [2, 3, 6, 13, 27]:27 <= 35, take it, remainder813 > 8, skip6 <= 8, take it, remainder23 > 2, skip2 <= 2, take it, remainder0- Bits recovered from largest to smallest:
27,13,6,3,2 -> 1,0,1,0,1, which read in original order gives10101— matching the original plaintext block.
Time Complexity
- Key generation: generating the superincreasing sequence and computing
nmodular multiplications takes $O(n)$ arithmetic operations. - Encryption: for each
n-bit block, I do at mostnadditions, so encryption is $O(n)$ per block, or $O(n \cdot L)$ for a message ofLblocks. - Decryption (legitimate, with trapdoor): one modular multiplication plus the greedy superincreasing solve, which is $O(n)$ per block.
- Decryption without the trapdoor (attacker’s brute-force case): solving general subset-sum is NP-complete, so worst case is exponential, $O(2^n)$, though as I mention in the disadvantages section, the actual security of the constructed instances was far weaker than this suggests.
Space Complexity
The private key needs storage for w (n integers), plus a and m, so $O(n)$ space. The public key needs n integers as well, so $O(n)$ space. Ciphertext blocks require space proportional to the number of blocks in the message, each block being a single integer roughly the size of m.
Correctness Analysis
I can prove correctness by tracing the algebra. Encryption computes:
$$C = \sum_i x_i b_i = \sum_i x_i (a w_i \bmod m)$$
Because addition is being done in the integers rather than modulo m at encryption time, this isn’t immediately equal to $a \sum_i x_i w_i \bmod m$ — but by construction m is chosen larger than $\sum_i w_i$, and a is applied consistently, so modular arithmetic still lets me recover the sum correctly: multiplying C by a^-1 modulo m gives
$$C’ = a^{-1} \left( \sum_i x_i (a w_i \bmod m) \right) \bmod m = \left( \sum_i x_i w_i \right) \bmod m$$
Since m is larger than any possible sum of the wi, the mod operation doesn’t wrap around, so $C’ = \sum_i x_i w_i$ exactly. Because w is superincreasing, this sum has a unique subset representation, and my greedy algorithm always finds it correctly, which is why decryption always recovers the exact original bits.
Advantages
- The underlying operations are additions and modular multiplications, which made it much faster than RSA’s modular exponentiation on the hardware of the late 1970s.
- The concept is very intuitive to teach: I find it much easier to explain subset-sum to newcomers than modular exponentiation and Euler’s theorem.
- It historically diversified the field’s risk by proposing a public-key scheme not based on factoring.
Disadvantages
- The single-iteration scheme is completely broken; Shamir’s 1982 attack recovers the private key from the public key in polynomial time by exploiting the structure left behind by the modular transform.
- Even the multiple-iteration variants, meant to disguise the superincreasing structure further, were broken by Brickell in 1984.
- The information rate is poor compared to modern schemes: the ciphertext numbers grow larger than the plaintext bits they encode.
- It has no signature capability in its basic form, unlike RSA, which was another reason it fell out of favor.
Applications
Historically, it was proposed for general public-key encryption and digital envelopes in the late 1970s and early 1980s. Today, I would only ever bring it up in an academic or historical context — as a teaching tool for public-key cryptography courses, in cryptanalysis coursework to demonstrate lattice-reduction attacks, and in the history-of-cryptography literature as a cautionary tale about why “NP-complete in general” doesn’t guarantee that constructed problem instances are hard.
Implementation in C
#include <stdio.h>
#include <stdlib.h>
#define N 5
/* Extended Euclidean algorithm to find modular inverse */
long long mod_inverse(long long a, long long m) {
long long m0 = m, t, q;
long long x0 = 0, x1 = 1;
if (m == 1) return 0;
while (a > 1) {
q = a / m;
t = m;
m = a % m, a = t;
t = x0;
x0 = x1 - q * x0;
x1 = t;
}
if (x1 < 0) x1 += m0;
return x1;
}
int main(void) {
/* Private key: superincreasing sequence */
long long w[N] = {2, 3, 6, 13, 27};
long long m = 60; /* modulus, must exceed sum(w) */
long long a = 7; /* multiplier, gcd(a, m) = 1 */
long long b[N]; /* public key */
long long a_inv;
int i;
/* Step 1: generate public key */
for (i = 0; i < N; i++) {
b[i] = (a * w[i]) % m;
}
printf("Public key: ");
for (i = 0; i < N; i++) printf("%lld ", b[i]);
printf("\n");
/* Step 2: encrypt a 5-bit block, e.g. 1 0 1 0 1 */
int plaintext_bits[N] = {1, 0, 1, 0, 1};
long long cipher = 0;
for (i = 0; i < N; i++) {
if (plaintext_bits[i]) cipher += b[i];
}
printf("Ciphertext: %lld\n", cipher);
/* Step 3: decrypt using the trapdoor */
a_inv = mod_inverse(a, m);
long long c_prime = (cipher * a_inv) % m;
printf("Recovered superincreasing sum: %lld\n", c_prime);
int recovered_bits[N] = {0};
long long target = c_prime;
for (i = N - 1; i >= 0; i--) {
if (target >= w[i]) {
recovered_bits[i] = 1;
target -= w[i];
}
}
printf("Recovered plaintext bits: ");
for (i = 0; i < N; i++) printf("%d ", recovered_bits[i]);
printf("\n");
return 0;
}
I designed this program to walk through key generation, encryption, and decryption in one flow, printing intermediate values so I can verify each stage against my manual example above.
Sample Input and Output
Input: private superincreasing sequence w = [2, 3, 6, 13, 27], modulus m = 60, multiplier a = 7, plaintext bits 10101.
Output:
Public key: 14 21 42 31 9
Ciphertext: 65
Recovered superincreasing sum: 35
Recovered plaintext bits: 1 0 1 0 1
This matches my hand-worked example exactly, which gives me confidence the arithmetic and the greedy solver are correct.
Optimization Techniques
- I can precompute the modular inverse
a^-1once during key setup instead of recomputing it for every decryption. - For encrypting long messages, I can pack multiple
n-bit blocks and process them in a tight loop, minimizing function-call overhead in performance-critical C implementations. - Using fixed-width big-integer libraries instead of built-in 64-bit integers avoids overflow once
ngrows large, since sums of many big weights can overflow standard integer types. - Some historical proposals suggested iterating the modular transformation (multiple moduli/multipliers) to try to hide the superincreasing structure better — though, as I noted above, this was ultimately broken too, so I mention it here only as a historical optimization attempt rather than one I would recommend today.
Common Mistakes
- Choosing
mtoo small, i.e., not strictly greater than the sum of all weights inw; this breaks correctness because the modular reduction during decryption will wrap around and give the wrong sum. - Picking
awithout checkinggcd(a, m) = 1, which means no modular inverse exists and decryption becomes impossible. - Forgetting that the “hardness” of the general subset-sum problem does not transfer automatically to the specific transformed sequence — this was the very mistake that doomed the scheme itself.
- Implementing the superincreasing solver in the wrong order (I must go from the largest weight to the smallest); doing it in ascending order breaks the greedy correctness argument.
- Using this cryptosystem in any real security-sensitive system today — it should only be used for educational demonstration, since it has been broken for decades.
Further Reading
- Merkle, R. and Hellman, M., “Hiding Information and Signatures in Trapdoor Knapsacks,” IEEE Transactions on Information Theory, 1978: https://ee.stanford.edu/~hellman/publications/22.pdf
- Shamir, A., “A Polynomial Time Algorithm for Breaking the Basic Merkle-Hellman Cryptosystem,” 1982: https://www.wisdom.weizmann.ac.il/~shamir/papers.html
- Schneier, B., Applied Cryptography, 2nd Edition, Wiley, 1996: https://www.schneier.com/books/applied-cryptography/
- Stanford Crypto course notes on knapsack cryptosystems: https://crypto.stanford.edu/~dabo/cryptobook/
- Wikipedia overview of the Merkle-Hellman Knapsack Cryptosystem: https://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsack_cryptosystem
