Comparative Analysis of the Merkle–Hellman Knapsack and RSA Public-Key Cryptosystems: Efficiency vs. Security
Keywords:
Public-key cryptography; RSA; Merkle – Hellman cryptosystem; Subset sum problem; Algorithmic complexityAbstract
This paper provides a targeted comparative analysis of the Merkle–Hellman knapsack cryptosystem and the RSA public-key scheme, aiming to evaluate their relative efficiency and practical relevance. The research investigates key generation complexity, encryption and decryption performance, and resistance to established cryptanalytic techniques. Based on an experimental implementation and benchmarking across different key sizes, the result indicates that the Merkle–Hellman approach achieves lower computational overhead in both encryption / decryption process, due to its reliance on super-increasing sequences. However, these efficiency advantages are counterbalanced by structural weaknesses in the key transformation process, which expose the system to polynomial-time attacks. By comparison, RSA, despite higher computational costs, preserves robust security grounded in the hardness of integer factorization. Overall, the analysis demonstrates the conclusion that Merkle–Hellman, despite its historical importance, fails to achieve a sustainable efficiency-security balance for modern applications, reinforcing RSA’s dominance in practical public-key cryptography.
References
Boneh, D. (1999). Twenty years of attacks on the RSA cryptosystem. Notices of the AMS, 46(2), 203–213.
Boneh, D., & Durfee, G. (2000). Cryptanalysis of RSA with private key d less than [missing value]. IEEE Transactions on Information Theory, 46(4), 1339–1349.
Brickell, E. F. (1984). Solving low density knapsacks. In Advances in cryptology, Proceedings, CRYPTO 83 (pp. 25–37). Plenum Press.
Joux, A., & Stern, J. (1991). Improving the critical density of the Lagarias–Odlyzko attack against subset sum problems. Lecture Notes in Computer Science, 529, 258–264.
Katz, J., & Lindell, Y. (2015). Introduction to modern cryptography (2nd ed.). Chapman & Hall/CRC.
Katz, J., & Lindell, Y. (2020). Introduction to modern cryptography. CRC Press.
Lagarias, J. C. (1983). The knapsack problem and public-key cryptography. In Advances in cryptology: Proceedings of CRYPTO 82 (Lecture Notes in Computer Science, Vol. 196, pp. 3–21). Springer.
Lagarias, J. C., & Odlyzko, A. M. (1985). Solving low-density subset sum problems. Journal of the Association for Computing Machinery, 32(1), 229–246.
Menezes, A., van Oorschot, P., & Vanstone, S. (1996). Handbook of applied cryptography. CRC Press.
Merkle, R., & Hellman, M. (1978). Hiding information and signatures in trapdoor knapsacks. IEEE Transactions on Information Theory, 24(5), 525–530.
Micciancio, D., & Regev, O. (2009). Lattice-based cryptography. In Post-quantum cryptography (pp. 147–191). Springer.
National Institute of Standards and Technology. (2024). Digital signature standard (DSS): FIPS PUB 186-5. National Institute of Standards and Technology.
Odlyzko, A. M. (1990). The rise and fall of knapsack cryptosystems. In Cryptology and computational number theory (Proceedings of Symposia in Applied Mathematics, Vol. 42, pp. 75–88). American Mathematical Society.
Rivest, R., Shamir, A., & Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2), 120–126.
Schneier, B. (1996). Applied cryptography (2nd ed.). Wiley.
Shamir, A. (1984). A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystem. IEEE Transactions on Information Theory, IT-30(5).
Shoup, V. (2009). A computational introduction to number theory and algebra (2nd ed.). Cambridge University Press.
Stern, J. (1993). A new identification scheme based on syndrome decoding. In Advances in cryptology—CRYPTO ’93 (Lecture Notes in Computer Science, Vol. 773, pp. 13–21). Springer.
Stinson, D. R. (2006). Cryptography: Theory and practice (3rd ed.). Chapman & Hall/CRC.
Wiener, M. J. (1990). Cryptanalysis of short RSA secret exponents. IEEE Transactions on Information Theory, 36(3), 553–558.
Downloads
Published
Issue
Section
License
Copyright (c) 2026 EIRP Proceedings
This work is licensed under a Creative Commons Attribution 4.0 International License.
You are free to:
- Share — copy and redistribute the material in any medium or format
- Adapt — remix, transform, and build upon the material
- for any purpose, even commercially.
- The licensor cannot revoke these freedoms as long as you follow the license terms.
Under the following terms:
-
Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.
