A Polynomial Time Algorithm for Breaking the Basic Merkle-Hellman Cryptosystem

The cryptographic security of the Merkle-Hellman cryptosystem has been a major open problem since 1976. In this paper we show that the basic variant of this cryptosystem, in which the elements of the public key are modular multiples of a superincreasing sequence, is breakable in polynomial time.

Authors

• Adi Shamir

Keywords

• Polynomials
• Public key cryptography
• Security
• Mathematics
• Public key
• Performance analysis
• Protection
• Communication channels
• Greedy algorithms
• H infinity control
• Upper Bound
• Conditional Probability
• Sequence Elements
• Uniform Density
• Subintervals
• Linear Inequalities
• Problem Instances
• Independent Random Variables
• Limit Point
• Part Of Algorithm
• Sawtooth
• Worst-case Complexity
• Encryption Key
• Integer Programming Problem
• Correct Guesses