|
3.2.3 Муравьиный алгоритм
В представленной работе решается задача нахождения ключа по
известному оригинальному и зашифрованному тексту. Оригинальный текст,
ключи, зашифрованный текст обрабатываются в виде бинарных строк, что
позволяет использовать достаточно простую фитнесс-функцию сравнения
бинарных битовых строк.
В заголовочном файле ant.h определены основные параметры и
функции для работы муравьиного алгоритма.
Реализована структура постоянных параметров алгоритма, которые
устанавливаются для работы муравьиного алгоритма struct ant_cfg, структура,
управляющая работой муравьиного алгоритма struct ant.
Значение основных параметров для работы алгоритма криптоанализа, а
также ключ и текст для шифрования задается в функции int test_ant_aes() и int
test_ant_des()
Для обеспечения работы муравьиного алгоритма необходимо
определить начальное значение феромонов вдоль пути муравья, который
представляет собой ориентированный граф (см. рис. 3.1). Значение, которое
определяет величину изменения феромона:
increment = 1.0 / seed_count,
(3-1)
где
seed_count — количество начальных «псевдоключей» для путей, по
которым определяется начальное значение феромонов.
Расчет величины increment подобран таким образом, чтобы значение
феромона было не слишком большим и в среднем оно не зависит от seed_count.
55
Значения уровня феромонов хранятся в массиве, который можно
представить, как: tau[4 * k + 2 * prev_bit + bit], где
tau — величина феромона
k – номер бита по порядку
prev_bit, bit – значение предыдущего бита и текущего бита
Рисунок 3.1 - Общее представление возможных путей муравья по графу
с данными об уровне феромнов.
В случае DES начальное значение феромонов определяется следующим
образом:
Берется заданное количество пар оригинального текста, и
соответствующего ему оригинального зашифрованного текста. Для пар
применяется операция XOR. Для полученных результатов вдоль пути
раскидываются феромоны. Такой подход возможен, так как в случае DES
известна корреляция между данными: в циклах шифрования используется
операция XOR.
В случае AES корреляция данных устроена гораздо сложнее, и
моделирование начальных ключей является отдельным темой для
исследований, поэтому в данной работе используется более общий подход. Для
формирования начальных «псевдоключей» генерируется seed_count количество
случайных ключей (каждому ключу сопоставляется путь муравья) и вдоль этих
путей распределяются феромоны. То есть в итоге будет получено общее число
феромонов по результатам всех полученных ключей.
56
При формировании ключа вероятность перехода в бит со значением 0
определяется по формуле (2-2). Для реализации поставленной задачи запишем
выражение следующим образом:
chance = tau0
alfa
* eta0
beta
/ ( tau0
alfa
* eta0
beta
+ tau1
alfa
* eta1
beta
)
(3-2)
где
chance - вероятность перехода муравья из текущей вершины в вершину со
значением 0
tau0, tau1- величина феромона (вес ребра) для перехода из текущей вершины в
вершину со значением 0 и 1, соответственно
eta0, eta1 – величина фитнесс-функции, получаемой при определенных
переходах
𝛼, 𝛽 – эмпирические коэффициенты, которые управляют соотношением
предпочтительности между информацией о феромоне tau0, tau1 и величине,
обратно пропорциональной eta0, eta1
На первой итерации для первого муравья параметры eta0 = eta1 = 1. Для
следующего муравья и на следующих итерациях коэффициент определяется
равным значению фитнесс-функции перехода в значение 0 (eta0) и в значение 1
(eta1).
Случайность или право выбора муравья следовать определенному пути
обеспечивается использованием генерации случайного числом от 0 до
RAND_MAX
(2147483647)
и
сравнения
этого
числа
с
величиной(int)(RAND_MAX * chance))
bit = (rand() < (int)(RAND_MAX * chance)) ? 0 : 1,
(3-3)
где
chance – вероятность перехода
bit – установка значения бита в значении 0 или 1.
Так как при генерации случайных числе распределение является
нормальным то, например, если chance для перехода в 0 составляет 0,8, то в 8
случаях из 10 выбор будет сделан в пользу более вероятного перехода в
57
значение бита 0, и только 2 случая остается на переход в значение, являющееся
менее вероятным, то есть 1.
После получения на итерации и для отдельного муравья полного
тестового ключа, определяется величина увеличения феромонов, исходя из
лучшей фитнесс-функции итерации [3-2-2]:
tau = tau + increment
(3-4)
Increment = best fitness / log2 key_length
(3-5)
где
tau – уровень феромонов
Increment – величина изменения уровня феромонов
best fitness – лучшее значение фитнесс-функции на итерации
key_length – длина ключа
Увеличение значения феромонов происходит только для тех переходов,
которые присутствуют в лучшем ключе итерации ключе.
Параметр, отражающий, какой уровень феромонов останется после
испарения
, задается в качестве параметра алгоритма rho,
и применяется ко всем
возможным переходам:
tau = tau * rho
(3-6)
где
rho - параметра алгоритма, отражающий, какой уровень феромонов
останется после испарения
Фиксирование бит, как определенных происходит при достижении
определенных условий.
Для определения будет ли зафиксирован бит
используется соотношение:
optimum_keys_stat[k] >= оptimum_keys * delta
(3-7)
optimum_keys_stat[k] <= optimum_keys * (1.0 — delta)
(3-8)
где
k — номер бита
optimum_keys_stat - сумма бит в определенной позиции по всем
оптимальным ключам
58
оptimum_keys - количество оптимальных ключей
delta — параметр для определения будет ли зафиксирован бит, как
определенный
Если сумма бит в определенной позиции по всем оптимальным ключам
больше или равна количеству оптимальных ключей с учетом параметра delta,
то бит будет зафиксирован в значении 1 (3-7).
Если сумма бит в определенной позиции по всем оптимальным ключам
меньше или равна количеству оптимальных ключей с учетом параметра (1-
delta), то бит будет зафиксирован в значении 0 (3-8).
Также было добавлено условие требующее, чтобы бит хотя бы раз
менялся. То есть если получено 2 тестовых ключа и бит в определенной
позиции ни разу не менялся, то такой бит не будет зафиксирован. Данное
условие позволило улучшить качество корректных найденных битов.
Do'stlaringiz bilan baham: | 
