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

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

Аннотация

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

Сведения об авторах

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

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

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

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

Литература

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. Gü 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.
Опубликована
2016-11-25
Как цитировать
ЗАИКИН, Олег Сергеевич; ЧУГУНОВ, Андрей Александрович. ПАРАЛЛЕЛЬНЫЙ ЛОГИЧЕСКИЙ КРИПТОАНАЛИЗ ГЕНЕРАТОРА ПЕРЕМЕННОГО ШАГА. Современные информационные технологии и ИТ-образование, [S.l.], v. 12, n. 2, p. 70-76, nov. 2016. ISSN 2411-1473. Доступно на: <http://sitito.cs.msu.ru/index.php/SITITO/article/view/49>. Дата доступа: 05 aug. 2025
Форматы библиографических ссылок
Выпуск
Том 12 № 2 (2016): Современные информационные технологии и ИТ-образование
Раздел
Параллельное и распределенное программирование, грид-технологии
Лицензия Creative Commons

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

Редакционная политика журнала основывается на традиционных этических принципах российской научной периодики и строится с учетом этических норм работы редакторов и издателей, закрепленных в Кодексе поведения и руководящих принципах наилучшей практики для редактора журнала (Code of Conduct and Best Practice Guidelines for Journal Editors) и Кодексе поведения для издателя журнала (Code of Conduct for Journal Publishers), разработанных Комитетом по публикационной этике - Committee on Publication Ethics (COPE). В процессе издательской деятельности редколлегия журнала руководствуется международными правилами охраны авторского права, нормами действующего законодательства РФ, международными издательскими стандартами и обязательной ссылке на первоисточник.
Журнал позволяет авторам сохранять авторское право без ограничений. Журнал позволяет авторам сохранить права на публикацию без ограничений.
Издательская политика в области авторского права и архивирования определяются «зеленым цветом» в базе данных SHERPA/RoMEO.
Все статьи распространяются на условиях лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная, которая позволяет другим использовать, распространять, дополнять эту работу с обязательной ссылкой на оригинальную работу и публикацию в этом журналe.