Merkle–Hellman is an asymmetric-key cryptosystem, meaning that two keys are required for communication: a public key and a private key. Furthermore, unlike RSA, it is one-way: the public key is used only for encryption, and the private key is used only for decryption. Thus it is unusable for authentication by cryptographic signing. The Merkle–Hellman system is based on the subset sum problem. The problem is as follows: given a set of numbers and a number b, find a subset of which sums to b. In general, this problem is known to be NP-complete. However, if the set of numbers is superincreasing, meaning that each element of the set is greater thanthe 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.
Key generation
In Merkle–Hellman, the keys are two knapsacks. The public key is a 'hard' knapsack, and the private key is an 'easy', or superincreasing, knapsack, combined with two additional numbers, a multiplier and a modulus. The multiplier and modulus can be used to convert the superincreasing knapsack into the hard knapsack. These same numbers are used to transform the sum of the subset of the hard knapsack into the sum of the subset of the easy knapsack, which is a problem that is solvable in polynomial time.
Encryption
To encrypt a message, a subset of the hard knapsack is chosen by comparing it with a set of bits equal in length to the key. Each term in the public key that corresponds to a 1 in the plaintext is an element of the subset, while terms that corresponding to 0 in the plaintext are ignored when constructing – they are not elements of the key. The elements of this subset are added together and the resulting sum is the ciphertext.
Decryption
Decryption is possible because the multiplier and modulus used to transform the easy knapsack into the public key can also be used to transform the number representing the ciphertext into the sum of the corresponding elements of the superincreasing knapsack. Then, using a simple greedy algorithm, the easy knapsack can be solved using O arithmetic operations, which decrypts the message. To encrypt n-bit messages, choose a superincreasing sequence of n nonzero natural numbers. Pick a random integer q, such that and a random integer, r, such that gcd = 1. q is chosen this way to ensure the uniqueness of the ciphertext. If it is any smaller, more than one plaintext may encrypt to the same ciphertext. Since q is larger than the sum of every subset of w, no sums are congruent mod q and therefore none of the private key's sums will be equal. r must be coprime to qor else it will not have an inverse modq. The existence of the inverse of r is necessary so that decryption is possible. Now calculate the sequence where The public key is β, while the private key is.
Encryption
To encrypt an n-bit message where is the i-th bit of the message and, calculate The ciphertext then is c.
Decryption
In order to decrypt a ciphertext c a receiver has to find the message bits αi such that they satisfy This would be a hard problem if the βi were random values because the receiver would have to solve an instance of the subset sum problem, which is known to be NP-hard. However, the values βi were chosen such that decryption is easy if the private key is known. The key to decryption is to find an integer s that is the modular inverse of r modulo q. That means s satisfies the equation sr mod q = 1 or equivalently there exist an integer k such that sr = kq + 1. Since r was chosen such that gcd=1 it is possible to find s and k by using the Extended Euclidean algorithm. Next the receiver of the ciphertext c computes Hence Because of rs mod q = 1 and βi = rwi mod q follows Hence The sum of all values wi is smaller thanq and hence is also in the interval . Thus the receiver has to solve the subset sum problem This problem is easy because w is a superincreasing sequence. Take the largest element in w, say wk. If wk > c' , then αk = 0, if wk≤c' , then αk = 1. Then, subtract wk×αk from c' , and repeat these steps until you have figured out α.
Example
First, a superincreasing sequence w is created w = This is the basis for a private key. From this, calculate the sum. Then, choose a number q that is greater than the sum. q = 881 Also, choose a number r that is in the range and is coprime to q. r = 588 The private key consists of q, w and r. To calculate a public key, generate the sequence β by multiplying each element in w by r mod q β = because mod 881 = 295 mod 881 = 592 mod 881 = 301 mod 881 = 14 mod 881 = 28 mod 881 = 353 mod 881 = 120 mod 881 = 236 The sequence β makes up the public key. Say Alice wishes to encrypt "a". First, she must translate "a" to binary 01100001 She multiplies each respective bit by the corresponding number in β a = 01100001 0 * 295 + 1 * 592 + 1 * 301 + 0 * 14 + 0 * 28 + 0 * 353 + 0 * 120 + 1 * 236 = 1129 She sends this to the recipient. To decrypt, Bob multiplies 1129 by r−1 mod 1129 * 442 mod 881 = 372 Now Bob decomposes 372 by selecting the largest element in w which is less than or equal to 372. Then selecting the next largest element less than or equal to the difference, until the difference is : 372 - 354 = 18 18 - 11 = 7 7 - 7 = 0 The elements we selected from our private key correspond to the 1 bits in the message 01100001 When translated back from binary, this "a" is the final decrypted message.
