ПАРАЛЛЕЛЬНЫЙ ЛОГИЧЕСКИЙ КРИПТОАНАЛИЗ ГЕНЕРАТОРА ПЕРЕМЕННОГО ШАГА

Олег Сергеевич Заикин; Андрей Александрович Чугунов

Олег Сергеевич Заикин Институт динамики систем и теории управления им. В.М. Матросова СО РАН; Иркутский государственный университет
Андрей Александрович Чугунов Байкальский государственный университет

Abstract

В статье рассматривается задача криптоанализа генератора переменного шага. В рамках данной задачи по известному фрагменту ключевого потока необходимо восстановить исходное внутреннее состояние генератора. Мы свели эту задачу к проблеме булевой выполнимости. Для версии данного генератора с 96-битным внутренним состоянием была найдена декомпозиция, обладающая приемлемой прогнозной трудоемкостью. При этом был использован алгоритм локального поиска, основанный на методе Монте-Карло. С помощью найденной декомпозиции был решен ряд экземпляров задачи криптоанализа указанной версии генератора. Большая часть экспериментов была выполнена на вычислительном кластере.

Author Biographies

Олег Сергеевич Заикин, Институт динамики систем и теории управления им. В.М. Матросова СО РАН; Иркутский государственный университет

кандидат технических наук, научный сотрудник; старший преподаватель кафедры информационных технологий

Андрей Александрович Чугунов, Байкальский государственный университет

студент магистратуры факультета информатики, учета и сервиса

References

1. Menezes A. J., van Oorschot P. C., Vanstone S.A. Handbook of applied cryptography. CRC Press. 1996. 810 p.
2. Семенов А.А. О сложности обращения дискретных функций из одного класса // Дискретный анализ и исследование операций. 2004. Т. 11. № 4. С. 44-55.
3. Семенов А.А. Декомпозиционные представления логических уравнений в задачах обращения дискретных функций // Известия Российской академии наук. Теория и системы управления. 2009. № 5. С. 47-61.
4. Семенов А.А., Беспалов. Д.В. Технологии решения многомерных задач логического поиска // Вестник Томского государственного университета. 2005. № 14. С. 61–73.
5. Cook, S.A., Mitchell, D.G. Finding hard instances of the satisfiability problem: A survey. American Mathematical Society (1997). pp. 1–17.
6. Gü nther C.G. Alternating step generators controlled by de Bruijn sequences // Advances in Cryptology - EuroCrypt '87. pp.5-14.
7. Otpuschennikov I. V., Semenov A. A., Kochemazov S. E. Transalg: a tool for translating procedural descriptions of discrete functions to SAT // Proceedings of the 5th International Workshop on Computer Science and Engineering: Information Processing and Control Engineering (WCSE 2015-IPCE). 2015. pp. 289-294.
8. Otpuschennikov I.V., Semenov A.A., Gribanova I.A., Zaikin O.S., Kochemazov S.E. Encoding cryptographic functions to SAT using Transalg system. Frontiers in Artificial Intelligence and Applications. Vol 285. pp. 1594-1595.
9. Заикин О.С., Семенов А.А. Применение метода Монте-Карло к прогнозированию времени параллельного решения проблемы булевои̮ выполнимости // Вычислительные методы и программирование: новые вычислительные технологии. 2014. Т. 15. № 1. С. 22-35.
10. Посыпкин М.А., Заикин О.С., Беспалов Д.В., Семенов А.А. Решение задач криптоанализа поточных шифров в распределенных вычислительных средах // Труды Института системного анализа России̮ скои̮ академии наук. 2009. Т. 46. С. 119-137.
11. Заикин, О.С., Семенов А.А., Посыпкин М.А. Процедуры построения декомпозиционных множеств для
распределенного решения SAT-задач в проекте добровольных вычислений SAT@home // Управление большими системами. М.: ИПУ РАН. Вып. 43. 2013. С. 138–156.
12. Иркутский суперкомпьютерный центр СО РАН. URL: http://hpc.icc.ru.
13. Semenov A., Zaikin O. On the accuracy of statistical estimations of SAT partitionings effectiveness in application to discrete function inversion problems // Proceedings of the International conference on Discrete optimization and operations research (DOOR). 2016. pp. 261-275.