Editing Merkle–Hellman knapsack cryptosystem (section)

===Example===
====Key generation====
Create a key to encrypt 8-bit numbers by creating a random superincreasing sequence of 8 values:
:<math>W = ( 2, 7, 11, 21, 42, 89, 180, 354 )</math>
The sum of these is 706, so select a larger value for <math>q</math>:
:<math>q = 881</math>.
Choose <math>r</math> to be coprime to <math>q</math>: 
:<math>r = 588</math>.

Construct the public key <math>B</math> by multiplying each element in <math>W</math> by <math>r</math> modulo <math>q</math>:

:<math>\begin{align}
&(2 * 588) \bmod 881 = 295 \\
&(7 * 588) \bmod 881 = 592 \\
&(11 * 588) \bmod 881 = 301 \\
&(21 * 588) \bmod 881 = 14 \\
&(42 * 588) \bmod 881 = 28 \\
&(89 * 588) \bmod 881 = 353 \\
&(180 * 588) \bmod 881 = 120 \\
&(354 * 588) \bmod 881 = 236
\end{align}</math>

Hence <math>B = ( 295, 592, 301, 14, 28, 353, 120, 236 )</math>.

====Encryption====
Let the 8-bit message be <math>m = 97 = 01100001_2</math>. We multiply each bit by the corresponding number in <math>B</math> and add the results:
   0 * 295
 + 1 * 592
 + 1 * 301
 + 0 * 14
 + 0 * 28
 + 0 * 353
 + 0 * 120
 + 1 * 236
     = 1129
The ciphertext <math>c</math> is 1129.

====Decryption====
To decrypt 1129, first use the Extended Euclidean Algorithm to find the modular inverse of <math>r</math> mod <math>q</math>:
:<math>r' = r^{-1} \bmod q = 588^{-1} \bmod 881 = 442</math>. 

Compute <math>c' = c r' \bmod q = 1129*442 \bmod 881 = 372</math>. 

Use the greedy algorithm to decompose 372 into a sum of <math>w_i</math> values:
:<math>\begin{align}
c' &= 372 \\
& w_8 = 354 \le 372  \\
c' &= 372-354 = 18 \\
& w_3 = 11 \le 18 \\
c' &= 18-11 = 7 \\
& w_2 = 7 \le 7 \\
c' &= 7-7 = 0
\end{align}</math>
Thus <math>372 = 354 + 11 + 7 = w_8 + w_3 + w_2</math>, and the list of indexes is <math>X = (8,3,2)</math>. The message can now be computed as
:<math>m = \sum_{i=1}^3 2^{n-x_i} = 2^{8-8} + 2^{8-3} + 2^{8-2} = 1 + 32 + 64 = 97</math>.