Рассматривается возможность применения алгоритмов пчелиных колоний для реализации криптоанализа шифров перестановок. Данная задача является классической оптимизационной задачей, для решения которой применяются известные методы пчелиных колоний, относящихся к сравнительно новому классу биоинспирированных оптимизационных методов. Показано, что данная задача является частным случаем задачи о назначениях и может быть решена с помощью алгоритма пчелиных колоний, основу поведения которых составляет самоорганизация, обеспечивающая достижение общих целей роя. На первом этапе с помощью пчёл-разведчиков формируется множество перспективных областей-источников, на втором этапе с помощью рабочих пчёл-фуражиров осуществляется исследование окрестностей данных областей. При этом основная цель колонии пчёл — найти источник, содержащий максимальное количество нектара. Рассмотрены методы представления решения (позиции в пространстве поиска), приведена формула для определения значения целевой функции (количества нектара). Показано, что целью поиска является определение оптимальной комбинации символов с максимальным значением целевой функции. Приводится описание основных этапов алгоритма пчелиных колоний, а также пример его работы.
криптоанализ, задача о назначениях, биоинспирированные методы, алгоритм пчелиных колоний, рабочие пчёлы (фуражиры), пчёлы-разведчики, шифр перестановки.
Введение. В последние годы интенсивно разрабатывается новое научное направление под названием «природные вычисления», объединяющее математические методы, в которых заложен принцип природных механизмов принятия решений. Как отмечено в [1], научное направление «природные вычисления» объединяет такие разделы, как эволюционное программирование, нейросетевые вычисления, алгоритмы роевого интеллекта, муравьиные и генетические алгоритмы. В моделях и алгоритмах эволюционных вычислений ключевым элементом является построение начальной модели и правил, по которым она может изменяться (эволюционировать). В течение последних лет были предложены разнообразные схемы эволюционных вычислений, в том числе генетические алгоритмы, генетическое программирование, эволюционные стратегии, эволюционное программирование. Общие концепции и методологический подход к построению эволюционных вычислений, основанных на природных системах, а также основные гипотезы, закономерности и положения концепции эволюционных вычислений отмечены в [2, 3]. В настоящее время известны применения генетических алгоритмов для оптимизации широкого круга задач, в том числе задач криптоанализа. В [4‒9] авторами рассматривались методы организации криптографических атак на традиционные симметричные криптосистемы, использующие шифры перестановки и замены, а также на блочные криптосистемы с использованием биоинспирированных методов. Следует заметить, что задачи такого типа относятся к переборным задачам с экспоненциальной временной сложностью. Побудительным мотивом для разработок новых алгоритмов являются возникшие потребности в решении задач большой размерности [10]. Анализ исследований показывает, что наиболее успешными в данных условиях являются методы, в которых заложены принципы природных механизмов принятия решений. Недостатком генетических алгоритмов является наличие «слепого» поиска, что приводит к увеличению времени поиска, генерации большого количества одинаковых и плохо приспособленных решений, что может привести к попаданию в локальный оптимум [11]. Поэтому представляет интерес применение эвристических мето-
1. Макконел, Д. Основы современных алгоритмов / Д. Макконел. — Москва : Техносфера, 2004. — 368 с.
2. Родзин, С. И. Интеллектуальные системы. О некоторых алгоритмах, инспирированных природными системами : коллективная монография / С. И. Родзин. — Москва : Физматлит, 2009. — С. 34‒45.
3. Курейчик, В. В. Концепция природных вычислений, инспирированных природными системами / В. В. Курейчик, В. М. Курейчик, С. И. Родзин // Известия ЮФУ. — 2009. — № 4. — С. 16‒24.
4. Сергеев, А. С. Исследование возможности организации криптографической атаки с использованием эволюционной оптимизации и квантового поиска при разработке систем передачи и защиты информации / А. С. Сергеев // Теоретические и прикладные вопросы современных информационных технологий : мат-лы 6 Всероссийской НТК. — Улан-Удэ, 2005. — С. 61‒65.
5. Биоинспирированные алгоритмы криптоанализа асимметричных алгоритмов шифрования на основе факторизации составных чисел / А. С. Сергеев [и др.] // Информационная безопасность — актуальная проблема современности. Совершенствование образовательных технологий подготовки специалистов в области информационной безопасности : сб. трудов. — Краснодар, 2011. — С. 41‒47.
6. Сергеев, А. С. Применение методов генетического поиска для организации криптоанализа блочных криптосистем на примере стандарта DES / А. С. Сергеев // Научная мысль Кавказа : Приложение. — 2006. — № 15. — С. 185‒193.
7. Сергеев, А. С. Исследование и разработка методов генетического поиска для организации криптоанализа блочных криптосистем в системах управления безопасностью и защиты информации на примере стандарта шифрования DES / А. С. Сергеев // Третья Международная конференция по проблемам управления : Пленарные доклады и избранные труды. — Москва : Ин-т проблем управления, 2006. — С. 328‒335.
8. Фатхи, В. А. Исследование возможности применения алгоритма муравьиных колоний для реализации криптоанализа шифров перестановок / В. А. Фатхи, А. С. Сергеев // Вестник Дон. гос. техн. ун-та. — 2011. — Т. 11, № 1 (52). — С. 10‒20.
9. Чернышёв, Ю. О. Исследование и разработка методов генетического поиска для реализации криптоанализа алгоритма IDEA и решения основных теоретико-числовых задач криптографии / Ю. О. Чернышёв, А. С. Сергеев, Н. Н. Венцов // Вестник РГУПС. — 2009. — № 3 (35). — С. 70‒79.
10. Лебедев, В. Б. Модели адаптивного поведения колонии пчёл для решения задач на графах / В. Б. Лебедев // Известия ЮФУ. — 2012. — № 7. — С. 42‒49.
11. Лебедев, О. Б. Трассировка в канале методом муравьиной колонии / О. Б. Лебедев // Известия ЮФУ. — 2009. — № 4. — С. 46‒52.
12. The Bees Algorithm. Technical Note, Manufacturing Engineering Centre. Cardiff University, UK, 2005.
13. An IDEA based on honey bee swarm for numerical optimization, technical report. Erciyes University, Engineering Faculty. Computer Engineering Department, 2005.
14. The Bees Algorithm. — A Novel Tool for Complex Optimisation Problems. Manufacturing Engineering Centre. — Cardiff University, Cardiff CF24 3AA, UK.
15. Алгоритм пчёл для оптимизации функции [Электронный ресурс]. — Режим доступа http://jenyay.net/Programming/Bees (дата обращения : 24.05.2013).
16. Алгоритм пчёл для оптимизации функции [Электронный ресурс]. — Режим доступа : http://lit999.narod.ru/soft/ga/index.html (дата обращения : 24.05.2013).
17. Курейчик, В. В. Роевой алгоритм в задачах оптимизации / В. В. Курейчик, Д. Ю. Запорожец // Известия ЮФУ. — 2010. — № 7 (108). — С. 28‒32.
18. Курейчик, В. М. Использование пчелиных алгоритмов для решения комбинаторных задач [Электронный ресурс] / В. М. Курейчик, А. А. Кажаров. — Режим доступа : http://archive.nbuv.gov.ua/portal/natural/ii/2010_3/AI_2010_3/6/00_Kureychik_Kazharov.pdf (дата обращения : 24.05.2013).
19. Курейчик, В. М. Применение пчелиных алгоритмов для раскраски графов / В. М. Курейчик, А. А. Кажаров // Известия ЮФУ. — 2010. — № 12 (113). — С. 7‒12.
20. Лебедев, Б. К. Размещение на основе метода пчелиной колонии / Б. К. Лебедев, В. Б. Лебедев // Известия ЮФУ. — 2010. — № 12 (113). — С. 12‒19.
21. Курейчик, В. В. Эволюционная оптимизация на основе алгоритма колонии пчёл / В. В. Курейчик, Е. Е. Полупанова // Известия ЮФУ. — 2009. — № 12 (101). — С. 41‒46.
22. Биоинспирированные методы криптоанализа асимметричных алгоритмов шифрования на основе факторизации составных чисел / А. С. Сергеев [и др.] // Вестник Дон. гос. техн. ун-та. — 2011. — Т. 11, № 9 (60). — С. 1544‒1554.
23. Чернышёв, Ю. О. Применение биоинспирированных методов оптимизации для реализации криптоанализа классических симметричных и асимметричных криптосистем / Ю. О. Чернышёв, А. С. Сергеев, Е. О. Дубров // Системный анализ в проектировании и управлении : сб. науч. трудов 16-й Междунар. науч.-практ. конф. — Санкт-Петербург, 2012. — С. 112‒122.
24. Зайцев, А. А. Обзор эволюционных методов оптимизации на основе роевого интеллекта / А. А. Зайцев, В. В. Курейчик, А. А. Полупанов // Известия ЮФУ. — 2010. — № 12 (113). — С. 7‒12.
25. Романец, Ю. В. Защита информации в компьютерных системах и сетях / Ю. В. Романец, П. А. Тимофеев, В. Ф. Шаньгин. — Москва : Радио и связь, 2001. — 376 с.
26. Основы криптографии / А. П. Алферов [и др.]. — Москва : Гелиос АРВ, 2002. — 480 с.
27. Чернышев, Ю. О. Применение алгоритма муравьиных колоний для реализации криптоанализа шифров перестановок / Ю. О. Чернышёв, А. С. Сергеев, Е. О. Дубров // Научная сессия, посвящённая Дню радио : сб. докладов 67-й Всероссийской конференции с Международным участием. — Москва, 2012. — С. 71‒75.
28. Морозенко, В. В. Генетический алгоритм для криптоанализа шифра Вижинера [Электронный ресурс] / В. В. Морозенко, Г. О. Елисеев. — Режим доступа : http://vestnik.psu.ru/files/articles/132_6410.p (дата обращения : 24.05.2013).
29. Городилов, А. Ю. Криптоанализ тригонометрического шифра с помощью генетического алгоритма [Электронный ресурс] / А. Ю. Городилов, А. А. Митраков. — Режим доступа : http://vestnik.psu.ru/files/articles/260_27019.p (дата обращения : 24.05.2013).
30. Городилов, А. Ю. Криптоанализ перестановочного шифра с помощью генетического алгоритма [Электронный ресурс] / А. Ю. Городилов. — Режим доступа : http://vestnik.psu.ru//files/articles/8_83883 (дата обращения : 24.05.2013).
