I approach the Graham-Shamir algorithm as a variant within the knapsack-based family of public-key cryptosystems, closely related to the better-known Merkle-Hellman scheme but distinguished by how it constructs its private superincreasing sequence. I find it useful to study alongside Merkle-Hellman because it shows me that the “knapsack cryptosystem” idea is really a family of related constructions, all built around the same core trick — hiding an easy subset-sum problem behind a modular transformation that makes it look like a hard one — with Graham and Shamir contributing a specific, more randomized way of generating the easy (superincreasing) sequence in the first place.
History and Background
I trace the Graham-Shamir construction to the same era as Merkle and Hellman’s original 1978 knapsack cryptosystem paper, where Ronald Graham and Adi Shamir are credited with proposing an alternative method for generating the private superincreasing sequence used as the trapdoor. Rather than the simple doubling approach Merkle and Hellman originally described (where each term is roughly double the sum of all previous terms), the Graham-Shamir approach adds an extra random offset at each step, intended to make the private sequence’s structure less predictable and, in theory, harder for an attacker to detect from the public transformed sequence. Like the rest of the knapsack cryptosystem family, this construction was ultimately undermined by Adi Shamir’s own 1982 cryptanalysis of the basic Merkle-Hellman scheme, and later by the broader use of lattice-basis-reduction attacks (LLL) in the 1980s, which could recover low-density knapsack trapdoors regardless of the exact sequence-generation method used.
Problem Statement
I want a public-key cryptosystem based on the subset-sum (knapsack) problem, which is NP-hard in its general form: given a set of numbers and a target sum, determine which subset of numbers adds up to the target. I want to construct a private version of this problem that is easy to solve (a superincreasing sequence, where each term exceeds the sum of all previous terms, letting me solve subset-sum greedily), then disguise it using modular multiplication so that the public version looks like a generic, hard subset-sum problem to anyone without the private trapdoor.
Core Concepts
- Superincreasing sequence — a sequence $b_1, b_2, \dots, b_n$ such that $b_i > \sum_{j=1}^{i-1} b_j$ for every $i$, which allows subset-sum to be solved in linear time via a simple greedy algorithm.
- Graham-Shamir generation method — constructing the superincreasing sequence as $b_1 = $ random value, and $b_i = 2\left(\sum_{j<i} b_j\right) + r_i$, where $r_i$ is a random value chosen in a bounded range, adding extra randomization beyond simple doubling.
- Modulus $M$ and multiplier $W$ — chosen such that $M$ exceeds the sum of all $b_i$, and $W$ is coprime to $M$, used to transform the private sequence into the public one.
- Public sequence — $a_i = (W \cdot b_i) \bmod M$, which looks like a random, non-superincreasing (and therefore hard) set of numbers.
- Subset-sum encryption — a message, represented as a bit-vector, selects which public numbers to sum together to form the ciphertext.
How It Works
I break the algorithm into key generation, encryption, and decryption:
- Key generation: Choose a random starting value $b_1$. For each subsequent term, compute $b_i = 2\left(\sum_{j=1}^{i-1} b_j\right) + r_i$, where $r_i$ is randomly chosen (commonly in the range $[1, \sum_{j<i} b_j]$), guaranteeing the superincreasing property while introducing additional randomness compared to plain doubling.
- Choose a modulus $M > \sum_{i=1}^n b_i$ and a multiplier $W$ coprime to $M$ (so a modular inverse $W^{-1}$ exists).
- Compute the public sequence $a_i = (W \cdot 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)$ as the private key.
- Encryption: Represent the message 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=1}^n x_i b_i \bmod M$ — a subset-sum instance over the easy superincreasing sequence.
- Solve this easy subset-sum problem greedily (from the largest $b_i$ down to the smallest) to recover the original bits $x_1, \dots, x_n$.
Working Principle
I understand the trapdoor logic here in the same way I understand Merkle-Hellman’s: the modular multiplication by $W$ “scrambles” the ordering and magnitude relationships that make the superincreasing sequence easy to solve, so the public sequence $a_i$ no longer has the superincreasing property and looks, to an outside observer, like an arbitrary hard subset-sum instance. Only someone who knows $W^{-1}$ and $M$ can undo the scrambling and recover the private superincreasing structure, at which point the subset-sum problem becomes trivially solvable. The Graham-Shamir contribution is specifically about making $b_i$ less predictable in its exact numeric growth pattern (adding random offsets $r_i$ rather than exact doubling), which was intended, at the time, to add a further layer of obscurity against pattern-based attacks on the private sequence’s structure.
Mathematical Foundation
I define the private superincreasing sequence recursively:
$$ b_1 = \text{random}, \qquad b_i = 2\sum_{j=1}^{i-1} b_j + r_i, \quad r_i \in \left[1, \sum_{j=1}^{i-1} b_j\right] $$
This guarantees the superincreasing property:
$$ b_i > \sum_{j=1}^{i-1} b_j $$
I choose $M$ and $W$ such that:
$$ M > \sum_{i=1}^{n} b_i, \qquad \gcd(W, M) = 1 $$
The public key is generated as:
$$ a_i = (W \cdot b_i) \bmod M $$
Encryption computes:
$$ c = \sum_{i=1}^n x_i a_i, \qquad x_i \in {0,1} $$
Decryption reverses the modular scaling:
$$ c’ = W^{-1} c \bmod M = W^{-1}\left(\sum_i x_i (W b_i \bmod M)\right) \bmod M = \sum_i x_i b_i \bmod M $$
Since $\sum_i x_i b_i < M$ by construction, the modular reduction has no effect, so:
$$ c’ = \sum_{i=1}^n x_i b_i $$
which I solve using the greedy superincreasing algorithm, checking from $b_n$ down to $b_1$ whether each term fits within the remaining value of $c’$.
Diagrams
flowchart TD
K1["Generate superincreasing sequence"] --> K2["Choose modulus and multiplier"]
K2 --> K3["Generate public key"]
K3 --> E1["Select public key values using message bits"]
E1 --> E2["Generate ciphertext"]
E2 --> D1["Transform ciphertext"]
D1 --> D2["Solve subset sum"]
D2 --> D3["Recover original message"]sequenceDiagram
participant S as Sender
participant R as Receiver
R->>S: Public sequence a_1..a_n
S->>S: Encode message as bits x_1..x_n
S->>S: 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
R->>R: Recover message bitsPseudocode
Function GrahamShamirKeyGen(n):
b[1] = randomInt()
sum = b[1]
for i in 2..n:
r_i = randomInt(1, sum)
b[i] = 2 * sum + r_i
sum = sum + b[i]
M = sum + randomInt(1, sum) // M > total 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 GrahamShamirEncrypt(bits[1..n], a[1..n]):
c = 0
for i in 1..n:
if bits[i] == 1:
c = c + a[i]
return c
Function GrahamShamirDecrypt(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 generate a small private sequence using the Graham-Shamir method. Starting with $b_1 = 3$, I choose $r_2 = 2$, giving $b_2 = 2(3) + 2 = 8$; running sum is now 11. I choose $r_3 = 5$, giving $b_3 = 2(11) + 5 = 27$; running sum is now 38. I choose $r_4 = 10$, giving $b_4 = 2(38) + 10 = 86$; running sum is now 124. My private sequence is $(3, 8, 27, 86)$, all superincreasing as required. I choose $M = 250$ (greater than 124) and $W = 41$ (coprime to 250). Computing the public sequence: $a_1 = 41\cdot3 \bmod 250 = 123$, $a_2 = 41\cdot8 \bmod 250 = 78$, $a_3 = 41\cdot27 \bmod 250 = 107$, $a_4 = 41\cdot86 \bmod 250 = 26$. Suppose I want to encrypt the message bits $1011$: I sum $a_1 + a_3 + a_4 = 123 + 107 + 26 = 256$. To decrypt, I compute $W^{-1} \bmod 250$, which is $61$ (since $41 \times 61 = 2501 \equiv 1 \bmod 250$), and compute $c’ = 61 \times 256 \bmod 250 = 15616 \bmod 250 = 116$. Applying the greedy algorithm against $(3,8,27,86)$ from largest to smallest: $86 \leq 116$, take it, remainder $30$; $27 \leq 30$, take it, remainder $3$; $8 > 3$, skip; $3 \leq 3$, take it, remainder $0$. This recovers bits $1011$ (from $b_4, b_3, b_2, b_1$ order), matching my original message.
Time Complexity
I count both encryption and decryption in terms of the sequence length $n$. Encryption sums at most $n$ public values:
$$ T_{\text{encrypt}} = O(n) $$
Decryption computes one modular multiplication (for $W^{-1}c \bmod M$) and then runs the greedy superincreasing solver, which checks each of the $n$ terms once:
$$ T_{\text{decrypt}} = O(n) $$
Key generation, dominated by generating $n$ terms and computing $n$ modular multiplications, is also:
$$ T_{\text{keygen}} = O(n) $$
(ignoring the cost of big-integer arithmetic, which grows with the bit-length of $M$).
Space Complexity
I need to store $n$ private terms $b_i$, $n$ public terms $a_i$, plus $W$ and $M$, giving:
$$ S = O(n) $$
integers, each up to $O(\log M)$ bits long, so total bit-space is $O(n \log M)$.
Correctness Analysis
I consider the scheme correct because the modular transformation $a_i = Wb_i \bmod M$ is linear, so summing a subset of the $a_i$ values and then multiplying by $W^{-1} \bmod M$ exactly recovers the sum of the corresponding $b_i$ values, as long as that true sum stays below $M$ (which key generation guarantees by choosing $M$ larger than the total sum of all $b_i$). Since the $b_i$ sequence is genuinely superincreasing, the greedy decoding algorithm is guaranteed to correctly and uniquely identify exactly which subset was summed, so decryption always recovers the exact original message bits under honest key generation.
Advantages
- Encryption is extremely fast, requiring only additions.
- Conceptually simple and easy to implement compared to number-theoretic schemes like RSA.
- The added randomization in generating $b_i$ was intended to obscure the private sequence’s structure more than simple doubling.
- Historically important as one of the earliest concrete public-key cryptosystem proposals, contributing to the broader development of public-key cryptography.
Disadvantages
- Fundamentally broken as a secure cryptosystem — Shamir’s 1982 attack and subsequent lattice-reduction (LLL) attacks can recover the private key or an equivalent trapdoor from the public sequence alone, regardless of whether the Graham-Shamir randomized generation method is used.
- The extra randomization does not meaningfully increase the density of the knapsack, so it remains vulnerable to low-density subset-sum attacks.
- No longer used in practical, secure systems; retained mainly for historical and educational study.
- Provides no formal security reduction to a well-studied hard problem, unlike RSA or Rabin.
Applications
- Historical study of early public-key cryptosystem design and the subsequent cryptanalysis that shaped modern cryptographic design principles.
- Educational demonstrations of subset-sum-based encryption and the superincreasing sequence technique.
- Illustrative example in cryptography courses of how “hard-looking” problems can still be efficiently broken via structural attacks like lattice basis reduction.
- Occasionally referenced in research exploring lattice attacks and cryptanalysis techniques more broadly.
Implementation in C
#include <stdio.h>
#include <stdlib.h>
#define N 4
long long b[N], a[N];
long long W, M;
long long ext_gcd(long long a1, long long b1, long long *x, long long *y) {
if (b1 == 0) { *x = 1; *y = 0; return a1; }
long long x1, y1;
long long g = ext_gcd(b1, a1 % b1, &x1, &y1);
*x = y1;
*y = x1 - (a1 / b1) * y1;
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() {
/* Key generation using the Graham-Shamir style superincreasing sequence */
long long r[N] = {0, 2, 5, 10}; /* fixed for reproducibility of the example */
b[0] = 3;
long long sum = b[0];
for (int i = 1; i < N; i++) {
b[i] = 2 * sum + r[i];
sum += b[i];
}
M = 250;
W = 41;
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 */
int bits[N] = {1, 0, 1, 1};
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: 3 8 27 86
Public sequence a: 123 78 107 26
Ciphertext c = 256
Decoded bits: 1 0 1 1
This matches my hand-worked example exactly.
Optimization Techniques
- Using big-integer arithmetic libraries for large $n$ and large $M$, since real security-relevant parameters need hundreds of bits, though even then the scheme remains insecure against lattice attacks.
- Precomputing $W^{-1} \bmod M$ once during key generation rather than recomputing it for every decryption.
- Batch-processing multiple ciphertexts using vectorized addition when summing selected public terms for large messages.
- None of these optimizations, however, address the scheme’s fundamental cryptanalytic weaknesses, which is worth remembering when studying it.
Common Mistakes
- Believing the added randomization in the Graham-Shamir sequence generation meaningfully improves security — it does not resist LLL-based lattice attacks any better than simple doubling.
- Choosing $M$ too close to the sum of all $b_i$, risking ciphertext overflow past $M$ during encryption and causing decryption errors.
- Forgetting to verify $\gcd(W, M) = 1$, which would make the modular inverse $W^{-1}$ not exist and break decryption entirely.
- Treating this as a currently secure cryptosystem instead of a broken, historically significant scheme meant for educational study.
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” (the LLL algorithm), 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
- Brickell, E. F., Odlyzko, A. M., “Cryptanalysis: A Survey of Recent Results,” Proceedings of the IEEE, 1988. https://ieeexplore.ieee.org/document/4741
