Proceedings of International Conference on Applied Innovation in IT  ·  2026/06/12  ·  Vol. 14  ·  Issue 4  ·  pp. 471–476
Cryptanalysis of the Merkle-Hellman Knapsack Cryptosystem Using Continued Fraction: Two Attack Scenarios
Rana Abdul Latif, Rifaat Z. Khalaf and Aqeel Ismael Hasan
This paper presents a mathematical cryptanalysis of the Merkle-Hellman knapsack cryptosystem: using continued fractions as the sole analytical tool. We explore two distinct attack scenarios: (1) partial knowledge of the private key, and (2) access to the public key only. In both cases, we demonstrate how continued fractions can be used to approximate the transformation ratio r⁄q, enabling recovery of the secret parameters and the original super increasing sequence. Our results show that this approach is effective under certain conditions. The aim of this section is to evaluate the effectiveness of our method in two different cases of attacker knowledge. In the first case, the attacker knows the public key and only one element of the private key (the increasing sequence). In the second case, the attacker knows only the public key. These two cases will be presented in detail in the experiments section to measure the efficiency of the proposed method under different levels of the attacker knowledge. Furthermore, our method was compared with other well-known attacks on the Merkle-Hellman cryptosystem, and the results demonstrated the proposed approach achieves high efficiently for analyzing this type of encryption scheme.
Merkle-Hellman Knapsack Continued Fractions Public-Key Cryptography
References
  1. J. Bi, L. Su, H. Peng, and L. Wang, “A simple and efficient attack on the Merkle-Hellman knapsack cryptosystem,” PLOS ONE, vol. 20, no. 5, p. e0322726, 2025.
  2. A. A. Khaleell, “Secure knapsack cryptosystem against LLL algorithm based on continued fraction,” 2024.
  3. H. Tahiri Alaoui, A. Azouaoui, and J. El Kafi, “Artificial neural networks cryptanalysis of Merkle-Hellman knapsack cryptosystem,” Lecture Notes in Networks and Systems, vol. 637, 2023.
  4. H. Grari, S. Lamzabi, A. Azouaoui, and K. Zine-dine, “Cryptanalysis of Merkle-Hellman cipher using ant colony optimization,” IAES Int. J. Artif. Intell. (IJ-AI), vol. 10, no. 2, pp. 490-500, Jun. 2021, [Online]. Available: https://doi.org/10.11591/ijai.v10.i2.pp490-500.
  5. G. Anantharaman and J. Ding, “Camera zoom-based paper-pencil cipher encryption scheme atop Merkle-Hellman knapsack cryptosystem,” 2025.
  6. M. Zheng, Y. Feng, A. Nitaj, and Y. Pan, “Improving RSA cryptanalysis: Combining continued fractions and Coppersmith’s techniques,” 2025.
  7. G. Romeo, “Continued fractions in the field of p-adic numbers,” Bulletin of the American Mathematical Society, vol. 61, no. 2, p. 343, 2024.
  8. T. Sauer, Continued Fraction, Version 1.0, University of Passau, Mar. 26, 2019.
  9. A. D. Kumar and R. Sivaraman, “On some properties of fabulous fraction tree,” Mathematics and Statistics, vol. 10, no. 3, pp. 477-485, 2022.
  10. C. Elsner and C. R. M. Havens, Continued Fraction: A Modern and Classical Journey into the World of Siegel’s Continued Fraction. Cham, Switzerland: Springer, 2025.
  11. R. Z. Khalaf, H. B. Habib, and T. A. Jawad, “Attacking the Knapsack Public-key Cryptosystem,” Webology, vol. 19, no. 1, pp. 5302-5309, 2022.


Proceedings of the International Conference on Applied Innovations in IT by Anhalt University of Applied Sciences is licensed under CC BY-SA 4.0
 ·  This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License

ICAIIT 2026
International Conference on Applied Innovation in IT
Navigation
Publisher
ISSN2199-8876
Location Anhalt University of Applied Sciences
Phone +49 (0) 3496 67 5611
Address Building 01, Room 425
Bernburger Str. 55
D-06366 Köthen, Germany
Open Access License

All works are licensed under the Creative Commons Attribution-ShareAlike 4.0 International License (CC BY-SA 4.0), unless otherwise noted.

Published by ICAIIT in cooperation with Anhalt University of Applied Sciences.

© 2026 ICAIIT — International Conference on Applied Innovations in IT. Anhalt University of Applied Sciences, Köthen, Germany.
Visitors: site traffic counter