Применение комбинированных биоинспирированных стратегий (генетический алгоритм и алгоритм пчелиных колоний) для реализации криптоанализа классических шифров перестановок

Размещено на http://www.allbest.ru/

Донской государственный технический университет, Ростов-на-Дону

Применение комбинированных биоинспирированных стратегий (генетический алгоритм и алгоритм пчелиных колоний) для реализации криптоанализа классических шифров перестановок

Ю.О. Чернышев, А.С. Сергеев

Аннотация

криптоанализ биоинспирированный демонстрационный шифртекст

Рассматривается задача криптоанализа с использованием новой модели оптимизационных стратегий - комбинированного биоинспирированного алгоритма. Описано применение комбинированного биоинспирированного алгоритма (генетический алгоритм и алгоритм муравьиных колоний) для реализации криптоанализа шифров перестановок. Приводится описание комбинированного алгоритма, отмечены его отличительные особенности, описан демонстрационный пример реализации криптоанализа строки шифртекста данным алгоритмом. Применительно к данному алгоритму показано также, что вероятность получения оптимального варианта решения при реализации комбинированных алгоритмов криптоанализа не может быть меньше вероятности получения оптимального решения при использовании классических биоинспирированных алгоритмов.

Ключевые слова: криптоанализ, биоинспирированный алгоритм, генетический алгоритм, алгоритм пчелиных колоний, кроссинговер, мутация, шифр перестановок.

Введение

В настоящее время научное направление «природные вычисления», объединяющее математические методы, в которых заложен принцип природных механизмов принятия решений, получает все более широкое распространение для решения различного круга оптимизационных задач, в том числе задач криптоанализа. В данных методах и моделях основным определяющим элементом является построение начальной модели и правил, по которым она может изменяться (эволюционировать). В [1] авторами рассматривались методы решения задачи криптоанализа, относящейся к переборным задачам с экспоненциальной временной сложностью, на традиционные симметричные криптосистемы, использующие шифры перестановки и замены, а также на шифры гаммирования с использованием генетических алгоритмов, в [2] - на симметричные и ассиметричные криптосистемы с использованием биоинспирированных методов (алгоритмов муравьиных и пчелиных колоний). В [3] исследована возможность применения методов генетического поиска для реализации криптоанализа блочных криптосистем. Поскольку данные задачи в большинстве своем являются NP-полными (имеют комбинаторную сложность), то, как отмечено в [4], основным мотивом для разработок новых алгоритмов решения комбинаторных задач являются возникшие потребности в решении задач большой и очень большой размерности. Отметим также, что разработке новых моделей биоинспирированных методов глобальной оптимизации посвящена работа [5], где рассмотрены новые биоинспирированные технологии, имитирующие поведение лягушек, кукушек, светлячков, и распространения сорняков. Основная отличительная особенность всех четырех методов состоит в возможности поиска глобального экстремума многоэкстремальных целевых функций с большим числом переменных. В этом плане можно отметить также новые подходы, связанные с применением биоинспирированных алгоритмов (алгоритмы пчелиных колоний) для криптоанализа блочных методов шифрования [18], а также подход, связанный с применением биоинспирированных методов для решения проблемы моделирования процессов распределения потока ресурсов [27].

Тем не менее, как отмечено в [6], разработанные структуры генетических алгоритмов фактически являются “слепыми” поисковыми структурами с присущими им недостатками: генерация решений с нарушениями, что требует дополнительного контроля; генерация большого количества подобных решений; генерация большого количества “плохих” решений; попаданию в локальный оптимум. Поэтому представляет интерес применение эвристических методов, инспирированных природными системами, в которых осуществляется поэтапное построение решения задачи путем добавления нового оптимального частичного решения к уже построенному частичному оптимальному решению. В этом плане можно отметить работы [2,3,7,8], в которых рассматривалось применение алгоритмов муравьиных и пчелиных колоний для криптоанализа классических симметричных, асимметричных и блочных криптосистем. В данной работе мы рассмотрим возможность разработки и применения комбинированного биоинспирированного метода (комбинирование генетического метода и алгоритма пчелиных колоний) для криптоанализа классических шифров перестановок. Отметим также, что в [9,10] приводится обзор авторских работ, посвященных решению задачи криптоанализа классических криптографических методов, а также исследованию возможности применения «алгоритма муравья» и алгоритма «колонии пчел» для реализации криптоанализа перестановочных шифров, а также асимметричных алгоритмов шифрования на основе решения теоретико-числовых задач криптографии. В [11] приводится обзор авторских работ, посвященных решению задачи криптоанализа блочных криптографических методов на основе новых моделей искусственного интеллекта - генетических алгоритмов, методов муравьиных и пчелиных колоний.

Постановка задачи. Генетические алгоритмы и алгоритмы пчелиных колоний

Следует заметить, что в качестве первичного признака, по которому производится классификация шифров, используется тип преобразования, осуществляемого с открытым текстом при шифровании. Если буквы открытого текста при шифровании только меняются местами друг с другом, то данный шифр относится к классу шифров перестановок [1,2,7], основные виды которых описаны, например, в [12,13]. В результате применения данных шифров полученная криптограмма включает только те символы, которые составляют открытый текст, то есть задача определения открытого текста заключается в определении позиций для назначения символов криптограммы таким образом, при котором целевая функция, определяющая оптимальность исходного текста, достигает экстремума. Данную задачу криптоанализа, таким образом, можно представить как задачу о назначениях, цель которой - определить оптимальные варианты размещения символов в позиции.

Отметим, что описание возможного применения алгоритма муравьиных колоний для задач криптоанализа (на основе сведения ее к квадратичной задаче о назначениях, описанной в [14]) приведено в [2,7]. Описание применения генетического алгоритма для реализации криптоанализа классических шифров перестановок наряду с экспериментальными результатами приведено в [1]. В соответствии с [1,3] можно выделить следующие этапы простого генетического алгоритма, впервые описанного Гольдбергом на основе работ Холланда [15,16].

1. Инициализировать и оценить популяцию.

2. Повторять пункты 2.1-2.5, пока не выполнится условие останова.

2.1. Отбор (селекция). Отобрать часть популяции для воспроизводства.

2.2. Скрещивание. Выполнить скрещивание «генов» отобранных родителей.

2.3. Мутация. Случайным образом осуществить мутацию полученной популяции.

2.4. Оценивание. Оценить пригодность популяции (функция fitness).

2.5. На основе полученных значений функции fitness выбрать выживших индивидов.

Отметим, что основные модели, отличительные черты генетических алгоритмов, а также способы реализации их основных этапов описаны, например, в [1,3,17]. Тем не менее, несмотря на имеющую место за последние годы широкую область применимости эволюционных методов, они обладают рядом недостатков, отмеченных выше (наличие «слепого» поиска, приводящего к попаданию в локальный оптимум). Одной из последних разработок в области искусственного интеллекта является алгоритм пчел, который в последнее время используется для нахождения экстремумов сложных многомерных функций [8]. Отметим, что обзор некоторых публикаций, посвященных применению алгоритмов пчелиных колоний для решения комбинаторных теоретико-графовых задач (задача разбиения графа, раскраска графа, сравнение с другими «биоинспирированными» методами), решению задачи размещения, задачи разложения составных чисел на простые сомножители, используемoй при криптоанализе асимметричных алгоритмов, приводится в [8].

Как и ранее в [2,7,8], для решения задачи криптоанализа определим целевую функцию вида

где X_ij=1, если символ i назначен в позицию j, и X_ij=0 в противном случае, С_ij вероятность того, что за символом в позиции i должен следовать символ в позиции i+1. Кроме этого, вводится параметр Q_i, показывающий, насколько фрагмент текста из i символов носит осмысленный характер, то есть совпадает со словарным запасом языка.

Как отмечено в [8], при реализации алгоритма пчелиных колоний каждое решение представляет собой позицию в пространстве поиска, содержащую определенное количество нектара. При этом данное количество нектара определяет значение целевой функции в этой точке. Решение задачи криптоанализа представляет собой последовательность символов алфавита , пройденных при перемещении агентапчелы в пространстве поиска. Целью поиска является определение оптимальной комбинации (последовательности прохождения) символов с максимальным значением целевой функции R, которая определяется комбинациями символов, пройденных агентамипчелами.

Комбинированный алгоритм пчелиных колоний.

Далее при описании алгоритма будем использовать методику и терминологию, используемую в [4,8,18]. Как отмечено в [8,18], итерационный процесс поиска решений при реализации алгоритма криптоанализа заключается в последовательном перемещении агентовпчел в новые позиции в пространстве поиска и формировании соответствующих вариантов текста с последующей проверкой их оптимальности, а также выборе соответствующего оптимального (или квазиоптимального) варианта ключа.

В соответствии с [4,8,19] алгоритм колонии пчел включает следующие основные операции.

1. Формирование пространства поиска и создание популяции пчел.

2. Оценка целевой функции (ЦФ) пчел в популяции путем определения ЦФ, определяющей оптимальность исходного текста.

3. Формирование перспективных участков для поиска в их окрестности.

4. Отправка пчел-разведчиков и поиск агентами-разведчиками перспективных позиций для поиска в их окрестности.

5. Выбор пчел с лучшими значениями ЦФ с каждого участка.

6. Отправка рабочих пчел (пчел-фуражиров) для случайного поиска и оценка их ЦФ.

7. Формирование новой популяции пчел.

8. Проверка условия остановки алгоритма. Если они выполняются, переход к 9, иначе к 2.

9. Конец работы алгоритма.

Структурная схема алгоритма колонии пчел приведена в [19]. В соответствии с [19] в лучшем случае временная сложность пчелиных алгоритмов Т составляет, в худшем случае .

Отметим, что пример реализации алгоритма пчелиных колоний для криптоанализа шифров перестановок (на основе модели, описанной в [14]) приведен в [2,8], для криптоанализа блочных криптосистем на основе определения секретного ключа - в [18]. В связи с этим возникает актуальный вопрос о возможности применения комбинированных биоинспирированных методов для реализации криптоанализа, в том числе, о возможности разработки методов, сочетающих основные черты генетических и пчелиных алгоритмов. Очевидно, что при реализации криптоанализа текстов значительной длины применение генетических операций, производимых над полученными частичными решениями, может существенно сократить временные затраты, а также повысить разнообразие генетического материала популяции, ускоряя процесс сходимости к глобальному оптимуму.

Как отмечено в [26], в гибридных алгоритмах, объединяющих различные либо однотипные алгоритмы, но с различными значениями параметров, преимущества одного алгоритма могут компенсировать недостатки другого. Поэтому одним из основных путей повышения эффективности решения задач глобального поиска в настоящее время является разработка гибридных популяционных алгоритмов. Отметим, что в настоящее время существует значительное число способов гибридизации оптимизационных алгоритмов, некоторые разновидности классификаций данных алгоритмов приведены в [26] (одноуровневая классификация Ванга, двухуровневая классификация Эль-Абда и Камэла, четырехуровневая классификация Рейдла).

В соответствии с классификацией Ванга выделяют три категории гибридных алгоритмов, рассмотренных в [26]: вложенные алгоритмы, алгоритмы типа препроцессор/постпроцессор, коалгоритмы.

В категории методов гибридизации вложением выделяют высокоуровневую и низкоуровневую гибридизации.

Высокоуровневая гибридизация вложением предполагает слабую связь объединяемых алгоритмов, обычно при этом данные алгоритмы сохраняют значительную независимость.

При низкоуровневой гибридизации комбинируемые алгоритмы интегрированы достаточно сильно, так что при низкоуровневой гибридизации алгоритмов, по сути, формируется новый алгоритм.

Отметим, что в [26] приведена общая схема последовательной высокоуровневой гибридизации вложением, которая представлена в следующем виде.

1. Инициализация агентов популяционного алгоритма.

2. Выполнение заданного числа итераций популяционного алгоритма.

3. При полученных координатах агентов выполнение локального поиска с помощью второго вложенного комбинируемого алгоритма. Координаты лучших найденных точек полагаются равными текущим координатам агентов .

4. Проверка выполнения условия окончания выполнения итераций. Если это условие выполнено, завершение вычислений, в противном случае переход к 2.

В качестве примера высокоуровневой гибридизации приведем комбинированный алгоритм криптоанализа шифров перестановок, где в качестве популяционного алгоритма используется алгоритм пчелиных колоний, а в качестве алгоритма локального поиска - генетический алгоритм.

Таким образом, используя терминологию и обозначения, введенные в [4,8,18,], комбинированный алгоритм криптоанализа сформулируем в следующей форме. Как и ранее, будем предполагать, что пространство поиска, в котором размещены символы алфавита шифртекста, представляет собой прямоугольную матрицу А заданного размера m₁ х m₂.

1. Определить начальные параметры алгоритма: количество пчелагентов N; размер популяции пчел М; количество итераций L; количество агентовразведчиков n_r; количество агентовфуражиров n_f; значение максимального размера окрестности л_макс; количество базовых позиций n_b; n_b1 количество базовых позиций, формируемых из лучших позиций а^*, найденных на l-1 итерации; n_rl количество агентовразведчиков, выбирающих случайным образом новые позиции на итерациях 2,3,..,L; n_b2 количество базовых позиций, формируемых из n_rl новых лучших позиций, найденных агентамиразведчиками на l итерации.

2. Задать номер итерации l=1.

3. Разместить n_r агентовразведчиков случайным образом в пространстве поиска, то есть выбрать произвольным образом n_r символов в матрице А. Определить значение ЦФ R равным малому положительному числу.

4. Сформировать множество n_b базовых решений и соответствующее множество базовых позиций А_b={a_bi} с лучшими значениями ЦФ R.

5. f=1 (задание номера агентафуражира).

6. Выбор базовой позиции а_iА_b.

7. Выбор позиции а_s(l), расположенной в окрестности базовой позиции а_i, не совпадающей с ранее выбранными на данной итерации позициями, и соответствующего решения (списка E_s).

8. Для всех вновь включенных позиций рассчитать и поставить им в соответствие списки (частичные решения) E_s и соответствующие значения ЦФ R.

9. f=f+1, если f>n_f, переход к п. 10, иначе к п. 6.

10. Провести операцию кроссинговера (скрещивания) полученных индивидуумов (частичных решений в виде списков E_s, содержащих более двух символов) на основе заданной нормы, получение заданного количества потомков (формирование расширенной популяции).

11. Провести операцию мутации индивидуумов популяции на основе заданной нормы мутации, получение заданного количества мутированных потомков.

12. Подсчитать целевые функции R вновь полученных индивидуумов и умножить на весовой коэффициент Q.

13. Провести селекцию индивидуумов расширенной популяции родителей и потомков для сокращения популяции до размера М.

14. Среди всех значений R_i выбрать лучшее значение R^* и соответствующее решение (список Е^*).

15. Если значение R^*(l) предпочтительней значения R^*(l-1), то сохранить значение R^*(l), в противном случае сохраненным остается значение R^*(l-1).

16. Если l<L (не все итерации пройдены), l=l+1(переход к следующей итерации), переход к п. 17, иначе к п. 21.

17. Начать формирование множества базовых позиций для следующей итерации. Во множество А_b1 включается n_b1 лучших позиций, найденных агентами на итерации l-1.

18. Разместить n_rl агентовразведчиков случайным образом в пространстве поиска для выбора n_rl позиций в пространстве поиска, осуществить выбор этих позиций.

19. Включить в множество А_b2 n_b2 позиций из множества n_rl новых позиций, найденных агентамиразведчиками на итерации l. (n_b2+n_b1= n_b).

20. Определить множество базовых позиций на итерации l как А_b= А_b1 А_b2, перейти к п. 5.

21. Конец работы алгоритма, список Е^* вариант исходного текста с лучшим значением ЦФ R^*.

Таким образом, в данном алгоритме операторы 1-9, 17-21 соответствуют операторам пчелиного алгоритма, обеспечивая формирование пространства решений и глобальный поиск, операторы 10-16 соответствуют операторам генетического алгоритма и обеспечивают локальный поиск в пространстве решений.

Таким образом, применение эволюционных операторов, обеспечивающих повышение разнообразия частичных решений для получения оптимального варианта текста, может оказаться целесообразным при значительном объеме текста и может увеличить скорость схождения к глобальному оптимуму. В этом плане также может оказаться целесообразным применение некоторых модифицированных генетических операторов, описанных, например, в [20,21] (транслокация, сегрегация, рекомбинация), применение моделей параллельных эволюционных стратегий, таких как глобальный параллельный гибридный алгоритм, распределенный параллельный гибридный алгоритм (островная модель) [1,3,22,23], а также некоторые специальные модели генетических алгоритмов (hybrid аlgorithms, CHC, Genitor, клеточная модель), описанных в [1,3,22],

Демонстрационный пример

Как и ранее в [7,8], рассмотрим реализацию представленного алгоритма на демонстрационном примере. Пусть задана строка из 12 символов ДИАИОБСУРНЯЦ, требуется определить возможную перестановку символов, входящую в словарный состав языка. Как и ранее в [7,8], составим матрицу С_ij, показывающую вероятность того, что за символом i может следовать символ j. Матрица С_ij составлена на основе данных, приведенных в [13,24], и показана в табл. 1. Значения, приведенные в [13], промасштабированы и округлены до десятых долей.

Таблица № 1. Вероятность появления биграмм в тексте

	Д И А О Б С У Р Н Я Ц
Д И А О Б С У Р Н Я Ц	0.1 0.8 0.9 0.8 0.1 0.7 0.8 0.6 0.5 0.2 0.1 0.7 0.8 0.4 0.5 0.6 0.8 0.1 0.7 0.8 0.5 0.1 0.8 0.7 0.2 0.4 0.8 0.7 0.2 0.7 0.8 0.5 0.4 0.8 0.5 0.2 0.2 0.9 0.9 0.1 0.9 0.8 0.1 0.1 0.1 0.6 0.7 0.8 0.1 0.1 0.5 0.5 0.2 0.1 0.1 0.3 0.7 0.8 0.9 0.1 0.1 0.6 0.4 0.7 0.1 0.1 0.3 0.1 0.1 0.1 0.4 0.3 0.1 0.7 0.5 0.1 0.1 0.3 0.7 0.9 0.9 0.1 0.3 0.4 0.1 0.3 0.2 0.1 0.2 0.8 0.9 0.9 0.1 0.2 0.4 0.1 0.2 0.3 0.1 0.2 0.1 0.1 0.1 0.1 0.2 0.1 0.2 0.3 0.1 0.1 0.1 0.5 0.4 0.2 0.1 0.1 0.2 0.1 0.1 0.1 0.1

Пространство поиска, как и ранее в [8], определим в виде матрицы А размером 21х24 заполненной символами из алфавита шифртекста, размещенными случайным образом в ячейках с соответствующими координатами (табл. 2).

Будем предполагать, что весовой коэффициент Q используется для списков длиной более 2 символов, используется также операция универсального кроссинговера по маске. Если скрещиваются хромосомы разной длины, то случайным образом выбирается номер позиции начала скрещивания.

Таблица 2. Пространство поиска для комбинированного алгоритма

24

И

Р

Б

Я

И

У

Н

И

С

Р

Ц

О

А

С

И

Р

Б

Я

Б

Р

У

23

Д

И

Н

Я

О

Р

Д

С

Я

И

Р

Н

Б

О

А

С

И

Р

Б

Я

И

22

Р

Д

С

Я

И

Р

Н

Б

У

С

А

И

Я

Б

Р

У

И

А

Ц

О

А

21

Б

Б

Д

И

Н

Я

Ц

А

С

У

С

А

И

Ц

И

Р

Б

Я

И

У

Н

20

О

А

С

И

Р

Б

Я

И

У

Н

И

С

Р

Я

И

Б

А

Р

С

У

Ц

19

Б

Я

И

У

Н

И

С

Р

А

И

Ц

С

У

Ц

Б

Р

Я

Д

С

У

Ц

18

Б

Р

У

И

А

Ц

О

А

С

И

Р

Б

Я

И

Д

Я

О

Р

И

Р

Н

17

С

А

И

Ц

И

Р

Б

Я

И

У

Н

Б

Я

И

У

Н

И

С

Р

Ц

О

16

Р

Д

С

Я

И

Р

Н

Б

У

С

А

И

Ц

С

У

Ц

Д

И

Ц

Я

Б

15

У

Б

Б

Д

И

Н

Я

О

Р

Д

С

Я

И

О

У

Р

Н

С

У

Б

Б

14

Р

Д

С

Я

И

Р

Н

Б

О

А

С

И

А

С

У

С

А

И

Ц

С

У

13

С

А

И

Я

Б

Р

У

И

А

Ц

О

С

И

Р

Б

Я

И

У

Н

И

О

12

Д

И

Н

Я

О

Р

Д

С

Я

И

Р

Н

Б

Д

С

Я

И

Р

Н

Б

У

11

А

Р

С

У

Ц

Д

Н

Я

Б

С

У

С

А

И

Ц

С

У

Ц

Б

Р

Я

10

А

Р

С

У

Ц

Д

Н

Я

Б

С

У

О

Д

Ц

Я

Б

Р

У

И

А

Ц

9

Д

И

Ц

Я

Б

Р

У

И

А

Ц

О

А

С

У

С

А

И

Ц

С

У

Ц

8

У

О

Д

А

С

Ц

О

У

Р

Н

С

У

Б

Б

Д

И

Н

Я

Ц

Ц

Я

7

О

Р

Н

С

У

Б

Б

Д

И

Н

Я

О

Р

Д

С

Я

И

Р

Н

Б

У

6

Б

Я

И

У

Н

Б

Я

И

У

Н

С

А

И

Ц

И

Р

Б

Я

И

У

Д

5

Д

С

Р

У

А

О

И

Ц

Н

Р

Д

Я

О

Р

И

Р

Н

Б

У

С

А

4

А

Д

И

Ц

Я

Б

Р

У

И

А

Ц

О

А

С

И

Р

Б

Я

И

У

Н

3

И

Ц

Б

О

Р

Д

С

Я

И

Р

Н

Б

У

С

А

И

Ц

С

У

Ц

Б

2

Н

У

Ц

Я

И

Б

А

Р

С

У

Ц

Д

Н

Я

Б

С

У

О

Д

А

С

1

Д

С

Р

У

А

О

И

Ц

Н

Р

Д

Я

О

Р

Н

С

У

Б

Б

Д

И

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

Итерация 1.

1. В соответствии с этапами 1-3 алгоритма определим количество агентовразведчиков n_r=10 и разместим их случайным образом в пространстве поиска, то есть выберем произвольным образом n_r символов в матрице А. Пусть это будут символы С(16,1), Р(9,8), Ц(5,11), Д(10,15), Б(13,12), И(14,18), О(7,18), Р(16,21), С(8,23), У(21,24), выделенные в табл. 2 жирным курсивом. Положим значение ЦФ R для всех позиций равным малому положительному числу R=0.001. Определим размер популяции пчел М=10.

2. В соответствии с шагом 4 алгоритма определим множество базовых решений n_b=6 и соответствующие базовые позиции с лучшими значениями ЦФ (на этом этапе, как и в [8], их выберем произвольно). Пусть это будут позиции А_b={С(16,1), Ц(5,11), И(14,18), Д(10,15), Р(16,21), Б(13,12)}.

3. В соответствие с этапами 5-9 алгоритма определим количество агентов-фуражиров n_f=8, размер максимальной окрестности л_макс=20. Пусть базовые позиции выбираются восемью агентами-фуражирами в следующем порядке а₁=Ц(5,11), а₂=И(14,18), а₃=С(16,1), а₄=И(14,18), а₅=С(16,1), а₆=Д(10,15), а₇=Б(13,12), а₈=Р(16,21). Пусть базовым позициям ставятся в соответствие следующие позиции а_s: Ц(5,11)>У(4,11); И(14,18)>И(12,16); С(16,1)>У(13,3); И(14,18)>C(14,16); С(16,1)>Я(16,7); Д(10,15)>И(10,12); Б(13,12)>Д(13,10); Р(16,21)>О(17,18).

Таким образом, в соответствии с шагом 8 будем иметь перечень позиций, списков и значений функции R, определенных в соответствии с табл. 1. Для позиций Ц(5,11), И(14,18), С(16,1), Д(10,15), Б(13,12), Р(16,21) R=0,001, списки Е₁-Е₆ состоят из одного символа, R=0.001. Для позиций: У(4,11) Е₇={ЦУ}, R=0.2; И(12,16) Е₈={ИИ}, R=0.8; У(13,3) Е₉={СУ}, R=0.6; С(14,16) Е₁₀={ИС}, R=0.8; Я(16,7) Е₁₁={СЯ}, R=0.1; И(10,12) Е₁₂={ДИ}, R=0.8; Д(13,10) Е₁₃={БД}, R=0.1; О(17,18) Е₁₄={РО}, R=0.9.

4. В соответствии с шагом 10 алгоритма проведем операцию универсального кроссинговера для списков Е₇ -Е₁₄, выбрав норму 75%. Пусть для получения 6 потомков Е₁₅ -Е₂₀ выбраны списки Е₇-Е₁₀, Е₁₃-Е₁₄, Е₁₀-Е₁₁, и сформированы следующие маски: 10; 01; 01. В этом случае получим следующих потомков: Е₁₅={ИУ}, R=0.1; Е₁₆={ЦС}, R=0.1; Е₁₇={БО}, R=0.8; Е₁₈={РД}, R=0.3; Е₁₉={ИЯ}, R=0.5; Е₂₀={СС}, R=0.1.

5. В соответствии с шагом 11 алгоритма проведем операцию точечной мутации. Будем предполагать далее, что мутация проводится путем случайного выбора хромосом популяции, случайного выбора количества генов и произвольной замены значений выбранных генов на допустимые из произвольно выбранных позиций. Пусть после выбора хромосомы (списка) Е₁₃ меняется значение гена Б на Р(16,21), после выбора хромосомы Е₁₅ меняется значение У на Н(11,17), после выбора хромосомы Е₁₆ меняется значение гена С на А(4,8). В этом случае потомки будут иметь вид: Е₁₃={РД(13,10)}, R=0,3; Е₁₅={ИН(11,17)}, R=0,8; Е₁₆={ЦА(4,8)}, R=0,4.

Таким образом, на итерации 1 мы будем иметь следующий перечень списков (хромосом), координат и значений функции R:

{Ц(5,11)}, {И(14,18)}, {C(16,1)}, {Д(10,15)}, {Б(13,12)}, {P(16,21)}, R=0.001; {ЦУ(4,11)}, R=0.2; {ЦА(4,8)}, R=0.4; {ИИ(12,16)}, R=0.8; {ИС(14,16)}, R=0.8; {ИН(11,17)}, R=0.8; {ИЯ(16,7)}, R=0.5; {СУ(13,3)}, R=0.6; {СЯ(16,7)}, R=0.1 {СС(14,16)}, R=0.1; {ДИ(10,12)}, R=0.8; {БО(17,18)}, R=0.8; {РО(17,18)}, R=0.9; РД(13,10)}, R=0.3; {РД(13,10)}, R=0,3.

6. Проводя в соответствии с шагом 13 элитную селекцию, удалим индивидуумы популяции с наименьшим значением R до сокращения размера популяции до размера М=10. Это индивидуумы {Ц(5,11)}, {И(14,18)}, {C(16,1)}, {Д(10,15)}, {Б(13,12)}, {P(16,21)}, {СС(14,16)}, {СЯ(16,7)}, {ЦУ(4,11)}, РД{(13,10)}.

7. Выбирая среди всех значений R_i лучшее значение, получим, что R^*=0,9; E^*={РО}.

8. Полагаем l=2.

Итерация 2.

1. В соответствии с шагом 17 алгоритма определим число n_b1= 3; включим во множество А_b1 позиции А_b1={РО(17,18), R=0.9; ИН(11,17), R=0.8; ДИ(10,12), R=0.8}.

2. В соответствии с шагом 18 определим количество агентов-разведчиков n_rl=6 и разместим их произвольным образом в пространстве поиска. Пусть произвольным образом выбираются символы СУ(13,3), РД(13,10), Н(19,7), А(10,4), Ц(17,3), И(9,4).

3. В соответствии с шагом 19 включим во множество А_b2 n_b2=3 позиции из множества n_rl=6 позиций, найденных агентамиразведчиками на итерации 2. Пусть это будут позиции А_b2={СУ(13,3), R=0.6; РД(13,10), R=0.3; A(10,4), R=0.001}.

4. Таким образом, на итерации l=2 n_b1+ n_b2=6 и множество базовых позиций А_b={РО(17,18), ИН(11,17), ДИ(10,12), СУ(13,3), РД(13,10), A(10,4)}. Пространство поиска показано в табл. 3, базовые позиции отмечены прямым жирным шрифтом.

5. В соответствие с этапами 5-9 алгоритма определим количество агентов-фуражиров n_f=8, размер максимальной окрестности л_макс=20. Пусть базовые позиции выбираются в следующем порядке:

а₁=РО(17,18), а₂=А(10,4), а₃=ИН(11,17), а₄=А(10,4), а₅=РД(13,10), а₆=РД(13,10), а₇=СУ(13,3), а₈=ДИ(10,12).

Пусть базовым позициям ставятся в соответствие следующие позиции а_s: РО(17,18)>Ц(19,16); А(10,4)>Ц(8,5); ИН(11,17)>ИИ(12,16); А(10,4)>Ц(4,4); РД(13,10)>ИЯ(16,7); РД(13,10)>ИИ(12,16); СУ(13,3)>БО(17,18); ДИ(10,12)>ЦА(4,8).

Таким образом, на данном шаге мы будем иметь следующий список позиций, решений и соответствующих значений функции R.

Таблица 3. Пространство поиска для комбинированного алгоритма после 1 итерации

24

И

Р

Б

Я

И

У

Н

И

С

Р

Ц

О

А

С

И

Р

Б

Я

Б

Р

У

23

Д

И

Н

Я

О

Р

Д

С

Я

И

Р

Н

Б

О

А

С

И

Р

Б

Я

И

22

Р

Д

С

Я

И

Р

Н

Б

У

С

А

И

Я

Б

Р

У

И

А

Ц

О

А

21

Б

Б

Д

И

Н

Я

Ц

А

С

У

С

А

И

Ц

И

Р

Б

Я

И

У

Н

20

О

А

С

И

Р

Б

Я

И

У

Н

И

С

Р

Я

И

Б

А

Р

С

У

Ц

19

Б

Я

И

У

Н

И

С

Р

А

И

Ц

С

У

Ц

Б

Р

Я

Д

С

У

Ц

18

Б

Р

У

И

А

Ц

О

А

С

И

Р

Б

Я

И

Д

Я

РО БО

Р

И

Р

Н

17

С

А

И

Ц

И

Р

Б

Я

И

У

ИН

Б

Я

И

У

Н

И

С

Р

Ц

О

16

Р

Д

С

Я

И

Р

Н

Б

У

С

А

ИИ

Ц

ИС

У

Ц

Д

И

Ц

Я

Б

15

У

Б

Б

Д

И

Н

Я

О

Р

Д

С

Я

И

О

У

Р

Н

С

У

Б

Б

14

Р

Д

С

Я

И

Р

Н

Б

О

А

С

И

А

С

У

С

А

И

Ц

С

У

13

С

А

И

Я

Б

Р

У

И

А

Ц

О

С

И

Р

Б

Я

И

У

Н

И

О

12

Д

И

Н

Я

О

Р

Д

С

Я

ДИ

Р

Н

Б

Д

С

Я

И

Р

Н

Б

У

11

А

Р

С

У

Ц

Д

Н

Я

Б

С

У

С

А

И

Ц

С

У

Ц

Б

Р

Я

10

А

Р

С

У

Ц

Д

Н

Я

Б

С

У

О

РД

Ц

Я

Б

Р

У

И

А

Ц

9

Д

И

Ц

Я

Б

Р

У

И

А

Ц

О

А

С

У

С

А

И

Ц

С

У

Ц

8

У

О

Д

ЦА

С

Ц

О

У

Р

Н

С

У

Б

Б

Д

И

Н

Я

Ц

Ц

Я

7

О

Р

Н

С

У

Б

Б

Д

И

Н

Я

О

Р

Д

С

ИЯ

И

Р

Н

Б

У

6

Б

Я

И

У

Н

Б

Я

И

У

Н

С

А

И

Ц

И

Р

Б

Я

И

У

Д

5

Д

С

Р

У

А

О

И

Ц

Н

Р

Д

Я

О

Р

И

Р

Н

Б

У

С

А

4

А

Д

И

Ц

Я

Б

Р

У

И

А

Ц

О

А

С

И

Р

Б

Я

И

У

Н

3

И

Ц

Б

О

Р

Д

С

Я

И

Р

Н

Б

СУ

С

А

И

Ц

С

У

Ц

Б

2

Н

У

Ц

Я

И

Б

А

Р

С

У

Ц

Д

Н

Я

Б

С

У

О

Д

А

С

1

Д

С

Р

У

А

О

И

Ц

Н

Р

Д

Я

О

Р

Н

С

У

Б

Б

Д

И

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

О(17,18), Е₁={CУБО}, R=1.8; А(10,4), Е₂={А}, R=0.001; Н(11,17), Е₃={ИН}, R=0.8; Д(13,10), Е₄={РД}, R=0.3; У(13,3), Е₅={СУ}, R=0.6; И(10,12), Е₆={ДИ}, R=0.8; Ц(19,16), Е₇={РОЦ}, R=1; Ц(8,5), Е₈={АЦ}, R=0.4; И(12,16), Е₉={ИНИИ}, R=2.4; Ц(4,4), Е₁₀={АЦ}, R=0.4; Я(16,7), Е₁₁={РДИЯ}, R=1.6; И(12,16), Е₁₂={РДИИ}, R=1.9; А(4,8), Е₁₃={ДИЦА}, R=1.3; О(17,18), Е₁₄={РО}, R=0.9.

6. В соответствии с шагом 10 алгоритма проведем операцию универсального кроссинговера по норме 75%, при этом для получения 9 потомков Е₁₅-Е₂₃ выбраны следующие списки: Е₉-Е₁₀ (с позиции 3, потомки Е₁₅, Е₁₆), Е₈ -Е₁₂ (с позиции 2, потомки Е₁₇, Е₁₈), Е₃-Е₁₁ (с позиции 3, потомки Е₁₉, Е₂₀), Е₁₀-Е₁₁ (с позиции 1, потомки Е₂₁, Е₂₂), Е₄-Е₆ (потомок Е₂₃). Пусть сформированы следующие маски: 00, 01, 10, 11, 01. В этом случае получим потомков: Е₁₅={ИНИИ}, R=2.4, Е₁₆={ИНАЦ}, R=2.1, Е₁₇={РАИИ}, R=2.4, Е₁₈={РДЦИ}, R=0.9, Е₁₉={РДИН}, R=1.9, Е₂₀={РДИЯ}, R=1.6, Е₂₁={РДИЯ}, R=1.6, Е₂₂={АЦИЯ}, R=1.4, Е₂₃={РИ}, R=0.7.

7. В соответствии с шагом 11 алгоритма проведем операцию точечной мутации. Пусть после выбора списка Е₁₁ в нем меняется ген Я на Н(11,17), после выбора списка Е₁₅ ген Н меняется на Ц, после выбора списка Е₁₇ ген А меняется на Я, в списке Е₂₃ ген И меняется на Д(13,10). В этом случае получим потомков: Е₁₁={РДИН}, R=1.9, Е₁₅={ИЦИИ}, R=1.4, Е₁₇={РЯИИ}, R=1.1, Е₂₃={РД}, R=0.3.

8. Таким образом, на итерации 2 мы будем иметь следующий перечень списков (хромосом), координат и значений функции R.

{CУБО(17,18)}, R₁=1.8; {А(10,4)}, R₂=0.001; {ИН(11,17)}, R₃=0.8; {РД(13,10)}, R₄=0.3; {СУ(13,3)}, R₅=0.6; {ДИ(10,12)}, R₆=0.8; {РОЦ(19,16)}, R₇=1; {АЦ(8,5)}, R₈=0.4; {ИНИИ(12,16)}, R₉=2.4; {АЦ(4,4)}, R₁₀=0.4; {РДИН(11,17)}, R₁₁=1.9; {РДИИ(12,16)}, R₁₂=1.9; {ДИЦА(4,8)}, R₁₃=1.3; {РО(17,18)}, R₁₄=0.9; {ИЦИИ(12,16)}, R₁₅=1.4; {ИНАЦ(4,4)}, R₁₆=2.1; {РЯИИ(12,16)}, R₁₇=2.4; {РДЦИ(12,16)}, R₁₈=0.9; {РДИН(11,17)}, R₁₉=1.9; {РДИЯ(16,7)}, R₂₀=1.6; {РДИЯ(16,7)}, R₂₁=1.6; {АЦИЯ(16,7)}, R₂₂=1.4; {РД(13,10)}, R₂₃=0.3.

Для списков, состоящих из 3 и более символов, применим весовой коэффициент Q. Определим для списка Е₁ Q=1 и R₁=1.8; для списка Е₇ Q=0.8 и R₇=0.8; для списка Е₉ Q=0.6 и R₉=1.44; для списка Е₁₁ Q=1 и R₁₁=1.9; для списка Е₁₂ Q=0.7 и R₁₂=1.33; для списка Е₁₃ Q=0.7, R₁₃=0.91; для списка Е₁₅ Q=0.9, R₁₅=1.26; для списка Е₁₆ Q=0.8, R₁₆=1.68; для списка Е₁₇ Q=0.5, R₁₇=1.2; для списка Е₁₈ Q=0.4, R₁₈=0.36; для списка Е₁₉ Q=1, R₁₉=1.9; для списка Е₂₀ Q=0.85, R₂₀=1.36; для списка Е₂₁ Q=0.85, R₂₁=1.36; для списка Е₂₂ Q=1, R₂₂=1.4.

В этом случае перечень списков будет следующий:

{CУБО(17,18)}, R₁=1.8; {А(10,4)}, R₂=0.001; {ИН(11,17)}, R₃=0.8; {РД(13,10)}, R₄=0.3; {СУ(13,3)}, R₅=0.6; {ДИ(10,12)}, R₆=0.8; {РОЦ(19,16)}, R₇=0.8; {АЦ(8,5)}, R₈=0.4; {ИНИИ(12,16)}, R₉=1.44; {АЦ(4,4)}, R₁₀=0.4; {РДИН(11,17)}, R₁₁=1.9; {РДИИ(12,16)}, R₁₂=1.33; {ДИЦА(4,8)}, R₁₃=0.91; {PO(17,18), R₁₄=0.9}; {ИЦИИ(12,16)}, R₁₅=1.26; {ИНАЦ(4,4)}, R₁₆=1.68; {РЯИИ(12,16)}, R₁₇=1.2; {РДЦИ(12,16)}, R₁₈=0.36; {РДИН(11,17)}, R₁₉=1.9; {РДИЯ(16,7)}, R₂₀=1.36; {РДИЯ(16,7)}, R₂₁=1.36; {АЦИЯ(16,7)}, R₂₂

статья "Применение комбинированных биоинспирированных стратегий (генетический алгоритм и алгоритм пчелиных колоний) для реализации криптоанализа классических шифров перестановок" скачать

Подобные документы

• Анализ шифров перестановки. Элементы криптоанализа шифров перестановки

  Выбор шифров перестановки для проведения анализа. Анализ алгоритма двух различных шифров, построение блок-схемы алгоритма и программы, разработка общего интерфейса. Сравнение шифров перестановки по результатам шифрования и криптоанализа текстов.
  
  курсовая работа [2,8 M], добавлен 14.01.2014
  

• Изучение классических криптографических алгоритмов

  Изучение классических криптографических алгоритмов моноалфавитной подстановки и перестановки для защиты текстовой информации. Анализ частоты встречаемости символов в тексте для криптоанализа классических шифров. Сущность одноалфавитного метода шифрования.
  
  лабораторная работа [2,8 M], добавлен 25.03.2015
  

• Электронные приборы голосования

  Система электронного голосования (ЭГ). Взлом криптосистем с открытым ключом с помощью криптоанализа. Реализация протокола ЭГ с помощью алгоритма RSA. Использование открепительного талона в протоколе ЭГ. Задача RSA и уязвимость учебного алгоритма RSA.
  
  курсовая работа [3,5 M], добавлен 20.12.2009
  

• Генетический алгоритм

  Определение и описание "генетического алгоритма", идея которого состоит в организации эволюционного процесса, конечной целью которого является получение оптимального решения в сложной комбинаторной задаче. Пример его тривиальной реализации на C++.
  
  контрольная работа [172,1 K], добавлен 24.05.2010
  

• Анализ алгоритмов шифрования в сетях передачи данных

  Краткое описание терминологии, используемой в криптологии. Определение места криптографических методов защиты в общей системе обеспечения безопасности информации. Изучение простых шифров и оценка методов их взлома. Методы современного криптоанализа.
  
  курсовая работа [52,3 K], добавлен 13.06.2012
  

• Генетический алгоритм как метод оптимизации

  Описание генетических алгоритмов. Применение генетического алгоритма для решения задачи коммивояжера. Постановка задачи безусловной оптимизации. Изучение распространения генетических алгоритмов на модель с несколькими взаимодействующими популяциями.
  
  дипломная работа [979,1 K], добавлен 30.05.2015
  

• Основные понятия криптографии (интернет обзор различных источников)

  История алгоритмов симметричного шифрования (шифрования с закрытым ключом). Стандарты на криптографические алгоритмы. Датчики случайных чисел, создание ключей. Сфера интересов криптоанализа. Системы электронной подписи. Обратное преобразование информации.
  
  краткое изложение [26,3 K], добавлен 12.06.2013
  

• Изучение и анализ генетического алгоритма

  Описание принципа работы генетического алгоритма, проверка его работы на функции согласно варианту на основе готовой программы. Основные параметры генетического алгоритма, его структура и содержание. Способы реализации алгоритма и его компонентов.
  
  лабораторная работа [20,2 K], добавлен 03.12.2014
  

• Применение генетического алгоритма для решения задачи коммивояжера

  Этапы работы генетического алгоритма, область его применения. Структура данных, генерация первоначальной популяции. Алгоритм кроссинговера - поиск локальных оптимумов. Селекция особей в популяции. Техническое описание программы и руководство пользователя.
  
  реферат [1014,2 K], добавлен 14.01.2016
  

• Генетический алгоритм

  Программа реализации генетического алгоритма, использование визуальной среды программирования. Руководство пользователя, листинг программы. Возможность ввода параметров: объем популяции, число поколений, коэффициент скрещивания и мутации, число городов.
  
  курсовая работа [2,9 M], добавлен 20.08.2009
  

• Генетические алгоритмы

  Операторы генетического алгоритма. Пример простейшей программы. Процесс генерации и накопления информации о выживании и продолжении рода в ряде поколений популяции. Программа, реализующая простой генетический алгоритм для нахождения минимума функции.
  
  курсовая работа [39,3 K], добавлен 29.10.2012
  

• Анализ алгоритмов шифрования в сетях передачи данных

  Криптографическая защита как элемент систем обеспечения безопасности информации. Исторические шифры и их взлом. Особенности современной криптологии и криптографии. Основные методы современного криптоанализа, их сущность, особенности и характеристика.
  
  курсовая работа [57,1 K], добавлен 14.06.2012
  

• Численное решение алгебраических уравнений методом половинного деления

  Описание математической модели. Обоснование метода реализации. Вид алгоритма и программы. Руководство системного программиста, оператора. Комбинирование метод хорд и касательных. Интерпретация и анализ результатов. Листинг программы, контрольный пример.
  
  курсовая работа [3,3 M], добавлен 12.01.2014
  

• Алгоритм раскраски графа

  Математические графы, области их применения. Способы раскраски вершин и ребер графов, задачи на их применение. Разработка алгоритма, работающего на основе операций с матрицей смежности. Описание логической структуры программы. Пример зарисовки графа.
  
  курсовая работа [145,5 K], добавлен 27.01.2013
  

• Виды и свойства алгоритмов. Решение задачи Майхилла (о стрелках)

  Виды алгоритмов как логико-математических средств, характеристика свойств. Корректный вывод алгоритма при решении вычислительной задачи. Механизм реализации алгоритма, его описание. Решение задачи Майхилла при помощи автоматной модели поведения стрелка.
  
  курсовая работа [53,6 K], добавлен 17.07.2014
  

• Ручная реализация алгоритма решения задачи

  Особенности метода неопределенных множителей Лагранжа, градиентного метода и метода перебора и динамического программирования. Конструирование алгоритма решения задачи. Структурная схема алгоритма сценария диалога и описание его программной реализации.
  
  курсовая работа [1010,4 K], добавлен 10.08.2014
  

• Создание игровой программы "Морской бой"

  Программирование игр с использованием визуальных компонентов. Описание операторов, используемых при практической реализации разработанной программы. Работа над созданием программы "Морской бой", постановка задачи, алгоритм реализации работы, блок-схема.
  
  курсовая работа [175,9 K], добавлен 10.05.2010
  

• Оптимизация структуры распределённого параллельного генетического алгоритма

  Основные особенности эволюционных алгоритмов. Описание алгоритмов селекции, мутации, скрещивания, применяемых для реализации генетических алгоритмов. Вычисление функции приспособленности. Программная реализация. Тестирование и руководство пользователя.
  
  курсовая работа [1,3 M], добавлен 11.03.2014
  

• Алгоритм и его свойства

  Определение понятия "алгоритм". Изображение схемы алгоритма. Разработка схемы действий и этапы решения задач. Рассмотрение функции разрабатываемого приложения. Распределение исходного кода по файлам проекта. Контрольный пример и описание результатов.
  
  реферат [695,9 K], добавлен 28.09.2014
  

• Построение аналитических моделей алгоритмов и оценка их сложности

  Описание формальной модели алгоритма на основе рекурсивных функций. Разработка аналитической и программной модели алгоритма для распознающей машины Тьюринга. Разработка аналитической модели алгоритма с использованием нормальных алгоритмов Маркова.
  
  курсовая работа [1,5 M], добавлен 07.07.2013
  

Другие документы, подобные "Применение комбинированных биоинспирированных стратегий (генетический алгоритм и алгоритм пчелиных колоний) для реализации криптоанализа классических шифров перестановок"

• главная
• рубрики
• по алфавиту
• вернуться в начало страницы
• вернуться к началу текста
• вернуться к подобным работам