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

Работа выполнена при финансовой поддержке РФФИ (проект 12-01-00474).

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

Первые публикации, посвящённые пчелиным алгоритмам для нахождения экстремумов сложных многомерных функций, относятся к 2005 году [12, 13]. В [14] рассмотрена суть этого алгоритма, приведено сравнение алгоритма пчёл с генетическим алгоритмом и алгоритмом, моделирующим поведение муравьев. Описание алгоритма, основанного на поведении колонии пчёл, приводится в [15, 16, 17]. Исследование пчелиных алгоритмов для решения комбинаторных теоретико-графовых задач (задача разбиения графа, раскраска графа, сравнение с другими «биоин-спирированными» методами) приводится в [18, 19]. Можно отметить также работы [20, 21], посвящённые рассмотрению алгоритма решения задачи размещения на основе моделирования поведения пчелиной колонии, основным принципам работы простого пчелиного алгоритма, улучшенного пчелиного алгоритма, алгоритма колонии пчёл, моделирующих поведение пчёл в живой природе в поисках нектара. Алгоритм разложения составных чисел на простые сомножители с использованием пчелиных колоний, используемый при криптоанализе алгоритма RSA, описан авторами в [22, 23]. Обзор актуальных алгоритмов и методов роевого интеллекта (муравьиных, пчелиных алгоритмов, метода роя частиц), их отличительные особенности, достоинства, недостатки и возможности практического применения приведены в [24].

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

Понятие шифров перестановок. В качестве первичного признака, по которому производится классификация шифров, используется тип преобразования, осуществляемого с открытым текстом при шифровании. Если буквы открытого текста при шифровании только меняются местами друг с другом, то данный шифр относится к классу шифров перестановок [25, 26]. Результатом применения данного класса шифров к открытому тексту является строка символов (криптограмма), получаемая путём перестановки символов открытого текста в определённом порядке.

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

Как и в предыдущих работах [8, 27], для решения задачи криптоанализа определим X ij = 1, если объект i назначен в пункт j , и X j = 0 в противном случае. Предположим, что C ij — вероятность того, что за символом в позиции i должен следовать символ в позиции i + 1. Кроме этого, введём параметр Q_i , показывающий, насколько фрагмент текста из i символов носит осмысленный характер, то есть совпадает с словарным запасом языка. В этом случае оптимизационная модель будет иметь вид:

nn

R = ZZ Q i^cij^xij---- > max.                              (1)

i =1 j =1

Элементы C_ij задаются в виде матрицы размерности n х n ( n — число символов текста).

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

Таким образом, множество вариантов решений определяется числом перестановок P = л ! без повторений n символов, входящих в шифртекст в n позициях. Даная задача имеет комбинаторный характер, что приводит к необходимости использования метаэвристических алгоритмов. Алгоритм решения. Основу поведения пчелиного роя составляет самоорганизация, обеспечивающая достижение общих целей роя при двухуровневой стратегии поиска. На первом уровне с помощью пчёл-разведчиков формируется множество перспективных областей-источников, на втором уровне с помощью рабочих пчёл-фуражиров осуществляется исследование окрестностей данных областей. При этом основная цель колонии пчёл — найти источник с максимальным количеством нектара [10].

В алгоритме каждое решение представляет собой позицию в пространстве поиска, содержащую определённое количество нектара. При этом данное количество нектара определяет значение целевой функции в этой точке. Решение задачи криптоанализа представляет собой последовательность символов алфавита x ₁ , x ₂ , ..., x_k , пройденных при перемещении агента-пчёлы в пространстве поиска. Целью поиска является определение оптимальной комбинации (последовательности прохождения) символов с максимальным значением R . Значение целевой функции R определяется комбинациями символов, пройденных агентами-пчёлами, в соответствии с (1).

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

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

Таким образом, в соответствии с [10, 21] общую структуру пчелиного алгоритма представим в следующем виде.

• 1.    Формирование пространства поиска.

• 2.    Оценка целевой функции (ЦФ) пчёл в популяции.

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

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

• 5.    Отправка пчёл-фуражиров для случайного поиска и оценка их ЦФ.

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

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

• 8.    Конец.

Первым этапом пчелиного алгоритма является формирование пространства поиска. Позиция a s пространства поиска представляет собой размещенный в пространстве символ алфавита текста. При этом будем предполагать, что каждая пчела-агент содержит в памяти упорядоченный список E s = { e s , i = 1,2, ..., л } посещённых символов. Список E s , поставленный в соответствие каждому символу в пространстве поиска, который посетила пчела, фактически представляет решение — исходный текст, для которого может быть определена ЦФ. В случае текстов достаточно большой размерности для оценки ЦФ может быть применена функция Якобсена, использованная для криптоанализа в [28‒30]. В случае строк незначительной длины для оценки качества расшифрования может быть использована формула (1).

Основной операцией пчелиного алгоритма является исследование окрестностей перспективных позиций в пространстве поиска. Пусть пространство поиска, в котором размещены символы алфавита шифртекста, представляет собой прямоугольную матрицу А размером m х m . Назовём окрестностью размера λ позиции a s множество позиций a si , находящихся на расстоянии (определяемом как количество элементов матрицы), не превышающем λ, от позиции a s .

Таким образом, для реализации пчелиного алгоритма необходимо задание следующих параметров: количество пчёл-агентов N , количество итераций L , количество агентов-разведчиков n r , количество агентов-фуражиров n f , значение максимального размера окрестности λ макс .

На / = 1 итерации алгоритма n r агентов-разведчиков случайным образом размещаются в пространстве поиска, то есть выбирается произвольным образом n r символов в матрице А . Поскольку на начальном этапе фрагменты текста не определены (состоят из одного символа), значение ЦФ R на начальном этапе полагается равным малому положительному числу.

На следующем шаге алгоритма выбирается n b базовых (лучших) решений, у которых значения ЦФ R не хуже, чем значения ЦФ у любого другого решения. На начальной итерации этот выбор осуществляется, очевидно, случайным образом. Формируется множество базовых позиций A b = { a bi } в пространстве поиска, соответствующих базовым решениям.

На следующем шаге алгоритма в окрестности каждой базовой позиции направляется заданное число пчёл-фуражиров. Отметим, что в [10] предлагается три основных подхода к определению числа агентов-фуражиров, направляемых в окрестности базовых позиций: равномерное распределение фуражиров по базовым позициям, распределение пропорционально значению ЦФ позиции и вероятностный выбор.

После выбора агентом-фуражиром n fi базовой позиции a i реализуется случайный выбор позиции а s , расположенной в окрестности базовой позиции a i . При этом случайным образом определяется значение окрестности λ в границах 1 ≤ λ ≤ λ макс .

Таким образом, будем предполагать, что каждая пчела-агент содержит в памяти упорядоченный список E s посещённых символов пространства поиска с определённой для этого списка ЦФ, и данная последовательность ставится в соответствие последнему посещённому пчелой-агентом символу (позиции) пространства поиска. Аналогично [10] введём понятие области D i , представляющей собой D i = a i U O i , где O i — множество позиций, выбранных агентами-фуражирами в окрестности позиции а i . В каждой области D i выбирается позиция (символ) а с лучшей оценкой ЦФ R i ^* , которую назовём оценкой области D i . Среди всех оценок областей R i ^* выбирается лучшая оценка R i ^* и соответствующее решение (список E s ). Лучшее решение (вариант исходного текста) запоминается, и осуществляется переход к следующей итерации.

На последующих итерациях алгоритма n rl агентов-разведчиков отправляются на поиск новых позиций ( n r <  n ). Множество базовых позиций A b ( / ) формируется из двух частей A_{b 1} ( / ) ^{и A} b 2 ( ^/ ) :

A b ( / ) = A bi ( / ) U A b 2 ( / ) .

Часть A_{b 1} ( / ) содержит n_b1 лучших решений а* , найденных в каждой из областей на итерации / - 1, часть A b 2 ( / ) содержит n_b2 лучших решений из n r позиций, найденных пчёлами-разведчиками на итерации l .

Следовательно, n b 1 + n b 1 = n b . Далее, как и на первой итерации, определяется число агентов-фуражиров, отправляемых в окрестности каждой базовой позиции. Каждым агентом-фуражиром n f выбирается базовая позиция a i ( / ) , а также позиция a s ( / ) , расположенная в окрестности этой базовой позиции. Формируются области D i ( / ) . В каждой области D i ( / ) выбирается лучшая позиция а i ^* c лучшей оценкой ЦФ R i ^* , среди оценок R i ^* выбирается лучшая R ^* . Если R ( / ) предпочтительней, чем R ( / - 1 ) , то соответствующее решение запоминается, и осуществляется переход к следующей итерации.

Таким образом, алгоритм криптоанализа на основе пчелиной колонии можно сформулировать в следующем виде:

• 1.    Определить начальные параметры алгоритма: количество пчёл-агентов N ; количество итераций L ; количество агентов-разведчиков n r ; количество агентов-фуражиров n f ; значение максимального размера окрестности λ макс ; количество базовых позиций n b ; n b 1 — количество базовых позиций, формируемых из лучших позиций а* , найденных на / - 1 итерации; n r — количество агентов-разведчиков, выбирающих случайным образом новые позиции на итерациях 2, 3, …, L ; n b 2 — количество базовых позиций, формируемых из n rl новых лучших позиций, найденных агентами-разведчиками на l итерации.

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

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

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

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

• 6.    Выбор базовой позиции a i е A_b .

• 7.    Выбор позиции a s ( / ) , расположенной в окрестности базовой позиции а , не совпадающей с ранее выбранными на данной итерации позициями, и соответствующего решения (списка E s ).

• 8.    Включить позицию a s в множество О , (где О , — множество позиций, выбранных агентами-фуражирами в окрестности позиции а i ).

• 9.    Для всех вновь включенных позиций рассчитать и поставить им в соответствие решения E s и соответствующие значения ЦФ R .

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

• 11.    Сформировать для каждой базовой позиции а , области D i = a i U O , .

• 12.    В каждой области D i выбрать лучшую позицию а i ^* с лучшим значением ЦФ R i ^* .

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

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

• 15.    Если / <  L (не все итерации пройдены), / = / + 1, переход к п. 16, иначе к п. 20.

• 16.    Начать формирование множества базовых позиций. Во множество А b 1 включается n b 1 лучших позиций, найденных агентами среди позиций а , в каждой из областей D , на итерации / - 1.

• 17.    Разместить n rl агентов-разведчиков случайным образом в пространстве поиска для выбора n rl позиций в пространстве поиска.

• 18.    Включить в множество А b 2 n b 2 лучших позиций из множества n rl новых позиций, найденных агентами-разведчиками на итерации l . Следовательно, n b 2 + n b 1 = n b .

• 19.    Определить множество базовых позиций на итерации / как A b ( / ) = A b1 ( / ) U A b ₂ ( / ) . Перейти к п. 5.

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

Демонстрационный пример. Рассмотрим пример реализации представленного выше алгоритма криптоанализа, аналогичный приведённому в [8, 26]. Пусть задана строка символов: БКСОА. Тре- буется определить возможную перестановку символов, входящую в словарный состав языка. Матрица Cij , показывающая частоту биграмм, приведённая в [8, 26], показана на рис. 1.

Определим пространство поиска в виде матрицы А размером 11 х 11, заполненной символами из алфавита шифртекста, размещёнными случайным образом в ячейках с соответствующими координатами (рис. 2). При реализации алгоритма будем предполагать, что выбор позиции а s , расположенной в окрестности базовой позиции а i , производится пропорционально значению ЦФ R полученного решения (списка E s ).

Б      К      С      О      А Б      0,01     0,01      0,1       0,5       0,6 К     0,01     0,01     0,01      0,5       0,4 С     0,05     0,08     0,05      0,6      0,3 О      0,6      0,3      0,5      0,02      0,1 А      0,6      0,6      0,6      0,1      0,01 Рис. 1. Матрица С , элемент С ij которой определяет вероятность соседства в тексте символов i и j

11

О

А

О

А

С

О

О

О

К

А

Б

10

Б

С

К

А

Б

О

Б

Б

Б

О

С

9

А

С

А

К

С

Б

К

О

С

О

С

8

К

А

С

К

Б

Б

А

О

К

Б

А

7

С

Б

Б

А

А

К

К

С

К

А

Б

6

А

Б

О

К

К

А

О

А

К

Б

К

5

Б

А

Б

К

О

А

А

Б

С

С

Б

4

А

Б

А

С

А

А

С

А

А

О

С

3

О

О

С

Б

К

Б

Б

К

Б

О

Б

2

О

К

О

К

А

С

С

О

Б

С

А

1

Б

К

Б

О

Б

К

А

Б

С

А

К

1

2

3

4

5

6

7

8

9

10

11

Рис. 2. Матрица А , представляющая пространство поиска для пчелиного алгоритма

Итерация 1.

• 1.    Определим количество агентов-разведчиков n r = 7 и разместим их случайным образом в пространстве поиска, то есть выберем произвольным образом n r символов в матрице А . Пусть это будут символы К(5, 6), С(7, 4), А(1, 4), А(1, 6), Б(6, 9), О(10, 4), К(11, 1), выделенные на рис. 2 курсивом. Положим значение ЦФ R для всех позиций равным малому положительному числу R = 0,001.

• 2.    Определим множество базовых решений n b = 5 и соответствующие базовые позиции с лучшими значениями ЦФ (на этом этапе их выберем произвольно). Пусть это будут позиции A_b = { К ( 5, 6 ) , Б ( 6, 9 ) , С ( 7, 4 ) , О ( 10, 4 ) , А ( 1, 4 ) } .

• 3.    Определим число агентов-фуражиров n f = 6 и размер окрестности Х_макс = 3. Пусть базовые позиции выбираются в следующем порядке А, О, Б, К, С, О и им ставятся в соответствие следующие позиции а s : А → К(2, 2); О → А(9, 4); Б → К(7, 9); К → C(4, 4); С → К(8, 3); О → А(11, 2). Таким образом, на данном шаге мы будем иметь следующий список позиций, решений и соответствующих значений ЦФ: позиции К(5, 6), Б(6, 9), С(7, 4), О(10, 4), А(1, 4), R = 0,001, список Е состоит из одного символа; позиция К(2, 2), E = { АК } , R = 0,6; позиция А(9, 4), E = { ОА } , R = 0,1; позиция К(7, 9), E = { БК } , R = 0,01; позиция C(4, 4), E = { КС } , R = 0,01; позиция К(8,3), R = 0,08; позиция А(11, 2), E = { ОА } , R = 0,1. Области D i будут иметь вид:

• 4.    В каждой области D i выберем лучшую позицию а i ^* с лучшим значением ЦФ R i ^* . Получим D 1 → К(2, 2), R 1^* =0,6; D 2 → А(9, 4), R 2^* =0,1; D 3 → К(7, 9), R 3^* =0,01; D 4 → С(4, 4), R 4^* =0,01; D 5 → К(8, 3), R 5^* =0,08.

• 5.    Выбирая среди всех значений R i лучшее значение, получим, что R *(1)=0,6; E - ( 1 ) = { АК } .

• 6.    Полагаем l = 2.

D = { А ( 1,4 ) ,K ( 2,2 ) } ; D ₂ = { О ( 10,4 ) ,А ( 9,4 ) ,А ( 11,2 ) } ; D 3 = { Б ( 6,9 ) ,K ( 7,9 ) } ; D 4 = { К ( 5,6 ) ,С ( 4,4 ) } ; D ₅ = { С ( 7,4 ) , К ( 8,3 ) } .

Итерация 2.

• 1.    Определим число n_b1 = 3. Во множество А_Ь1 включается n_b1 лучших позиций, найденных агентами среди позиций а i ^* в каждой из областей D i на итерации 1. Получим A_b1 = { К ( 2, 2 ) , А ( 9, 4 ) , К ( 8, 3 ) } . Этим позициям поставлены в соответствие списки, представленные на рис. 3.

• 2.    Определим количество агентов-разведчиков n_rl = 5 и разместим их произвольным образом в пространстве поиска. Пусть будут выбраны символы О(7, 6), О(10, 3), Б(8, 1), А(8, 6), К(3, 10).

• 3.    Включение в множество A_b 2 n_{b 2} = 2 лучших позиций из множества n_rl новых позиций, найденных агентами-разведчиками на итерации 2. Пусть A_{b 2} = { О ( 10, 3 ) , Б ( 8, 1 ) } . Таким образом, П ь1 + П ь 2 = 5 и A b = { К ( 2, 2 ) , А ( 9, 4 ) , К ( 8, 3 ) , О ( 10, 3 ) , Б ( 8, 1 ) } .

• 4.    Как и ранее, полагаем n f = 6 и размер окрестности Л_макс = 3. Пусть базовым позициям ставятся в соответствие следующие позиции из их окрестностей: К(2, 2) → О(2, 3); А(9, 4) → Б(8, 5); К(8, 3) → О(8, 2); О(10, 3) → А(11, 2); Б(8, 1) → А(10, 1); О(10, 3) → С(11, 4). Таким образом, на данном шаге мы будем иметь следующий список позиций, решений и соответствующих значений ЦФ: позиция К(2, 2), E = { АК } , R = 0,6; позиция А(9, 4), E = { ОА } , R = 0,1; позиция К(8, 3), E = { СК } ,

• 5.    В каждой области D i выберем лучшую позицию а i ^* с лучшим значением ЦФ R i ^* . Получим D 1 → О(2, 3), R 1^* =0,66; D 2 → Б(8, 5), R 2^* =0,42; D 3 → О(8, 2), R 3^* =0,58; D 4 → С(11, 4), R 4^* =0,5; D 5 → А(10, 1), R 5^* =0,6.

• 6.    Выбирая среди всех значений R i лучшее значение, получим, что R *( 2 ) = 0,66; E * ( 1 ) = { АКО } .

• 7.    Полагаем l = 3.

  11	О	А	О	А	С	О	О	О	К	А	Б
  10	Б	С	К	А	Б	О	Б	Б	Б	О	С
  9	А	С	А	К	С	Б	К	О	С	О	С
  8	К	А	С	К	Б	Б	А	О	К	Б	А
  7	С	Б	Б	А	А	К	К	С	К	А	Б
  6	А	Б	О	К	К	А	О	А	К	Б	К
  5	Б	А	Б	К	О	А	А	Б	С	С	Б
  4	А	Б	А	С	А	А	С	А	ОА	О	С
  3	О	О	С	Б	К	Б	Б	СК	Б	О	Б
  2	О	АК	О	К	А	С	С	О	Б	С	А
  1	Б	К	Б	О	Б	К	А	Б	С	А	К
  	1	2	3	4	5	6	7	8	9	10	11

R = 0,08; позиции О(10, 3), Б(8, 1), R = 0,001, список Е состоит из одного символа; позиция

О(2, 3), E = { АКО } , R = 1,1; позиция Б(8, 5), E = { ОАБ } , R = 0,7; позиция О(8, 2), E = { СКО } ,

R = 0,58; позиция А(11, 2), E = { ОА } , R = 0,1; позиция А(10, 1), E = { БА } , R = 0,6; позиция

С(11, 4), E = { ОС } , R = 0,5. Отметим, что фрагменты текста, состоящие из трёх и более символов, умножим на значения Q i в соответствие с частотой встречаемости. Для списков АКО, ОАБ, СКО положим соответственно Q = 0,6; Q = 0,6; Q = 1. В этом случае для позиции О(2, 3), E = { АКО } , R = 0,66 ; для позиции Б(8, 5), E = { ОАБ } , R = 0,42 ; для позиции О(8, 2), E = { СКО } , R = 0,58. Области D i будут иметь вид D 1 = { К ( 2,2 ) , О ( 2,3 ) } ; D 2 = { А ( 9,4 ) , Б ( 8,5 ) } ; D ₃ = { К ( 8,3 ) ,О ( 8,2 ) } ; D 4 = { О ( 10,3 ) , А ( 11,2 ) , С ( 11,4 ) } ; D = { Б ( 8,1 ) , А ( 10,1 ) } .

Рис. 3. Матрица А , представляющая пространство поиска для пчелиного алгоритма после 1 итерации

Итерация 3.

• 1.    Определим, как и ранее, число n_b1 = 3 . Во множество A_b1 включается n_b1 лучших позиций, найденных агентами среди позиций а i ^* в каждой из областей D i на итерации 2. Получим A_b1 = { О ( 2, 3 ) , А ( 10, 1 ) , О ( 8, 2 ) } . Этим позициям поставлены в соответствие списки, представленные на рис. 4.

• 2.    Определим количество агентов-разведчиков n rl = 5 и разместим их произвольным образом в пространстве поиска. Пусть будут выбраны символы К(2, 2), О(1, 11), К(8, 3), А(10, 11), А(3, 9).

• 3.    Включение в множество A b ₂ n_{b 2} = 2 лучших позиций из множества n r новых позиций, найденных агентами-разведчиками на итерации 2. На данной итерации, A_{b 2} = { К ( 2, 2 ) , К ( 8, 3 ) } . Таким образом, n_{b 1} + n_{b 2} = 5 и A_b = { О ( 2, 3 ) , А ( 10, 1 ) , О ( 8, 2 ) , К ( 2, 2 ) , К ( 8, 3 ) } .

• 4.    Полагаем n f = 6 и размер окрестности Л_макс = 3. Поставим базовым позициям в соответствие следующие позиции из их окрестностей: О(2, 3) → Б(4, 3); А(10, 1) → К(11, 1); О(8, 2) → А(10, 1); К(2, 2) → О(3, 2); К(8, 3) → А(9, 4); О(8, 2) → Б(8, 1). Таким образом, получаем следующий список позиций, решений и соответствующих значений ЦФ: позиция О(2, 3), E = { АКО } , R = 1,1; позиция А(10, 1), E = { БА } , R = 0,6; позиция О(8, 2), E = { СКО } , R = 0,58; позиция К(2, 2), E = { АК } , R = 0,6; позиция К(8, 3), E = { СК } , R = 0,08; позиция Б(4, 3), E = { АКОБ } , R = 1,7; позиция К(11, 1), E = { БАК } , R = 1,2; позиция А(10, 1), E = { СКОБА } , R = 1,78; позиция О(3, 2), E = { АКО } , R = 1,1; позиция О(9, 4), E = { СКООА } , R = 0,7; позиция Б(8, 1), E = { СКОБ } , R = 1,18 . Фрагменты текста, состоящие из трёх и более символов, умножим на значения Q i в соответствие с частотой встречаемости. Для списков АКО, СКО, АКОБ, БАК, СКОБА, СКООА, СКОБ положим соответственно Q = 0,6; Q = 1; Q = 0,7; Q = 1; Q = 1; Q = 0,8; Q = 1. В этом случае для позиции О(2, 3), E = { АКО } , R = 0,66; для позиции О(8, 2), E = { СКО } , R = 0,58; для позиции Б(4, 3), E = { АКОБ } , R = 1,19 ; для позиции К(11, 1), E = { БАК } , R = 1,2 ; для позиции А(10, 1), E = { СКОБА } , R = 1,78; для позиции О(3, 2), E = { АКО } , R = 0,66 ; для позиции О(9, 4), E = { СКООА } , R = 0,56 ; для позиции Б(8, 1), E = { СКОБ } , R = 1,18 .

Таким образом, на данной итерации позиции А(10, 1) соответствует список E = {СКОБА} с максимальным значением ЦФ R = 1,78. Данная позиция, очевидным образом, будет включена в множество Аb для следующей итерации алгоритма, и списки с лучшим значением ЦФ будут осуществлять постепенное заполнение популяции решений.

11	О	А	О	А	С	О	О	О	К	А	Б
10	Б	С	К	А	Б	О	Б	Б	Б	О	С
9	А	С	А	К	С	Б	К	О	С	О	С
8	К	А	С	К	Б	Б	А	О	К	Б	А
7	С	Б	Б	А	А	К	К	С	К	А	Б
6	А	Б	О	К	К	А	О	А	К	Б	К
5	Б	А	Б	К	О	А	А	Б	С	С	Б
4	А	Б	А	С	А	А	С	А	ОА	О	С
3	О	АКО	С	Б	К	Б	Б	СК	Б	О	Б
2	О	АК	О	К	А	С	С	СКО	Б	С	А
1	Б	К	Б	О	Б	К	А	Б	С	БА	К
	1	2	3	4	5	6	7	8	9	10	11

Рис. 4. Матрица А , представляющая пространство поиска для пчелиного алгоритма после 2 итерации

Заключение. Рассмотрена возможность применения метода пчелиной колонии для решения задачи криптоанализа перестановочного шифра, приведён пример, иллюстрирующий схему реализации алгоритма. В отличие от классических подходов, описанных, например, в [10, 15], в задаче криптоанализа осуществляется поиск экстремума немонотонной функции, то есть построение списка Е с наилучшим значением ЦФ не означает его оптимальность на последующих итерациях. В связи с этим при реализации алгоритма может оказаться целесообразным учитывать следующие отличительные особенности:

• •    пространство поиска должно быть достаточно большим для предотвращения попадания в локальный оптимум;

• •    на каждой последующей итерации сохраняются списки, поставленные в соответствие каждому символу пространства поиска на предыдущей итерации (как показано на рис. 4);

• •    при наличии временных и вычислительных ресурсов подсчёт целевой функции для каждого списка может производиться после достижения списком длины шифруемого текста (как при реализации муравьиного алгоритма криптоанализа, описанного в [8]);

• •    для предотвращения попадания в локальный оптимум могут также использоваться операторы, применяемые в эволюционном моделировании (например, оператор мутации).

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