
Тип работы:	Предмет:	Язык работы:

СХЕМА РЕАЛИЗАЦИИ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ КАК ИНСТРУМЕНТ ЗАЩИТЫ ОБРАБАТЫВАЕМЫХ ДАННЫХ

Работа №	77538
Тип работы	Дипломные работы, ВКР
Предмет	информационная безопасность
Объем работы	28
Год сдачи	2017
Стоимость	4370 руб.
ПУБЛИКУЕТСЯ ВПЕРВЫЕ
Просмотрено	207

Не подходит работа?

Узнай цену на написание

Содержание

ВВЕДЕНИЕ
1. ОПИСАНИЕ ЗАДАЧИ ДИСКРЕТНОГО ЛОГАРИФМИРОВАНИЯ
1.1. Дискретные логарифмы в конечном поле
1.2. Алгоритм Шенкса 6
1.3. Алгоритм Полига-Хеллмана 8
1.4. p-метод Полларда 9
2. РЕАЛИЗАЦИЯ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ, ТЕОРЕТИЧЕСКАЯ
ОЦЕНКА СЛОЖНОСТИ 11
2.1. Алгоритм Шенкса 11
2.2. p-метод Полларда 12
2.3. Алгоритм Полига-Хеллмана
2.4. Общее описание приложения
3. АНАЛИЗ ПОЛУЧЕННЫХ РЕЗУЛЬТАТОВ 16
3.1. Сравнительный анализ алгоритма Шенкса 16
3.2. Сравнительный анализ алгоритма Полига-Хеллмана
3.3. Сравнительный анализ p-метода Полларда
ЗАКЛЮЧЕНИЕ 21
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 23
ПРИЛОЖЕНИЕ 24

Введение

Нужна ли обычному человеку защита обрабатываемых данных? Безусловно, да. Люди могут работать в государственных учреждениях, в банках. Они могут вести конкурирующую предпринимательскую деятельность, разрабатывать новые продукты, изделия, готовить патенты. Они могут общаться в социальных сетях либо совершать интернет покупки. Они могут просто желать защиты от вторжения в их личную жизнь. Итог один: по многим причинам обрабатываемые данные и линии связи должны быть закрыты от постороннего доступа.
В современной литературе много работ, посвященных криптографическим протоколам, методам и алгоритмам. Но наравне с разработкой новых криптографических методов необходимо также уделять внимание оптимизации уже известных алгоритмов.
Связано это с тем, что в настоящий момент требования к скорости работы алгоритмов такие же высокие, как и требования к стойкости. Разрабатываются распределенные и параллельные вычисления. В первом варианте используются несколько компьютеров для решения трудоемких вычислительных задач, во втором - программы разрабатываются как набор взаимодействующих вычислительных процессов, работающих параллельно.
Целью данной работы была реализация параллельных вычислений для алгоритмов Шенкса, Полига-Хеллмана и p-метода Полларда, основанных на задаче дискретного логарифмирования и проведение сравнительного анализа среднего времени работы алгоритмов.
Для реализации поставленной цели были рассмотрены следующие задачи:
1. изучить алгоритмы Шенкса, Полига-Хеллмана и p-метода Полларда, основанных на задаче дискретного логарифмирования;
2. изучить способы организации компьютерных вычислений, при которых программы разрабатываются как набор взаимодействующих вычислительных процессов, работающих параллельно;
3. реализовать распараллеливание алгоритмов Шенкса, Полига- Хеллмана и p-метода Полларда;
4. провести сравнительный анализ среднего времени работы перечисленных алгоритмов до и после применения параллельных вычислений;
5. изучить другие показатели (число разрядов входных данных, характеристики компьютера, на котором запускается алгоритм, число потоков и д.р.), влияющих на время работы алгоритмов.
Результатом работы стали реализованные алгоритмы, решающие задачу дискретного логарифмирования и выводы, полученные в ходе сравнительного анализа времени работы алгоритмов

Возникли сложности?

Нужна помощь преподавателя?

Помощь студентам в написании работ!

ДИПЛОМНЫЕ МАГИСТЕРСКИЕ ДИССЕРТАЦИИ

Курсовые Статьи Диплом Рязань

Заключение

В ходе работы удалось достигнуть поставленную цель: реализовать параллельные вычисления для алгоритмов Шенкса, Полига-Хеллмана и р- метода Полларда, основанных на задаче дискретного логарифмирования и провести сравнительный анализ среднего времени работы алгоритмов.
Цель была достигнута посредством выполнения следующих задач:
1. изучены алгоритмы Шенкса, Полига-Хеллмана и р-метода Полларда, основанных на задаче дискретного логарифмирования;
2. изучены способы организации компьютерных вычислений, при которых программы разрабатываются как набор взаимодействующих вычислительных процессов, работающих параллельно;
3. реализовано распараллеливание алгоритмов Шенкса, Полига- Хеллмана и р-метода Полларда;
4. проведен сравнительный анализ среднего времени работы перечисленных алгоритмов до и после применения параллельных вычислений;
5. изучены другие показатели (число разрядов входных данных, характеристики компьютера, на котором запускается алгоритм, число потоков и д.р.), влияющих на время работы алгоритмов.
Результатом работы стали реализации указанных алгоритмов и выводы, полученные в процессе их исследования. После проведения сравнительного анализа были получены следующие результаты:
Из трех рассматриваемых алгоритмов наиболее хорошие результаты показал р-метод Полларда, далее алгоритм Шенкса. В обоих алгоритмах удалось сократить среднее время вычисления дискретного логарифма путем распараллеливания. Для р-метода Полларда время вычислений сократилось на 20%, для алгоритма Шенкса - на 40%.
Алгоритм Полига-Хеллмана хороших результатов не дал. Связано это с тем, что самой затратной операцией здесь является операция факторизации, поэтому распараллеливание алгоритма выигрыша во времени не дает. Алгоритм Полига-Хеллмана эффективен, если р — 1 раскладывается на небольшие простые множители.
Экспериментально показана зависимость продолжительности работы алгоритмов от технических характеристик устройства, на котором они запускаются.

Литература

1. Шнайер Б. Прикладная криптография. - М. : Триумф, 2002. - 816 с.
2. B.A. LaMacchia and A.M. Odlyzko, “Computation of Discrete Logarithms in Prime Fields, Designs, Codes and Cryptography”, v.1, 1991, pp 46-62.
3. Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. —
М.: МЦНМО, 2003. — 328 с. — ISBN 5-94057-103-4.
4. Горбенко И.Д., Качко Е.Г., Погребняк К.А. Параллельный метод Полларда решения задачи дискретного логарифмирования в группе точек ЭК // Параллельные вычислительные технологии (ПАВТ - 2012): труды международной научной конференции (Новосибирск, 26-30 марта, 2012 г.). Челябинск: Издательский центр ЮУрГУ, 2012. - С. 723.
5. A. Odlyzko, “Discrete Logarithms in Finite Fields and Their Cryptographic Sig nificance,” Advances in Cryptology: Proceedings of eurocrypt 84, Springer-Verlag, 1985, pp. 224-314.
6. И. А. Панкратова. Теоретико-числовые методы в криптографии: Учебное пособие. — Томск: ТГУ, 2009. — С. 90-98. — 120 с.
7. Методы факторизации натуральных чисел: учебное пособие / Ш.Т. Ишмухаметов. Казань: Казан. ун. 2011. 190 с.
8. Н. Коблиц. Курс теории чисел и криптографии. — М.: Научное издательство ТВП, 2001. — 254 с.
9. Нечаев В.И. "ЭЛЕМЕНТЫ КРИПТОГРАФИИ (Основы теории защиты информации)". — М.: "Высшая школа", 1999. — 109 с.
10. Ю. В. Нестеренко. Глава 4.8. Дискретное логарифмирование // Введение в криптографию / Под ред. В. В. Ященко. — Питер, 2001. — 288 с.