Editing Merkle–Hellman knapsack cryptosystem (section)

==Description==
Merkle–Hellman is a public key cryptosystem, meaning that two keys are used, a public key for encryption and a private key for decryption. It is based on the [[subset sum problem]] (a special case of the [[knapsack problem]]).<ref>{{cite web
| url=http://math.ucdenver.edu/~wcherowi/courses/m5410/ctcknap.html
| title=Merkle-Hellman Knapsack Cryptosystem 
| date=2002-03-02
| first=William
| last=Cherowitzo
| work=Math 5410 - Modern Cryptology
| access-date=2019-08-18}}</ref> The problem is as follows: given a set of integers <math>A</math> and an integer <math>c</math>, find a subset of <math>A</math> which sums to <math>c</math>. In general, this problem is known to be [[NP-complete]]. However, if <math>A</math> is [[Superincreasing sequence|superincreasing]], meaning that each element of the set is greater than the sum of all the numbers in the set lesser than it, the problem is "easy" and solvable in polynomial time with a simple [[greedy algorithm]].

In Merkle–Hellman, decrypting a message requires solving an apparently "hard" knapsack problem. The private key contains a superincreasing list of numbers <math>W</math>, and the public key contains a non-superincreasing list of numbers <math>B</math>, which is actually a "disguised" version of <math>W</math>. The private key also contains some "trapdoor" information that can be used to transform a hard knapsack problem using <math>B</math> into an easy knapsack problem using <math>W</math>.

Unlike some other public key cryptosystems such as [[RSA (cryptosystem)|RSA]], the two keys in Merkle-Hellman are not interchangeable; the private key cannot be used for encryption. Thus Merkle-Hellman is not directly usable for authentication by [[Digital signature|cryptographic signing]], although Shamir published a variant that can be used for signing.<ref>{{cite journal |first=Adi |last=Shamir |title=A Fast Signature Scheme |date=July 1978 |journal=MIT Laboratory for Computer Science Technical Memorandum |volume=79 |issue=MIT/LCS/TM–107|page=15240 |bibcode=1978STIN...7915240S }}</ref>

===Key generation===
1. Choose a block size <math>n</math>. Integers up to <math>n</math> bits in length can be encrypted with this key.

2. Choose a random superincreasing sequence of <math>n</math> [[positive integers]]
:<math>W = ( w_1, w_2, \dots, w_n )</math>
:The superincreasing requirement means that <math>w_k > \sum_{i = 1}^{k-1} w_i</math>, for <math>1 < k \le n</math>.

3. Choose a random integer <math>q</math> such that
: <math>q > \sum_{i = 1}^n w_i</math>

4. Choose a random integer <math>r</math> such that <math>\gcd(r,q) = 1</math> (that is, <math>r</math> and <math>q</math> are [[coprime]]).

5. Calculate the sequence
:<math>B = ( b_1, b_2, \dots, b_n )</math>
:where <math>b_i = r w_i \bmod q</math>.

The public key is <math>B</math> and the private key is <math>(W,q,r)</math>.

===Encryption===
Let <math>m</math> be an <math>n</math>-bit message consisting of bits <math>m_1 m_2 \dots m_n</math>, with <math>m_1</math> the highest order bit. Select each <math>b_i</math> for which <math>m_i</math> is nonzero, and add them together. Equivalently, calculate
:<math>c = \sum_{i = 1}^n m_i b_i</math>.
The ciphertext is <math>c</math>.

===Decryption===
To decrypt a ciphertext <math>c</math>, we must find the subset of <math>B</math> which sums to <math>c</math>. We do this by transforming the problem into one of finding a subset of <math>W</math>. That problem can be solved in polynomial time since <math>W</math> is superincreasing.

1. Calculate the [[modular inverse]] of <math>r</math> modulo <math>q</math> using the [[Extended Euclidean algorithm]]. The inverse will exist since <math>r</math> is coprime to <math>q</math>.
:<math>r' := r^{-1} \pmod q</math>
:The computation of <math>r'</math> is independent of the message, and can be done just once when the private key is generated.

2. Calculate
:<math>c' := c r' \bmod q</math>

3. Solve the subset sum problem for <math>c'</math> using the superincreasing sequence <math>W</math>, by the simple greedy algorithm described below. Let <math>X = (x_1, x_2, \dots, x_k)</math> be the resulting list of indexes of the elements of <math>W</math> which sum to <math>c'</math>. (That is, <math>c' = \sum_{i=1}^k w_{x_i}</math>.)

4. Construct the message <math>m</math> with a 1 in each <math>x_i</math> bit position and a 0 in all other bit positions:
:<math>m = \sum_{i=1}^k 2^{n-x_i}</math>

====Solving the subset sum problem====
This simple greedy algorithm finds the subset of a superincreasing sequence <math>W</math> which sums to <math>c'</math>, in polynomial time:

:1. Initialize <math>X</math> to an empty list.

:2. Find the largest element in <math>W</math> which is less than or equal to <math>c'</math>, say <math>w_j</math>.

:3. Subtract: <math>c' := c' - w_j</math>.

:4. Append <math>j</math> to the list <math>X</math>.

:5. Remove <math>w_j</math> from the superincreasing sequence <math>W</math>

:6. If <math>c'</math> is greater than zero, return to step 2.

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