Исследование методов криптоанализа асимметричных шифров с использованием природных алгоритмов

Криптоанализ — это наука, изучающая методы взлома криптосистем, позволяющая оценить качество криптосистем. Криптоанализ современных асимметричных криптосистем является трудновыполнимой задачей затрачивающей катастрофически большое количество времени. Поэтому поиск новых и эффективных методов криптоанализа является актуальной задачей. Безопасность шифра зависит от выбора функции ловушки. Функция ловушка — это функция, которая позволяет эффективно вычислить значение, но не позволяет легко обратить вычисление без наличия числа подсказки. Пример функции реализован в алгоритме асимметричного шифрования RSA. Базовый принцип алгоритма RSA строится на том, что можно найти такие числа e, d и n, чтобы возведение шифруемого целого числа m в степень e · d по модулю n для всех целых чисел m были равны m:

Экспонента d является закрытым ключом и вычислить его крайне сложно, даже если n, e и m известны. Экспонента e и число n в паре являются открытым ключом. Открытый ключ n состоит из произведения 2-ух простых чисел p и q огромного размера, которые отличаются друг от друга на несколько знаков для усложнения криптоанализа. Если p и q огромные, то процесс разложения произведения p · q является трудновычислимой задачей. Числа p и q используются для вычисления закрытого ключа d. Разложение чисел можно осуществить с использованием метода «Квадратичного решета» или «Ро-алгоритма Полларда». Для факторизации числа n в настоящей работе предлагаются природные алгоритмы криптоанализа: алгоритм муравьиных колоний и алгоритм пчелиной колонии.

Алгоритм муравьиных колоний является вероятностным подходом к решению задач, подражающий поведению муравьёв. Алгоритм заключается в следующем: дан граф G = (E, V), m муравьёв. Муравьи размещаются на вершинах графа G и строят маршруты. Муравьи могут быть размещены случайным образом. Во время построения маршрута, муравьи откладывают феромон на пройденном пути. При выборе следующей вершины для перехода, учитывается уровень феромона, отложенного на переходе из текущей вершины в следующую. Вероятность перехода муравья на доступные ему вершины определяется следующей формулой:

Где τ_xy — количество феромона, отложенного муравьём на ребре xy, η_xy — привлекательность маршрута, α, β — факторы, контролирующие влияние параметров τ_xy и η_xy, J_k — множество рёбер, доступные муравью k из вершины x. После построения маршрутов, значения феромонов на рёбрах обновляются по следующей формуле

Где τ_xy^k — количество феромона на ребре xy муравьём k, ρ — коэффициент испарения, — количество феромона, отложенного муравьём на ребре xy во время текущей итерации. Количество отложенного феромона определяется по следующей формуле:

Где L_k — цена перехода по ребру xy, Q — константа. Если условия остановки алгоритма не выполнены, процедура повторяется. Условиями остановки могут быть ограничения по времени или достижение оптимального решения. Для нахождения простого делителя составного числа N, примем следующие параметры алгоритма:

Где S_k — маршрут, построенный муравьём k, — функция, получающая дробную часть от деления на N. Q определяет уменьшение уровня феромона с увеличением длины маршрута, можно принять равным длине маршрута. Целью алгоритма найти маршрут, .

Алгоритм пчелиной колоний — стохастический бионический алгоритм оптимизации, подражающий поведению пчёл. В этом алгоритме выделяются несколько этапов: начальная разведка и локальная разведка. Во время начальной разведки выбираются C точек. Выбор точек может происходить случайным образом. Далее на выбранных точках происходит локальная разведка, где происходит поиск более оптимального решения в радиусе R на выбранных точках. При улучшении значения, значение целевой функции F и набор аргументов X сохраняются. Для разложения составного числа, целевой функцией примем:

В качестве радиуса поиска примем значение , где c — количество цифр в двоичной записи искомого числа.

Система реализована в 2 модуля: модуль реализующий алгоритм и графический интерфейс. Такой способ реализации удобен так как позволят легко отделить логику реализации графического интерфейса от алгоритма криптоанализа. При разработке использовались 2 языка программирования: C и C++. C был выбран за счёт популярности и простоты взаимодействия с низким уровнем программирования в результате чего можно просто оптимизировать программу на скорость. C++ выбран из-за зависимости от библиотеки Qt.

Система криптоанализа состоит из следующих компонент:

• Криптографический модуль libsodium;
• Библиотека, реализующая алгебру с большими числами GMP;
• Графический интерфейс.

Модуль криптоанализа реализует логику криптоанализа и взаимодействует с криптографическим модулем для проверки промежуточных результатов. Позволяет разложить составное число и тем самым восстановить закрытый ключ, отчитывается о проведённых действиях. Модуль реализован на языке программирования C и использует libsodium и GNU MP.

libsodium предоставляет ряд криптографических функций. Используется для генерации качественных случайных чисел. Библиотека написана на языке C и распространяется под лицензией BSD.

GNU MP реализует работу с большими числами и предоставляет ряд математических функций, включая функции теорий чисел. Библиотека написана с использованием языков C и C++ и распространяется под лицензиями LGPL и GPL.

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

Особенности системы:

• Использует оптимизированные алгоритмы (спасибо GNU MP);
• Использует эвристические методы разложения составного числа;
• Производит криптоанализ в несколько потоков.

Для проверки эффективности системы, был проведён ряд экспериментов: сравнение времени работы алгоритмов от размера ключа и время работы алгоритмов в зависимости от параметров. Каждый опыт был запущен 10 раз и в качестве результата взято среднее время исполнения, так как алгоритмы используют случайные числа для работы и время исполнения каждый раз может отличаться. Для первого эксперимента используются следующие параметры:

• Для алгоритма муравьиных колоний: количество муравьёв: 4; длина пути: 64; коэффициент испарения феромона: 0.4;
• Для алгоритм пчелиной колонии: количество пчёл: 4; количество точек для исследования: 4096.

Результаты эксперимента приведены на графике:

По графику видно, что алгоритм пчелиной колонии справляется лучше с задачей криптоанализа, чем алгоритм муравьиных колоний. Экспериментально были проверены только ключи небольшого размера, не являющиеся криптостойкими. Это связано с ограничением вычислительных ресурсов устройства на котором проводились эксперименты. Далее проведём эксперимент, показывающий влияние увеличения количества потоков на скорость алгоритма. Для проведения эксперимента, были заданы следующие постоянные параметры:

• Раскладываемое число: 664543753253;
• Диапазон поиска: [903, 815196];
• Для алгоритма муравьиных колоний: количество муравьёв: 4; длина пути: 64; коэффициент испарения феромона: 0.4;
• Для алгоритма пчелиной колонии: количество пчёл: 4; количество точек для исследования: 4096.

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

• Раскладываемое число: 664543753253;
• Диапазон поиска: [903, 815196];
• Количество пчёл: 4.

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

• Раскладываемое число: 664543753253;
• Диапазон поиска: [903, 815196];
• Количество муравьёв: 4;
• Длина пути: 64.

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

• Раскладываемое число: 664543753253;
• Диапазон поиска: [903, 815196];
• Количество муравьёв: 4;
• Коэффициент испарения феромона: 0.4.

По графику видно, что оптимальное значение длины маршрута является значение от 16 до 128. Маршруты короче или длиннее приводят к увеличенным временным затратам.

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