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

Недостатком генетических алгоритмов является наличие слепого поиска. В общем случае это приводит к генерации решений с нарушениями и тем самым увеличивает время поиска и требует дополнительного контроля, генерации большого количества одинаковых решений, генерации большого количества плохо приспособленных решений, что может привести к попаданию в локальный оптимум [10]. Поэтому представляют интерес эвристические методы, инспирированные природными системами, в которых осуществляется поэтапное построение решения задачи (то есть добавление нового оптимального частичного решения к уже построенному частичному оптимальному решению). К методам данного вида относят и муравьиные алгоритмы, моделирующие поведение муравьев, связанное с их способностью быстро находить кратчайший путь от муравейника к источнику пищи. Колония муравьев рассматривается как многоагентная система, в которой каждый муравей-агент действует автономно на основе простых правил (http://rain.ifmo.ru/cat/data/theory/ unsorted/ant-algo-2006/article.pdf). Однако в противоположность примитивному поведению отдельных агентов поведение всей колонии оказывается достаточно разумным. Отметим, что исследования в этой области проводятся с середины 90-х годов, и сегодня известно их применение к квадратичной задаче о назначениях [11], задачам о коммивояжере [12], о раскраске графа [13], к задачам определения оптимальных маршрутов в коммутационных сетях [14], маршрутизации транспортных средств [15], борьбы с вредоносным программным обеспечением (http://chaos.in.ua/news/murav-inyie-alghoritmy-v-dieistvii).

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

Постановка задачи. Понятие блочных методов шифрования. Современная криптография включает в себя следующие основные типы криптосистем: симметричные криптосистемы, криптосистемы с открытым ключом, системы электронной подписи, управление ключами [16, 17]. Кроме того, известны поточные, блочные криптосистемы и блочные криптосистемы с обратной связью [18]. Основные требования к современным криптосистемам изложены в [19], в [18] отмечены также основные характерные признаки криптографических систем и методов (операции с отдельными битами или блоками, зависимость функции шифрования от результатов шифрования предыдущих частей, а также от положения знаков в тексте, симметрия или асимметрия функции шифрования).

В настоящее время актуальной является задача криптоанализа блочных криптосистем, так как переход к блочному шифрованию открывает дополнительные возможности для повышения стойкости криптоалгоритмов. Сведения о криптостойкости ряда блочных алгоритмов, в частности, к линейному и дифференциальному криптоанализу, а также результаты его применения к алгоритму DES приведены в [19, 20]. Основные виды криптоаналитических атак, а также основные принципы построения блочных шифров и их основные преобразования (рассеивание и перемешивание) описаны в [16, 18]. Описание некоторых блочных стандартов шифрования (в том числе стандарта DES) с введенными терминами и обозначениями приводится в [16, 18, 20, 21].

Возможные подходы к криптоанализу блочных криптосистем с использованием генетического поиска изложены в [5, 22, 23]. Рассмотрим возможный подход к реализации криптоанализа с использованием алгоритма муравьиных колоний и покажем, как задача определения секретного ключа может быть сведена к частной задаче о назначениях. Задача поиска алгоритма муравьиных колоний в общем случае заключается в определении позиций для символов из алфавита ключа таким образом, что целевая функция, определяющая оптимальность шифртекста (при заданном открытом тексте) при реализации алгоритма шифрования или оптимальность открытого текста (при заданном шифртексте) при реализации алгоритма криптоанализа, достигает экстремума. То есть по сути данная задача – частный случай квадратичной задачи о назначениях, традиционно являющейся тестовой задачей для оценки эффективности методов поиска.

Описание муравьиного алгоритма. Рассмотрим задачу определения секретного ключа подробнее. В соответствии с [24] задачу о назначениях сформулируем в следующем виде. Пусть xij=1, если объект i назначен в пункт j, и xij=0 в противном случае, Cij  – затраты на передачу объема ресурсов из пункта i в пункт j. В этом случае математическая модель будет выглядеть следующим образом:  при ограничениях  

где n – число объектов и мест их размещения.

Применительно к рассматриваемой задаче криптоанализа введем параметр Cij  – вероятность того, что за символом в позиции i должен следовать символ, стоящий в позиции i+1. Введем также параметр Qi, показывающий, насколько блок текста из i символов носит осмысленный характер, то есть совпадает сo словарным запасом языка. В этом случае целевая функция будет иметь вид

Отметим, что вычисление на каждой итерации значения Q (оценки приспособленности особей) –основной момент при реализации описанного алгоритма. Одним из методов, предлагаемых в [25], является использование целевой функции Якоб­ceна, описанной, например, в [26] и допускающей использование на текстах достаточной длины. Данный метод основан на использовании информации о распределении частот встречаемости биграмм в открытых текстах и использует целевую функцию как сумму разностей по модулю между заранее известным среднестатистическим количеством биграмм и их реальным количеством в шифртексте.

Таким образом, если Dij – элемент матрицы D, равный количеству встретившихся в тексте Т биграмм ij, то целевая функция W в соответствии с [25] будет иметь вид  где Eij – частоты биграмм, зафиксированные в алгоритме в качестве эталонных. Таким образом, матрица Е отражает среднестатистическое распределение и меньшему значению целевой функции будет соответствовать большее значение приспособленности особи (возможно также использование функции 1/W).

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

Общее значение целевой функции R, определяющей оптимальность блока открытого текста при каждом конкретном варианте назначения n символов из алфавита ключа в n позиций, аналогично [11] может быть определено как длина маршрута, соединяющего выбранные элементы декартова произведения [номер позиции ´ номер символа]. Отсюда следует, что секретному ключу, представленному маршрутом с большим значением R, должна соответствовать более высокая концентрация феромона F, которая используется в качестве вероятности выбора очередного маршрута, представляющего очередной вариант ключа, муравьями-агентами. Отметим, что использование феромона для выбора пути муравьями является основным моментом в концепции муравьиных алгоритмов (http://rain.ifmo.ru/cat/data/theory/unsort- ed/ant-algo-2006/article.pdf).

Так, основными операциями муравьиного алгоритма являются 1) создание популяции муравьев, 2) поиск решения, 3) обновление феромона.

На этапе 1 задается начальный уровень феромона, определяющий ненулевые вероятности перехода в следующую вершину. Формулы для определения вероятности перехода между соседними вершинами и нового уровня феромона можно найти по адресу http://rain.ifmo.ru/cat/data/theory/ unsorted/ant-algo-2006/article.pdf.

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

1. Случайным равновероятным образом выбирается m вариантов маршрутов, представляющих m вариантов секретного ключа k1, …, km, и вычисляются значения целевых функций R1, …, Rm путем определения оптимальности блока открытого текста при реализации алгоритма дешифрования для каждого ключа k1, …, km.

2. Комбинациям ik, l размещения символов открытого текста k в позиции i присваивается весовой коэффициент

Fik,l=Rl, l=1, 2, …, m.                                        (1)

3. Для каждой комбинации ik вычисляется результирующая концентрация:

                                                          (2)

Для тех комбинаций ik, которые ни разу не встретились в выборке из m ключей, задается нижнее значение концентрации феромона:

, где 0

4. Производится имитация испарения феромона в соответствии с формулой

                                             (4)

где r – интенсивность испарения; tij – уровень феромона на ребре ij.

5. После переопределения количества феромона определяются новые вероятности размещения символа k в позиции i по формуле

                                                    (5)

6. В соответствии с вычисленными вероятностями Pik формируется d*m новых маршрутов (где d – коэффициент, выбираемый согласно [11] из условия d<1), представляющих варианты секретного ключа, для которых определяются соответствующие блоки открытого текста и критерии Rm+1, …, Rm+m*d, и далее производится выборка из m лучших вариантов. Если оптимальное значение критерия не изменяется в течение некоторого определенного количества циклов, то поиск завершается, в противном случае производится возврат к шагу 2.

Структурная схема криптоанализа алгоритма DES с использованием генетического поиска представлена в [5]. Структурная схема криптоанализа второго типа данного алгоритма на основе метода муравьиных колоний показана на рисун- ках 1 и 2.

Демонстрационный пример. Для иллюстрации функционирования данного алгоритма криптоанализа рассмотрим пример, в котором на основе блока шифртекста небольшой длины требуется определить блок исходного текста и секретный ключ. Пусть алгоритм шифрования использует блоки открытого текста, шифртекста и секретный ключ длиной 6 бит. Для упрощения предположим, что каждый бит шифртекста определяется каждым битом исходного текста и каждым битом ключа (то есть, зная секретный ключ и шифртекст, можно сразу определить исходный текст и наоборот, хотя, как отмечено в [21], после восьми этапов алгоритма DES шифртекст представляет собой случайную функцию всех битов открытого текста и ключа) и что шифртекст и исходный текст содержат символы одного и того же алфавита. Пусть секретный ключ представляет последовательность латинских букв от А до F, а блок шифртекста – строку символов русского языка ИОСАКБ. Вначале для возможности оценки целевой функции ключа составим матрицу С, приведенную в таблице 1 и показывающую вероятность того, что за символом i может следовать символ j (основные характеристики открытых сообщений, в том числе частоты букв, биграмм и сочетаемость букв, приведены в [16]).

Установим число муравьев m=5 и поставим в соответствие каждому из них символ ключа (от А до F).

Таблица 1

Матрица вероятностей появления биграмм в тексте

	Б	О	С	К	А	И
Б	0,01	0,5	0,1	0,01	0,6	0,6
О	0,6	0,02	0,5	0,3	0,1	0,1
С	0,05	0,6	0,05	0,08	0,3	0,3
К	0,01	0,5	0,01	0,01	0,4	0,4
А	0,6	0,1	0,6	0,6	0,01	0,01
И	0,6	0,1	0,6	0,6	0,01	0,01

Итерация 1.

1. На этапе 1 выберем случайным образом m маршрутов, представляющих варианты секретного ключа, и определим значения их критериев R1, …, Rm  путем реализации алгоритма дешифрования. Пусть выбраны варианты секретного ключа:

1. BDCEFA

2. CADFEB

3. AFBCDE

4. FBEDCA

5. DEFBAC

и пусть при реализации алгоритма дешифрования получены следующие строки исходного текста:

1. КСБАОИ R1=0,01+0,05+0,6+0,1+0,1=0,86

2. БКОСИА R2=0,01+0,5+0,5+0,3+0,01=1,32

3. СОАБИК R3=0,6+0,1+0,6+0,6+0,6=2,5

4. ОАКБСИ R4=0,1+0,6+0,01+0,1+0,3=1,11

5. АКБИСО R5=0,6+0,01+ 0,6+0,6+0,6=2,41

Таким образом, поскольку варианты 1, 2, 4, 5 далеки от словарного состава языка, умножим соответствующие значения Ri на Q=0,5, а R3 на Q=0,9, так как после перестановок двух пар букв получается допустимое слово. Получим следующие значения критериев: R1=0,43, R2=0,66, R3=2,25, R4=0,55, R5=1,2.

2. На этапе 2 всем комбинациям размещения символов в позиции присваивается весовой коэффициент (уровень феромона) в соответствии с приведенными выше формулами (1) и (2), аналогичными приведенным в [11]. Для комбинаций, которые не встретились в выборке из m маршрутов, задается нижнее граничное значение концентрации феромона по формуле (3): Fmin=a*maxFik, l. Значение а определим как а=0,1, тогда Fmin=0,22. Отметим, что значение а в общем случае может быть выбрано из условия, что элемент, определяющий нижнее граничное значение концентрации феромона, является минимальным в матрице результирующих концентраций, но необязательно минимальным в матрице результирующих концентраций после испарения. Матрица результирующих концентраций феромона будет иметь вид, показанный в таблице 2.

3. На этапе 3 в соответствии с формулой (4) проводим испарение феромона (табл. 3), определив r=0,6 (см. http://www.wikiznanie.ru/ru-wz/in­dex.php/).

4. Далее вычислим вероятности размещения символов в соответствующие позиции (табл. 4) по формуле (5).

Таблица 2

Матрица результирующих концентраций феромона после 1-й итерации

Символ	Позиция
	1	2	3	4	5	6
О	0,55	2,25	0,66	0,22	0,43	1,2
С	2,25	0,43	0,22	0,66	1,75	0,22
А	1,2	0,55	2,25	0,43	0,22	0,66
И	0,22	0,22	0,22	1,2	2,91	0,98
К	0,43	1,86	0,55	0,22	0,22	2,25
Б	0,66	0,22	1,63	2,8	0,22	0,22

5. В соответствии с матрицей вычисленных вероятностей сформируем новые варианты ключей, выбрав d=0,8. Пусть выбраны варианты секретных ключей:

6. BACEFD

7. EFCDBA

8. ACDEFB

9. DABCFE

Они принадлежат следующим блокам исходного текста (муравьи размещены в позициях С, А, Б, О в соответствии с вероятностями размещения):

6. СОБИКА R6=0,6+0,6+0,6+0,6+0,4=2,8

7. АОБИСК R7=0,1+0,6+0,6+0,6+0,08=1,98

8. БКАСИО R8=0,01+0,4+0,6+0,3+0,1=1,41

9. ОАБСКИ R9=0,1+0,6+0,1+0,08+0,4=1,28

Таблица 3

Матрица результирующих концентраций феромона после испарения

Символ	Позиция
	1	2	3	4	5	6
О	0,22	0,9	0,26	0,22	0,17	0,48
С	0,9	0,17	0,22	0,26	0,7	0,22
А	0,48	0,22	0,9	0,17	0,22	0,26
И	0,22	0,22	0,22	0,48	1,16	0,39
К	0,17	0,74	0,22	0,22	0,22	0,9
Б	0,26	0,22	0,65	1,12	0,22	0,22

 Таблица 4

Матрица вероятностей размещения символов в позиции после 1-й итерации

Символ	Позиция
	1	2	3	4	5	6
О	0,10	0,36	0,11	0,09	0,07	0,19
С	0,40	0,07	0,09	0,11	0,26	0,09
А	0,21	0,09	0,36	0,07	0,08	0,11
И	0,10	0,09	0,09	0,19	0,43	0,16
К	0,07	0,30	0,09	0,09	0,08	0,36
Б	0,12	0,09	0,26	0,45	0,08	0,09

Для вариантов 6, 7, 8, 9 определим значения Q соответственно как 0,9; 0,5; 0,5; 0,7, поскольку в варианте 6 требуется только одна перестановка пары букв, в варианте 9 – две перестановки.

В этом случае R6=2,52, R7=0,99, R8=1,13, R9=0,9. Из полученной популяции выберем m=5 вариантов с лучшими значениями целевой функции. Это будут варианты R6, R3, R8, R5, R7, соответствующие ключам

6. BACEFD

3. AFBCDE

8. ACDEFB

5. DEFBAC

7. EFCDBA

Пусть далее R1=R6=2,52, R2=R3=2,25, R3=R8=1,13, R4=R5=1,2, R5=R7=0,99.

Итерация 2. Имеем следующие маршруты (варианты исходного текста):

1. СОБИКА R1=2,52

2. СОАБИК R2=2,25

3. БКАСИО R3=1,13

4. АКБИСО R4=1,2

5. АОБИСК R5=0,99

1. Матрица результирующих концентраций феромона будет иметь вид, как в таблице 5.

2. На шаге 2 проводится испарение феромона (соответствующая матрица концентраций показана в табл. 6).

Таблица 5

Матрица результирующих концентраций феромона после 2-й итерации

Символ	Позиция
	1	2	3	4	5	6
О	0,22	5,76	0,22	0,22	0,22	2,33
С	4,77	0,22	0,22	1,13	2,19	0,22
А	2,19	0,22	3,38	0,22	0,22	2,52
И	0,22	0,22	0,22	4,71	3,38	0,22
К	0,22	2,33	0,22	0,22	2,52	3,24
Б	1,13	0,22	4,71	2,25	0,22	0,22

3. Матрица вероятностей размещения символов в позиции после 2-й итерации показана в таблице 7.

4. Сгенерируем 4 новых варианта секретного ключа:

6. BEFDAC

7. EADBCF

8. FABCDA

9. CDAFAB

Варианты соответствуют следующим блокам исходного текста (муравьи размещены в позициях С, С, С, А):

6. СОБИКА R6=0,6+0,6+0,6+0,6+0,4=2,8

7. СОБАКИ R7=0,6+0,6+0,6+0,6+0,4=2,8

8. СКБИОА R8=0,08+0,01+0,6+0,1+0,1=0,89

9. АОБАИК R9=0,1+0,6+0,6+0,01+0,6=1,91

Для вариантов 6, 7, 8, 9 определим значения Q соответственно как 0,9; 1; 0,5; 0,4. Тогда получим R6=2,52, R7=2,8, R8=0,45, R9=0,76. Далее из представленной популяции вновь выберем 5 лучших блоков полученного исходного текста с лучшими значениями целевой функции R. Это будут варианты R7, R6, R1, R2, R4, соответствующие ключам

7. EADBCF

6. BEFDAC

1. BACEFD

2. AFBCDE

4. DEFBAC

Обозначим R1=R7=2,8; R2=R6=2,52; R3=R1= =2,52; R4=R2=2,25; R5=R4=1,2.

Таблица 6

Матрица результирующих концентраций феромона после испарения

Символ	Позиция
	1	2	3	4	5	6
О	0,22	2,30	0,22	0,22	0,22	0,93
С	1,9	0,22	0,22	0,5	0,9	0,22
А	0,88	0,22	1,35	0,22	0,22	1,00
И	0,22	0,22	0,22	1,88	1,35	0,22
К	0,22	0,93	0,22	0,22	1,00	1,30
Б	0,45	0,22	1,88	0,9	0,22	0,22

Таблица 7

Матрица вероятностей размещения символов в позиции после 2-й итерации

Символ	Позиция
	1	2	3	4	5	6
О	0,06	0,56	0,05	0,06	0,05	0,24
С	0,49	0,05	0,05	0,13	0,23	0,05
А	0,22	0,05	0,33	0,06	0,05	0,27
И	0,06	0,05	0,05	0,47	0,36	0,05
К	0,06	0,24	0,05	0,06	0,26	0,34
Б	0,12	0,05	0,47	0,22	0,05	0,05

Итерация 3. Имеем следующие варианты блоков исходного текста:

1. СОБАКИ R1=2,8

2. СОБИКА R2=2,52

3. СОБИКА R3=2,52

4. СОАБИК R4=2,25

5. АКБИСО R5=1,2

1. Матрица результирующих концентраций феромона будет иметь вид, как в таблице 8.

2. После испарения феромона получим матрицу концентраций, приведенную в таблице 9.

3. Матрица вероятностей размещения символов в позиции после 3-й итерации показана в таблице 10.

Таблица 8

Матрица результирующих концентраций феромона после 3-й итерации

Символ	Позиция
	1	2	3	4	5	6
О	0,22	10,09	0,22	0,22	0,22	1,2
С	10,09	0,22	0,22	0,22	1,2	0,22
А	1,2	0,22	2,25	2,8	0,22	5,04
И	0,22	0,22	0,22	6,24	2,25	2,8
К	0,22	1,2	0,22	0,22	7,84	2,25
Б	0,22	0,22	9,04	2,25	0,22	0,22

Таблица 9

Матрица результирующих концентраций феромона после испарения

Символ	Позиция
	1	2	3	4	5	6
О	0,22	4,04	0,22	0,22	0,22	0,48
С	4,04	0,22	0,22	0,22	0,48	0,22
А	0,48	0,22	0,9	1,12	0,22	2,02
И	0,22	0,22	0,22	2,5	0,9	1,12
К	0,22	0,48	0,22	0,22	3,14	0,9
Б	0,22	0,22	3,62	0,9	0,22	0,22

Таблица 10

Матрица вероятностей размещения символов в позиции после 3-й итерации

Символ	Позиция
	1	2	3	4	5	6
О	0,04	0,75	0,04	0,04	0,04	0,10
С	0,75	0,04	0,04	0,04	0,09	0,04
А	0,09	0,04	0,17	0,22	0,04	0,41
И	0,04	0,04	0,04	0,48	0,18	0,23
К	0,04	0,09	0,04	0,04	0,61	0,18
Б	0,04	0,04	0,67	0,18	0,04	0,04

4. Продолжая процесс, сформируем 4 варианта секретного ключа:

6. BDACEF

7. EDCABF

8. FCBADE

9. DACEBF

вместе с соответствующими блоками исходного текста (муравьи размещены в позициях С, С, С, А в соответствии с матрицей вероятностей размещений):

6. СОБИКА R6=0,6+0,6+0,6+0,6+0,4=2,8

7. СОБИКА R7=0,6+0,6+0,6+0,6+0,4=2,8

8. СОБАКИ R8=0,6+0,6+0,6+0,6+0,4=2,8

9. АОБИСК R9=0,1+0,6+0,6+0,6+0,08=1,98

Для вариантов 6, 7, 8, 9 определим значения Q соответственно как 0,9; 0,9; 1; 0,5. Получим R6=2,52, R7=2,52, R8=2,8, R9=0,99. Выберем 5 блоков исходного текста с лучшими значениями целевой функции. Это варианты R8, R1, R2, R3, R6, соответствующие ключам

8. FCBADE

1. EADBCF

2. BEFDAC

3. BACEFD

6. BDACEF

Обозначим R1=R8=2,8; R2=R1=2,8; R3=R2=2,52; R4=R3=2,52; R5=R6=2,52.

Итерация 4. Таким образом, на итерации 4 мы имеем следующие варианты блоков исходного текста:

1. СОБАКИ R1=2,8

2. СОБАКИ R2=2,8

3. СОБИКА R3=2,52

4. СОБИКА R4=2,52

5. СОБИКА R5=2,52

1. Матрица результирующих концентраций феромона показана в таблице 11.

2. После испарения феромона получим матрицу концентраций, показанную в таблице 12.

3. Матрица вероятностей размещения символов в позиции после 4-й итерации показана в таблице 13.

 Таблица 11

Матрица результирующих концентраций феромона после 4-й итерации

Символ	Позиция
	1	2	3	4	5	6
О	0,22	13,16	0,22	0,22	0,22	0,22
С	13,16	0,22	0,22	0,22	0,22	0,22
А	0,22	0,22	0,22	5,6	0,22	7,56
И	0,22	0,22	0,22	7,56	0,22	5,6
К	0,22	0,22	0,22	0,22	13,16	0,22
Б	0,22	0,22	13,16	0,22	0,22	0,22

Таблица 12

Матрица результирующих концентраций феромона после испарения

Символ	Позиция
	1	2	3	4	5	6
О	0,22	5,3	0,22	0,22	0,22	0,22
С	5,3	0,22	0,22	0,22	0,22	0,22
А	0,22	0,22	2,22	2,24	0,22	3,02
И	0,22	0,22	0,22	3,02	0,22	2,24
К	0,22	0,22	0,22	0,22	5,3	0,22
Б	0,22	0,22	5,3	0,22	0,22	0,22

Таблица 13

Матрица вероятностей размещения символов в позиции после 4-й итерации

Символ	Позиция
	1	2	3	4	5	6
О	0,03	0,85	0,03	0,03	0,03	0,03
С	0,85	0,03	0,03	0,03	0,03	0,03
А	0,03	0,03	0,03	0,38	0,03	0,50
И	0,03	0,03	0,03	0,50	0,03	0,38
К	0,03	0,03	0,03	0,03	0,85	0,03
Б	0,03	0,03	0,85	0,03	0,03	0,03

4. Продолжая процесс, определим 4 маршрута по вероятностям размещения:

6. СОБИКА R6=2,52

7. СОБИКА R7=2,52

8. СОБАКИ R8=2,8

9. СОБИКА R9=2,52

Маршруты соответствуют отмеченным выше секретным ключам:

6. BEFDAC

7. BACEFD

8. EADBCF

9. BDACEF

Выбирая 5 блоков исходного текста с лучшими значениями R, получим блоки R1, R2, R8, R3, R4.

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

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

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

Литература

1.     Родзин С.И. Интеллектуальные системы. О некоторых алгоритмах, инспирированных природными системами; [под ред. В.М. Курейчика]. М.: Физматлит, 2009. С. 34–45.

2.     Курейчик В.В., Курейчик В.М., Родзин С.И. Концепция природных вычислений, инспирированных природными системами // Изв. ЮФУ. 2009. № 4. С. 16–24.

3.     Сергеев А.С. Исследование возможности организации криптографической атаки с использованием эволюционной оптимизации и квантового поиска при разработке систем передачи и защиты информации // Теоретические и прикладные вопросы современных информационных технологий: матер. 6-й Всерос. науч.-технич. конф. Улан-Удэ: Изд-во ВСГТУ, 2005. С. 61–65.

4.     Cергеев А.С., Крупенин А.В., Третьяков О.П., Васильев А.Е., Чернышев Ю.О. Биоинспирированные алгоритмы криптоанализа асимметричных алгоритмов шифрования на основе факторизации составных чисел // Информационная безопасность – актуальная проблема современности. Совершенствование образовательных технологий подготовки специалистов в области информационной безопасности: сб. тр. Краснодар: Изд-во Военной академии связи, 2011. С. 41–47.

5.     Сергеев А.С. Исследование и разработка методов генетического поиска для организации криптоанализа блочных криптосистем в системах управления безопасностью и защиты информации на примере стандарта шифрования DES // Третья Междунар. конф. по проблемам управления: пленарные докл. и избр. тр. М.: Институт проблем управления, 2006. С. 328–335.

6.     Сергеев А.С., Третьяков О.П., Васильев А.Е., Чернышев Ю.О. Биоинспирированные методы криптоанализа асимметричных алгоритмов шифрования на основе факторизации составных чисел // Вестн. ДГТУ. 2011. Т. 11. № 9 (60). С. 1544–1554.

7.     Фатхи В.А., Сергеев А.С. Исследование возможности применения алгоритма муравьиных колоний для реализации криптоанализа шифров перестановок // Вестн. ДГТУ. 2011. Т. 11. № 1 (52). С. 10–20.

8.     Чернышев Ю.О., Сергеев А.С., Венцов Н.Н. Исследование и разработка методов генетического поиска для реализации криптоанализа алгоритма IDEA и решения основных теоретико-числовых задач криптографии // Вестн. РГУПС. 2009. № 3 (35). C. 70–79.

9.     Курейчик В.М. Модифицированные генетические операторы // Изв. ЮФУ: сер. Технические науки. 2009. № 12. С. 7–14.

10.  Лебедев О.Б. Трассировка в канале методом муравьиной колонии // Изв. ЮФУ: сер. Интеллектуальные САПР. 2009. № 4. С. 46–52.

11.  Васильев Е.М., Свистунов А.А. Решение комбинаторных задач моделированием поведения муравьиных колоний. URL: http://www.v-itc.ru/electrotech/2008/01/pdf/2008-01-15.pdf (дата обращения: 28.01.2013).

12.  Курейчик В.М. О некоторых модификациях муравьиного алгоритма // Изв. ЮФУ. Технические науки: сер. Интеллектуальные САПР. 2008. № 4 (81). С. 7–12.

13.  Costa D. Ants can colour graphs. Journ. of the Operation Research Society (JORS). 1997, vol. 48, pp. 295–305.

14.  Di Caro G. Extending AntNet for best-effort Quality-of-Service routing// Unpublished presentation at ANTS’98 – From Ant Colonies to Artifical Ants: First International Workshop on Ant Colony Optimization, October 15–16, 1998.

15.  Игнатьев А.Л. Использование алгоритма муравьиных колоний для решения задачи маршрутизации транспортных средств. URL: http://2009.it-edu.ru/docs/Sekziya_8/3_Ignat'ev_Ig­natyev.doc (дата обращения: 28.01.2013).

16.  Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии. М.: Гелиос АРВ, 2002. 480 с.

17.  Баричев С.Г. Основы современной криптографии. М.: Горячая линия–Телеком, 2001. 122 c.

18.  Романец Ю.В., Тимофеев П.А., Шаньгин В.Ф. Защита информации в компьютерных системах и сетях. М.: Радио и связь, 2001. 376 с.

19.  Куликов А.Л., Петрова И.Ю. Выбор оптимального блочного алгоритма шифрования трафика в информационной системе вуза. URL: http://systech.miem.edu.ru/2004/n2/Kuli­kov2.htm (дата обращения: 28.01.2013).

20.  Бабенко Л.К., Ищукова Е.А. Современные алгоритмы блочного шифрования и методы их анализа. М.: Гелиос АРВ, 2006. 376 с.

21.  Шнайер Б. Прикладная криптография. М.: Триумф, 2003. 816 с.

22.  Сергеев А.С. Исследование и разработка информа- ционных технологий криптоанализа в системах защиты информации на основе генетического поиска и эволюционной оптимизации на примере стандартов шифрования России // Фундаментальные прикладные проблемы приборостроения, информации и экономики: науч. тр. Юбилейной 10-й Междунар. науч.-практич. конф. М.: Изд-во МГУПИ, 2007. Кн. 2. С. 161–167.

23.  Сергеев А.С. Разработка методов криптоанализа на основе генетического поиска при реализации стратегий и технологий информационной защиты на примере стандартов шифрования России // Коммуникативные стратегии информационного общества: тр. Междунар. науч.-технич. конф. СПб: Изд-во Санкт-Петербургского политех. ун-та, 2007. С. 56–65.

24.  Вагнер Г. Основы исследования операций. М.: Мир, 1972. 336 с.

25.  Городилов А.Ю. Криптоанализ перестановочного шифра с помощью генетического алгоритма. URL: http://vest­nik.psu.ru/files/articles/8_83883 (дата обращения: 28.01.2013).

26.  Аграновский А.В., Хади Р.А. Практическая криптография: алгоритмы и их программирование. М.: СОЛОН-Пресс, 2002. 258 c.

References

1.     Rodzin S.I. Intellektualnye sistemy. O nekotorykh algoritmakh, inspirirovannykh prirodnymi sistemami [Intelligent systems. About some algorithms inspired by natural systems]. Moscow, Fizmatlit Publ., 2009, pp. 34–45 (in Russ.).

2.     Kureychik V.V., Kureyhik V.M., Rodzin S.I. The concept of natural calculations inspired by natural systems. Izvestiya YuFU [Izvestiya SFedU]. 2009, no. 4, pp. 16–24 (in Russ.).

3.     Sergeev A.S. Investigating the possibility of organizing a crypto attack using evolutionary optimization and quantum search when developing data transmission and security systems. Materialy 6 Vserossiyskoy nauch.-tekh. konf. “Teoreticheskie i prikladnye voprosy sovremennykh informatsionnykh tekhnologiy” [Proc. of the 6th All-Russian sci. and tech. conf. “Theoretical and applied questions of modern information technologies”]. Ulan-Ude, East Siberia State Univ. of Technology and Management Publ., 2005, pp. 61–65 (in Russ.).

4.     Sergeev A.S., Krupenin A.V., Tretyakov O.P., Vasilyev A.E., Chernyshev Yu.O. Bio inspired algorithms of cryptanalysis of asymmetric encryption algorithms based on composite numbers factorization. Sbornik trudov “Informatsionnaya bezopasnost – ak­tualnaya problema sovremennosti. Sovershenstvovanie obrazo­vatelnykh tekhnologiy podgotovki spetsialistov v oblasti informa­tsionnoy bezopasnosti” [Collected papers “Information security as a topical issue. Improvements of educational technologies of specialists training in the field of the information security”]. Krasnodar, Voennaya Academiya Svyazi Publ., 2011, pp. 41–47 (in Russ.).

5.     Sergeev A.S. Investigating and developing methods of genetic search to organize a cryptanalysis of block cryptosystems in security control and data security systems with DES as an example. Materialy 3 Mezhdunarodnoy konf. po problemam upravleniya: plenarnye doklady i izbrannye trudy [Proc. of the 3rd int. conf. on management problems: plenary reports and chosen works]. Moscow, Institute of Control Sciences Publ., 2006, pp. 328–335 (in Russ.).

6.     Sergeev A.S., Tretyakov O.P., Vasilyev A.E., Chernyshev Yu.O. Bio inspired methods of cryptanalysis of asymmetric encryption algorithms based on composite numbers factorization. Vestnik DGTU [Vestnik of Don State Technical University]. 2011, vol. 11, no. 9 (60), pp. 1544–1554 (in Russ.).

7.     Fatkhi V.A., Sergeev A.S. Investigating the possibility of application of ant colony algorithm for transposition ciphers cryptanalysis. Vestnik DGTU [Vestnik of Don State Technical University]. 2011, vol. 11, no. 1 (52), pp. 10–20 (in Russ.).

8.     Chernyshev Yu.O., Sergeev A.S., Ventsov N.N. Investigating and developing methods of genetic search to implement a cryptanalysis of IDEA algorithm and solving basic number-theo­retic tasks of cryptography. Vestnik RGUPS [Bulletin of Rostov State Transport University]. 2009, no. 3 (35), pp. 70–79 (in Russ.).

9.     Kureychik V.M. Modifyed genetic operators. Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engeneering Sciences]. 2009, no. 12, pp. 7–14 (in Russ.).

10.  Lebedev O.B. Tracking in a channel using ant colony method. Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engeneering Sciences]. 2009, no. 4, pp. 46–52 (in Russ.).

11.  Vasilyev E.M., Svistunov A.A. Solving combinatorial problems using ant colony behavioral modeling. Available at: http://www.v-itc.ru/electrotech/2008/01/pdf/2008-01-15.pdf (accessed 28 January 2013).

12.  Kureychik V.M. About some modifications of the ant algorithm. Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engeneering Sciences]. Taganrog, 2008, no. 4 (81), pp. 7–12 (in Russ.).

13.  Costa D. Ants can colour graphs. Journ. of the Operation Research Society (JORS). Palgrave Macmillan Publ., 1997, vol. 48, pp. 295–305.

14.  Di Caro G. Extending AntNet for best-effort Quality-of-Service routing. Unpublished presentation at ANTS’98 – From Ant Colonies to Artifical Ants: 1st int.Workshop on Ant Colony Optimization. October 15–16, 1998.

15.  Ignatyev A.L. Using ant colony algorithm to solve the problem of transport routing. Available at: http://2009.it-edu.ru/ docs/Sekziya_8/3_Ignat'ev_Ignatyev.doc (accessed 28 January 2013).

16.  Alferov A.P., Zubov A.Yu., Kuzmin A.S., Cheremushkin A.V. Osnovy kriptografii [The basics of cryptography]. Moscow, Gelios ARV Publ., 2002, 480 p.

17.  Barichev S.G. Osnovy sovremennoy kriptografii [The basics of modern cryptography]. Moscow, Goryachaya liniya–Tele­kom Publ., 2001, 122 p.

18.  Romanec Yu.V., Timofeev P.A., Shangin V.F. Zashchita informatsii v kompyuternykh sistemakh i setyakh [Information security in computer systems and networks]. Moscow, Radio i svyaz Publ., 2001, 376 p.

19.  Kulikov A.L., Petrova I.Yu. Vybor optimalnogo blochnogo algoritma shifrovaniya trafika v informatsionnoy sisteme vuza [Choosing an appropriate block encryption algorithm in a university information system]. Available at: http://systech.miem.edu.ru/ 2004/n2/Kulikov2.htm (accessed 28 January 2013).

20.  Babenko L.K., Ishchukova E.A. Sovremennye algoritmy blochnogo shifrovaniya i metody ikh analiza [Modern algorithms of block encryption and methods of their analysis]. Moscow, Gelios ARV Publ., 2006, 376 p.

21.  Schneier B. Applied cryptography. 2nd ed., John Wiley & Sons Publ., 1996, 784 p.

22.  Sergeev A.S. Investigating and developing information technologies of cryptanalysis in information security systems based on genetic search and evolutionary optimizing with examples from Russian encryption standards. Nauchnye trudy Yubileynoy 10 Mezhdunar. nauchno-praktich. konf. “Fundamentalnye prikladnye problemy priborostroeniya, informatsii i ekonomiki” [Proc. of 10th Anniversary int. scientific and practical conf. “Fundamental applied problems of instrumentation, information and economics”]. Moscow, 2007, vol. 2, pp. 161–167 (in Russ.).

23.  Sergeev A.S. Developing cryptanalysis methods based on genetic search when implementing information security strategies and technologies with examples from Russian encryption standards. Trudy mezhdunar. nauch.-tehnich. konf. “Kommunikativnye strate­gii informatsionnogo obshchestva” [Proc. of the int. scientific and tech. conf. ”Communicative strategy of information society”]. St. Petersburg, 2007, pp. 56–65 (in Russ.).

24.  Vagner G. Osnovy issledovaniya operatsiy [The basics of operations research]. Moscow, Mir Publ., 1972, 336 p.

25.  Gorodilov A.Yu. A transposition cipher cryptanalysis using genetic algorithm. Available at: http://vestnik.psu.ru/files/ar­ticles/8_83883 (accessed 28 January 2013).

26.  Agranovskiy A.V., Khadi R.A. Prakticheskaya kriptogra­fiya: algoritmy i ikh programmirovanie [Practical cryptography: algorithms and their programming]. Moscow, SOLON-Press Publ., 2002, 258 p.