Merkle–Hellman knapsack cryptosystem
The Merkle -Hellman cryptosystem (MH ) is an asymmetric encryption scheme which is based on the knapsack problem.
- 2.1 Key Generation
- 2.2 encryption
- 2.3 decryption
Description
The Merkle -Hellman cryptosystem is one of the first asymmetric encryption method and was developed by Ralph Merkle and Martin Hellman. Unlike some other encryption methods (eg the RSA cryptosystem ) there is no analogous method for the digital signature. Because it is an asymmetric process, a public key is used for encryption of that used by the decryption and the secret key is different.
The Merkle -Hellman cryptosystem is based on the knapsack problem. Since the general knapsack problem is NP-hard problem, it is suitable to construct a one-way function thereof. It serves a lot of objects of different weights, which describe such a general knapsack problem, as the public key. The private key is also from such a set of weights, but which describe a simple knapsack problem. In the secret key of the weights form a strong increase in vector applies to the for all. A knapsack problem as described is easily solved by a greedy algorithm in linear time. The public key is calculated from the secret key.
Key generation
The Merkle -Hellman cryptosystem the key quantities of goods are of a certain weight. The public key formulated a ' heavy ', the private one ' simple ' knapsack problem. Combining the private key with two numbers, the multiplier and the module, you can for the simple knapsack problem construct a heavy. Since these two numbers are also used to gain from the severe problem, the simple, include these two numbers also to the private key. This transformation is possible in polynomial time.
From the private key, the multiplier and the module 's public key is obtained as follows:
Here, the multiplier and the modulus should be prime. The easiest way to this is the fact that one chooses as a module a prime number. In addition, the module should be a number that is greater than the sum of the elements of the backpack.
Encoding
To encrypt a message using the public key. We assume that the message to be encrypted is in a binary format. This is then divided into blocks whose size is the size of the quantity of items in the public key complies. Each of these blocks is individually encrypted with the public key. Now corresponds to an element in the key with the block, then these elements are added to the result value.
The values are obtained then the ciphertext.
Decryption
The decryption is possible, because of the multiplier and modulus that are used for the generation of the public key can also be used to transform the ciphertext into a sum of elements of simple knapsack problem. Then, a naive greedy algorithm can then be used to determine which items occur of the private key in the amount.
To calculate, it takes the inverse of the multiplier, so that. This inverse can be computed with the extended Euclidean algorithm.
The plaintext is created again from the bits that correspond to elements of the private key and the resulting sum.
Example
Key generation
Select a private key. This must be a rapidly growing vector.
Furthermore, the multiplier and modulus are still needed.
Now one can compute the public key:
This means that the public key as follows:
Encoding
If a text is encrypted, so this is broken down as the key into blocks of the same length. For example, we use the text 011000 110101 101110th
Well definitely a bit out of the block if the corresponding element from the key goes into the ciphertext:
Block
Block
The ciphertext is then 174, 280, 333
Decryption
To decrypt a ciphertext, we need the private key as well as the multiplier and modulus. From the multiplier and the module is the inverse calculated. This goes with the extended Euclidean algorithm. For the given values of and results
For this purpose, the sum of elements of the public key can be easily viewed. Now we draw from this sum the largest element from the key off, which is less than or equal to the sum. When we are through the list, the sum should be obtained. If it does not, the text with a wrong key was attempted to decipher. The items that we have to be deducted from, as counted, those who are not in use are, however, counted with.
For the block, the plaintext can then restore as follows:
Block
Block
The plaintext is therefore 011000 110101 101110th
History
Also known under the name Knapsack algorithm method was invented in 1978 by Ralph Merkle and Martin Hellman. It seemed to establish itself as a competitor to RSA and the Diffie- Hellman algorithm, but was broken in 1983 by Adi Shamir and Richard Zippel in theory and practice ( on an Apple II). Even an iterated process in which the weights are repeatedly transformed with different pairs of multipliers and modules to generate the ' difficult ' knapsack problem can be successfully attacked with polynomial complexity.