The Knapsack cipher, also known as the Merkle–Hellman knapsack cryptosystem, is an early public-key cryptosystem introduced by Ralph Merkle and Martin Hellman in 1978. It is based on the subset-sum problem, where the goal is to select numbers from a set that sum to a target value. The cipher uses a private superincreasing sequence, then applies a multiplier m and a modulus n to produce a public key. The private key consists of the superincreasing sequence, m, and n, while the public key is used for encryption.
To encrypt, the plaintext is first converted into binary blocks. Each bit determines whether the corresponding element of the public key is included in the sum. For example, consider the plaintext letter “H” (ASCII 72, binary 01001000). Suppose the private superincreasing sequence is [2, 3, 6, 13, 27, 52, 105, 210], with multiplier m = 31 and modulus n = 909. The public key is generated by computing each element as (sequence element × m mod n), giving [62, 93, 186, 403, 837, 731, 612, 343]. The ciphertext is then calculated by summing the public key elements corresponding to 1s in the binary block. For 01001000, the bits at positions 2 and 5 are 1, so the sum is 93 + 837 = 930. This 930 is the ciphertext for “H”.
Decryption requires the private key. The recipient computes c × m⁻¹ mod n, where m⁻¹ is the modular inverse of m modulo n, then solves the subset-sum problem using the superincreasing sequence to recover the original binary block. Converting the binary back to decimal yields the plaintext letter. The Knapsack cipher is historically significant as one of the first practical public-key systems, demonstrating how number-theoretic hardness and modular arithmetic can secure communications. Including m and n explicitly shows how the private key disguises the superincreasing sequence into a usable public key, providing asymmetric encryption while maintaining the reversible structure for decryption.