Merkle-Hellman cryptosystem

The Merkle-Hellman cryptosystem ( MH ) is an asymmetric encryption method published in 1978 that is based on the backpack problem. It was broken in 1983.

description

The Merkle-Hellman cryptosystem is one of the first asymmetric encryption methods and was developed by Ralph Merkle and Martin Hellman . In contrast to some other encryption methods (e.g. the RSA cryptosystem ), there is no analog method for digital signature here . Since this is an asymmetrical procedure, a public key is used for encryption, which is different from the secret key used for decryption.

The Merkle-Hellman cryptosystem is based on the backpack problem . Since the general backpack problem is an NP-hard problem, it is suitable for constructing a one-way function from it . A set of objects of different weights, which describe such a general backpack problem, serves as a public key. The secret key also consists of such a set of weights, which describe a simple backpack problem. In the secret key, the weights form a rapidly increasing vector that applies to all . A backpack problem described in this way can be easily solved in linear time using a greedy algorithm . The public key is calculated from the secret key. ${\displaystyle a}$ ${\displaystyle a_{i}>\sum _{k=1}^{i-1}a_{k}}$ ${\displaystyle i}$

Key generation

In the Merkle-Hellman cryptosystem, the keys are sets of objects with a certain weight. The public key formulates a 'difficult' problem, the private one a 'simple' backpack problem. If you combine the private key with two numbers, the multiplier and the module, you can turn the simple backpack problem into a difficult one. Since these two numbers are also needed to get the simple problem out of the difficult problem, these two numbers also belong to the private key. This transformation succeeds in polynomial time.

The public key can be obtained from the private key , the multiplier and the module as follows: ${\displaystyle A}$ ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle B}$ ${\displaystyle B_{i}=\left(A_{i}\cdot n\right)\mod {m}}$

The multiplier and the module should be coprime. The easiest way to do this is to choose a prime number as the module. In addition, the module should be a number that is greater than the sum of the elements of the backpack. ${\displaystyle n}$ ${\displaystyle m}$

Encryption

The public key is used to encrypt a message. We assume that the message to be encrypted is in a binary format. This is then divided into blocks , the size of which corresponds to the size of the number of objects in the public key. Each of these blocks is individually encrypted with the public key. If an element in the key corresponds to one in the block, these elements are added to the result value. ${\displaystyle b_{i}=(x_{1},\ldots ,x_{\left\vert B\right\vert })}$ ${\displaystyle 1}$

${\displaystyle C_{i}=\sum _{k=1}^{\left\vert B\right\vert }B_{k}\cdot {b_{i}}_{k}}$

The values then result in the ciphertext. ${\displaystyle C_{i}}$

Decryption

Decryption is possible because the multiplier and module used to generate the public key can also be used to transform the ciphertext into a sum of elements of the simple backpack problem. A naive greedy algorithm can then be used to determine which elements of the private key appear in the sum. ${\displaystyle C_{i}}$ ${\displaystyle D_{i}}$

${\displaystyle D_{i}=\sum _{k=1}^{\left\vert A\right\vert }A_{k}\cdot {b_{i}}_{k}}$

To calculate that, you need the inverse of the multiplier such that . This inverse can be calculated with the extended Euclidean algorithm . ${\displaystyle D_{i}}$ ${\displaystyle n^{-1}}$ ${\displaystyle n}$ ${\displaystyle n\cdot n^{-1}\equiv 1\mod {m}}$

${\displaystyle D_{i}=\left(C_{i}\cdot n^{-1}\right)\mod {m}}$

The plain text is then created again from the bits that correspond to the elements from the private key and result in the sum . ${\displaystyle D_{i}}$

example

Key generation

Choosing a private key. This must be a rapidly growing vector.

${\displaystyle A=\left\{2,3,6,13,27,52\right\}}$

Furthermore, the multiplier and the module are required. ${\displaystyle n}$ ${\displaystyle m}$

${\displaystyle n=31}$

${\displaystyle m=105}$

Now you can calculate the public key:

${\displaystyle {\begin{aligned}\left(2\cdot 31\right)\mod {105}&=62\\\left(3\cdot 31\right)\mod {105}&=93\\\left(6\cdot 31\right)\mod {105}&=81\\\left(13\cdot 31\right)\mod {105}&=88\\\left(27\cdot 31\right)\mod {105}&=102\\\left(52\cdot 31\right)\mod {105}&=37\\\end{aligned}}}$

The public key is thus:

${\displaystyle B=\left\{62,93,81,88,102,37\right\}}$

Encryption

If a text is to be encrypted, it is broken down into blocks of the same length as that of the key. For the example we use the text 011000 110101 101110.

${\displaystyle b=011000110101101110}$

${\displaystyle b_{1}=011000}$

${\displaystyle b_{2}=110101}$

${\displaystyle b_{3}=101110}$

${\displaystyle B=\left\{62,93,81,88,102,37\right\}}$

Now a bit from the block ${\displaystyle b_{1}}$ determines whether the corresponding element from the key is included in the ciphertext:

0	1	1	0	0	0
62	93	81	88	102	37
0	93	81	0	0	0	Total: 174

block ${\displaystyle b_{2}}$

1	1	0	1	0	1
62	93	81	88	102	37
62	93	0	88	0	37	Total: 280

block ${\displaystyle b_{3}}$

1	0	1	1	1	0
62	93	81	88	102	37
62	0	81	88	102	0	Total: 333

The ciphertext is then 174, 280, 333. ${\displaystyle C}$

Decryption

To decrypt a ciphertext we need the private key as well as the multiplier and the module . The inverse is calculated from the multiplier and the module . This works with the extended Euclidean algorithm . For the given values ​​of and we get ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle n^{-1}}$ ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle n^{-1}=61}$

${\displaystyle n^{-1}=61}$

${\displaystyle \left(174\cdot 61\right)\mod {105}=9}$

${\displaystyle \left(280\cdot 61\right)\mod {105}=70}$

${\displaystyle \left(333\cdot 61\right)\mod {105}=48}$

${\displaystyle D=\left\{9,70,48\right\}}$

To do this, they are simply viewed as the sum of the elements of the private key. Now we subtract the largest element from this sum from the key, which is less than or equal to the sum . When we're through the list, it should add up. If it doesn't, an attempt was made to decrypt the text with the wrong key. The elements that we have subtracted from are counted as, those that are not used are counted as well. ${\displaystyle D_{i}}$ ${\displaystyle D_{i}}$ ${\displaystyle 0}$ ${\displaystyle D_{i}}$ ${\displaystyle 1}$ ${\displaystyle 0}$

The plain text for the block ${\displaystyle D_{1}}$ can then be restored as follows:

2	3	6th	13	27	52
0	3	6th	0	0	0	Total: 9
0	1	1	0	0	0	Plain text

block ${\displaystyle D_{2}}$

2	3	6th	13	27	52
2	3	0	13	0	52	Total: 70
1	1	0	1	0	1	Plain text

block ${\displaystyle D_{3}}$

2	3	6th	13	27	52
2	0	6th	13	27	0	Total: 48
1	0	1	1	1	0	Plain text

The plain text is 011000 110101 101110.

history

The process, also known as the Knapsack algorithm , was invented in 1978 by Ralph Merkle and Martin Hellman . It seemed to be establishing itself as a competitor to RSA and the Diffie-Hellman algorithm , but was broken in theory and practice (on an Apple II ) by Adi Shamir and Richard Zippel in 1983 . Even an iterated method in which the weights are transformed several times with different pairs of multipliers and modules in order to generate the 'difficult' backpack problem can be successfully attacked with polynomial effort.

literature

• Bruce Schneier: Applied Cryptography: protocols, algorithms, and source code in C. 2nd edition. John Wiley & Sons, New York 1995, ISBN 0-471-11709-9 , pp. 462-466.

Individual evidence

1. ↑ Ralph Merkle, Martin Hellman: Hiding information and signatures in trapdoor knapsacks. In: Information Theory, IEEE Transactions. Vol. 24, No. 5, Sep 1978, pp. 525-530. (online at: ieeexplore.ieee.org )
2. ^ Adi Shamir: A polynomial-time algorithm for breaking the basic Merkle - Hellman cryptosystem . In: Information Theory, IEEE Transactions Edition . tape 30 , no. 5 , 1984, pp. 699-704 , doi : 10.1109 / SFCS.1982.5 .
3. ^ Leonard M. Adleman: On Breaking the Iterated Merkle-Hellman Public-Key Cryptosystem . In: Advances in Cryptology: Proceedings of CRYPTO '82 . Plenum Press, 1982, pp. 303-308 .