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

На правах рукописи

Сидоров Игорь Дмитриевич

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

05.13.19 «Методы и системы защиты информации, информационная

безопасность»

АВТОРЕФЕРАТ

диссертации на соискание учёной степени кандидата технических наук

Таганрог 2009

003474047

Работа выполнена на кафедре безопасности информационных технологий факультета информационной безопасности Технологического института Южного федерального университета в г. Таганроге.

НАУЧНЫЙ РУКОВОДИТЕЛЬ:

доктор технических наук, профессор Бабенко Людмила Климентьевна ОФИЦИАЛЬНЫЕ ОППОНЕНТЫ:

доктор технических наук, профессор Моддовян Александр Андреевич (г. Санкт-Петербург);

кандидат технических наук, доцент Котенко Владимир Владимирович (г. Таганрог)

ВЕДУЩАЯ ОРГАНИЗАЦИЯ:

ФГНУ НИИ «Спецвузавтоматика»,г. Ростов-на-Дону

Защита диссертации состоится «02» июля 2009 г. в 14:20 на заседании диссертационного совета Д 212.208.25 Южного федерального университета по адресу: 347928, Ростовская обл., г. Таганрог, ул. Чехова, 2, ауд. И-409.

Отзывы на автореферат в двух экземплярах, заверенные гербовой печатью, просим направлять по адресу: 347928, Ростовская обл., г. Таганрог, пер. Некрасовский, 44, Технологический институт Южного федерального университета в г. Таганроге, Учёному секретарю диссертационного совета Д 212.208.25 Брюхомицкому Юрию Анатольевичу.

С диссертацией можно ознакомиться в Зональной научной библиотеке ЮФУ по адресу: 344007, Ростовская обл., г. Ростов-на-Дону, ул. Пушкинская, 148.

Автореферат разослан « 04 » и И?И Я 2009 г.

Ученый секретарь диссертационного совета

Брюхомицкий Ю.А.

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

Стойкость всех алгоритмов асимметричной криптографии базируется на вычислительной сложности решения нескольких фундаментальных задач, таких как задача факторизации (разложения на множители), задача дискретного логарифмирования, задача укладки рюкзака и некоторых других. Объектом исследования в данной работе является задача дискретного логарифмирования, так как решение этой задачи лежит в основе криптоанализа таких алгоритмов шифрования и цифровой подписи, как Эль-Гамаль, ГОСТ Р 34.10-94 и ГОСТ Р 34.10-94. Для произвольной циклической группы G задача формулируется следующим образом: по известным a,beGнайти такой логарифм х, что а' = Ь.

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

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

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

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

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

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

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

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

В соответствии с целью определены следующие задачи исследования: -анализ существующих методов дискретного логарифмирования и их временных затрат, выявление вычислительно сложных участков;

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

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

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

Объект исследования - задача дискретного логарифмирования в различных группах

Предмет исследования — параллельные алгоритмы для реализации вычислительно сложных этапов дискретного логарифмирования

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

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

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

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

Основные научные результаты работы: 1. Разработаны параллельные алгоритмы просеивания и Гауссова исключения для реализации субэкспоненциальных методов ДЛ - базы разложения и решета числового поля, позволяющие получить на многопроцессорной системе значения эффективности 0.9-0.98 для просеивания и 0.5-0.7 для Гауссова исключения. (Эффективностью назовём меру того, насколько хорошо параллельная программа

использует многопроцессорную систему. Она определяется как £=—5—, где Е-

р*т„

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

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

3. Проведены исследования влияния параметров реализаций (размера базиса для субэкспоненциальных методов, размера БД для экспоненциальных и других) и вычислительной системы (числа процессорных ядер, качества передающей среды) на время вычислений.

4. Разработан алгоритм нахождения решения из сравнений вида jr = -sr'(modr), s<r, t<r, который в отличие от базового в таких случаях расширенного алгоритма Евклида не требует взаимной простоты чисел t,r, что позволяет решать сравнения в общем случае.

5. Модифицирован базовый метод решета числового поля для решения задачи ДЛ в общем случае - при любых образующей а и экспоненте b в выражении а' — ¿(modр),а < р,Ь < р.

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

1. Разработанные параллельные алгоритмы для ускорения выполнения реализаций субэкспоненциальных и экспоненциальных методов позволяют эффективно решать задачу ДЛ на распределённых вычислительных системах, показывая эффективность 0.9-0.98 на этапе просеивания, 0.93-0.97 на этапе построения БД, и 0.5-0.7 на этапе Гауссова исключения, причём эффективность сохраняется при увеличении числа процессорных ядер..

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

3. Модифицированный метод решета числового поля позволяет, в отличие от базового, находить решение при произвольной образующей а и экспоненте b в выражении а' = ¿(mod р),а< p,b< р .

4. Разработанный алгоритм решения сравнений вида (modг)^ 3<Г; t<rj не требующий взаимной простоты чисел t,r, позволяет находить решение из сравнений, которые невозможно решить базовым в таких случаях расширенным алгоритмом Евклида.

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

Практическая ценность полученных автором результатов

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

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

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

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

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

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

Диссертация состоит из введения, четырёх глав, заключения, списка источников, четырёх приложений. Основной текст диссертации изложен на 141 странице, включая 31 рисунок и 8 таблиц.

ОСНОВНЫЕ ПОЛОЖЕНИЯ РАБОТЫ

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

В первой главе описывается, чем обусловлено появление и широкое распространение асимметричной криптографии. Показывается, что стойкость таких схем, как Эль-Гамаля, Диффи-Хеллмана, Месси-Омуры, напрямую зависит от сложности решения задачи дискретного логарифмирования.

Рассматриваются группы, важные для криптографии - мультипликативная группа числового поля GF(p), в дальнейшем обозначаемая Fp, и группа точек эллиптической кривой, в дальнейшем обозначаемая как E(FP).

Постановка задачи дискретного логарифмирования в этих группах осуществляется следующим образом. Для группы Fp : по заданному модулю р, образующему элементу а порядка г и степени b найти х е О..г-l, такой, что b=ax(mod р). Для группы E(FP): для заданной эллиптической кривой над конечным полем GF(p) найти порядок I элемента P = IQ в циклической группе <Q> известного порядка г.

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

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

Метод встречи посередине основан на так называемом «парадоксе дней рождения» - для того, чтобы при выборке с возвратом из множества мощности г получить два одинаковых элемента, необходимо сделать в среднем 0(4г) попыток. Метод встречи посередине хорошо подходит для дискретного логарифмирования в нечисловых группах (например, в группе точек эллиптической кривой), поскольку не использует никаких дополнительных свойств элементов группы. Метод имеет оценку сложности 0(4г\о%г), обладает потенциалом для ускорения с помощью РМВ, так как генерацию, сортировку и поиск точек могут выполнять несколько процессоров одновременно.

Метод встречи на случайном дереве схож с методом встречи посередине, однако имеются два отличия. Во-первых, к случайно сгенерированным элементам группы перед помещением в БД применяется сжимающее отображение, служащее для уменьшения группы точек. Пример подобного отображения для точек из Е(Рр):

Во-вторых, операции формирования БД и поиска в ней совмещены - если искомая точка отсутствует в БД, то она туда добавляется. Метод имеет асимптотическую оценку сложности 0(^¡r log г) - лучше, чем метод встречи посередине, однако требует дополнительных затрат времени на вычисление сжимающего отображения. Аналогично методу встречи посередине, метод встречи на случайном дереве обладает потенциалом для ускорения с помощью РМВ, так как генерацию и поиск точек могут осуществлять несколько процессоров одновременно.

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

1. Нахождение заданного числа элементов, гладких по определённому базису (или базисам), составление матрицы показателей.

2. Преобразование матрицы показателей с целью зануления заданных столбцов.

3. Составление сравнения, вычисление искомого логарифма.

Субэкспоненциальные методы имеют хорошую оценку время выполнения (для метода базы разложения ьр (2; fy = 0(exp(2^1n pin In />)), для метода решета числового

поля Lp(],923;j/Ç)). Методы имеют потенциал для распараллеливания, т.к. поиск гладких

элементов можно производить независимо, а на этапе обработки матрицы можно параллельно обрабатывать отдельные её участки.

В итоге для параллельной реализации дискретного логарифмирования как наиболее перспективные определены: в группе E(FP) методы встречи посередине и встречи на случайном дереве, а в группе Fp — методы базы разложения и решета числового поля. Эти методы обладают хорошими оценками времени выполнения и потенциалом для значительного ускорения с помощью РМВ.

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

R + Q,eслиО<дг, <у

t(R) = \ R + Р,ссли — <*„< — w 3 ' 3

Я + 22,если — <xr< р

2р . 3

О)

определяется как Е _ R _ ri , где R-ускорение, р-число процессорных ядер, Т,-время р (р'г„)

выполнения программы на одном ядре, Тр-время выполнения программы на р ядрах. Если программа имеет линейное ускорение (т.е. скорость вычислений растёт пропорционально росту вычислительной мощности), ее эффективность равна 1,0. Эффективность менее 1,0 означает, что ускорение менее, чем линейное.

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

Для ускорения просеивания разрабатывается алгоритм параллельного просеивания.

Алгоритм параллельного просеивания.

Вход: описание задачи дискретного логарифмирования <а,Ь,р,г>, базис разложения D = (pi,p2, - p„) размером п, параметры алгоритма - число просеиваемых за один приём чисел (sieving_th), число дополнительных строк матрицы (matrix_addon). Выход: распределённые по вычислительным узлам полосы матрицы е, содержащей показатели, с которыми элементы базиса входят в разложение числа-кандидата.

1. [Инициализировать]. Определить номер узла, общее число узлов.

п |Мл|

2. [Определить проверяющее число]. checker= Р, °8Л

¡=2

3. [Обнулить checked]. Checked=0. Переменная checked хранит количество проверенных на гладкость чисел

4. [Определить значение кандидата cand для проверки на гладкость]. Конкретный способ определяется тем, какой метод логарифмирования реализуется.

5. [Проверить гладкость] НОД (cand,checker)==cand? Если да, то установить показатель при -1 равным 0 и перейти к шагу 7.

6. [Проверить гладкость отрицательного числа] НОД (-cand(mod p),checker)==cand? Если да, то установить показатель при -1 равным 1 и перейти к шагу 7. Если нет, перейти на шаг 10.

7. [Найти разложение] С помощью алгоритма 2.2 пробным делением найти разложение числа cand по элементам базиса.

8. [Сохранить результат] Записать найденное разложение в полосу матрицы е, принадлежащую нашедшему узлу.

9. [Увеличить число найденных гладких чисел] found=found-H

10. [Увеличить количество проверенных кандидатов] checked=checked+l

11. [Продолжить просеивание?] Если значение checked меньше заданного порога sieving_th, перейти к шагу 4.

12. [Обменяться результатами] Найти sum_found — сумму числа найденных строк по всем процессам.

13. [Продолжить работу?] Если эта сумма меньше заданного порога (n+matrix_addon_sive), перейти к шагу 3.

14. Конец алгоритма.

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

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

1. [Инициализировать] Для i=l..m used[i]=0; j=-l

2. [Перейти к следующему столбцу] j=j+l

3. [Проверить] Если keep[j]=l, перейти к шагу 2.

4. [Найти опорную строку] Каждый узел ищет индекс base, такой что e[base][j]#) и used[base]=0.

5. [Собрать и обработать данные]. Каждый узел посылает головному узлу результат этапа 4. Головной узел собирает результаты. Если один узел нашёл опорную строку, рассылается номер этого узла. Если более одного узла нашли подходящую строку, случайным или иным образом выбирается один из них и рассылается его номер. Если ни один узел не нашёл подходящую строку, рассылается значение -1.

6. [Решить, можно ли устранить текущий столбец]. Если получили значение -1, столбец устранить нельзя. Переход на 2.

7. [Пометить опорную строку]. Узел, выбранный головным узлом для рассылки опорной строки (т.е. его номер совпадает с разосланным), помечает строку как использованную: used[base]=l

8. [Разослать опорную строку] Узел, выбранный головным узлом для рассылки опорной строки, широковещательно рассылает её, остальные узлы принимают.

9. [Выполнить Гауссово исключение] Обозначить принятую опорную строку как вектор s. Тогда для всех i=0..m-l, таких что used[i]=0, выполнить присваивания: t=e[i][j]; для k=j..n-l e[i][k]=s[j]*e[i][k]- s[k]*t (mod г)

10. [Выход] Если j>n, выход, иначе перейти к шагу 2.

В ходе работы для обеспечения полноты полученных решений разработаны две модификации базовых методов. Первая из них применяется для всех четырёх методов и служит для нахождения решения сравнения * = (mod г) в общем случае - при HOfl(t,r)> 1, когда расширенный алгоритм Евклида применить нельзя. Для решения сравнения найдём r'=r/HOfl(t,r) и вычислим *' = -gr1(modr'). Решением исходного уравнения а з¿(modр) будет одно из чисел х,=x'+ir',i<=O..HOM(t,r), которое находится подстановкой Xj в исходное уравнение.

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

Для этого на этапе Гауссова исключения занулим все столбцы, относящиеся к базису D2 и к тем элементам базиса D1, которые не входят в разложение а,Ь. После этого из матрицы показателей уберём занулённые строки и столбцы. Полученную

матрицу транспонируем и допишем к ней слева столбцы, являющиеся векторами показателей разложений а,Ь по базису D1. Матрица примет следующий вид (2):

ах Ь, еп еп - еlk

а2 Ь2 е2] е22 — е2к

ат Ьт ет! ет2 ... е^ ^2)

Затем предположим, что известны коэффициенты s,t, Wj, такие, что выполняется сравнение (3)

k т

а°Ь' = П^Пл* (3)

н ¡=1

Если выполняется это сравнение, тогда выполняются и сравнения (4) для показателей из матрицы (2)

к

Щ +tbt = ^w^. (mod г), г = \..т (4)

м

Коэффициенты s,t можно найти с помощью Гауссова исключения. Для этого в матрице (2) исключим столбцы с третьего по последний. Далее, найдём строку (или линейную комбинацию строк), в которой первые два элемента ненулевые, а остальные равны нулю. Обозначим первый элемент как р, второй как q. Тогда за искомые коэффициенты s,t можно принять s=q,t=-p (mod г). Эти коэффициенты дадут сравнение а'Ь' = l(modр), из которого затем находится искомый логарифм.

В общем случае, числа а,Ь не являются гладкими по базису D1. Однако их можно сделать гладкими, возведя в некоторую степень. На практике числа a, b последовательно возводят в степень 1,2,3,..., г-1 и проверяют на гладкость.

В третьей главе осуществляется разработка параллельных алгоритмов, позволяющих ускорить вычислительно сложные этапы экспоненциальных методов дискретного логарифмирования, работающих в E(Fp). В начале главы приводится алгоритм генерации случайной эллиптической кривой и задачи дискретного логарифмирования на ней по заданной длине модуля р. Затем осуществляется анализ выбранных методов - встречи посередине и встречи на случайном дереве. Показано, что оба этих метода основаны на формировании базы данных точек, и поиске в ней. Основное отличие состоит в том, что в методе встречи посередине этапы формирования БД и поиска в ней разделены, а в методе встречи на случайном дереве -выполняются одновременно.

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

диапазоне 1—<х< + ,;'е0..я-1, принадлежат i-тому вычислительному узлу. п п

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

10

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

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

Разрабатывается параллельный алгоритм реализации метода встречи посередине. Параллельный алгоритм дискретного логарифмирования методом встречи

посередине

Вход: описание задачи ДЛ на эллиптической кривой (см. пп. 3.1), параметры: размер БД db_size, размер блока blocksize. Выход: искомый логарифм I.

1. [Инициализировать матрицу взаимодействия] Построить матрицу взаимодействия узлов с помощью описанного выше алгоритма.

2. [Сгенерировать точки] Каждый узел генерирует block_size точек вида vQ, где v, -случайные числа.

3. [Обменяться точками] Узлы обмениваются выработанными точками, используя для планирования обмена матрицу взаимодействий.

4. [Вычислить размер БД]. Узлы вычисляют суммарный размер БД.

5. [Продолжать генерацию] Если размер БД меньше db size, необходимо осуществить переход к шагу 2.

6. [Отсортировать массивы] Узлы производят сортировку массивов точек алгоритмом Quicksort.

7. [Сгенерировать точки] Сгенерировать block_size точек вида щР, где ц -случайные числа.

8. [Обменяться точками] Узлы обмениваются выработанными точками, используя для планирования обмена матрицу взаимодействий (см. подраздел 3.4).

9. [Осуществить поиск] Узлы ищут в своих упорядоченных массивах с помощью бинарного поиска точки с х-координатой, совпадающей с х-координатой одной из полученных точек.

10. [Решить, продолжать ли поиск] Узлы обмениваются информацией, нашёл ли кто-нибудь пару точек с одинаковой х-координатой.

11. [Продолжить поиск] Если совпадения не было, перейти к шагу 7.

12. [Найти решения] Решив сравнение, найти искомый логарифм.

13. [Завершить работу]

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

применяется сжимающее отображение т (см. формулу (1) на странице 7); - поиск в БД и добавление новых точек в неё осуществляются одновременно, для чего БД реализована с помощью красно-чёрных деревьев.

Параллельный алгоритм дискретного логарифмирования методом встречи на

случайном дереве

Вход: описание задачи ДЛ на эллиптической кривой, параметры: размер БД db_size, размер блока block_size, число применений сжимающего отображения к. Выход: искомый логарифм I

1. [Инициализировать матрицу взаимодействия] Построить матрицу взаимодействия узлов с помощью описанного выше алгоритма.

2. [Сгенерировать точки] Каждый узел генерирует block size точек вида u,P + v,Q, где u„vt - случайные числа.

3. [Применить сжимающее отображение] Узлы применяют к сгенерированным на шаге 2 точкам к раз отображение г.

4. [Обменяться точками] Узлы обмениваются выработанными точками, используя для планирования обмена матрицу взаимодействий (см. подраздел 3.4).

5. [Осуществить поиск и добавление] Узлы осуществляют поиск каждой полученной точки в БД. Если точки с такой же х-координатой нет в БД, и размер БД не превышает db size, узел добавляет точку в БД.

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

7. [Решить, продолжать ли поиск] Если пара не найдена, перейти на шаг 2.

8. [Найти логарифм] Составить сравнение и из него найти искомый логарифм l.

9. [Завершение работы]

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

определение эффективности распараллеливания вычислений; изучение влияния параметров реализации на время вычислений. Эксперименты проводились на вычислительном кластере кафедры Безопасности информационных технологий ТТИ ЮФУ. Его основные параметры - 20 процессорных ядер Intel Xeon, 10 Гб ОЗУ, 2 GigabitEthernet коммутатора.

Результаты вычислительных экспериментов по определению эффективности

Рисунок 1. Эффективность реализации алгоритма параллельного просеивания

12

Число процессорных ядер

Рисунок 2. Эффективность реализации алгоритма параллельного Гауссова исключения

1.1

0.9

■а

Й

о

X

а

й08

ш

-е-

■е-

о

0.7 0.6

50 2 4 6 8 ¡0 \2 14 16 18 20 Число процессорных ядер

Рисунок 3. Эффективность реализации алгоритма построения распределённой базы точек

и поискав ней.

По результатам экспериментов эффективность (см. определение на стр. 7) распараллеливания фазы просеивания составила 0.9-0.98, а фазы линейной алгебры -0.5-0.7. Эти значения предсказуемы, так как при просеивании взаимодействие между вычислительными узлами сведено к минимуму, а при выполнении метода Гаусса для обработки каждого столбца узлы сначала выбирают опорную строку, а затем один из узлов широковещательно рассылает эту строку всем остальным. Строки в матрице могут содержать тысячи и десятки тысяч элементов. Даже при упаковке этих чисел в единый пакет данных, пересылка и приём этих данных займут существенное время. Однако с увеличением числа процессорных ядер эффективность остаётся примерно одинаковой, так что разработанный автором параллельный метод Гаусса можно использовать в реальных задачах.

Распараллеливание основных этапов экспоненциальных алгоритмов - построения БД и поиска в ней — также осуществляется с достаточно высокой эффективностью -0.93-0.97. Из этих экспериментов следует вывод, что параллельные алгоритмы имеют достаточную эффективность для практического применения.

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

Таблица 1. Рекомендуемые значения параметров субэкспоненциальных алгоритмов.

Наименование параметра Рекомендуемые значения

Размер базиса basis_size(d lbasissize) Зависит от размера ОЗУ, размера задачи и характеристик передающей среды. При больших размерностях задачи рекомендуется выбирать таким образом, чтобы полностью заполнить доступную ёмкость ОЗУ

Размер базиса алгебраических чисел d2 basis size 20-30

Число независимо просеиваемых степеней block size 2000-20000

Число дополнительных строк matrix addon size 0.1 *basis_size (); 0.1*(dl basis size+d2 basis size)

Максимальный показатель степени алгебраического числа max d2 index 70-100

Начальный показатель степени start power 100-1000

Таблица 2. Рекомендуемые значения параметров экспоненциальных алгоритмов.

Наименование параметра Рекомендуемые значения параметра

Размер БД (db_size) Для метода встречи посередине: шах(л/г .максимально физически доступный); Для метода встречи на случайном дереве: максимально физически доступный

Число генерируемых точек (block size) 1000-10000

Число применений сжимающего отображения (к) l-O(logr)

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

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

3. Разработан алгоритм решения сравнений вида x = ~st (niodr)^ s<r> t<r> не требующий взаимной простоты чисел t,r и позволяющий находить решение из сравнений, которые невозможно решить невозможно решить базовым в таких случаях расширенным алгоритмом Евклида.

4. Модифицирован базовый метод решета числового поля, что позволяет решать задачу ДЛ в общем случае - при любых образующей а и экспоненте b в выражении а" = £>(modр),а< p,b< р

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

6. Экспериментально исследована эффективность распараллеливания реализаций разработанных алгоритмов. Разработанные параллельные алгоритмы показали эффективность 0.9-0.98 на этапе просеивания, 0.93-0.97 на этапе построения БД, и 0.5-0.7 на этапе Гауссова исключения, причём эффективность сохраняется при увеличении числа процессорных ядер. (Эффективностью назовём меру того, насколько хорошо параллельная программа использует многопроцессорную

т

систему. Она определяется как е = —!—, где E-эффективность, р-число

р*тр

процессорных ядер, Тгвремя выполнения программы на одном ядре, Тр-время выполнения программы на р ядрах. При Е=1 программа максимально полно использует процессоры, при Е<1 - имеются потери).

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ Публикации в ведущих рецензируемых изданиях, рекомендуемых ВАК РФ

1. И.Д. Сидоров. Обзор средств защиты современных систем распределённых вычислений. С 114. Известия ЮФУ. Технические науки. Специальный выпуск. Материалы LIII научно-технической конференции профессорско-преподавательского состава, аспирантов и сотрудников ТТИ ЮФУ. Таганрог: Изд-во ТТИ ЮФУ, 2008. №1(78). 277 с.

2. Бабенко Л.К., Сидоров И.Д. Параллельный алгоритм дискретного логарифмирования методом решета числового поля // Изв. ЮФУ. Технические науки. - 2008. - №8. - С. 199203.

Публикации в других изданиях

3. И.Д. Сидоров. Анализ эффективности высокопроизводительного алгоритма дискретного логарифмирования методом базы разложения. Инновационные технологии XXI века в

управлении информатике и образовании: I Всероссийская научно-практическая конференция студентов, аспирантов и молодых ученых: Сборник тезисов,- Нальчик: Издательство М. и В. Котлеровых, 2008г. - 324с.

4. И.Д. Сидоров Высокопроизводительный алгоритм дискретного логарифмирования методом базы разложения. С 112-114. IV ежегодная научная конференция студентов и аспирантов базовых кафедр Южного научного центра РАН: Тезисы докладов (9-18 апреля 2008 г., г. Ростов-на-Дону). Ростов н/Д: Изд-во ЮНЦ РАН, 2008. 384 с.

5. JI.K. Бабенко, И.Д. Сидоров. Параллельные алгоритмы дискретного логарифмирования н группе точек эллиптической кривой. С. 175-177. Материалы X Международной научно-практической конференции «Информационная безопасность». 4.2. - Таганрог: Изд-во ТТИ ЮФУ, 2008.-287 с.

6. JI.K. Бабенко, И.Д. Сидоров. Параллельный алгоритм дискретного логарифмирования методом решета числового поля. С. 172-174. Материалы X Международной научно-практической конференции «Информационная безопасность». 4.2. - Таганрог: Изд-во ТТИ ЮФУ, 2008.-287 с.

7. JI.K. Бабенко, И.Д. Сидоров. Эффективность параллельных алгоритмов дискретного логарифмирования на эллиптической кривой. С. 329-331. Высокопроизводительные вычислительные системы // Материалы Пятой международной научной молодёжной школы. Материалы Международной молодёжной научно-технической конференции -Таганрог: Изд-во ТТИ ЮФУ, 2008. - С. 329-331.478 с.

8. И.Д. Сидоров. Параллельная реализация дискретного логарифмирования методом решета числового поля. С 112-114 IX Всероссийская научная конференция «Техническая кибернетика, радиоэлектроника и системы управления»: Тезисы докладов. - Таганрог: Изд-во ТТИ ЮФУ, 2008. Т.2. - 352 с.

9. L.K. Babenko, I.D. Sidorov Parallel algorithms for discrète log solving in GF(p) and elliptic curves. Proceedings of the Workshop on Computer Science and Information Technologies (CSIT'2008), Antalya, Turkey, September 15-17, 2008. Volume 1. Ufa State Aviation Technical University, 2008.

10. Сидоров И.Д. Анализ эффективности параллельных алгоритмов дискретного логарифмирования на эллиптической кривой // Молодежь и современные информационные технологии. Сборник трудов VII Всероссийской научно-практической конференции студентов, аспирантов и молодых ученых «Молодежь и современные информационные технологии». Томск, 25 - 27 февраля 2009 г., ч.1. Томск: Изд-во СПБ Графике- 354 с.

11. Сидоров И.Д. Нахождение дискретного логарифма методом решета числового поля для негладких образующей и экспоненты. // Неделя науки - 2008; Сб. тезисов, Том 2. -Таганрог; Изд-во ТТИ ЮФУ, 2008. - 464 с.

Программы для ЭВМ

12. Свидетельство о государственной регистрации программы для ЭВМ № 2009611840. Параллельная программа дискретного логарифмирования методом решета числового поля. Авторы: Макаревич О.Б., Бабенко Л.К., Сидоров И.Д.

13. Свидетельство о государственной регистрации программы для ЭВМ № 2009611837. Параллельная программа дискретного логарифмирования на эллиптической кривой методом встречи посередине. Авторы: Макаревич О.Б., Бабенко JI.K., Сидоров И.Д.

14. Свидетельство о государственной регистрации программы для ЭВМ № 2009611839. Параллельная программа дискретного логарифмирования методом встречи на случайном дереве. Авторы: Макаревич О.Б., Бабенко JI.K., Сидоров И.Д.

15. Свидетельство о государственной регистрации программы для ЭВМ № 2009611838. Параллельная программа дискретного логарифмирования методом базы разложения. Авторы: Макаревич О.Б., Бабенко JI.K., Сидоров И.Д.

Определения.

Обозначения и сокращения.

Введение.

1. Анализ известных методов дискретного логарифмирования.

1.1. Появление асимметричной криптографии.

1.2. Асимметричные схемы, основанные на дискретном логарифмировании.

1.2.1. Алгоритм обмена ключами Диффи-Хеллмана.

1.2.2. Бесключевое шифрование Месси-Омуры.

1.2.3. Алгоритм шифрования и подписи Эль-Гамаля.

1.3. Задача дискретного логарифмирования.

1.3.1. Задача ДЛ в общем виде.

1.3.2. Задача ДЛ в мультипликативной группе вычетов по модулю р.

1.3.3. Задача ДЛ в группе точек эллиптической кривой.

1.4. Анализ методов дискретного логарифмирования.

1.4.1. Полный перебор.

1.4.2. Метод Гельфонда.

1.4.3. Встреча посредине.

1.4.4. Метод Шенкса (Giant steps - baby steps).

1.4.5. Метод Полларда.

1.4.5. Встреча на случайном дереве.

1.4.6. Метод базы разложения.

1.4.7. Метод решета числового поля.

1.4.8. Выводы.

1.5. Используемые вычислительные средства.

1.5.1. Классификация параллельных архитектур.

1.5.2. Интерфейс передачи сообщений (MPI).

1.6. Оценка эффективности параллельных программ.

1.6.1. Закон Амдала.

1.6.2. Сетевой закон Амдала.

1.7. Выводы.

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

2.1. Построение задачи дискретного логарифмирования заданной размерности.

2.2. Анализ методов базы разложения и решета числового поля.

2.3. Разработка алгоритма параллельного просеивания.

2.4. Разработка алгоритма параллельного гауссова исключения.

2.5. Алгоритм решения сравнений по составному модулю.

2.6: Применение метода решета числового поля для произвольных основания и экспоненты.

2.7. Реализация метода-базы разложения с помощью разработанных алгоритмов.

2.8: Реализация метода решета числового поля с помощьюразработанных алгоритмов.

2.9. Ускорение решения задачи дискретного логарифмирования с помощью предвычислений.

2.10. Выводы.

3. Решение задачи дискретного логарифмирования в группе точек эллиптической кривой.

3.1. Построение задачи дискретного логарифмирования заданной размерности.

3.2. Анализ методов дискретного логарифмирования на эллиптической кривой.

3.3. Распределение базы точек между процессами.

3.4. Планирование взаимодействия процессов в топологии «полносвязный граф»

3.5. Разработка абстрактного типа данных и выбор структур данных для хранения точек эллиптической кривой.

3.6. Разработка параллельного алгоритма'дискретного логарифмирования методом встречи посередине.

3.7. Разработка параллельного алгоритма дискретного логарифмирования методом встречи на случайном дереве.89*

3.8». Возможность предвычислений.

3.9. Выводы.

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

4.1. Теоретические оценки сложности'субэкспоненциальных методов.

4.1.1. Оценка сложности метода базы разложения.

4.1.2. Оценка сложности метода решета числового поля.

4.2. Теоретические оценки сложности экспоненциальных алгоритмов.

4.2.1. Оценка сложности метода встречи посередине.

4.2.2. Оценка сложности метода встречи на,случайном дереве.

4.3. Аппаратные и программные средства, используемые в вычислительных экспериментах-.100 >

4.3.11. Аппаратные средства.

4.3.2. Программные средства.

4.4. Эффективность алгоритмов, используемых в библиотеках.

4.4.1. Умножение целых чисел.

4.4.2. Возведение в степень.

4.4.3. Нахождение НОД.

4.4.4. Нахождение мультипликативного обратного элемента.

4.5. Экспериментальные оценки эффективности субэкспоненциальных методов.

4.5.1. Определение эффективности распараллеливания.

4.5.2. Влияние размера задачи-на время вычислений.

4.5.3. Определение влияния параметров алгоритмов на время вычислений.

4.6. Экспериментальные оценки эффективности экспоненциальных методов.

4.6.1. Определение эффективности.распараллеливания.

4.6.2. Влияние размера задачи на время вычислений'.

4.6.3. Влияние параметров алгоритмов на время вычислений.

4.7. Методики применения разработанных алгоритмов и программных реализаций

4.7.1. Методика применения субэкспоненциальных алгоритмов.

4.7.2. Методика применения экспоненциальных алгоритмов.

4.8. Оценки стойкости криптографических схем, основанных на задаче ДЛ.

4.9. Выводы.

Асимметричная криптография, выдвинутая Диффи и Хеллманом [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<r, t<r и НОДЦ, г)ф 1;

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

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

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

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

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

4. разработанный алгоритм позволяет решать сравнения вида х = -^"'(modr) при s<r, t<r, НОД(1,г)>1, которые нельзя разрешить напрямую.

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

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

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

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

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

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

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

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

В третьей главе разрабатываются параллельные алгоритмы для решения задачи дискретного логарифмирования в группе точек эллиптической кривой методами встречи посередине и встречи на случайном дереве. Вводится понятие распределённой базы данных. Разрабатывается вариант применения известных структур данных (красно-чёрных деревьев [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<r, t<r и НОДЦ,г)ф 1. Также для всех методов оценена эффективность предвычислений.

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

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

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

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

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

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

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

1. W. Diffie and М.Е. Hellman, "New Directions in Cryptography", IEEE Transactions on Information Theory, v. IT-22, n. 6, Nov 1976, pp. 644-654.

2. R.C. Merkle, "Secure Communication Over Insecure Channels", Communications of the ACM, v.21, n. 4, 1978, pp. 294-299.

3. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. М.: Издательство ТРИУМФ, 2003 - 816 е.: ил.

4. ГОСТ Р 34.10-94 Информационная технология. Криптографическая защита информации. Процедуры выработки-и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма.

5. ГОСТ Р 34.10-2001 Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи.

6. Formal Press Release; US government standard broken in less than a day; January 19th, 1999 Электронный ресурс. Режим доступа: http://www.distributed.net/des/release-desiii.txt, свободный.

7. Закон Мура Электронный. ресурс. Режим доступа: http://ru.wikipedia.Org/wiki/3aKOHMypa, свободный

8. Красно-черные деревья Электронный ресурс. Режим доступа: http://algolist.manual.ru/ds/rbtree.php, свободный.

9. R.L. Rivest, A. Shamir, L.M. Adleman, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems", Communications of the ACM, v. 21, n. 2, Feb 1978, pp.120-126

10. R.L. Rivest, A. Shamir, L.M. Aldeman, "On Digital* Signatures and: Public Key Cryptosystems", MIX Laboratory for Computer Science, Technical Report, MIT/LCS/TR-212, Jan 1979.

11. Ростовцев A.F., Маховенко Е.Б. Теоретическая криптография. — СПб:: АНО НПО «Профессионал», 2005. — 480 е., ил.

12. Элементарное введение в эллиптическую криптографию: Протоколы криптографии на эллиптических кривых. — М.: КомКнига, 2006. 280 с.

13. Т. ElGamal, "A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms", Advances in Cryptology: Proceedings of CRYPTO 84, Springer-Verlag, 1985, pp. 1-18.

14. T.ElGamal; "A Public-Key Cryptosytem and a Signature Scheme Based on Discrete Logarithms", IEEETransactions onInformation Theory, v. IT-31, n. 4,. 1985, pp. 469472.16; Каргополов М.И-VМерзляков

15. Курош А.Г.Теория групп: Mi: Наука;1967."

16. Новиков; Ф.А, Дискретная математика для программистов: Учебник для вузов. 3-е изд.- СПб.: Питер, 20081 384 с.: ил.- (Серия "Учебник для вузов!').

17. Schoof R. Counting points on elliptic curves over finite fields // Journal de Theorie,des Nombres de Bordeaux. 1995. Vol. 7. p. 219-254.

18. Нечаев В.И. Элементы криптографии. Основы теории защиты информации. М:: Высшая школа, 1999.

19. Don Coppersmith, Andrew М. Odlzyko and Richard Schroeppel, Discrete logarithms in GF(p). Algorithmica 1 (1986), 1-15

20. J.M. Pollard. Monte-carlo methods for index computation (mod p). Mathematics of computation 32 (1978)

21. Gordon D. Discrete logarithms in GF(p) using the number field sieve // SLAM Journal on Discrete Mathematics. 1993. Vol. 6. P. 124-138

22. Weber D. An implementation of the general number field sieve to compute discrete logarithms mod p. // Advances in Cryptology EUROCRYPT '1995. Lecture notes in Computer Science. Springer - Verlag. 1995. Vol. 921. P. 95-105.

23. Судоплатов C.B., Овчинникова E.B. Дискретная математика: Учебник. 2-е изд., перераб. - М.: ИНФРА-М; Новосибирск: Изд-во НГТУ, 2007. - 256 с. - (Высшее образование).

24. Классификация параллельных вычислительных систем Электронный ресурс. -Режим доступа: http://ru.wikipedia.org/wiki/Kлaccификaцияпapaллeльныxвычиcлитeльныxcиcт ем; свободный.

25. Воеводин В.В., Воеводин Вл. В. Параллельные вычисления. Спб.: БХВ-Петербург, 2002г.

26. Кнут, Дональд, Эрвин. Искусство программирования, том 1. Основные алгоритмы, 3-е изд. : Пер. с англ. : Уч. Пос. М. : Издательский дом «Вильяме», 2000. - 720 с. : ил. - Парал. тит. англ.

27. Ахо, Альфред В., Хопкрофт, Джон, Ульман, Джеффри Д. Структуры данных и алгоритмы. : Пер. с англ. : М. : Издательский дом «Вильяме», 2001. 384 с. : ил. — Парал. тит. англ.

28. Немнюгин С.А., Стесик O.JI. Параллельное программирование для многопроцессорных вычислительных систем. СПб.: БХВ-Петербург, 2002. — 400 е.: ил.

29. Простое число Софи Жермен. Электронный ресурс. — Режим доступа: Ьйр://ш^1к1ре<11а.ог§/ш11а/ПростоечислоСофиЖермен, свободный

30. R. Solovay and V. Strassen, «А Fast Monte-Carlo Test for Primality," SIAM journal on Computing, v. 6; Mar 1977, pp. 84-85; erratum in ibid, v. 7, 1978, p. 118.

31. M.O. Rabin, "Probabilistic Algorithm for Testing Primality," Journal- of Number Theory, v. 12, n. 1, Feb 1980; pp. 128-138.

32. G.L. Miller, "Riemann's Hypothesis and Tests for Primality," Journal of Computer Systems Science, v. 13, п. 3-, Dec 1976, pp. 300-317.

33. Писсанецки С. Технологияфазреженных матриц. М:: Мир; 1988.

34. Кнут, Д.Э: Искусство программирования, том- 2. Получисленные алгоритмы, 3-е издание.: Пер. с англ. : Уч. пос. М. : Издательский дом «Вильяме», 2001. - 832 с. : ил. - Парал. тит. англ.

35. Бабенко JI.K., Сидоров И.Д. Параллельный алгоритм дискретного логарифмирования методом решета числового поля .// Изв. ЮФУ. Технические науки. 2008. - №8. - С. 199-203.

36. Сидоров ИД. Нахождение дискретного логарифма методом решета числового поля для негладких образующей и экспоненты. // Неделя = науки 2008; Сб. тезисов, Том 2. - Таганрог; Изд-во ТТИ ЮФУ, 2008. - 464 с.

37. А. Г. Ростовцев. О выборе эллиптической кривой над простым полем для построения криптографических алгоритмов* «Проблемы информационной безопасности. Компьютерные системы», СПб., 19991 № 3. С. 37-40

38. Кнут, Дональд Эрвин. Искусство программирования, том 3. Сортировка и поиск,, 2-е изд. : Пер. с англ. : Уч. пос. Ml : Издательский дом «Вильяме», 2000. - 832" с. : ил. — Парал. тит. англ.

39. Красно-чёрное дерево. Электронный ресурс. — Режим доступа: http://m.wikipedia.0rg/wiki/KpacH0-4epH0e^n,epeB0, свободный

40. Кнут, Дональд, Эрвин. Искусство программирования, том 1. Основные алгоритмы, 3-е изд. : Пер. с англ. : Уч. Пос. — М. : Издательский дом «Вильяме», 2000. — 720 с. : ил. Парал. тит. англ.

41. Харт, Джонсон, М. Системное программирование в среде Windows, 3-е издание, : Пер, с англ. — М. : Издательский дом "Вильяме", 2005. — 592 е.: ил. — Парал. тит. англ.

42. NTL: A Library for doing Number Theory Электронный ресурс. Режим доступа: http://www.shoup.net/ntl/, свободный

43. The GNU Multiple Precision Bignum Library Электронный ресурс. Режим доступа: http://gmplib.org/, свободный

44. ТОР 500 Электронный ресурс. Режим доступа: http://www.top500.org/, свободный