Merkle–Hellman knapsack cryptosystem

1. Choose a block size ${\displaystyle n}$. Integers up to ${\displaystyle n}$ bits in length can be encrypted with this key.

2. Choose a random superincreasing sequence of ${\displaystyle n}$ positive integers

${\displaystyle W=(w_{1},w_{2},\dots ,w_{n})}$

The superincreasing requirement means that ${\displaystyle w_{k}>\sum _{i=1}^{k-1}w_{i}}$, for ${\displaystyle 1<k\leq n}$.

3. Choose a random integer ${\displaystyle q}$ such that

${\displaystyle q>\sum _{i=1}^{n}w_{i}}$

4. Choose a random integer ${\displaystyle r}$ such that ${\displaystyle \gcd(r,q)=1}$ (that is, ${\displaystyle r}$ and ${\displaystyle q}$ are coprime).

5. Calculate the sequence

${\displaystyle B=(b_{1},b_{2},\dots ,b_{n})}$

where ${\displaystyle b_{i}=rw_{i}{\bmod {q}}}$.

The public key is ${\displaystyle B}$ and the private key is ${\displaystyle (W,q,r)}$.

Let ${\displaystyle m}$ be an ${\displaystyle n}$-bit message consisting of bits ${\displaystyle m_{1}m_{2}\dots m_{n}}$, with ${\displaystyle m_{1}}$ the highest order bit. Select each ${\displaystyle b_{i}}$ for which ${\displaystyle m_{i}}$ is nonzero, and add them together. Equivalently, calculate

${\displaystyle c=\sum _{i=1}^{n}m_{i}b_{i}}$.

The ciphertext is ${\displaystyle c}$.

To decrypt a ciphertext ${\displaystyle c}$, we must find the subset of ${\displaystyle B}$ which sums to ${\displaystyle c}$. We do this by transforming the problem into one of finding a subset of ${\displaystyle W}$. That problem can be solved in polynomial time since ${\displaystyle W}$ is superincreasing.

1. Calculate the modular inverse of ${\displaystyle r}$ modulo ${\displaystyle q}$ using the Extended Euclidean algorithm. The inverse will exist since ${\displaystyle r}$ is coprime to ${\displaystyle q}$.

${\displaystyle r':=r^{-1}{\pmod {q}}}$

The computation of ${\displaystyle r'}$ is independent of the message, and can be done just once when the private key is generated.

2. Calculate

${\displaystyle c':=cr'{\bmod {q}}}$

3. Solve the subset sum problem for ${\displaystyle c'}$ using the superincreasing sequence ${\displaystyle W}$, by the simple greedy algorithm described below. Let ${\displaystyle X=(x_{1},x_{2},\dots ,x_{k})}$ be the resulting list of indexes of the elements of ${\displaystyle W}$ which sum to ${\displaystyle c'}$. (That is, ${\displaystyle c'=\sum _{i=1}^{k}w_{x_{i}}}$.)

4. Construct the message ${\displaystyle m}$ with a 1 in each ${\displaystyle x_{i}}$ bit position and a 0 in all other bit positions:

${\displaystyle m=\sum _{i=1}^{k}2^{n-x_{i}}}$

This simple greedy algorithm finds the subset of a superincreasing sequence ${\displaystyle W}$ which sums to ${\displaystyle c'}$, in polynomial time:

1. Initialize ${\displaystyle X}$ to an empty list.

2. Find the largest element in ${\displaystyle W}$ which is less than or equal to ${\displaystyle c'}$, say ${\displaystyle w_{j}}$.

3. Subtract: ${\displaystyle c':=c'-w_{j}}$.

4. Append ${\displaystyle j}$ to the list ${\displaystyle X}$.

5. If ${\displaystyle c'}$ is greater than zero, return to step 2.

Create a key to encrypt 8-bit numbers by creating a random superincreasing sequence of 8 values:

${\displaystyle W=(2,7,11,21,42,89,180,354)}$

The sum of these is 706, so select a larger value for ${\displaystyle q}$:

${\displaystyle q=881}$.

Choose ${\displaystyle r}$ to be coprime to ${\displaystyle q}$:

${\displaystyle r=588}$.

Construct the public key ${\displaystyle B}$ by multiplying each element in ${\displaystyle W}$ by ${\displaystyle r}$ modulo ${\displaystyle q}$:

${\displaystyle {\begin{aligned}&(2*588){\bmod {8}}81=295\\&(7*588){\bmod {8}}81=592\\&(11*588){\bmod {8}}81=301\\&(21*588){\bmod {8}}81=14\\&(42*588){\bmod {8}}81=28\\&(89*588){\bmod {8}}81=353\\&(180*588){\bmod {8}}81=120\\&(354*588){\bmod {8}}81=236\end{aligned}}}$

Hence ${\displaystyle B=(295,592,301,14,28,353,120,236)}$.

Let the 8-bit message be ${\displaystyle m=97=01100001_{2}}$. We multiply each bit by the corresponding number in ${\displaystyle B}$ and add the results:

  0 * 295
+ 1 * 592
+ 1 * 301
+ 0 * 14
+ 0 * 28
+ 0 * 353
+ 0 * 120
+ 1 * 236
    = 1129

The ciphertext ${\displaystyle c}$ is 1129.

To decrypt 1129, first use the Extended Euclidean Algorithm to find the modular inverse of ${\displaystyle r}$ mod ${\displaystyle q}$:

${\displaystyle r'=r^{-1}{\bmod {q}}=588^{-1}{\bmod {8}}81=442}$.

Compute ${\displaystyle c'=cr'{\bmod {q}}=1129*442{\bmod {8}}81=372}$.

Use the greedy algorithm to decompose 372 into a sum of ${\displaystyle w_{i}}$ values:

${\displaystyle {\begin{aligned}c'&=372\\&w_{8}=354\leq 372\\c'&=372-354=18\\&w_{3}=11\leq 18\\c'&=18-11=7\\&w_{2}=7\leq 7\\c'&=7-7=0\end{aligned}}}$

Thus ${\displaystyle 372=354+11+7=w_{8}+w_{3}+w_{2}}$, and the list of indexes is ${\displaystyle X=(8,3,2)}$. The message can now be computed as

${\displaystyle m=\sum _{i=1}^{3}2^{n-x_{i}}=2^{8-8}+2^{8-3}+2^{8-2}=1+32+64=97}$.