Offensive Security Researcher & Quantum Cryptography Analyst

Graham-Shamir Algorithm: Working, Explanation, and Cryptographic Applications

Abdul Wahab Junaid
Graham-Shamir algorithm and working of this algorithm

Graham-Shamir algorithm and working of this algorithm

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

How It Works

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

  1. 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.
  2. Choose a modulus $M > \sum_{i=1}^n b_i$ and a multiplier $W$ coprime to $M$ (so a modular inverse $W^{-1}$ exists).
  3. Compute the public sequence $a_i = (W \cdot b_i) \bmod M$ for each $i$.
  4. Publish $(a_1, \dots, a_n)$ as the public key; keep $(b_1, \dots, b_n, W, M)$ as the private key.
  5. 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$.
  6. 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.
  7. 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 bits

Pseudocode

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

Disadvantages

Applications

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

Common Mistakes

Further Reading

Exit mobile version