 Merkle–Hellman knapsack cryptosystem

The Merkle–Hellman knapsack cryptosystem was one of the earliest public key cryptosystems invented by Ralph Merkle and Martin Hellman in 1978.^{[1]} Although its ideas are elegant, and far simpler than RSA, it has been broken.^{[2]}
Contents
Description
MerkleHellman is an asymmetrickey cryptosystem, meaning that for communication, two keys are required: a public key and a private key. Furthermore, unlike RSA, it is oneway—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 MerkleHellman system is based on the subset sum problem (a special case of the knapsack problem). The problem is as follows: given a set of numbers A and a number b, find a subset of A, which sums to b. In general, this problem is known to be NPcomplete. However, if the set of numbers (called the knapsack) is superincreasing — that is, each element of the set is greater than the sum of all the numbers before it — the problem is 'easy' and solvable in polynomial time with a simple greedy algorithm.
Key generation
In MerkleHellman, the keys are 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, which were 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 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 (the plaintext) equal in length to the key, and making each term in the public key that corresponds to a 1 in the plaintext an element of the subset, while ignoring the terms corresponding to 0 terms in the plaintext. The elements of this subset are added together and the resulting sum is the cyphertext.
Decryption
Decryption is possible because the multiplier and modulus used to transform the easy, superincreasing 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(n) arithmetic operations, which decrypts the message.
Mathematical method
Key generation
To encrypt nbit messages, choose a superincreasing sequence
 w = (w_{1}, w_{2}, ..., w_{n})
of n nonzero natural numbers. Pick a random integer q, such that
 ,
and a random integer, r, such that gcd(r,q) = 1 (i.e. r and q are coprime).
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. r must be coprime to q or else it will not have an inverse mod q. The existence of the inverse of r is necessary so that decryption is possible.
Now calculate the sequence
 β = (β_{1}, β_{2}, ..., β_{n})
where
 β_{i} = rw_{i} mod q.
The public key is β, while the private key is (w, q, r).
Encryption
To encrypt an nbit message
 α = (α_{1}, α_{2}, ..., α_{n}),
where α_{i} is the ith bit of the message and {0, 1}, calculate
The cryptogram 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 NPhard. However, the values β_{i} were chosen such that decryption is easy if the private key (w, q, r) 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 s r mod q = 1 or equivalently there exist an integer k such that sr = kq + 1. Since r was chosen such that gcd(r,q)=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} = rw_{i} mod q follows
Hence
The sum of all values w_{i} is smaller than q and hence is also in the interval [0,q1]. 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 w_{k}. If w_{k} > c' , then α_{k} = 0, if w_{k}≤c' , then α_{k} = 1. Then, subtract w_{k}×α_{k} from c' , and repeat these steps until you have figured out α.
Example
First, a superincreasing sequence w is created
w = {2, 7, 11, 21, 42, 89, 180, 354}
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 [1,q) 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
β = {295, 592, 301, 14, 28, 353, 120, 236}
because
2 * 588 mod 881 = 295 7 * 588 mod 881 = 592 11 * 588 mod 881 = 301 21 * 588 mod 881 = 14 42 * 588 mod 881 = 28 89 * 588 mod 881 = 353 180 * 588 mod 881 = 120 354 * 588 mod 881 = 236
The sequence β makes up the public key.
Say Alice wishes to encrypt "a". First, she must translate "a" to binary (in this case, using ASCII or UTF8)
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 = 1129She sends this to the recipient.
To decrypt, Bob multiplies 1129 by r ^{−1} mod q (See Modular inverse)
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 0:
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.
References
 ^ Merkle, Ralph and Martin Hellman, "Hiding information and signatures in trapdoor knapsacks," Information Theory, IEEE Transactions on, vol.24, no.5, pp. 525530, Sep 1978 URL: http://ieeexplore.ieee.org/search/freesrchabstract.jsp?tp=&arnumber=1055927
 ^ Shamir, Adi, "A polynomialtime algorithm for breaking the basic Merkle  Hellman cryptosystem," Information Theory, IEEE Transactions on, vol.30, no.5, pp. 699704, Sep 1984 URL: http://ieeexplore.ieee.org/search/freesrchabstract.jsp?tp=&arnumber=4568386
Publickey cryptography Algorithms Benaloh · Blum–Goldwasser · Cayley–Purser · CEILIDH · Cramer–Shoup · Damgård–Jurik · DH · DSA · EPOC · ECDH · ECDSA · EKE · ElGamal (encryption · signature scheme) · GMR · Goldwasser–Micali · HFE · IES · Lamport · McEliece · Merkle–Hellman · MQV · Naccache–Stern · NTRUEncrypt · NTRUSign · Paillier · Rabin · RSA · Okamoto–Uchiyama · Schnorr · Schmidt–Samoa · SPEKE · SRP · STS · Threepass protocol · XTR
Theory Standardization ANS X9F1 · CRYPTREC · IEEE P1363 · NESSIE · NSA Suite B
Topics Digital signature · OAEP · Fingerprint · PKI · Web of trust · Key size
Cryptography Categories: Asymmetrickey cryptosystems
 Publickey cryptography
Wikimedia Foundation. 2010.
Look at other dictionaries:
MerkleHellman — (MH) was one of the earliest public key cryptosystems and was invented by Ralph Merkle and Martin Hellman in 1978. [Ralph Merkle and Martin Hellman, Hiding Information and Signatures in Trapdoor Knapsacks, IEEE Trans. Information Theory , 24(5),… … Wikipedia
MerkleHellmanKryptosystem — Das Merkle Hellman Kryptosystem (MH) ist ein asymmetrisches Verschlüsselungsverfahren, das auf dem Rucksackproblem basiert. Inhaltsverzeichnis 1 Beschreibung 1.1 Schlüsselerzeugung 1.2 Verschlüsselung … Deutsch Wikipedia
Naccache–Stern knapsack cryptosystem — Note: this is not to be confused with the Naccache–Stern cryptosystem based on the higher residuosity problem. The Naccache–Stern Knapsack Cryptosystem is an atypical public key cryptosystem developed by David Naccache and Jacques Stern in 1997.… … Wikipedia
Merkle — can refer to any of the following: Merkle, a pioneer motorcycle manufacturer Merkle–Damgård construction – A method to build cryptographic hash functions. Merkle–Hellman knapsack cryptosystem Merkle s Puzzles Surnames This page or section lists… … Wikipedia
Knapsack problem — BKP redirects here. For other uses, see BKP (disambiguation). Example of a one dimensional (constraint) knapsack problem: which boxes should be chosen to maximize the amount of money while still keeping the overall weight under or equal to… … Wikipedia
Naccache–Stern cryptosystem — Note: this is not to be confused with the Naccache–Stern knapsack cryptosystem. The Naccache–Stern cryptosystem is a homomorphic public key cryptosystem whose security rests on the higher residuosity problem. The Naccache–Stern cryptosystem was… … Wikipedia
Niederreiter cryptosystem — In cryptography, the Niederreiter cryptosystem is a variation of the McEliece Cryptosystem developed in 1986 by Harald Niederreiter [1]. It applies the same idea to the parity check matrix H of a linear code. Niederreiter is equivalent to… … Wikipedia
Publickey cryptography — In an asymmetric key encryption scheme, anyone can encrypt messages using the public key, but only the holder of the paired private key can decrypt. Security depends on the secrecy of that private key … Wikipedia
Outline of cryptography — See also: Index of cryptography articles The following outline is provided as an overview of and topical guide to cryptography: Cryptography (or cryptology) – practice and study of hiding information. Modern cryptography intersects the… … Wikipedia
Topics in cryptography — This article is intended to be an analytic glossary , or alternatively, an organized collection of annotated pointers.Classical ciphers*Autokey cipher *Permutation cipher*Polyalphabetic substitution **Vigenère cipher*Polygraphic substitution… … Wikipedia