ANALYSIS AND IMPLEMENTATION OF A CRYPTOSYSTEM BASED ON NON-INJECTIVE KNAPSACKS
The paper explores the properties of non-injective linear forms and their application in knapsack cryptosystems. The primary objective of the study is to analyze the potential of using non-injective knapsacks as private keys to enhance the cryptographic strength of knapsack-based systems against kno...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Joint Stock Company "Experimental Scientific and Production Association SPELS
2025-07-01
|
| Series: | Безопасность информационных технологий |
| Subjects: | |
| Online Access: | https://bit.spels.ru/index.php/bit/article/view/1815 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | The paper explores the properties of non-injective linear forms and their application in knapsack cryptosystems. The primary objective of the study is to analyze the potential of using non-injective knapsacks as private keys to enhance the cryptographic strength of knapsack-based systems against known types of attacks, including brute-force attacks and lattice basis reduction attacks. Special attention is given to the selection of cryptosystem parameters that provide a balance between security and computational efficiency. It is determined that, in order to protect against lattice-based attacks such as the LLL attack, the knapsack density must be maintained above 1.033. A key length of n = 200 is chosen, where the elements of the public key have a length of 170–200 bits. This provides a sufficient level of cryptographic strength at reasonable computational cost. To control the complexity of the decryption algorithm, methods are proposed to limit the average number of solutions to the knapsack problem. It is established that restricting the number of solutions to 2048 enables acceptable computational complexity while maintaining a high level of security. Additionally, a mechanism for eliminating redundant coefficients is developed, and a 16-bit checksum is introduced to avoid ambiguity during decryption. The results of the study demonstrate that the proposed methods can significantly improve the robustness of the knapsack cryptosystem at moderate computational cost, making it a promising candidate for practical implementation. |
|---|---|
| ISSN: | 2074-7128 2074-7136 |