
|
Cryptanalysis of the Merkle-Hellman Knapsack Cryptosystem Using Continued Fraction: Two Attack Scenarios
Abstract
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.
Keywords
Merkle-Hellman Knapsack
Continued Fractions
Public-Key
Cryptography
References
|
|
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
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.