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

The cryptographic security of the Merkle-Hellman system (which is one of the two public-key cryptosystems proposed so far) has been a major open problem since 1976. In this paper we show that when the elements of the public key a_l,...,a_n are modular multiples of a superincreasing sequence (as proposed by Merkle and Hellman), almost all the equations of the form % MathType!MTEF!2!1!+- % feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWaaabCaeaaca % WG4bWaaSbaaSqaaiaadMgaaeqaaOGaamyyamaaBaaaleaacaWGPbaa % beaakiabg2da9iaadkgacaaMf8UaamiEamaaBaaaleaacaWGPbaabe % aakiabgIGiopaacmaabaGaaGimaiaacYcacaaIXaaacaGL7bGaayzF % aaaaleaacaaIXaGaeyypa0JaamiBaaqaaiaad6gaa0GaeyyeIuoaaa % a!4B7C! $$ \sum\limits_{1 = l}^n {{x_i}{a_i} = b\quad {x_i} \in \left\{ {0,1} \right\}} $$ can be solved in polynomia time, and thus the cleartexts x_l...x_n that correspond to given ciphertexts b can be easily found.