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

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

Список литературы:

1. Александров А. В., Метлинов А. Д. Симметричная рюкзачная криптосистема с общей памятью и плотностью укладки больше единицы // Изв. вузов. Приборостроение. 2015. Т. 58, № 5. С. 344—350.
2. Hamlin N., Krishnamoorthy B., and Webb W. A Knapsack-Like Code Using Recurrence Sequence Representations // Fibonacci Quarterly. 2015. Vol. 53, N 1. Р. 24—33.
3. Маркушевич А. И. Возвратные последовательности. М.: Наука, 1983. 48 с.
4. Merkle D. R., Hellman M. Hiding in-formation and signatures in trapdoor knapsacks // Information Theory. IEEE Transactions. 1978. P. 525—530.
5. Hamlin N. Number in Mathematical Cryptography // Open Journal of Discrete Mathematics. 2017. N 7. P. 13—31.
6. Александров А. В., Метлинов А. Д. Алгоритмические и статистические свойства разреженной рюкзачной криптосистемы с общей памятью // Изв. вузов. Приборостроение. 2017. Т. 60, № 1. С. 5—9.
7. Александров А. В. Класс разреженных рюкзаков в задаче укладки рюкзака и его некоторых приложениях в секретной связи // Динамика сложных систем — XXI век. 2016. T. 10, № 4. С. 71—77.
8. Coster M. J., Joux A., LaMacchia B. A. et al. Improved low-density subset sum algorithms // Computational Complexity. 1992. N 2. P. 111—128.
9. Мурин Д. М. Модификация метода Лагариаса—Одлыжко для решения обобщенной задачи о рюкзаке и систем задач о рюкзаках // Прикладная дискретная математика. 2013. № 2(20). С. 91—100.
10. Marden M. Geometry of Polynomials. Providence, RI: American Mathematical Society. 1966. 243 p.
11. Черемушкин А. В. Криптографические протоколы. Основные свойства и уязвимости. М.: Академия, 2009. 272 с.
12. Dolev D., Yao A. One the security of public key protocol // IEEE Transact on Information Theory. 1983. Vol. 29, N 2. P. 198—208.
13. Метлинов А. Д. Модификация протокола TLS на основе разреженной криптосистемы с общей памятью // Изв. вузов. Приборостроение. 2018. Т. 6, № 11. С. 60—64.