Study of knapsack cryptosystems

• Main Author: Sathia Seelan Vetrichelvan
• Other Authors: Tay Kian Boon
• Format: Final Year Project
• Language: English
• Published: Nanyang Technological University 2020
• Subjects: Engineering::Computer science and engineering
• Online Access: https://hdl.handle.net/10356/144623
• Institution: Nanyang Technological University

Merkle-Hellman knapsack cryptosystem is a public-key cryptosystem proposed by the inventors of public-key cryptography. With the fusion of a mathematical problem and disguise, they developed a cryptosystem based on a one-way trapdoor function. The cryptosystem was successfully attacked by Adi Shamir, one of the inventors for the RSA cryptosystem. Despite the knapsack problem known to be a NP-complete problem with O(2n), Shamir broke the system in polynomial-time. The methods required to achieve Merkle-Hellman’s knapsack cryptosystem and the implementation in Python 3 are provided. Description of the attack and its algorithm are discussed and implemented. A simple comparison study with the RSA algorithm is made to understand benefits and flaws of the knapsack cryptosystem. Furthermore, test results of 90 combinations of knapsack set, multiplicative value and modulus value alongside the success rate of the decryption with the original private key and the polynomial-time attack are provided. The report finally concludes with the findings of the cryptosystem and the attack algorithm.