Editing Merkle–Hellman knapsack cryptosystem (section)

==Cryptanalysis==
{{Expand section|date=September 2020}}
In 1984 Adi Shamir published an attack on the Merkle-Hellman cryptosystem which can decrypt encrypted messages in polynomial time without using the private key. <ref name="shamir">{{cite journal |last1=Shamir|first1=Adi|year=1984|title=A polynomial-time algorithm for breaking the basic Merkle - Hellman cryptosystem|journal=IEEE Transactions on Information Theory|volume=30|issue=5|pages= 699–704|doi=10.1109/SFCS.1982.5}}</ref> The attack analyzes the public key <math>B = (b_1, b_2, \dots, b_n)</math> and searches for a pair of numbers <math>u</math> and <math>m</math> such that <math>(u b_i \bmod m)</math> is a superincreasing sequence. The <math>(u,m)</math> pair found by the attack may not be equal to <math>(r',q)</math> in the private key, but like that pair it can be used to transform a hard knapsack problem using <math>B</math> into an easy problem using a superincreasing sequence. The attack operates solely on the public key; no access to encrypted messages is necessary.

Shamir's attack on the Merkle-Hellman cryptosystem works in polynomial time even if the numbers in the public key are randomly shuffled, a step which is usually not included in the description of the cryptosystem, but can be helpful against some more primitive attacks.