Knapsack Cipher

The Knapsack Cipher is a public-key cryptosystem based on the mathematical problem of the subset sum, also known as the "knapsack problem." It was one of the first attempts at a public-key encryption scheme, proposed by Ralph Merkle and Martin Hellman in 1978. The cipher transforms a plaintext message into a binary representation and encodes it as a sum of elements from a specially chosen sequence, making decryption without the private key computationally difficult.

The system relies on a superincreasing sequence for the private key, where each element is greater than the sum of all previous elements. A public key is then generated by applying modular arithmetic with a chosen multiplier and modulus. Encryption involves converting each plaintext character into a binary string and taking the weighted sum of the corresponding public key elements.

Knapsack Cipher: Encoding

To encode a message, first select the private superincreasing sequence, a multiplier, and a modulus. Then generate the public key using these parameters. Each plaintext letter is converted to binary and summed using the public key to produce the ciphertext. For example, using the following parameters:

Sequence (private key): 2, 3, 7, 14, 30, 57, 120, 251
Multiplier: 44
Modulus: 525
Plaintext: CATENCODE

Ciphertext Calculation:
Each letter is converted to binary (8 bits), then summed with the corresponding public key elements.

Ciphertext: 181 151 631 559 840 181 859 540 559

Notice how each plaintext character is mapped to a numeric sum using the public key derived from the sequence, multiplier, and modulus.

Knapsack Cipher: Decoding

Decoding requires the private superincreasing sequence, the multiplier, and the modulus. For each ciphertext number, apply the modular inverse of the multiplier modulo the modulus to adjust the sum, then determine the subset of the private key sequence that adds up to this value. Convert the resulting binary string back to letters:

Ciphertext: 181 151 631 559 840 181 859 540 559
Use private key sequence: 2, 3, 7, 14, 30, 57, 120, 251
Apply modular inverse and subset sum → Binary
Convert binary → ASCII letters

Plaintext: CATENCODE

Knapsack Cipher: Notes

The Knapsack Cipher illustrates the concept of trapdoor functions in early public-key cryptography. While the original Merkle-Hellman implementation was eventually broken due to structural weaknesses, it demonstrates how a mathematically hard problem, like the subset sum, can form the basis of a secure encryption scheme when properly implemented.