Применение алгоритма RSA для шифрования потоков данных - (диплом)
Применение алгоритма RSA для шифрования потоков данных - (диплом)
Дата добавления: март 2006г.
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
АМУРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
Факультет математики и информатики
Кафедра математического анализа и моделирования
Специальность 010200 – “прикладная математика”
ДОПУСТИТЬ К ЗАЩИТЕ
Зав. кафедрой ____________________
___________Т. В. Труфанова
“____”_____________2002 г.
ДИПЛОМНАЯ РАБОТА
на тему Применение алгоритма RSA при шифровании потоков данных
Исполнитель
студент группы 752 А. А. Малышев
Руководитель
к. ф. -м. н. , доцент А. Н. Семочкин
Нормоконтроль
к. т. н. , доцент А. Н. Гетман
Рецензент
к. ф. -м. н. , доцент Е. Ф. Алутина
Благовещенск 2002
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
АМУРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
Факультет математики и информатики
Кафедра математического анализа и моделирования
Утверждаю:
Зав. кафедрой
_______________________
подпись И. О. Фамилия
“__”_____________ 200_г.
ЗАДАНИЕ
К дипломной работе студента Малышева Андрея Александровича
1. Тема дипломной работы Применение алгоритма RSA при шифровании потоков данных (утверждено приказом от ____ №___________)
2. Срок сдачи студентом законченной работы ________________________ 3. Исходные данные к дипломной работе ___________________________ 4. Содержание дипломной работы (перечень подлежащих разработке вопросов) Исследовать современные методы шифрования и их приложимость к шифрованию потоков данных. Разработать собственную библиотеку алгоритмов шифрования и программный продукт, демонстрирующий работу этих алгоритмов при передаче данных в сети.
5. Дата выдачи задания “ ” ____________2002 г.
Руководитель дипломной работы Семочкин Александр Николаевич к. ф. -м. н. , доцент кафедры МАиА.
Задание принял к исполнению _____________________________________ РЕФЕРАТ
Дипломная работа 48 стр. , 11 источников, 4 приложения.
АЛГОРИТМ RSA, ФУНКЦИЯ ЭЙЛЕРА, ВЗАИМНО ПРОСТЫЕ ЧИСЛА
В данном дипломном проекте рассматривается задача анализа алгоритма шифрование в потоках данных RSA. Для этого построен алгоритм и реализован программный продукт. Программный продукт создан в среде визуального программирования Delphi 5. 0, отлажен и протестирован. На основании анализа полученных результатов сделаны выводы, указаны замечания и рекомендации исследователю по практическому использованию программы, а также по дальнейшему улучшению алгоритма и программного продукта в целом.
СОДЕРЖАНИЕ
Введение
5
1. Постановка задачи
10
2. Алгоритм RSA
11
2. 1. Система шифрования RSA
12
2. 2. Сложность теоретико-числовых алгоритмов
16
2. 2. 1. Алгоритм вычисления
17
2. 2. 2. Алгоритм Евклида
18
2. 2. 3. Алгоритм решения уравнения
18
2. 2. 4. Алгоритм нахождения делителей многочлена в кольце
21
3. Качественная теория алгоритма RSA
23
3. 1. Алгоритм, доказывающий непростоту числа
24
3. 2. Нахождение больших простых чисел
26
3. 3. Проверка большого числа на простоту
30
4. Практическая реализация алгоритма
37
4. 1. Реализованные алгоритмы
37
4. 2. Анализ результатов
38
5. Выводы
39
5. 1 Алгоритм
39
5. 2 Алгоритм и программа
39
Заключение
41
Список использованных источников
42
Приложение 1. Листинг программы
43
Приложение 2. Главная форма программы
46
Приложение 3. Форма базы данных абонентов
47
Приложение 4. Форма нахождения простых чисел и генерации ключей 48
ВВЕДЕНИЕ
Проблема защиты информации путем ее преобразования, исключающего ее прочтение посторонним лицом, волновала человеческий ум с давних времен. История криптографии - ровесница истории человеческого языка. Более того, первоначально письменность сама по себе была своеобразной криптографической системой, так как в древних обществах ею владели только избранные. Священные книги древнего Египта, древней Индии тому примеры. История криптографии условно можно разделить на 4 этапа.
1) наивная криптография.
2) формальная криптография.
3) научная криптография.
4) компьютерная криптография.
Для наивной криптографии (до нач. XVI века) характерно использование любых (обычно примитивных) способов запутывания противника относительно содержания шифруемых текстов. На начальном этапе для защиты информации использовались методы кодирования и стеганографии, которые родственны, но не тождественны криптографии. Большинство из используемых шифров сводились к перестановке или моноалфавитной подстановке. Одним из первых зафиксированных примеров является шифр Цезаря, состоящий в замене каждой буквы исходного текста на другую, отстоящую от нее в алфавите на определенное число позиций. Другой шифр, полибианский квадрат, авторство которого приписывается греческому писателю Полибию, является общей моноалфавитной подстановкой, которая проводится с помощью случайно заполненной алфавитом квадратной таблицейдля греческого алфавита размер составляет 5x5). Каждая буква исходного текста заменяется на букву, стоящую в квадрате снизу от нее. Этап формальной криптографии (кон. XV века - нач. XX века) связан с появлением формализованных и относительно стойких к ручному криптоанализу шифров. В европейских странах это произошло в эпоху Возрождения, когда развитие науки и торговли вызвало спрос на надежные способы защиты информации. Важная роль на этом этапе принадлежит Леону Батисте Альберти, итальянскому архитектору, который одним из первых предложил многоалфавитную подстановку. Данный шифр, получивший имя дипломата XVI века Блеза Вижинера, состоял в последовательном “сложении” букв исходного текста с ключом (процедуру можно облегчить с помощью специальной таблицы). Его работа “Трактат о шифре” (1466) считается первой научной работой по криптологии. Одной из первых печатных работ, в которой обобщены и сформулированы известные на тот момент алгоритмы шифрования является труд “Полиграфия”(1508 г. ) немецкого аббата Иоганна Трисемуса. Ему принадлежат два небольших, но важных открытия: способ заполнения полибианского квадрата (первые позиции заполняются с помощью легко запоминаемого ключевого слова, остальные - оставшимися буквами алфавита) и шифрование пар букв (биграмм). Простым но стойким способом многоалфавитной замены (подстановки биграмм) является шифр Плейфера, который былоткрыт в начале XIX века Чарльзом Уитстоном. Уитстону принадлежит и важное усовершенствование - шифрование “двойным квадратом”. Шифры Плейфера и Уитстона использовались вплоть до первой мировой войны, так как с трудом поддавались ручному криптоанализу.
В XIX веке голландец Керкхофф сформулировал главное требование к криптографическим системам, которое остается актуальным и поныне: секретность шифров должна быть основана на секретности ключа, но не алгоритма. Наконец, последним словом в донаучной криптографии, которое обеспечили еще более высокую криптостойкосить, а также позволило автоматизировать (в смысле механизировать) процесс шифрования стали роторные криптосистемы. Одной из первых подобных систем стала изобретенная в 1790 году Томасом Джефферсоном, будущим президентомСША механическая машина. Многоалфавитная подстановка с помощью роторной машины реализуется вариацией взаимного положения вращающихся роторов, каждый из которых осуществляет“прошитую” в нем подстановку. Практическое распространение роторные машины получили только в начале XX века. Одной из первых практически используемых машин, стала немецкая Enigma, разработанная в 1917 году Эдвардом Хеберном и усовершенствованная Артуром Кирхом. Роторные машины активно использовались во время второй мировой войны. Помимо немецкой машины Enigma использовались также устройства Sigaba (США), Турех (Великобритания), Red, Orange и Purple2 (Япония). Роторные системы -вершина формальной криптографии так как относительно просто реализовывали очень стойкие шифры. Успешные криптоатаки на роторные системы стали возможны только с появлением ЭВМ в начале 40-х годов.
