Разработка и исследование параллельных алгоритмов анализа криптосистем, основанных на задаче дискретного логарифмирования

Асимметричная криптография, выдвинутая Диффи и Хеллманом [1] и независимо Мерклом [2], за очень короткий срок оказала большое влияние на развитие информационных технологий. Электронная коммерция, электронные платёжные системы, распространение ПО через глобальные сети были бы невозможны без активного использования алгоритмов симметричной и асимметричной криптографии. Криптография и криптоанализ вышли за стены закрытых институтов, и число публикаций по теме очень велико. К тому же, с большинством статей и книг можно оперативно ознакомиться через Интернет.

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

Стойкость всех алгоритмов асимметричной криптографии базируется на вычислительной сложности решения нескольких фундаментальных задач, таких как задача факторизации (разложения на множители), задача дискретного логарифмирования, задача укладки рюкзака и некоторых других. В качестве объекта исследования в данной работе была выбрана задача дискретного логарифмирования, так как решение этой задачи лежит в основе криптоанализа таких алгоритмов шифрования и цифровой подписи, как Эль-Гамаль[3], ГОСТ Р 34.10−94 [4] и ГОСТ Р 34.10−94 [5].

Решение задачи дискретного логарифмирования требует больших вычислительных мощностей, и сложность этой задачи существенно увеличивается при росте размерности. Последовательные вычисления с использованием одного процессорного ядра займут слишком много времени. Например, для нахождения дискретного логарифма методом базы разложения по модулю простого числа длиной 130 бит необходимо 2776 MIPS-года, что составляет около 359 суток (почти год) работы одного ядра процессора Intel® Xeon® CPU Е5345 с частотой 2.33GHz.

6]. Действенным способом ускорения вычислений является использование распределённых многопроцессорных вычислений.

Отличительной чертой современной криптографии является широкая доступность относительно больших вычислительных мощностей. Если в 70-е — 80-е годы двадцатого века алгоритм DES считался практически стойким, то в 1999 году он был взломан с помощью распределённых вычислений путём полного перебора ключей менее чем за сутки [7]. Сегодня вычислительные кластеры широко используются для решения прикладных задач в различных отраслях науки. Оборудование для их построения предлагается по доступным ценам. Кроме того, криптоаналитик-энтузиаст может использовать время простоя имеющихся компьютеров.

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

Имеющиеся в открытой печати статьи в основном описывают некоторые методы решения задач дискретного логарифмирования, такие как решето числового поля, встреча на случайном дереве и т. п. Детали реализации (в том числе распараллеливания трудоёмких этапов вычислений) не разглашаютсяприводятся только краткие характеристики проведённых вычислительных экспериментов[8].

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

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

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

В соответствии с целью определены следующие задачи исследования:

— анализ существующих методов дискретного логарифмирования, их времени выполнения и пригодности для распараллеливания;

— разработка параллельных алгоритмов, предназначенных для ускорения • вычислительно сложных участков выбранных методов дискретного логарифмирования;

— разработка программ, реализующих параллельные алгоритмы дискретного логарифмирования;

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

Методы исследования.

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

Научная новизна работы.

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

В ходе работы были получены следующие основные результаты:

1. разработаны параллельные алгоритмы просеивания и Гауссова исключения для ускорения субэкспоненциальных методов ДЛ, пригодных для мультипликативной группы числового поля;

2. разработаны параллельные алгоритмы для ускорения экспоненциальных методов ДЛ, пригодных для группы точек эллиптической кривой;

3. проведены исследования влияния параметров алгоритмов и вычислительной системы на время выполнения алгоритмов;

4. разработан алгоритм нахождения решения из сравнений вида х = -st (mod г) при s.

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

Положения, выносимые на защиту:

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

2. результаты экспериментов показывают эффективность разработанных алгоритмов и программ;

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

4. разработанный алгоритм позволяет решать сравнения вида х = -^" '(modr) при s1, которые нельзя разрешить напрямую.

Апробация работы.

Результаты работы представлялись на региональных, всероссийских и международных конференциях — «Информационная Безопасность-2008», CSIT-2008, РусКрипто-2009 и других. По результатам работы опубликовано 11 печатных работ, среди них 4 тезиса докладов и 7 статей. Две статьи опубликованы в журнале «Известия ТТИ ЮФУ. Технические науки», входящем в перечень изданий, рекомендуемых ВАК. Также было получено 4 свидетельства о регистрации программ для ЭВМ.

Внедрение работы.

Результаты работы были использованы в учебном процессе кафедры БИТ ТТИ ЮФУ, а также при выполнении г/б работы № г. р. 01.2.077 4 968 — «Разработка и исследование распределённых методов оценки вычислительной стойкости криптоалгоритмов, основанных на задаче разложения на множители и задаче дискретного логарифмирования». Имеются соответствующие акты о внедрении.

Состав и структура диссертации.

Представленная диссертация состоит из 4 глав, содержит 31 рисунок, 8 таблиц, 4 приложения.

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

Во второй главе приводятся разработанные параллельные алгоритмы, позволяющие находить дискретный логарифм в мультипликативной группе GF (p) двумя методами — базы разложения и решета числового поля. Также приводятся разработанный вспомогательный алгоритм решения сравнения jc^-jf'Onodr) при s1 и разработанная модификация метода решета числового поля, позволяющая находить решение в общем случае.

В третьей главе разрабатываются параллельные алгоритмы для решения задачи дискретного логарифмирования в группе точек эллиптической кривой методами встречи посередине и встречи на случайном дереве. Вводится понятие распределённой базы данных. Разрабатывается вариант применения известных структур данных (красно-чёрных деревьев [9]) для решения задачи методом встречи на случайном дереве.

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

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

4.9. Выводы.

В данной главе были рассмотрены теоретические и экспериментальные оценки сложности для субэкспоненциальных и экспоненциальных методов. Представлены программные и аппаратные средства, с помощью которых производились вычислительные эксперименты. К аппаратным средствам относится вычислительный кластер кафедры БИТ мощностью 56 ГФлопс, к программным — библиотеки GMP и NTL, реализующие множество целочисленных операций. Рассмотрены применяемые в программных библиотеках и разработанных автором абстрактных типах данных алгоритмы, предназначенные для выполнения базовых операций — умножения целых чисел, возведения в степень, нахождения НОД и мультипликативного обратного.

Приведены результаты проведённых с программными моделями экспериментов. Эксперименты, направленные на определение эффективности распараллеливания, показали достаточную эффективность представленных в главах 2, 3 параллельных алгоритмов дискретного логарифмирования: 0.9−0.98 для просеивания, 0.5−0.7 для Гауссова исключения и 0.93−0.97 для построения распределённой базы точек и поиска в нейкроме того, эффективность распараллеливания остаётся на постоянном уровне при увеличении числа процессорных ядер. Также с помощью экспериментов выявлено влияние параметров алгоритмов на время вычислений. По результатам экспериментов сформированы методики применения, определяющие оптимальные значения параметров алгоритмов.

Выполнены оценки сложности, основанные на показателях производительности современных суперкомпьютеров, прогнозируемой скорости роста и эффективности разработанных алгоритмов. На рассматриваемом гипотетическом вычислителе можно с помощью метода базы разложения решить задачу в Fp* размерностью порядка 200 бит, а используя метод решета числового поля — задачу размерностью порядка 900 бит. Для того же вычислителя максимальная размерность разрешимой задачи дискретного логарифмирования в E (FP) составляет 160 бит.

Заключение

.

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

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

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

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

Для всех типов методов разработан алгоритм нахождения решения из сравнений вида лгг-л'Г^шоёгЗпри s.

Выбранные методы реализованы в виде программ, что позволило экспериментально оценить эффективность разработанных параллельных алгоритмов.

Представлены результаты проведённых вычислительных экспериментов. Для Т оценки параллельных программ вычислялась эффективность как Е =-1—, где Е.

Р*Тр) эффективность, р — число задействованных процессорных ядер, Тх, Тр —. время выполнения программы на одном ядре и на р ядрах соответственно.

По результатам экспериментов эффективность распараллеливания этапа просеивания близка к линейной (Е=0.9−1) и сохраняется: на высоком уровне при увеличении., количества задействованных процессорных ядер. Эффективность параллельного Гауссова-исключения заметно ниже линейной (Е=0.4−0.7), и остаётся постояннойпри? увеличении количества задействованных' процессорных ядер, Эффективность построения, и поиска в> распределённой БД убывает при увеличении количества задействованных процессорных ядер — (Е=0−95 при пяти ядрах, Е-0.5 при двадцати ядрах)., .

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

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

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