АНАЛИЗ И РЕАЛИЗАЦИЯ КРИПТОСИСТЕМЫ НА ОСНОВЕ НЕИНЪЕКТИВНЫХ РАНЦЕВ

Мария Сабина А. Волков

Аннотация


В работе исследуются свойства неинъективных линейных форм и их применение в ранцевых криптосистемах. Основной целью исследования является анализ возможностей использования неинъективных ранцев в качестве закрытых ключей для повышения криптографической стойкости ранцевых криптосистем к известным видам атак, включая атаки методом перебора и атаки, основанные на редукции базиса решеток. Особое внимание уделено выбору параметров криптосистемы, обеспечивающих баланс между безопасностью и вычислительной эффективностью. Определено, что для защиты от атак на основе редукции решеток, таких как LLL-атака, необходимо поддерживать плотность ранца выше 1,033. В качестве значения длины ключа выбрано n = 200, при котором элементы открытого ключа имеют длину 170–200 бит. Это обеспечивает достаточный уровень криптостойкости при разумных вычислительных затратах. Для контроля сложности алгоритма расшифрования предложены методы ограничения среднего числа решений задачи о ранце. Установлено, что ограничение числа решений значением 2048 позволяет достичь приемлемой вычислительной сложности, сохраняя высокий уровень безопасности. Дополнительно разработан механизм исключения избыточных коэффициентов и введена 16-битная контрольная сумма, позволяющая избежать неоднозначности при расшифровании. Результаты исследования показывают, что предложенные методы позволяют существенно повысить стойкость ранцевой криптосистемы при умеренных вычислительных затратах, делая её перспективной для практического применения.

Ключевые слова


NP-трудные задачи, задача об укладке ранца, криптография, ранцевая криптосистема.

Полный текст:

PDF

Литература


1. Wang, J., Liu, L., Lyu, S., et al. Quantum-safe cryptography: crossroads of coding theory and cryptography. Science China Information Sciences. 2022, v. 65, no. 1, p. 111301.
DOI: https://doi.org/10.1007/s11432-021-3354-7.

2. Merkle R., Hellman M. Hiding information and signatures in trapdoor knapsacks. IEEE Transactions on Information Theory. September. 1978, v. 24, no. 5, p. 525–530.
DOI: https://doi.org/10.1109/TIT.1978.1055927.

3. Odlyzko A. M. The rise and fall of knapsack cryptosystems. Cryptology and computational number theory, 1990, v. 42, no. 2. DOI: https://doi.org/10.1090/psapm/042/1095552.

4. Coster M., Joux A., Lamacchia B., Odlyzko A., Schnorr C., Stern J. Improved Low-Density Subset Sum Algorithms. Computational Complexity. 1992, v. 2, p. 111–128.
DOI: https://doi.org/10.1007/BF01201999.

5. Lu B. A Review of Modern Cryptography: From the World War II Era to the Big-Data Era. Optimization and Control for Systems in the Big-Data Era: Theory and Applications. 2017, v. 252, p. 101–120.
DOI: https://doi.org/10.1007/978-3-319-53518-0_7.

6. Okamoto T., Tanaka K., Uchiyama S. Quantum Public-Key Cryptosystems. In: Bellare, M. (eds) Advances in Cryptology – CRYPTO 2000. CRYPTO 2000. Lecture Notes in Computer Science,
v. 1880. Springer, Berlin, Heidelberg.
DOI: https://doi.org/10.1007/3-540-44598-6.

7. Murakami Y., Nasako T. Knapsack Public-Key Cryptosystem Using Chinese Remainder Theorem. IACR Cryptology ePrint Archive. 2007. – 12 p. URL: https://www.semanticscholar.org/paper/Knapsack-Public-Key-Cryptosystem-Using-Chinese-Murakami-Nasako/2ae27b1b4fa41a7ecccde83e329dd6378b545b04 (дата обращения: 05.10.2024).

8. Naccache D., Stern J. A new public key cryptosystem based on higher residues. In Proceedings of the 5th ACM conference on Computer and communications security (CCS '98). Association for Computing Machinery, New York, NY, USA. 1998, p. 59–66.
DOI: https://doi.org/10.1145/288090.288106.

9. Волков, Мария Сабина А.; Гордеев, Эдуард Н. Применение неинъективных векторов в ранцевых криптосистемах. Безопасность информационных технологий, [S.l.], 2025, т. 32, № 1, с. 122–131.
DOI: http://dx.doi.org/10.26583/bit.2025.1.08.

10. Гордеев Э.Н, Леонтьев В.К. О некоторых комбинаторных свойствах задачи о ранце. Журнал вычислительной математики и математической физики. 2019, т. 59, № 8, с. 1439–1447.
DOI: https://doi.org/10.1134/S0044466919080076. – EDN: HHFSAT.

11. Леонтьев В.К., Гордеев Э.Н. О числе решений системы булевых уравнений. Автоматика и телемеханика. 2021, № 9, c. 150–168. – EDN: UQANSY.

12. Леонтьев В.К., Гордеев Э.Н., Волков М.С.А. Классическая непрерывность и ее дискретный вариант. Прикладная физика и математика. 2022, № 1, c. 31–37.
DOI: https://doi.org/10.25791/pfim.01.2022.1221. – EDN: ZITBKA.

13. Волков М.С.А. Комбинаторные свойства задачи об ограниченном ранце. Прикладная дискретная математика. 2024, № 63, c. 117–130.
DOI: https://doi.org/10.25791/10.17223/20710410/63/8. – EDN: PKMABD.

14. Zhang W., Wang B., Hu Y. A New Knapsack Public-Key Cryptosystem, 2009 Fifth International Conference on Information Assurance and Security, Xi'an, China. 2009, p. 53–56.
DOI: https://doi.org/10.1109/IAS.2009.300.

15. Jain, A., Chaudhari, N.S. Cryptanalytic Results on Knapsack Cryptosystem Using Binary Particle Swarm Optimization. In: de la Puerta, J., et al. International Joint Conference SOCO’14-CISIS’14-ICEUTE’14. Advances in Intelligent Systems and Computing. 2014, v. 299, p. 375–384.
DOI: https://doi.org/10.1007/978-3-319-07995-0_37.

16. Schnorr, C.P., Euchner, M. Lattice basis reduction: Improved practical algorithms and solving subset sum problems. Mathematical Programming 66, p. 181–199 (1994).
DOI: https://doi.org/10.1007/BF01581144.

17. Koskinen A., Non-Injective Knapsack Public-Key Cryptosystems. Theoretical Computer Science, March 2001, v. 255, no. 1–2, p. 401–422. DOI: https://doi.org/10.1016/S0304-3975(99)00297-2.

18. Liu J., Bi J. Xu S. An Improved Attack on the Basic Merkle–Hellman Knapsack Cryptosystem. IEEE Access, 2019, v. 7, p. 59388-59393. DOI: https://doi.org/10.1109/ACCESS.2019.2913678.

19. Khalaf R.Z., Hamza B.H., Thakwan A.J. Attacking the Knapsack Public-key Cryptosystem. Webology. 2022, v. 19, no. 1, p. 5302–5309. DOI: https://doi.org/10.14704/web/v19i1/web19356.




DOI: http://dx.doi.org/10.26583/bit.2025.3.08

Ссылки

  • На текущий момент ссылки отсутствуют.


Лицензия Creative Commons
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.