Класс разреженных рюкзаков в задаче укладки рюкзака и его некоторых приложениях в секретной связи

А.В. Александров

Класс разреженных рюкзаков в задаче укладки рюкзака и его некоторых приложениях в секретной связи

научная статья Страницы: 71-77

¹ к.ф.-м.н., доцент, кафедра «Информатика и защита информации», Владимирский государственный университет им. А.Г. и Н.Г. Столетовых

Ключевые слова: общая память задача об укладке рюкзака разреженные рюкзаки плотность укладки задачи о рюкзаке атака Костера-Одлыжко блочный шифр с режимом зацепления блоков хеш-функция

Аннотация

В терминах базисов возвратных последовательностей конечного порядка и им соответствующих сигнатур для обобщенной задачи об укладке рюкзака доказаны достаточные условия разреженных рюкзаков, обеспечивающих плотность укладки Костера-Одлыжко за пределами интервала (0,1). Получены их асимптотические и алгоритмические свойства. Конструкции таких рюкзаков использованы для построения блочного шифра в режиме зацепления блоков и соответствующей ему хеш-функции в виде свертки блоков шифра. Приведены некоторые сравнения скоростных и статистических свойств алгоритма шифрования по сравнению с известными стандартами блочного шифрования.

Для цитирования

Александров А.В. Класс разреженных рюкзаков в задаче укладки рюкзака и его некоторых приложениях в секретной связи // Динамика сложных систем - XXI век. 2016. № 4. С. 71–77.

Список источников

Diffie R. Merkle, Hellman M. Hiding information and signatures in trapdoor knapsacks // IEEE Transactions on Information Theory. 1978. P. 525−530.
Shamir A. A polynomial time algorithm for breaking the basis Merkle-Hellman cryptosystem // Proc. 23-rd IEEE Symp. Found. Computer Science. 1982. P. 145−152.
Coster M.J., Joux A., LaMacchia B.A., et al. Improved low-density subset sum algorithms // Computational Complexity. 1992. № 2. P. 111−128.
Мурин Д.М. Модификация метода Лагариаса-Одлыжко для решения обобщенной задачи о рюкзаке и систем задач о рюкзаках // Прикладная дискретная математика. 2013. № 2(20). С. 91−100.
Александров А.В., Метлинов А.Д. Симметричная рюкзачная криптосистема с общей памятью и плотностью укладки больше единицы // Проблемы информационной безопасности. Компьютерные системы. 2014. № 4. С. 58−65.
Hamlin N., Krishnamoorthy B., Webb W. A Knapsack-Like Code Using Recurrence Sequence Representations // Fibonacci Quarterly. 2015. 1 (53). 24−33.
Graham Everest, Alf van der Poorten, Igor Shparlinski, Thomas Ward. Recurrence sequences. 2003. AMS, Mathematical Surv. and monographs. V104.
Dolev D., Yao A. On the Security of Public Key Protocols // IEEE Transact. on Inform. Theory. 1983. V. 29. № 2. P. 198−208.
Александров А.В. О семействе рюкзачных блочных шифров с общей памятью и разреженной плотностью укладки // Сб. научных трудов III Междунар. научно-практической конф. «Информационная безопасность в свете Стратегии Казахстан‑2050». 2015. С. 26−30.

[1] Diffie R. Merkle, Hellman M. Hiding information and signatures in trapdoor knapsacks // IEEE Transactions on Information Theory. 1978. P. 525−530.

[2] Shamir A. A polynomial time algorithm for breaking the basis Merkle-Hellman cryptosystem // Proc. 23-rd IEEE Symp. Found. Computer Science. 1982. P. 145−152.

[3] Coster M.J., Joux A., LaMacchia B.A., et al. Improved low-density subset sum algorithms // Computational Complexity. 1992. № 2. P. 111−128.

[4] Мурин Д.М. Модификация метода Лагариаса-Одлыжко для решения обобщенной задачи о рюкзаке и систем задач о рюкзаках // Прикладная дискретная математика. 2013. № 2(20). С. 91−100.

[5] Александров А.В., Метлинов А.Д. Симметричная рюкзачная криптосистема с общей памятью и плотностью укладки больше единицы // Проблемы информационной безопасности. Компьютерные системы. 2014. № 4. С. 58−65.

[6] Hamlin N., Krishnamoorthy B., Webb W. A Knapsack-Like Code Using Recurrence Sequence Representations // Fibonacci Quarterly. 2015. 1 (53). 24−33.

[7] Graham Everest, Alf van der Poorten, Igor Shparlinski, Thomas Ward. Recurrence sequences. 2003. AMS, Mathematical Surv. and monographs. V104.

[8] Dolev D., Yao A. On the Security of Public Key Protocols // IEEE Transact. on Inform. Theory. 1983. V. 29. № 2. P. 198−208.

[9] Александров А.В. О семействе рюкзачных блочных шифров с общей памятью и разреженной плотностью укладки // Сб. научных трудов III Междунар. научно-практической конф. «Информационная безопасность в свете Стратегии Казахстан‑2050». 2015. С. 26−30.