Offensive Security Researcher & Quantum Cryptography Analyst

Knapsack Encryption Algorithm: Working, Explanation, and Implementation

Abdul Wahab Junaid
Knapsack algorithm and working of this algorithm.

Knapsack algorithm and working of this algorithm.

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:

How It Works

I generate my keys in these stages:

  1. I choose a superincreasing sequence of n positive integers: w1, w2, ..., wn, where each wi > sum(w1...w(i-1)).
  2. I pick a modulus m that is larger than the sum of all elements in my superincreasing sequence.
  3. I pick a multiplier a such that gcd(a, m) = 1 (so that a has a modular inverse mod m).
  4. I compute my public key as bi = (a * wi) mod m for each i. The sequence b1, ..., bn is what I publish; it no longer looks superincreasing to an outside observer.
  5. To encrypt, a sender takes their plaintext, breaks it into blocks of n bits, and for each block computes the sum of the bi values whose corresponding bit is 1. That sum is the ciphertext for that block.
  6. To decrypt, I compute the modular inverse a^-1 mod m, multiply the ciphertext by it modulo m, 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 bits

Pseudocode

// 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.

  1. 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).
  2. I choose m = 60 (greater than the total sum 51).
  3. I choose a = 7 (since gcd(7, 60) = 1).
  4. I compute the public key:
    • b1 = (7*2) mod 60 = 14
    • b2 = (7*3) mod 60 = 21
    • b3 = (7*6) mod 60 = 42
    • b4 = (7*13) mod 60 = 31
    • b5 = (7*27) mod 60 = 9
    • Public key: b = [14, 21, 42, 31, 9]
  5. 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
  6. On my side, I compute a^-1 mod 60. Since 7 * 43 = 301 = 5*60 + 1, the inverse is 43.
    • C' = (65 * 43) mod 60 = 2795 mod 60 = 35
  7. I solve the superincreasing problem for target 35 against w = [2, 3, 6, 13, 27]:
    • 27 <= 35, take it, remainder 8
    • 13 > 8, skip
    • 6 <= 8, take it, remainder 2
    • 3 > 2, skip
    • 2 <= 2, take it, remainder 0
    • Bits recovered from largest to smallest: 27,13,6,3,2 -> 1,0,1,0,1, which read in original order gives 10101 — matching the original plaintext block.

Time Complexity

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

Disadvantages

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

Common Mistakes

Further Reading

Exit mobile version