A simple and efficient attack on the Merkle-Hellman knapsack cryptosystem

Jingguo Bi, Lei Su, Haipeng Peng and Lin Wang

PLOS ONE, 2025, vol. 20, issue 5, 1-14

Abstract: The Merkle-Hellman knapsack cryptosystem was one of the two earliest public key cryptosystems, which was invented by Merkle and Hellman in 1978. One can recover the equivalent keys by using Shamir’s method. The most time-consuming part of Shamir’s attack is to recover the critical intermediate parameters by solving an integer programming problem with a fixed number of variables, whose worst-case complexity is exponential of the number of variables. In this paper, we present an improved algorithm to analyze the basic Merkle-Hellman public key cryptosystem. The main idea is to recover a partial super-increasing sequence as equivalent private key, which is the main difference from Shamir’s. More precisely, we first obtain a super-increasing sequence by invoking the LLL algorithm on a special lattice with a small dimension. We can recover most part of the plaintext from the tail by solving the super-increasing knapsack problem. Finally, we get the first part of plaintext by solving a size-reduced knapsack problem. Experimental data shows that one can recover the whole plaintext in less than 1 second on a laptop for the typical parameters of the Merkle-Hellman cryptosystem, whose time complexity is reduced by a polynomial level compared with Shamir’s algorithm.

Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0322726 (text/html)
https://journals.plos.org/plosone/article/file?id= ... 22726&type=printable (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:plo:pone00:0322726

DOI: 10.1371/journal.pone.0322726

Access Statistics for this article

More articles in PLOS ONE from Public Library of Science
Bibliographic data for series maintained by plosone ().