Разработка генетической модели поиска простых чисел для криптоанализа RSA на основе клиент-серверной структуры

БИБЛИОГРАФИЧЕСКИМ СПИСОК

1. Гладков Л.А., Курейчик В.М, Курейчик В.В. Генетические алгоритмы. - Ростов-на-Дону: Ростиздат, 2004.

2. Ахо А., Хопкрофт Дж., Ульман Д. Построение и анализ вычислительных алгоритмов. -М.: Мир, 1979.

3. ГладкоеЛ.А. Генетические операторы. - Таганрог Изд-во: ТРТУ, 2005

4. ., . . .

- М.: Мир, 1985.

УДК 687.06

Х.А. Кажаров

РАЗРАБОТКА ГЕНЕТИЧЕСКОМ МОДЕЛИ ПОИСКА ПРОСТЫХ ЧИСЕЛ

ДЛЯ КРИПТОАНАЛИЗА RSA НА ОСНОВЕ КЛИЕНТ-СЕРВЕРНОЙ

СТРУКТУРЫ

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

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

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

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

RSA. , RSA,

представлена формулой (1):

f : х—> xe

Для дешифрования сообщения a=f(x) достаточно решить уравнение (2):

xe=a mod m.

При некоторых условиях, налагаемых на m и е, это сравнение имеет единственное решение х [1]. Если показатель степени е в сравнении с (2) взаимно прост с

(m) ( ), (2) .

найти, необходимо определить число d, удовлетворяющее условию (3):

de = 1

Решением задачи будет следующее уравнение: ad = xde = x mod m.

При этом (e, m) - открытый ключ, который передается по незащищенным каналам, a (d, m) - секретный ключ. Для вычисления секретного ключа d необходимо вычислить функцию Эйлера для m. Функцией Эйлера ç(m) называется количество

, m m:

ср =

m = pq, p q - , -

ляется с помощью (4) [2].

Таким образом, для криптоанализа системы RSA необходимо знать разложение модуля m. Самые лучшие алгоритмы факторизации (р^ложения) имеют суб-

:

L [yc] = e(c+o(1))(lnm)Y(lnlnm)1-Y

где c и y - постоянные, o(1) ^ 0 , X ^ +œ . в [3] подробно описываются алгоритмы разложения составного числа на простые множители.

Таким образом, для применения ГА при криптоанализе RSA, с учетом его , -стых множителей заданного составного числа.

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

Метод оптимизации технических систем, в котором реализована эта идея, получил название «Генетические алгоритмы». Генетические алгоритмы позволяют получать хорошие результаты при решении NP - полных задач [4].

.

, .

находим из равенства m = pq.

В данной работе используются бинарные хромосомы. Бинарная хромосома является гомологичной числовой хромосомой, каждый ген которой может принимать целые значения в интервале [0, 1].

Приведем пример кодировки хромосомы для x e N, 0 < x < 1023. В этом случае одно число кодируется бинарной хромосомой из 10 ген, как показано на рис. 1.

0 0 1 0 1 1 0 0 1 1

Рис. 1. Кодировка хромосомы

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

О = Ао*20+А1*21+А2*22+.. ,+Ап*2п = 820.

где Лг - значение бита в г-м разряде.

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

а) одеяло - покрываем равномерно пространство поиска n решениями, где n -размерность популяции;

б) дробовик - случайный выбор n потенциальных решений;

) - -.

Простое число генерируется случайным выбором значения битов. Последний бит всегда устанавливается равным 1. Затем вычисляем среднее расстояние между простыми числами r, после чего в диапазоне [G-r;G+r] осуществляется поиск наиболее вероятного простого числа.

В заданном диапазоне ведем поиск наиболее вероятного простого числа сле-. . число xe[G-r;G+r] последовательно проверяем на делимость с простыми числами в диапазоне [3; 2r]. В данном случае простые числа в этом диапазоне необходимо , . даже для чисел порядка 21024 составляет около семисот, то выведение простых чисел в диапазоне [3; 2r] не будет влиять на временную сложность алгоритма, т.е. им . -

странство поиска решений:

r=ln

Пусть G порядка 2512 , тогда r ~ 355. Поскольку вычисления производятся

,

:

r = log2 G а 10g2 G

log2 e 1,442695'

n (6) :

r =---------------------------П-.

1,442695

После сужения пространства поиска решений к оставшемуся множеству чисел применяем тест Миллера-Рабина [4]. В случае, когда остается несколько чисел, , ( -) ( , ).

Приведем пример работы данной схемы. Пусть n = 6, а сформированная хромосома имеет следующий вид:

1 0 1 0 1 1

Рис. 2. Пример хромосомы

Отсюда видно, что О = 43. Вычислим радиус:

г =-----6-----= 4,15888 - 5.

1,442695

, .

Рассматриваем следующий диапазон чисел [38; 48]. Далее проверяем делимость этих чисел на простые числа в диапазоне [2; 10], т.е. {2, 3, 5, 7}. Согласно

[38;48] , -

лящиеся на {2, 3, 5, 7}. В итоге получаем следующие простые числа {41, 43, 47}. Очевидно, что все три числа пройдут вероятностный тест Миллера-Рабина, а выбор остается за ЛПР.

Приведем еще один пример, показывающий необходимость применения вероятностного теста Миллера-Рабина. Примем О = 121. Тогда г - 5. Получаем следующий диапазон [118; 128], в котором исключаются числа, делящиеся на {2,3,5,7}. В итоге получаем следующие числа {121,127}. После применения к ним

- 127, 121 ,

121 = 11*11.

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

т

Ч = —.

Р

, -Рабина с целью получения информации о вероятности простоты числа q. Поскольку каждая хромосома получается в результате локального поиска с применением вышеуказанного вероятностного теста, то можно судить о вероятности простоты каждого сомножителя. Таким образом, значение целевой функции (ЦФ) определяется произведением вероятностей двух сомножителей:

Р = Р(ч)*Р(р).

Выбор родительской пары хромосом. Как правило, здесь используется три метода выбора родительской пары хромосом: а) случайный; б) элитный; в) «колесо рулетки» [5].

Экспериментальные исследования показали, что наиболее эффективным является случайный выбор. Это обусловлено спецификой задачи. Поскольку вероятность того, что Р(ч)=0 и, соответственно, ЦФ в целом для многих хромосом в популяции будет равна 0, высока, то элитный выбор и «колесо рулетки» будут способствовать локализации пространства поиска, а ГА войдет в состояние стагнации.

.

операторы кроссинговера: а) одноточечный; б) двухточечный; в) многоточечный [5]. Модификация заключалась в следующем. Работа оператора разбивается на . . Второй этап заключается в локальном поиске наиболее вероятного простого числа в окрестности декодированного числа У. Радиус окрестности определяется формулой (5), и, следовательно, пространство поиска соответствует интервалу [О-г; О+г]. Соотношение (5) подтверждено экспериментальными исследованиями.

Рассмотрим результат работы программы для диапазона [1; 1024]. Находим экстремум функции распределения простых чисел в заданном диапазоне. В диапазоне [1; 1024] он равен 20, для [1; 10240] получили значение 36, для [1; 102400] -

72. , -

ми в заданном диапазоне.

На рис. 2 показаны два графика: зависимость расстояния между двумя простыми числами от размера числа и среднее значение. Из графиков видно, что среднее расстояние между простыми числами в зависимости от размерности распределено по логарифмическому закону. Это подтверждается законом Валле-Пуссена [4].

Рис. 2. Вычисление плотности распределения простых чисел

Найденное число и будет являться потомком.

Мутация. В качестве оператора мутации используются обмен и инверсия, к которым также применяется локальный поиск наиболее вероятного простого числа. Отметим, что для определения простоты числа также используем алгоритм вероятностного теста Миллера-Рабина, благодаря которому становится известным .

Оператором отбора могут служить стандартные операторы: а) случайный; б) элитный; в) «колесо рулетки» [5].

Применение экспертной системы. Как известно, для криптоанализа RSA применяются распределенные вычисления. Такой подход реализуем и для ГА на . -, . ,

ГА очень удобен для реализации экспертной системы (ЭС). ЭС предназначается для выявления параметров ГА, при которых ЦФ быстрее всего достигает своего .

параметрами (вероятности кроссинговера и мутации, вариации генетических опе-( ), ). , основе анализа информации об индивидах из различных популяций выделяет <аучшие» параметры ГА. При этом ЭС может также влиять на параметры ГА, которые являются динамическими.

На рис. 3 показан пример взаимодействия 8 популяций с ЭС.

Рис. 3. Модель взаимодействия ЭС с 8 популяциями

Связь между популяциями и блоком экспертной системы двусторонняя (см. рис. 3). Каждая популяция посылает в блок ЭС информацию о лучших индивидах ( ) ( ). -лиза полученных решений ЭС возвращает каждой популяции новые параметры, которые в дальнейшем определят их адаптируемость.

. -структуру (см. рис. 3). Так как каждый клиент представляет одну популяцию со своими специфическими индивидами, то экспертная система необходима, чтобы периодически производить обмен видов между различными популяциями, как по. 4, , , .

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

Рис. 4. Работа сервера при взаимодействии с клиентом

При взаимодействии клиент посылает определенное количество случайно выбранных решений из всей популяции (см. рис. 4). Экспертная система объединяет всех индивидов, полученных от клиентов, затем каждое решение мигрирует в случайно выбранную популяцию. Представленная организация многопопуляционного генетического алгоритма может иметь произвольное количество клиентских , .

Параметры интеллектуальной системы. Представленная интеллектуальная система характеризуется следующими параметрами: а) количество популяций;

б) размер популяций; в) количество индивидов для выборки при миграции.

Каждый из этих параметров задается ЛПР. Важной частью представленной интеллектуальной системы является работа ЭС. Логика работы экспертной системы отражена в следующей формуле:

Pi = Pi + AP, i e N, i < n, Pi Ф Pb,

где Pi={p

cross’ Pmub ocross, omut> or> os} КОртеЖ Параметров /-И ПОПуЛЯЦИИ; Pcross И pmut

- вероятности, соответственно, кроссинговера и мутации; ocross и omut - операторы, соответственно, кроссинговера и мутации; or - оператор редукции; os - оператор .

. -

пов генетического алгоритма для решения задачи криптоанализа RSA. В работе проведен анализ криптосистемы RSA, рассмотрены различные подходы к крипто.

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

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Ященко В.В. Введение в криптографию. - М.: МЦНМО, 2003.

2. Баричев С., Криптография без секретов [Электронный ресурс] - http://forum.armkb.com.

3. Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. - М.: МЦНМО, 2003.

4. МакКоннелл Дж. Основы современных алгоритмов. - М.: Техносфера, 2004.

5. Гладков Л.А., Курейчик В.М., Курейчик В.В. Генетические алгоритмы. - Ростов-на-Дону: ООО «Ростиздат», 2004.

УДК 681.31

П.В. Афонин, О.В. Кокшагина

ГИБРИДНЫЕ ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ ДЛЯ ЗАДАЧИ СОСТАВЛЕНИЯ РАСПИСАНИЯ ПРОЕКТА*

.

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

Классификация гибридных систем по уровню интеграции приведена в [1]. Согласно этой классификации выделяются автономные, трансформационные, слабосвязанные, сильно связанные и полностью интегрированные системы. Идея гибридных генетических алгоритмов (hybrid genetic algorithms) заключается в сочетании генетического алгоритма (ГА) с некоторым другим методом поиска [2].

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

основе трансформационной схемы. Программная реализация алгоритмов и проведение экспериментальных исследований осуществлялось в программной среде MatLab 7.1.

Постановка задачи. Рассмотрим следующую постановку задачи: проект представляет собой совокупность работ и ресурсов. Ресурс характеризуется нор-

( ), -стью единицы ресурса при нормальном потреблении и сверхурочном потреблении соответственно. Работа характеризуется длительностью, списком назначенных ресурсов, списком предшествующих и последующих работ, задержками между рабо-

( , ).

Необходимо составить расписание работ проекта. Под расписанием понима-, l t -, l t, , l момент времени t ресурс простаивает.

*

Работа выполнена при поддержке РФФИ (гранты № 08-07-00337, 08-07-00343). 46