Проектирование и разработка информационных систем

1010001x0011001x0000001x0101101x1110001x0000001x0100001x0100100x 
Ожидаемое значение изменения уровня феромонов 0,129147 при 
входных параметрах лучшего значения фитнесс-функции на итерации 0.75. 
Изменение уровня феромонов представлено в таблице 4.13. 
Таблица 4.13 
Увеличение уровня феромона
Переход 
в области 
поиска 
Начальное распределение феромонов 
Распределение феромонов
после 1 итерации 
0-0 
0-1 
1-0 
1-1 
0-0 
0-1 
1-0 
1-1 
-1 - 0 
0,50000 
0,50000 
- 
- 
0,50000 
0,62915 
- 
- 
0 - 1 
- 
0,50000 
0,50000 
- 
- 
0,50000 
0,62915 
- 
1 - 2 
- 
0,50000 
0,25000 
0,25000 
- 
0,62915 
0,25000 
0,25000 
2 - 3 
- 
0,25000 
0,50000 
0,25000 
- 
0,25000 
0,62915 
0,25000 
3 - 4 
0,25000 
0,25000 
0,25000 
0,25000 
0,37915 
0,25000 
0,25000 
0,25000 
4 - 5 
0,50000 
- 
0,25000 
0,25000 
0,62915 
- 
0,25000 
0,25000 
5 - 6 
- 
0,75000 
0,25000 
- 
- 
0,87915 
0,25000 
- 
6 - 7 
- 
0,25000 
0,25000 
0,50000 
- 
0,25000 
0,37915 
0,50000 

---

78 
Полученный результат соответствует ожидаемым. 
Параметр, отражающий какой уровень феромонов останется после 
испарения
, задается в качестве параметра алгоритма rho,
и применяется ко всем 
возможным переходам (3-6). У
ровень остающихся феромонов rho задается, как 
параметр алгоритма и равен 0,9500. Ожидаемые результаты распределения 
уровня феромонов приведены в таблице 4.14.
Таблица 4.14
Уменьшение уровня феромона 
Переход 
в области 
поиска 
Распределение феромонов до испарения 
Ожидаемое 
распределение феромонов после испарения 
0-0 
0-1 
1-0 
1-1 
0-0 
0-1 
1-0 
1-1 
-1 - 0 
0,50000 
0,62915 
- 
- 
0,47500 
0,59769 
- 
- 
0 - 1 
- 
0,50000 
0,62915 
- 
- 
0,47500 
0,59769 
- 
1 - 2 
- 
0,62915 
0,25000 
0,25000 
- 
0,59769 
0,23750 
0,23750 
2 - 3 
- 
0,25000 
0,62915 
0,25000 
- 
0,23750 
0,59769 
0,23750 
3 - 4 
0,37915 
0,25000 
0,25000 
0,25000 
0,36019 
0,23750 
0,23750 
0,23750 
4 - 5 
0,62915 
- 
0,25000 
0,25000 
0,59769 
- 
0,23750 
0,23750 
5 - 6 
- 
0,87915 
0,25000 
- 
- 
0,83519 
0,23750 
- 
6 - 7 
- 
0,25000 
0,37915 
0,50000 
- 
0,23750 
0,36019 
0,47500 
Данные полученные в результате тестирования подтверждают 
ожидаемые значения. 
5. Фиксирование бит при условии достижении параметра delta.
Цель тестирования: убедиться, что при достижении параметра биты в 
ключе фиксируются, как найденные. 
Параметр delta для определения будет ли зафиксирован бит, как 
определенный, задан, как входные данные и для тестирования равен 0,6. Также 
для тестирования фиксирования бит количество тестовых раундов 
криптоанализа было увеличено до 4.

---

79 
Для определения будет ли зафиксирован бит используются 
соотношения (3-7) и (3-8):
Оптимальный ключ 1: 
1010101x1111111x0101111x0001101x0001110x0000110x0100001x0000110x 
Оптимальный ключ 2: 
0110001x1111111x0100001x0001101x0001110x0011110x0101101x0100100x 
Оптимальный ключ 3: 
1010001x0011001x0100001x0001101x0010111x0000001x0100011x0010100x 
optimum_keys_stat[k] >= оptimum_keys * delta
= 3 * 0,6
= 1,8 (1) 
optimum_keys_stat[k] <= оptimum_keys * (1 - delta) = 3 * (1 - 0,6) = 1,2 (2) 
Результаты фиксации бит приведены в таблице 4.15 
Таблица 4.15
Фиксация значения бита
[k], 
бит 
Значение 
бита
ключ 1 
Значение 
бита
ключ 2 
Значение 
бита 
ключ 3 
Optimum 
keys stat 
[k]
Выполнение 
условия
(1) или (2) 
Установка 
значения 
бита 
0 
1 
0 
1 
2 
(1) 
1 
1 
0 
1 
0 
1 
(2) 
0 
2 
1 
1 
1 
3 
Не выполнено 
- 
3 
0 
0 
0 
0 
Не выполнено 
- 
4 
1 
0 
0 
1 
(2) 
0 
5 
0 
0 
0 
0 
Не выполнено 
- 
6 
1 
1 
1 
3 
Не выполнено 
- 
7 
1 
1 
0 
2 
(1) 
1 
Результат тестирования соответствует ожиданиям. 
6. 
Тестирование 
использования 
зафиксированных 
бит 
при 
инициализации уровня феромонов следующего раунда.
Цель тестирования: убедиться, что в следующем раунде для 
инициализации уровня феромонов будут использованы биты зафиксированные 
на предыдущем раунде, то есть переход в эти значения будет иметь 
обязательный характер. 

---

80 
Рассмотрим первые 8 бит. 
После нахождения третьего оптимального ключа были зафиксированы 
биты: 
Бит 
0 1 2 3 4 5 6 7 
Значение 1 0
0 
1 
Случайные ключи были сформированы по общему правилу. 
Бит/ 
ключ 
0 1 2 3 4 5 6 7 
1 
1 0 1 0 0 0 1 1 
2 
0 1 0 1 1 1 0 1 
3 
0 1 1 1 0 0 1 1 
4 
1 0 1 0 1 0 1 0 
Несмотря на формирование ключей, для определения уровня феромонов 
должны использоваться значения уже установленных бит (таблицы 4.16, 4.17).
Таблица 4.16
Распределение начального значения феромонов по «пути» муравьев
Переход/ 
ключ 
tau[4 * k + 0] 
0 — 0 
tau[4 * k + 1] 
0 — 1 
tau[4 * k + 2] 
1 — 0 
tau[4 * k + 3] 
1 — 1 
1 
2 
3 
4 
1 
2 
3 
4 
1 
2 
3 
4 
1 
2 
3 
4 
-1 - 0 
- 
- 
- 
- 
0,25 0,25 - 
0,25 - 
- 
- 
- 
- 
- 
- 
- 
0 - 1 
- 
- 
- 
- 
- 
- 
0,25 - 
0,25 0,25 - 
0,25 - 
- 
- 
- 
1 - 2 
- 
0,25 - 
- 
0,25 - 
- 
0,25 - 
- 
0,25 - 
- 
- 
- 
- 
2 - 3 
- 
- 
- 
- 
- 
0,25 0,25 - 
0,25 - 
- 
0,25 - 
- 
- 
- 
3 - 4 
0,25 - 
- 
0,25 - 
- 
- 
- 
- 
0,25 - 
- 
- 
- 
0,25 - 
4 - 5 
0,25 - 
- 
0,25 - 
0,25 - 
- 
- 
- 
0,25 - 
- 
- 
- 
- 
5 - 6 
- 
- 
0,25 - 
0,25 - 
- 
0,25 - 
0,25 - 
- 
- 
- 
- 
- 
6 - 7 
- 
- 
- 
- 
- 
0,25 0,25 - 
- 
- 
- 
- 
0,25 - 
- 
0,25 

---

81 
Таблица 4.17
Итоговое распределение начального значения феромонов по «пути» муравьев
Переход в 
области поиска 
tau[4 * k + 0] 
0 — 0 
tau[4 * k + 1] 
0 — 1 
tau[4 * k + 2] 
1 — 0 
tau[4 * k + 3] 
1 — 1 
-1 - 0 
- 
1 
- 
- 
0 - 1 
- 
- 
1 
- 
1 - 2 
0,25 
0,75 
- 
- 
2 - 3 
- 
0,25 
0,50 
0,25 
3 - 4 
0,50 
- 
0,50 
- 
4 - 5 
0,75 
0,25 
- 
- 
5 - 6 
- 
0,75 
0,25 
- 
6 - 7 
- 
0,25 
- 
0,75 
Полученные результаты подтверждаются. 
4.3 Тестирование реализации генетического алгоритма 
После реализации системы было проведено тестирование для алгоритмов 
шифрования DES и AES. Входные параметры перечислены в таблице 4.18. 
Таблица 4.18
Входные параметры для тестирования реализованной системы криптоанализа.
Переменная 
Значение 
Описание 
parents_to_keep 
2 
количество наилучших особей родительского поколения, 
которые сохраняются в следующем поколении 
mutation_rate 
0.02 
вероятность мутации 
delta 
0.70 
Параметр для установки известных бит 
generations 
2 
Количество поколений 
population_size 
4 
Количество популяций в поколении 
key_len 
128 
Длина ключа шифрования
(в случае алгоритма шифрования AES) 
des_rounds 
1 
Количество раундов алгоритма шифрования 
(в случае алгоритма шифрования DES) 

---

82 
4.3.1 
Тестирование реализации генетического алгоритма для AES
 
1.Формирование начальных популяций.
Начальная 
популяция 
заполняется 
ключами 
сформированными 
случайным образом.
Population: 0
01111101001101001100000010011000001101001010001001100011110101001111
001101011011011100110111110010011110010011110001101000100011
Population: 1 
11101101011111111011111000110010101100111101110101111110011001011001
101010001011011001101100010001001000111010100101111000001011
Population: 2 
11000001101111100101011100001101010000110000110111011011100010010101
000101010101000010110010000000111001000101000001001111001010
Population: 3 
01100100101000100000010111001111000000000111100010011001010110101111
011100000000101111101000000011101010111011110100101101011011
Определение значений фитнесс-функции начальной популяции по 
формуле (6) (таблице 4-19).
Таблица 4.19
Значение фитнесс-функции для начальных популяций
Популяция 
Число совпавших бит в 
тестовом и оригинальном 
шифртекстах (из всего бит) 
Фитнесс-
функция 
Population: 0
56 (128)
0,437500
Population: 1
64 (128)
0,500000
Population: 2
60 (128)
0,468750
Population: 3
65 (128)
0,507812
Определение лучшего ключа начальной популяции.

---

83 
По результатам формирования начальных популяций 
Population: 3 
имеет лучшее значение фитнесс-функции 0,507812. Ключ сформированный в 
Population: 3 записывается, как лучший ключ (Best key).
Затем происходит сортировка популяции по значению фитнесс-функции 
(таблица 4.20)
Таблица 4.20
Результат сортировки
Популяция после сортировки 
Популяция 
Значение фитнесс-функции 
Population: 0
Population: 3
0,507812
Population: 1
Population: 1
0,500000
Population: 2
Population: 2
0,468750
Population: 3
Population: 0
0,437500
Population: 0
01100100101000100000010111001111000000000111100010011001010110101111
011100000000101111101000000011101010111011110100101101011011
Population: 1 
11101101011111111011111000110010101100111101110101111110011001011001
101010001011011001101100010001001000111010100101111000001011
Population: 2 
11000001101111100101011100001101010000110000110111011011100010010101
000101010101000010110010000000111001000101000001001111001010
Population: 3 
01111101001101001100000010011000001101001010001001100011110101001111
001101011011011100110111110010011110010011110001101000100011 
2. Выбор «родителей» для формирования потомка. 
Случайным образом выбирается две особи. Сравниваются значения их 
фитнесс-функций, в качестве первого родителя из двух отобранных выбирается 
особь с лучшим значением фитнесс-функции.
Затем аналогичным образом выбирается второй родитель. 

---

84 
В качестве 1 родителя выбрана особь со значением фитнесс-функции 
0,507812. Следующий родитель был выбран таким же образом. Значение 
фитнесс-функции 0,468750.
Parents: 0, 2
Population: 0 
01100100101000100000010111001111000000000111100010011001010110101111
011100000000101111101000000011101010111011110100101101011011
Population: 2 
11000001101111100101011100001101010000110000110111011011100010010101
000101010101000010110010000000111001000101000001001111001010 
3.Формирование «потомка»
.
Потом формируется случайным разделением ключа в одной точке. 
При этом, как описано выше, д
ля того чтобы выбрать, какой из 
потомков будет получен, нужно выбрать, какой из родителей будет главным. 
Что также определятся случайным образом. 
В тестовом примере точка разделения была определена 18 битом. С 0 по 
18 бит включительно данные взяты от родителя Population: 0.
Потомок пары parents: 0, 2:
01100100101000100001011100001101010000110000110111011011100010010101
000101010101000010110010000000111001000101000001001111001010 
4.Мутация случайных генов.
В процессе мутации также происходит случайный выбор бит, которые 
будут инвертированы с учетом вероятности мутации 
mutation_rate, заданной в 
качестве параметра алгоритма, а также генерацией случайного числа: 
Случайность или право выбора муравья следовать определенному пути 
обеспечивается использованием генерации случайного числом от 0 до 
RAND_MAX (2147483647) и сравнения этого числа с величиной 
(int)(mutation_rate * RAND_MAX). Если получено случайное число меньше 
этой величины, то бит будет инвертирован. Значение параметра mutation_rate 
0,02 означает, что в среднем будет изменено два бита.

---

85 
Потомок пары parents: 0, 2:
До мутации 
01100100101000100001011100001101010000110000110111011011100010010101
000101010101000010110010000000111001000101000001001111001010
После мутации
01100100100000100001011100001101010000110000110111011011100010010101
000101011101000010110010000000111001000101000001001111001010 
5.Определение значений фитнесс-функции полученных потомков. 
По результатам первого поколения лучшим осталось значение фитнесс-
функции начальной популяции 
0,539062 (таблица 4.21). Лучшим ключом 
является потомок parents: 0, 1
11101101011111111010010111001111010000000111100010011001010110101111
011100000100111111101100001011101010111011110100101101011011

---

86 
Таблица 4.21
Значение фитнесс-функции для потомков
Популяция 
Число совпавших бит в 
тестовом и оригинальном 
шифртекстах (из всего бит) 
Фитнесс-
функция 
parents: 0, 2
67 (128)
0,523438
parents: 0, 1
69 (128)
0,539062
6.Формирование популяции следующего поколения.
При заданных параметрах на следующее поколение должны перейти 
потомки, а также два представителя текущего поколения с наилучшими 
значениями фитнесс-функции.
Результаты полученные в ходе тестирования соответствуют 
ожидаемым.
7.Фиксирование бит при условии достижении параметра delta.
Цель тестирования: убедиться, что при достижении параметра delta 
биты в ключе фиксируются, как найденные. 
Параметр delta для определения будет ли зафиксирован бит, как 
определенный, задан, как входные данные и для тестирования равен 0,6. Биты 
фиксируются по результатам всех особей в последней популяции.
Для определения будет ли зафиксирован бит используются 
соотношения (3-10) и (3-11) (таблица 4.22).
В результате работы алгоритма получено 4 ключа: