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

Мария Сабина А. Волков, Эдуард Н. Гордеев

Аннотация


В статье исследуются криптографические свойства неинъективных линейных форм и их применение в ранцевых криптосистемах. Основной целью работы является анализ возможностей использования неинъективных ранцев в качестве закрытых ключей для обеспечения криптографической стойкости систем к известным видам атак, включая атаки методом перебора и атаки с редукцией базиса решеток. Рассмотрены линейные формы с переменными, принимающими целые неотрицательные значения. Введено понятие сюръективной линейной формы и определены необходимые и достаточные условия сюръективности. Внимание уделено свойствам области значений таких форм и их способности избегать уязвимостей, связанных с низкой плотностью. Предлагается алгоритм для нахождения решений задачи об укладке сюръективного ранца, а также методы оптимизации его сложности. Получены оценки числа сюръективных линейных форм заданной размерности с булевыми переменными. Для устранения неоднозначности расшифрования рассматриваются способы добавления избыточности и модификации открытого ключа. Предлагается способ добавления контрольных сумм и исключения части младших коэффициентов формы для повышения однозначности расшифрования. В статье обсуждается влияние плотности ранца на безопасность системы и приводятся численные примеры, подтверждающие предложенные выводы. Результаты исследования показывают, что сюръективные линейные формы могут быть перспективным кандидатом для использования в криптографических системах, предлагая криптостойкость к известным видам атак при сохранении приемлемой вычислительной сложности.


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


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

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

PDF

Литература


1. Kellerer H., Pferschy U., Pisinger D. Knapsack problems. Berlin: Springer, 2004. – 548 p.
DOI: https://doi.org/10.1007/978-3-540-24777-7.

2. Zhang H., Han W., Lai X., Lin D., Ma J., Li J. Survey on cyberspace security. Science China Information Sciences. 2015, v. 58, no. 11, p. 1–43. DOI: https://doi.org/10.1007/s11432-015-5433-4.

3. 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.

4. 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.

5. 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.

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_9.

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, p. 59–66.
DOI: https://doi.org/10.1145/288090.288106.

9. 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.

10. 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.

11. Gordeev E.N., Leontiev V.K. On combinatorial properties of the knapsack problem. Computational Mathematics and Mathematical Physics. 2019, v. 59, no. 8, p. 1380–1388.
DOI: https://doi.org/10.1134/S0965542519080074. – EDN: QZNJJG.

12. Леонтьев В. К., Гордеев Э. Н. О числе решений системы булевых уравнений. Автоматика и телемеханика. 2021, № 9, С. 150–168. DOI: 10.31857/S0005231021090063. EDN: UVURXX.

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

14. 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.

15. 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.

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

17. Леонтьев В.К., Гордеев Э.Н. О некоторых особенностях задачи разрешимости систем булевых уравнений. Вопросы кибербезопасности. 2021, № 1(41), c. 18–28. DOI: https://doi.org/10.21681/2311-3456-2021-1-18-28. – EDN: BFBXYF.




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

Ссылки

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


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