350 руб
Журнал «Динамика сложных систем - XXI век» №4 за 2016 г.
Статья в номере:
Класс разреженных рюкзаков в задаче укладки рюкзака и его некоторых приложениях в секретной связи
Ключевые слова: общая память задача об укладке рюкзака разреженные рюкзаки плотность укладки задачи о рюкзаке атака Костера-Одлыжко блочный шифр с режимом зацепления блоков хеш-функция
Авторы:
А.В. Александров - к.ф.-м.н., доцент, кафедра «Информатика и защита информации», Владимирский государственный университет им. А.Г. и Н.Г. Столетовых E-mail: alex_izi@mail.ru
Аннотация:
В терминах базисов возвратных последовательностей конечного порядка и им соответствующих сигнатур для обобщенной задачи об укладке рюкзака доказаны достаточные условия разреженных рюкзаков, обеспечивающих плотность укладки Костера-Одлыжко за пределами интервала (0,1). Получены их асимптотические и алгоритмические свойства. Конструкции таких рюкзаков использованы для построения блочного шифра в режиме зацепления блоков и соответствующей ему хеш-функции в виде свертки блоков шифра. Приведены некоторые сравнения скоростных и статистических свойств алгоритма шифрования по сравнению с известными стандартами блочного шифрования.
Страницы: 71-77
Список источников

 

  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.