A Recursive and Parallelized Dynamic Programming Implementation of Hard Merkle-Hellman Knapsack System for Public Key Cryptography
Autor: | Rahul Vaddadi Sai, Prasanth N. Narayanan, Raja S. P. |
---|---|
Jazyk: | angličtina |
Rok vydání: | 2021 |
Předmět: | |
Zdroj: | Cybernetics and Information Technologies, Vol 21, Iss 2, Pp 58-69 (2021) |
Druh dokumentu: | article |
ISSN: | 1314-4081 2021-0019 |
DOI: | 10.2478/cait-2021-0019 |
Popis: | Merkle-Hellman public key cryptosystem is a long-age old algorithm used in cryptography. Despite being computationally fast, for very large input sizes it may operate slower due to thread creation overhead or reaching a deadlock situation. In this paper, we discuss the working principles of the Traditional Merkle-Hellman knapsack cryptosystem, which is an Easy knapsack. The challenges of Hard Knapsack and how it overcomes the shortcomings of the Traditional Easy Knapsack, are also discussed. The Hard knapsack variant of Merkle-Hellman is solved first using plain recursion and then improvised using a dynamic programming approach to the problem. Parallelism and Concurrency has been achieved on the dynamic programming implementation using OpenMP API which further has enhanced the performance time. A comparative study of both variants of Hard Knapsack for messages of different lengths has shown that the latter is faster. |
Databáze: | Directory of Open Access Journals |
Externí odkaz: |