Study of knapsack cryptosystems
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...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Final Year Project (FYP) |
| Language: | English |
| Published: |
Nanyang Technological University
2020
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/144623 |
| _version_ | 1811680680146370560 |
|---|---|
| author | Sathia Seelan Vetrichelvan |
| author2 | Tay Kian Boon |
| author_facet | Tay Kian Boon Sathia Seelan Vetrichelvan |
| author_sort | Sathia Seelan Vetrichelvan |
| collection | NTU |
| description | 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. |
| first_indexed | 2024-10-01T03:28:54Z |
| format | Final Year Project (FYP) |
| id | ntu-10356/144623 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T03:28:54Z |
| publishDate | 2020 |
| publisher | Nanyang Technological University |
| record_format | dspace |
| spelling | ntu-10356/1446232020-11-16T05:01:58Z Study of knapsack cryptosystems Sathia Seelan Vetrichelvan Tay Kian Boon School of Computer Science and Engineering kianboon.tay@ntu.edu.sg Engineering::Computer science and engineering 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. Bachelor of Engineering (Computer Engineering) 2020-11-16T05:01:58Z 2020-11-16T05:01:58Z 2020 Final Year Project (FYP) https://hdl.handle.net/10356/144623 en application/pdf Nanyang Technological University |
| spellingShingle | Engineering::Computer science and engineering Sathia Seelan Vetrichelvan Study of knapsack cryptosystems |
| title | Study of knapsack cryptosystems |
| title_full | Study of knapsack cryptosystems |
| title_fullStr | Study of knapsack cryptosystems |
| title_full_unstemmed | Study of knapsack cryptosystems |
| title_short | Study of knapsack cryptosystems |
| title_sort | study of knapsack cryptosystems |
| topic | Engineering::Computer science and engineering |
| url | https://hdl.handle.net/10356/144623 |
| work_keys_str_mv | AT sathiaseelanvetrichelvan studyofknapsackcryptosystems |