Диплом: Применение алгоритма RSA для шифрования потоков данных - текст диплома. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Диплом

Применение алгоритма RSA для шифрования потоков данных

Банк рефератов / Математика

Рубрики  Рубрики реферат банка

закрыть
Категория: Дипломная работа
Язык диплома: Русский
Дата добавления:   
 
Скачать
Microsoft Word, 5935 kb, скачать бесплатно
Заказать
Узнать стоимость написания уникальной дипломной работы

Узнайте стоимость написания уникальной работы

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ АМУРСКИЙ ГОСУДАРСТВЕНН ЫЙ УНИВЕРСИТЕТ Факультет математики и информатики Кафедра математического анализа и моделирования Специальность 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-х годов. Главная отличительная черта научной криптографии (30-е - 60-е годы XX века ) - появление криптосистем со строгим мате матическим обоснованием криптостойкости . К началу 30-х годов окончательно сформировались разделы математики , являющиеся научной основой криптологии : теория вероятностей и математическая статистика , общая алгебра , теория чисел , начали активно развиваться т е ория алгоритмов , теория информации , кибернетика . Своеобразным водоразделом стала работа Клода Шеннона «Теория связи в секретных системах» (1949), где сформулированы теоретические принципы криптографической защиты информации . Шеннон ввел понятия «рассеиван и е» и «перемешивание» , обосновал возможность создания сколь угодно стойких криптосистем. В 60-х годах ведущие криптографические школы подошли к созданию блочных шифров , еще более стойких по сравнению с роторными криптосистемами , однако допускающие практичес кую реализацию только в виде цифровых электронных устройств. Компьютерная криптография (с 70-х годов XX века ) обязана своим появлением вычислительным средствам с производительностью , достаточной для реализации критосистем , обеспечивающих при большой скорос ти шифрования на несколько порядков более высокую криптостойкость , чем «ручные» и «механические» шифры. Первым классом криптосистем , практическое применение которых стало возможно с появлением мощных и компактных вычислительных средств , стали блочные шифры . В 70-е годы был разработан американский стандарт шифрования DES (принят в 1978 году ). Один из его авторов , Хорст Фейстел (сотрудник IBM ), описал модель блочных шифров , на основе которой были построены другие , более стойкие симметричные криптосистемы , в т ом числе отечественный стандарт шифрования ГОСТ 28147-89. С появлением DES обогатился и криптоанализ , для атак на американский алгоритм был создано несколько новых видов криптоанализа (линейный , дифференциальный и т.д .), практическая реализация которых опя ть же была возможна только с появлением мощных вычислительных систем. В середине 70-х годов произошел настоящий прорыв в современной криптографии - появление асимметричных криптосистем , которые не требовали передачи секретного ключа между сторонами . Здесь отправной точкой принято считать работу , опубликованную Уитфилдом Диффи и Мартином Хеллманом в 1976 году под названием «Новые направления в современной криптографии» . В ней впервые сформулированы принципы обмена шифрованной информацией без обмена секретны м ключом . Независимо к идее асимметричных криптосистем подошел Ральф Меркли . Несколькими годами позже Рон Ривест , Ади Шамир и Леонард Адлеман открыли систему RSA , первую практическую асимметричную криптосистему , стойкость которой была основана на проблеме ф акторизации больших простых чисел . Асимметричная криптография открыла сразу несколько новых прикладных направлений , в частности системы электронной цифровой подписи (ЭЦП ) и электронных денег. В 80-90-е годы появились совершенно новые направления криптограф ии : вероятностное шифрование , квантовая криптография и другие . Осознание их практической ценности еще впереди . Актуальной остается и задача совершенствования симметричных криптосистем . В 80-90-х годах были разработаны нефейстеловские шифры ( SAFER , RC 6 и др .), а в 2000 году после открытого международного конкурса был принят новый национальный стандарт шифрования США - AES. 1. ПОСТАНОВКА ЗАДАЧИ Безопасность передачи данных по каналам связи является актуальной . Современные компьютерные сети не исключение . К сожалению , в сетевых операционных системах ( Windows NT / XP , Novell и т.д .) иностранного производства , как следствие , из-за экспортных соображений уровень алгоритмов шифрования заметно снижен. Задача : исследовать современные методы шифрования и их приложимос ть к шифрованию потоков данных . Разработать собственную библиотеку алгоритмов шифрования и программный продукт , демонстрирующий работу этих алгоритмов при передаче данных в сети. 2. АЛГОРИТМ RSA Труды Евклида и Диофанта , Ферма и Эйлера , Гаусса , Чебышева и Эрмита содер жат остроумные и весьма эффективные алгоритмы решения диофантовых уравнений , выяснения разрешимости сравнений , построения больших по тем временам простых чисел , нахождения наилучших приближений и т.д . В последние два десятилетия , благодаря в первую очередь запросам криптографии и широкому распространению ЭВМ , исследова ния по алгоритмическим вопросам теории чисел переживают период бур ного и весьма плодотворного развития . Вычислительные машины и электронные средства связи проникли практическ и во все сферы человеческой деятельности . Немыслима без них и современная криптография . Шифрование и дешифрование текстов можно представлять себе как процессы переработки целых чисел при помощи ЭВМ , а способы , которыми выполняются эти операции , как неко т о рые функции , определённые на множестве целых чисел . Всё это делает естественным появление в криптографии методов теории чисел . Кроме того , стойкость ряда современных криптосистем обосновывается только сложностью некоторых теоретико-числовых задач. Но возмо жности ЭВМ имеют определённые границы . Приходится раз бивать длинную цифровую последовательность на блоки ограниченной длины и шифровать каждый такой блок отдельно . Мы будем считать в дальнейшем , что все шифруемые целые числа неотрицательны и по вели чине меньше некоторого заданного (скажем , техническими ограничени ями ) числа m . Таким же условиям будут удовлетворять и числа , получае мые в процессе шифрования . Это позволяет считать и те , и другие числа элементами кольца вычетов . Шифрующая функция при этом может рассматриваться как взаимнооднозначное отображение колец вычетов а число представляет собой сообщение в зашифрованном виде. Простейший шифр такого рода - шифр замены , соответству ет отображению при некотор ом фиксированном целом k . Подобный шифр использовал еще Юлий Цезарь . Конечно , не каждое отображение подходит для целей надежного сокрытия инфор мации. В 1978 г . американцы Р . Ривест , А . Шамир и Л . Адлеман ( R . L . Rivest . A . Shamir . L . Adleman ) предложили пример функции , обла дающей рядом замечательных достоинств . На е ё основе была построена реально используемая система шифрования , получившая название по пер вым буквам имен авторов -система RSA . Эта функция такова , что 1) существует достаточно быстрый алгоритм вычисления значений ; 2) существует достаточно быстрый алгоритм вычисления значений об ратной функции ; 3) функция обладает некоторым «секретом» , знание которого позво ляет быстро вычислять значения ; в противном же случае вычисле ние становится трудно разрешимо й в вычислительном отношении задачей , требующей для своего решения столь много времени , что по его прошествии зашифрованная информация перестает представлять инте рес для лиц , использующих отображение в качестве шифра. Еще до выхода из печати статьи копия доклада в Массачусетском Технологическом институте , посвящённого системе RSA . была послана известному популяризатору математики М . Гарднеру , который в 1977 г. в журнале Scientific American опубликовал статью посвящённую этой системе шифрования . В русском переводе заглавие статьи Гарднера зву чит так : Новый вид шифра , на расшифровку которого потребуются мил лионы лет . Именно эта статья сыграла важнейшую роль в р аспростране нии информации об RSA , привлекла к криптографии внимание широких кругов неспециалистов и фактически способствовала бурному прогрессу этой области , произошедшему в последовавшие 20 лет. 2.1. с истема шифрования RSA Пусть и натуральные числа . Функция реализующая схему RSA , устроена следующим образом . (1) Для расшифровки сообщения достаточно решить сравнение . (2) При некоторых условиях на и это сравнение имеет единственное решение . Для того , чтобы описать эти условия и объяснить , как можно найти решение , нам потребуется одна теоретико-числовая функция , так назы ваемая функция Эйлера . Эта функция натурального аргу мента обозна чается и равняется количеству целых чисел на о трезке от 1 до , взаимно простых с . Так и для любого простого числа и натурального . Кроме того , для лю бых натуральных взаимно простых и . Эти свойства позволяют легко вычислить значение , если известно разложение числа на простые сомножители. Если показатель степени в сравнении (2) взаимно прост с , то сравнение (2) имеет единственное решение . Для того , чтобы найти его , определим целое число , удовлетворяющее усло виям . (3) Такое число существует , поскольку , и притом единствен но . Здесь и далее символом будет обозначаться наибольший общий делитель чисел и . Классическая теорема Эйлера , утверждает , что для каждого чис ла , взаимно простого с , выполняется сравнение и , следовательно. . (4) Таким образом , в предположении , единственн ое решение срав нения (2) может быть найдено в виде . (5) Если дополнител ьно предположить , что число состоит из различных простых сомножителей , то сравнение (5) будет выполняться и без предпо ложения . Действительно , обозначим и . Тогда делится на , а из (2) следует , что . Подобно (4), тепер ь легко находим . А кроме того , имеем . Получившиеся сравнения в силу дают нам (5). Функция (1), принятая в системе RSA , может быть вычислена доста точно быстро . Обратная к функция вычисляется по тем же правилам , что и , лишь с заменой показателя степени на . Таким образом , для функции (1) будут выполнены указанные выше свойства 1) и 2). Для вычисления функции (1) достаточно знать лишь числа и . Именно они составляют открытый ключ для шифрования . А вот для вы числения обратн ой функции требуется знать число . оно и является «се кретом» , о котором речь идёт в пункте в ). Казалось бы . ничего не стоит . зная число . разложить его на простые сомножители , вычислить затем с помощью известных правил значение и , наконец , с помощью (3) определить нужное число . Все шаги этого вычисления могут быть реа лизованы достаточно быстро , за исключением первого . Име нно разложе ние числа на простые множители и составляет наиболее трудоемкую часть вычислений . В теории чисел несмотря на многолетнюю её историю и на очень ин тенсивные поиски в течение последних 20 лет , эффективный алгоритм разложения натуральных чисел на множители так и не найден . Конечно , можно , перебирая все простые числа до , и . деля на них , найти требуемое разложение . Но , учитывая , что количество простых в этом промежутке , асимптотически равно , на ходим , что при , записываемом 100 десятичными цифрами , найдётся не менее простых чисел , на которые придётся делить при разложе нии его н а множители . Очень грубые прикидки показывают , что компью теру , выполняющему миллион делений в секунду , для разложения числа таким способом на простые сомножи тели потребуется не менее , чем лет . Известны и более эффективные способы разложения целых чисел на множители , чем простой перебор простых делителей , но и они работают очень медленно. Авторы схемы RSA предложили выбирать число в виде произведе ния двух простых множителей и , примерно одинаковых по величине . Так как , (6) то единственное условие на выбор показателя степени в отображении (1) есть . (7) Итак , лицо , заинтересованное в организации шифрованной переписки с помощью схемы RSA , выбирает два достаточно больших простых числа и . Перемножая их , оно находит число . Затем выбирается число , удовлетворяющее условиям (7), вычисляется с помощью (6) число и с помощью (3) - число . Числа и публикуются , число остается се кретным . Теперь любой может отправлять зашифрованные с помощью (1) сообщения организатору этой системы , а организатор легко сможет расшифровывать их с помощью (5). Для иллюстрации своего метода Ривест , Шамир и Адлеман зашифро вали таким способом некоторую английскую фразу . Сначала она стан дартным образом (а =01, b =02, .... z =26, пробел =00) была записана в виде целого числа , а затем зашифрована с помощью отобра жения (1) при m =11438162575788886766932577997614661201021829672124236256256184293570 6935245733897830597123563958705058989075147599290026879543541 и . Эти два числа были опубликованы , причем дополнительно сообщалось , что . где и - простые числа , записываемые со ответственно 64 и 65 десятичными знаками . Первому , кто расшифрует соответствующее сообщение , была обещана награда в 100$. Эта история завершилась спустя 17 лет в 1994 г ., когда D . Atkins , M . Graff , А . К . Lenstra и Р . С . Leyland сообщили о расшифровке фразы . Чис ла и оказались равными , . Этот замечательный результат (разложение на мно жители 129-значного десятичного числа ) был дос тигнут благодаря ис пользованию алгоритма разложения чисел на множители , называемого методом квадратичного решета . Выполнение вычислений потребовало колоссальных ресурсов . В работе , возглавлявшейся четырьмя авторами проекта , и продолжавшейся после предвар и тельной теоретической под готовки примерно 220 дней , на добровольных началах участвовало около 600 человек и примерно 1600 компьютеров , объединённых сетью Inter net . Наконец , отметим , что премия в 100$ была передана в Free Software Foundation . 2.2.Сложно сть теоретико-числовых алгоритмов Сложность алгоритмов теории чисел обычно принято измерять коли чеством арифметических операций (сложений , вычитаний , умножений и делений с остатком ), необходимых для выполнения всех действий , пред писанных алгоритмом . Впро чем , это определение не учитывает величины чисел , участвующих в вычислениях . Ясно , что перемножить два стозначных числа значительно сложнее , чем два однозначных , хотя при этом и в том , и в другом случае выполняется лишь одна арифметическая опе рация . Поэт о му иногда учитывают ещё и величину чисел , сводя дело к так называемым битовым операциям , т . е . оценивая количество необхо димых операций с цифрами 0 и 1, в двоичной записи чисел. Говоря о сложности алгоритмов , мы будем иметь в ви ду количество арифметическ их операций . При построении эффективных алгоритмов и обсуждении верхних оценок сложности обычно хватает ин туитивных понятий той области математики , которой принадлежит алго ритм . Формализация же этих понятий требуется лишь тогда , когда речь идёт об отсут с твии алгоритма или доказательстве нижних опенок слож ности. Приведем теперь примеры достаточно быстрых алгоритмов с опен ками их сложности . Здесь и в дальнейшем мы не будем придерживаться формального описания алгоритмов , стараясь в первую очередь объяснить смысл выполняемых действий. Следующий алгоритм вычисляет за арифмети ческих операций . При этом , конечно , предполагается , что натуральные числа и не превосходят по величине . 2.2.1. Алгоритм вычисления 1) Представим в двоичной системе счисления , где , цифры в двоичном представлении , равны 0 или 1, . 2) Положим и затем для вычислим . 3) есть искомый вычет . Справедливость этого алгоритма вытек ает из сравнения , легко доказываемого индукцией по . Так как каждое вычисление на шаге 2 требует не более трёх умноже ний по модулю и этот шаг выполняется раз , то сложность алгоритма может быть оценена величиной . Второй алгоритм - это классический алгоритм Евклида вычисления н аибольшего общего делителя целых чисел . Мы предполагаем заданными два натуральных числа и и вычисляем их наибольший общий дели тель . 2.2.2. Алгоритм Евклида 1) Вычислим - остаток от деления числа на , , . 2) Если , то есть искомое число. 3) Если , то заменим пару чисел парой и перейдем к шагу 1. Теорема 1. При вычислении наибольшего общего делителя с помощью алгоритма Евклида будет выполнено не более операций де ления с остатко м , где есть количество цифр в десятичной записи меньшего из чисел и . Доказательство . Положим и определим - последовательность делителей , появляющихся в процессе выполнения ша га 1 алгоритма Евклид а . Тогда . Пусть также , , , , - последователь ность Фибоначчи . Индукцией по от до легко доказывается неравенство . А так как , то имеем неравенства и . Немного подправив алгоритм Евклида , можно достаточно быстро ре шать сравнения при условии , что . Эта задача равносильна поиску целых решений уравнения . 2.2.3. Алгоритм решения уравнения 0) Определим матрицу . 1) Вычислим - остаток от деления числа на , , . 2) Если , то второй столбец матрицы даёт вектор решений уравнения. 3) Если , то заменим матрицу матрицей . 4) Заменим пару чисел парой и перейдем к шагу 1. Если обозначить через матрицу , возникающую в процессе рабо ты алгоритма перед шагом 2 после делений с остатком (шаг 1), то в обозначениях из доказательства теоремы 1 в этот момент выполняется векторное равенство . Поскольку числа и взаимно просты , имеем , и это доказы вает , что алгоритм действительно даёт решение уравнения . Буквой мы обозначили количество делений с остатком , которое в точ ност и такое же , как и в алгоритме Евклида. Три приведённых выше алгоритма относятся к разряду так называе мых полиномиальных алгоритмов . Это название носят алгоритмы , слож ность которых оценивается сверху степенным образом в зависимости от длины записи входящи х чисел . Если наибольшее из чисел , подаваемых на вход алгоритма , не превосходит , то сложность алгоритмов этого типа оценивается величиной , где - некото рая абсолютная постоянная . Во всех приведённых выше примерах . Полиномиальные алгоритмы в теории чисел - большая редкость . Да и опенки сложности алгоритмов чаше всего опираются на какие-либо не доказанные , но правдоподо бные гипотезы , обычно относящиеся к анали тической теории чисел. Для некоторых задач эффективные алгоритмы вообще не известны . Иногда в таких случаях все же можно предложить последовательность действий , которая , «если повезет» , быстро приводит к требуемому ре зультату . Существует класс так называемых вероятностных алгоритмов , которые дают правильный результат , но имеют вероятностную опен ку времени работы . Обычно работа этих алгоритмов зависит от одного или нескольких параметров . В худшем случае они работа ю т достаточно долго . Но удачный выбор параметра определяет быстрое завершение ра боты . Такие алгоритмы , если множество «хороших» значений параметров велико , на практике работают достаточно эффективно , хотя и не имеют хороших опенок сложности. Мы будем иногд а использовать слова детерминированный алгоритм , чтобы отличать алгоритмы в обычном смысле от вероятностных алго ритмов. Как пример , рассмотрим вероятностный алгоритм , позволяющий эф фективно находить решения полиномиальных сравнений по простому мо дулю . П усть — простое число , которое предполагается большим , и - м ногочлен , степень которого предполагается ограничен ной . Задача состоит в отыскании решений сравнения . (8) Например , речь может идти о решении квадратичных сравнений , если степень многочлена равна 2. Другими словами , мы должны отыскат ь в поле все элементы , удовлетворяющие уравнению . Согласно м алой теореме Ферма , все элементы поля являются од нократными корнями многочлена . Поэтому , вычислив наибольший общий делитель , мы найдем многочлен , множест во корней которого в поле совпадает с множеством корней многочлена , причем все эти корни однократны . Если окажется , что многочлен имеет нулевую степень , т . е . лежит в поле , это будет означать , что сравнение (8) не имеет решений. Для вычисления многочлена удобно сначала вычислить многочлен , пользуясь алгоритмом , подобным описанному выше алгоритму возведени я в степень (напомним , что число предполагается большим ). А затем с помощью аналога алгоритма Евклида вычислить . Всё это выполняется за полиномиальное количество арифметических операций. Таким образом , обсуждая далее задачу нахождения решений сравне ния (8), мы можем предполагать , что в кольце многочленов спра ведливо равенство 2.2.4 . Алгоритм нахождения делителей многоч лена в коль це 1) Выберем каким-либо способом элемент . 2) Вычислим наибольший общий делитель . 3) Если многочлен окажется собственным делителем , то многочлен распадётся на два множителя и с каждым из них незави симо нужно будет проделать все операции , предписываемые настоящим алгоритмом для многочлена . 4) Если окажется , что или , следует перейти к шагу 1 и . выбрав новое значение , продолжить выполнение алгоритма. Количество операций на шаге 2 оценивается величиной , ес ли вычисления проводить так , как это указывалось выше при нахожде нии . Выясним теперь , сколь долго придётся выбирать числа , пока на шаге 2 не будет найден собственный делитель . Количество решений уравнения в поле не превосходит . Это означает , что подмножество элементов , удовлетворяющих условиям , состоит не менее , чем из элементов . Учитывая теперь , что каждый ненулевой элемент удовлетворяет одному из равенств , либо , заключаем , что для одно из чисел будет корнем многочлена , а другое - нет . Для таких элементов многочлен , определённый на шаге 2 алгоритма , будет собственным делителем многочлена . Итак , существует не менее «удачных» выборов элемента , при которых на шаге 2 алгоритма многочлен распадётся на два соб ственных множителя . Следовательно , при «с лучайном» выборе элемента , вероятность того , что многочлен не разложится на множители после повторений шагов алгоритма 1-4. не превосходит . Вероят ность с ростом убывает очень быстро . И действительно , на практике этот алгоритм работает доста точно эффективно. Заметим , что при опенке вероятности мы использовали только два корня многочлена . При эта вероятность , конечно , еще меньше . Более тонкий анализ с использованием опенок А . Вейля для сумм харак теров показывает , что вероятность для многочлена не распасться на множители при однократном проходе шагов алгоритма 1-4. не пре восходит . Здесь постоянная в зависит от . Если в сравнении (8) заменить простой модуль составным моду лем , то задача нахождения решений соответствующего сравнения ста новится намного более сложной . Известные алгоритмы её решения осно ваны на сведении сравнения к совокупности сравнений (8) по просты м модулям — делителям , и . следовательно , они требуют разложения чи сла то на простые сомножители , что , как уже указывалось , является до статочно трудоемкой з адачей. 3. КАЧЕСТВЕННАЯ ТЕОРИЯ АЛГОРИТМА RSA Существует довольно эффективный способ убедиться , что заданное число является составным , не разлагая это число на множители . Согласно малой теореме Ферма , если число простое , то для любого целого , не делящегося на , выполняется сравнение . (9) Если же при каком-то это сравнение нарушается , можно утверждать , что - составное . Проверка (9) не требует больших вычислений , это следует из алгоритма 1. Вопрос только в том , как найти для составного целое число , не удовлетворяющее (9). Можно , например , пытаться найти необходимое число , испытывая все целые числа подряд , начиная с 2. Или попробовать выбирать эти числа случайным образом на отрезке . К сожалению , такой подход не всегда даёт то , что хотелось бы . Име ются составные числа , обладающие сво йством (9) для любого целого с условием . Такие числа называ ются числами Кармайкла . Рассмотрим , например , число . Так как 560 делится на каждое из чисел 2, 10, 16, то с помощью малой теоремы Ферма легко проверить , что 561 есть число Кармайкла . Можно доказать , что любое из чисел Кармайкла имеет вид , где все простые различны , причем делится на каждую разность . Лишь недавно , была решена проблема о бесконечности множества таких чисел. В 1976 г . Миллер предложил заменить проверку (9) проверкой несколь ко иного условия . Если - простое число , , где нечётно , то согласно ма лой теореме Ферма для каждого с условием хотя бы одна из скобок в произведении делится на . Обращение этого свойства можно использовать , чтобы от личать составные числа от простых. П усть - нечётное составное число , , где нечётно . Назовем целое число , , «хорошим» для , если нарушается одно из двух условий : 1) не делится на ; 2) или существует целое , , такое , что . Из сказанного ранее следует , что для простого числа не существует хороших чисел . Если же составное число , то , как доказал Рабин , их существует не менее . Теперь можно построить вероятностный алгоритм , отличающий со ставные числа от простых. 3.1. Алгоритм , доказывающий непростоту числа 1) Выберем случайным образом число , , и проверим для этого числа указанные выше свойства 1) и 2) п .2. 2) Если хотя бы одно из них нарушается , то число составное. 3) Если выполнены оба условия 1) и 2) п .2, возвращаемся к шагу 1. Из сказанного выше следует , что составное число не будет определено как составное после однократного выполнения шагов 1-3 с вероятностью не большей . А вероятность не определить его после повторений не превосходит . т . е . убывает очень быстро. Миллер предложил детерминированный алгоритм определения состав ных чисел , имеющий сложность , однако справедливость его ре зультата зависит от недоказанной в настоящее время так называемой расширенной гипотезы Римана . Согласно этому алгоритму достаточно проверить условия 1) и 2) п .2 для всех целых чисел , . Если при каком-нибудь из указанного промежутка нарушается одно из условий а ) или б ), число составное . В противном случае оно будет простым или степенью простого числа . Последняя возможность , конечно , легко проверяется. Напомним некоторые понятия , необходимые для формулиров ки расширенной гипотезы Римана . Они понадобятся нам и в дальнейшем . Пусть - целое число . Функция называется характе ром Дирихле по модулю , или просто характером , если эта функция периодична с периодом , отлична от нуля только на числах , взаимно простых с , и мультипликативна , т . е . для любых целых выполня ется равенство . Для каждого существует ровно характеров Дирихле . Они образуют группу по умножению . Единичным элеме нтом этой группы является так называемый главный характер , равный 1 на всех числах , взаимно простых с , и 0 на остальных це лых числах . Порядком характера называется его порядок как элемента мультипликативной группы характеров. С каждым характером может быть связана так называемая - функция Дирихле - функция комплексного переменного , определённая рядом . Сумма этого ряда аналитична в области и может быть аналитически п родолжена на всю комплексную плос кость . Следующее соотношение связывает L - функцию , отвечающую главному характеру , с дзета-функцией Римана . Расширенная гипотеза Римана утверждает , что комплексные нули всех L -функций Дирихле , расположенные в полосе , лежат на прямой . В настоящее время не доказана даже простей шая форма этой гипотезы - классическая гипотеза Римана , у твержда ющая такой же факт о нулях дзета-функции. В 1952 г . Анкени с помощью расширенной гипотезы Римана доказал , что для каждого простого числа существует кв адратичный невычет , удовлетворяющий неравенствам . Константа 70 была со считана позднее . Именно это утверждение и лежит в основе алгоритма Миллера . В 1957 г . Берджесс доказал существование такого невычета без использования расширенной гипотезы Римана, но с худшей оценкой , справедливой при любом положительном и , большем некоторой границы , зависящей от . Алгоритм Миллера п ринципиально отличается от алгоритма 2.1., так как полученное с его помощью утверждение о том , что число - со ставное , опирается на недоказанную расширенную г ипотезу Римана и по тому может быть неверным . В то время как вероятностный алгоритм 2.1. даёт совершенно правильный ответ для составных чисел . Несмотря на отсутствие оценок сложности , на практике он работает вполне удовле творительно. 3.2. Нахождение больш их простых чисел Конечно же , большие простые числа можно строить сравнительно быстро . При этом можно обеспечить их случайное распределение в заданном диапазоне величин . В противном случае теряла бы всякий практический смысл система шифрования RSA . Наиболее эффективным средством построения простых чисел является несколько модифицированная малая теорема Ферма. Теорема 2 . Пусть - нечётные натуральные числа , , причем для каждого простого делителя числа существует целое число такое , что . (10) Тогда каждый простой делитель числа удовлетворяет сравнению . Доказательство . Пусть - простой делитель числа , a - не который делитель . Из условий (10) следует , что в поле вычетов спра ведливы соотношения . (11) Обозначим буквой порядок элемента в мультипликативной группе поля . Первые д ва из соотношений (11) означают , что входит в раз ложение на простые множители числа в степени такой же , как и в раз ложение , а последнее - что делится на . Таким образом , каждый простой делитель числа входит в разложение в степени не меньшей , чем в , так что делится на . Кроме того , четно . Теорема 2 доказана. Следствие . Если выполнены условия теоремы 2 и , то - простое число. Действительно , пусть равняется произведению не менее двух про стых чисел . Каждое из них , согласно утверждению теоремы 2, не меньше , чем . Но тогда . Противоречие и доказывает следствие. Покажем теперь , как с помощью последнего утверждения, имея боль шое простое число , можно построить существенно большее простое число . Выберем для этого случайным образом чётное число на про межутке и положим . Затем проверим число на отсутствие малых простых делителей , разделив его на малые простые числа ; испытаем некоторое количес тво раз с помощью алгоритма 5. Если при этом выяснится , что - составное число , следует выбрать новое значение и опять повторить вычисления . Так следует делать до тех пор , пока не будет найдено число , выдержавшее испы тания алго ритмом 5 достаточно много раз . В этом случае появляется надежда на то , что - простое число , и следует попытаться доказать простоту с помощью тесто в теоремы 2. Для этого можно случайным образом выбирать число , и проверять для него выполнимость соотношений . (12) Если при выбранном эти соотношения вып олняются , то , согласно след ствию из теоремы 2, можно утверждать , что число простое . Если же эти условия нарушаются , нужно выбрать другое значение и повторять эти операции до тех пор , пока такое число не будет обнаружено. Предположим , что построенное число действительно является про стым . Зададимся вопросом , сколь долго придётся перебирать числа , по ка не будет найдено т акое , для которого будут выполнены условия (12). Заметим , что для простого числа первое условие (12), согласно малой теореме Ферма , будет выполняться всегда . Те же числа , для которых на рушается второе условие (12), удовлетворяют сравнению . Как известно , уравнение в поле вычетов имеет не более решений . Одно из них . Поэтому на проме жутке имеется не более чисел , для которых не выполняются у словия (12). Это означа ет , что , выбирая случайным образом числа на промежутке , при простом можно с вероятностью большей , чем , найти чи сло , для которого будут выполнены условия теоремы 2, и тем доказать , что действительно является простым числом. Заметим , что построенное таким способом простое число будет удо влетворять неравенству , т . е . будет записываться вдвое боль шим количеством цифр , чем исходное простое число . Заменив теперь число на найденное простое число и повторив с этим новым все указанные выше действия , можно построить еще большее простое число . Начав с какого-нибудь п ростого числа , скажем , записанного 10 десятич ными цифрами (простоту его можно проверить , например , делением на маленькие табличные простые числа ), и повторив указанную процедуру достаточное число раз . можно построить простые числа нужной величи ны. Обсуди м теперь некоторые теоретические вопросы , возникающие в связи с нахождением числа , удовлетворяющего неравенствам , и такого , что - простое число . Прежде всего , со гласно теореме Дирихле , доказанной еще в 1839 г ., прогрессия , содержит бесконечное количество простых чисел . Нас интересуют простые числа , лежащие недалеко от начала прогрессии . Опенка наименьшего простого числа в арифметической прогресс ии была полу чена в 1944 г . Ю . В . Линником . Соответствующая теорема утверждает , что наименьшее простое число в арифметической прогрессии не превосходит , где - некоторая достаточно большая абсолютная постоянная . Таким образом , в настоящее время никаких теоретических гарантий для существования простого числа не сущес твует . Тем не менее опыт вычислений на ЭВМ показывает , что простые числа в арифметической прогрессии встречаются достаточно близко к её началу . Упомянем в этой связи гипотезу о существовании бесконе чного количества простых чисел с условием , что число также п ростое , т . е . простым является уже первый член прогрессии. Очень важен в связи с описываемым методом построения простых чисел также вопрос о расстоянии между соседними простыми числами в арифметической прогрессии . Ведь убедившись , что при некотором число составное , можно следующее значение взять равным и действовать так далее , пока не будет найдено простое число . И если расстояние между соседними просты ми числами в прогрессии ве лико , нет надежды быстро построить нужное число . Перебор чисел до того момента , как мы наткнемся на простое число окажется слишком долгим . В более простом вопросе о расстоянии между соседни ми простыми числами и в натуральном ряде доказано лишь , что , что , конечно , не очень хорошо для наших целей . Вместе с тем существует так называемая гипотеза Крамера (1936 г .), что , дающая вполне приемлемую опенку . Примерно такой же результат следует и из расширенной гипотезы Римана . Вычисления на ЭВМ показывают , что простые числа в арифметических прогрессиях расположены достаточно плотно. В качестве итога обсуждения в этом пункте подчеркнём следующее : если принять на веру , что наименьшее простое число , а также расстояние между соседними простыми числами в прогрессии при оцениваются величиной , то описанная схема построения больши х простых чисел имеет полиномиальную опенку сложности . Кро ме того , несмотря на отсутствие теоретических опенок времени работы алгоритмов , отыскивающих простые числа в арифметических прогрес сиях со сравнительно большой разностью , на практике эти алгоритм ы работают вполне удовлетворительно . На обычном персональном компью тере без особых затрат времени строятся таким способом простые числа порядка . Конечно , спо соб конструирования простых чисел для использования в схеме RSA должен быть массовым , а сами простые числа должны быть в каком-то смысле хорошо распределёнными . Это вносит ряд дополнитель ных осложнений в работу алгоритмов . Наконец , отметим , что существую т методы построения больших про стых чисел , использующие не только простые делители , но и делите ли чисел . В основе их лежит использование после довательностей целых чисел , удовлетворяющих линейным рекуррентным уравнениям различных порядков . Отметим , что последовательность , члены которой присутствуют в формулировке малой теоремы Ферма , со ставляет решение рекуррентного уравнения первого порядка . 3.3. Проверка большого числа на простоту Есть некоторое отличие в постановках задач предыдущего и настоя щего пунктов . Когда мы строим простое число , мы обладаем некото рой дополнительной информацией о нем , возникающей в процессе постро ения . Например , такой информацией является знание простых делителей числа . Эта информация иногда облегчает доказательство просто ты . В этом пункте мы предполагаем лишь , что нам задано некоторое чи сло , например , выбранное случайным образом на каком-то промежут ке , и требуется установить его простоту , или доказать , что оно является составным . Эту задачу за полиномиальное количество операций решает указанный в п . 3 алгоритм Миллера . Однако , справедливость полученного с его помощью утверждения зависит от недоказанной расширенной гипо тезы Римана . Если число выдержало испытания алгоритмом 5 для 100 различных значений параметра , то , по-видимому , можно утверждать , что оно является простым с вероятностью большей , чем . Эта вероятность очень близка к единице , однако всё же оставляет некоторую тень сомнения на простоте числа . В дальнейшем в этом пункте мы будем считать , что заданное число является простым , а нам требуется лишь доказать это. В настоящее время известны детерминированные алгоритмы различ ной сложности для доказательства простоты чисел . Мы остановимся по дробнее на одном из них , предложенном в 1983 г . в совместной работе Адл емана . Померанца и Рамели . Для доказательства простоты или непростоты числа этот алгоритм требует арифметиче ских операций . Здесь - некоторая положительная абсолютная посто янная . Функция хоть и медленно , но всё же возрастает с росто м , поэтому алгоритм не является полиномиальным . Но всё же его прак тические реализации позволяют достаточно быстро тестировать числа на простоту . Существенны е усовершенствования и упрощения в перво начальный вариант алгоритма были внесены в работах X . Ленстры и А . Коена . Мы будем называть описываемый ниже алгоритм алго ритмом Адлемана - Ленстры. В основе алгоритма лежит использование сравнений типа малой те ор емы Ферма , но в кольцах целых чисел круговых полей , т . е . полей . порождённых над полем числами - корнями из 1. Пусть - простое нечётное число и — первообразный корень по модулю , т . е . образующий элемент мультипликативной группы поля , которая пиклична . Для каждого целого числа , не делящегося на , можно опре делить его индекс , , называемый также дискретным логарифмом , с помощью сравнения . Рассмотрим далее два простых числа , с условием , что делится на , но не делится на . Следующая функция , определённая на множестве целых чисел. является характером по модулю и порядок этого характера равен . Сумма называется суммой Гаусса . Формулируемая ниже теорема 3 представляет собой аналог малой теоремы Ферма , используемый в алгоритме Адлемана - Ленстры. Теорема 3. Пусть - нечетное простое число , . Тогда в кольце выполняется сравнение . Если при каких-либо числах сравнение из теоремы 3 нарушается . можно утверждать , что составное число . В противном случае , если сравнение выполняется , оно даёт некоторую информацию о возможных простых делителях числа . Собрав такую информацию для различных , в конце концов удаётся установить , что имеет лишь один простой делитель и является простым. В случае легко проверить , что сравнение из теоремы 3 равно сильно хорошо известному в элементарной теории чисел сравнению , (13) где - так называемый символ Якоби . Хорошо известно также , что последнее сравнение выполняется не только для простых , но и для любых целых , взаимно простых с . Заметим также , что для вычисления символа Якоби существует быстрый алгоритм , основанный на законе вза имности Гаусса и . в некотором смысле , подобный алгоритму Евклида вы числения наибольшего общего делителя . Следующий пример показывает . каким образом выполнимость нескольких сравнений типа (13) даёт неко торую информацию о возможных простых делителях числа . Пример ( X . Ленстра ). Пусть — натуральное число , . дл я которого выполнены сравнения , (14) а кроме того с некоторым целым числом имеем . (15) Как уже указывалось , при простом сравнения (14) выполняются для любого , взаимно простого с , а сравнение (15) означает , что есть первообразный корень по модулю . Количество первообразных корней равно , т . е . достаточно велико . Таким образом , число с усло вием (15) при простом может быть найдено достаточно быстро с помощью случайного выбора и последующей проверки (15). Докажем , что из выполнимости (14-15) следует , что каждый делитель числа удовлетворяет одному из сравнений или . (16) Не уменьшая общност и , можно считать , что - простое число . Введем теперь обозначения , где и - нечётные числа . Из (15) и сравнения следует , что . Далее , согласно (14). выполняются следующие сравнения , означающие (в силу того , что символ Якоби может равнят ься лишь -1 или +1), что . При это равенство означает , что при , и , следовательно , . Если же , то имеем и . Этим (16) доказано. Информация такого рода получается и в случае произвольных про стых чисел и с указанными выше свойствами. Опишем схему алгоритма Адлемана - Ленстры для про верки простоты : 1) выб ираются различные простые числа и различные про стые нечётные такие , что 1) для каждого все простые делители числа сод ержатся среди и не делятся на квадрат простого числа ; 1) . 2) для каждой пары выбранных чисел , проводятся тесты , подобные сравнению из теоремы 3. Если не удовлетворяет какому-либо из этих тестов - оно составное . В прот ивном случае 3) определяется не очень большое множество чисел , с которыми толь ко и могут быть сравнимы простые делители . А именно , каждый простой делитель числа должен удовлетворять сравнению вида , . 4) проверяется , содержит ли найденное множество делители . Ес ли при этом делители не обнаружены , утверждается , что - простое число. Если число составное , оно обязательно имеет простой де литель , меньший , который сам содержится среди возможных ост атков . Именно на этом свойстве основано применение пункта 4) алгоритма. Сумма Якоби определяется для двух характеров модулю . Если характеры имеют порядок , то соответствующая сумма Якоби принадлежит кольцу . Поскольку числа , участвующие в алгоритме , сравнительно невели ки , то вычисления с суммами Якоби производятся в полях существенно меньшей степени , чем вычисления с суммами Гаусса . Это главная при чина , по которой суммы Якоби предпочтительнее для вычислений . При выполняется классическое соотношение связывающее суммы Гаусса с суммами Якоби и позволяющее переписать сравнение теоремы 3 в термина х сумм Якоби . Так . при и соответствующее сравнение , справедливое для простых , отлич ных от 2,3,7, принимает вид , где и - некоторый корень кубический из 1. В 1984 г . было внесено существенное усовершенствование в алгоритм , позволившее освободиться от требования неделимости чисел на квадраты простых чисел . В результате , например , выбрав число и взяв равным произведению простых чисел с условием , что делится на , получим , что позволяет доказывать простоту чисел , записываемых сотней десятичных знаков . При этом вычисления будут проводиться в полях , порождённых корнями из 1 степеней 16, 9, 5 и 7. Персональный компьютер с процессором Pentium -150. пользуясь реализацией этого алгоритма на языке UBASIC , доказал простоту записываемого 65 десятичными знаками , большего из простых чисел в при мере Ривеста , Шамира и Адлемана за 8 с екунд . Сравнение этих 8 секунд и 17 лет , потребовавшихся для разложения на множители предложенного в примере числа , конечно , впечатляет. Отметим , что опенка сложности этого алгоритма представляет со бой трудную задачу аналитической теории чисел . Как уже ук азывалось , количество операций оценивается величиной . Однако соот ветствующие числа и , возникающие в процессе доказательства , не могут быть явно указаны в зависимости от . Доказано лишь существо вание чисел и , для которых достигается оценка . Впрочем , есть веро ятностный вариант алгоритма , доказывающий простоту простого числа с вероятнос тью большей за арифметических операций . А в предположении расширенной гипотезы Римана эта опенка сложности может быть получена при эффективно указанных и . 4. ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ АЛГОРИТМА Представленный выше алгоритм шифрования был реализован с помощью интегрированного пакета фирмы Borland Delphi 5.0. Выбор данного языка программирования обоснован тем что , он предо ставляет такие возможности , как объектно-ориентированный подход к программированию , основанный на формах , интеграция с программированием для Windows и компонентная технология . Среду визуального программирования Delphi 5 позволяет с помощью компонентного по дхода к созданию приложений , быстро и качественно "собрать " интерфейс программы и большую часть времени использовать именно на реализацию составленного алгоритма. Программа построена по технологии клиент /сервер , т.е . клиент передает по сети данные из стан дартного потока ввода (с клавиатуры ), предварительно зашифровав , сервер , получая поток данных , автоматически его расшифровывает. Программный продукт состоит из двух приложений . Первое приложение представляет собой программу генерации ключей . Она выводит в се простые числа заданного диапазона , из которых потом выбираются числа и . Там же находятся открытый и закрытый ключи , которые сохраняются на диске . Второе приложение , основная программа , производит соединение между двумя компьютерами и , отправляя сообщение , шифрует его . Это приложение клиент . Приложение сервер получает сообщение и расшифровывает его . Так же во второй программе содержится небольшая база данных абонентов , хранящая в себе имена абонентов , IP адреса и их открытые ключи. 4.1. Реализованные алгоритмы В программн ом продукте были реализованы основные алгоритмы схемы RSA . Функция ModDegree производит вычисление . Функция Prost находит все простые числа заданного диапазон а . Функция Evklid реализует алгоритм Евклида и находит закрытый ключ . Функция HOD производит вычисление наибольшего общего делителя и находит открытый ключ . Вышеперечисленные функции представлены в приложении 1. 4.2. Анализ результатов Результатом работы созданной программы являются зашифрованные и расшифрованны е сообщения . Для тестирования программы использовался пример приведенный в [11] , , и . Также и . 5. ВЫВОДЫ Перейдем к обсуждению выводов после д етального просмотра специфики метода , реализованного программного продукта на основе построенного алгоритма , а также представленного анализа результатов по обработанному материалу. 5.1 Алгоритм Использованный алгоритм RSA имеет ряд преимуществ : 1) алгоритм RSA является ассиметричным , т.е . он основывается на распространении открытых ключей в сети . Это позволяет нескольким пользователям обмениваться информацией , посылаемой по незащищенным каналам связи ; 2) пользователь сам может менять как числа , , так и открытый и закрытый ключ по своему усмотрению , только потом он должен распространить открытый ключ в сети . Это позволяет добиваться пользователю нужной ему криптостойкости. При всех этих преимуществах данный алгоритм имеет существенный недостаток – невысокая скорость работы . Алгоритм RSA работает более чем в тысячу р аз медленнее симметричного алгоритма DES . Из всего вышесказанного можно заключить , что данный алгоритм шифрования , хотя довольно медленный , но он ассиметричный и позволяет добиваться нужной криптостойкости , что делает его незаменимым при работе в незащищен ных каналах связи . 5.2 Алгоритм и программа Исходя из проработанных данных , по построенному алгоритму и созданному программному продукту сделаны следующие выводы : 1) построенный алгоритм , а соответственно и созданный на его базе программный продукт , полн остью реализует базовые механизмы схемы RSA и , таким образом удовлетворяют основным поставленным задачам ; 2) данный программный продукт построен по технологии клиент /сервер и предназначен сохранять конфиденциальность передачи информации в сети. Таким образ ом , по выводам о построенном алгоритме и созданном программном продукте можно заключить , что он подходит для решения проблем шифрования информации , связанных с передачей данных по сети. ЗАКЛЮЧЕНИЕ В рамках данного дипломного проектирования перед студентом Малышевым А.А . была поставлена задача : на основе алгоритма RSA для шифрования блоков данных , построить алгоритм и реализовать программный продукт для шифрования потоков данных. В результате выполнения дипломного проектирования был составлен принципиальный алгоритм для решения поставленной задачи . Далее он был детализован и реализован на ЭВМ . В конце , был проведён анализ полученных результатов , и сделаны необходимые выводы. За основу построения алгоритма был принят алгоритм RSA для шифрования блоков данных, изучена соответствующая литература по алгоритму , и был построен алгоритм и реализован программный продукт в среде визуального программирования Delphi 5 под ОС типа Windows для IBM PC -совместимых компьютеров . Созданный программный продукт позволяет решить поставленную задачу и , дополнительно , содержит в себе небольшую базу данных абонентов . Т.е . в результате выполнения программы исходное сообщение шифруется и передается по сети , где оно расшифровывается . Также можно указать о том , что программа имеет инту и тивно понятный интерфейс , что дополнительно помогает пользователю с наибольшей результативностью использовать всю ресурсную базу. В заключении , после анализа полученных результатов были сделаны выводы , согласно которым алгоритм работает и применим для пост авленной задачи . СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 1. Ященко В . В . Основные понятия криптографии // Математическое просвещение . Сер . 3. № 2. 1998. С . 53-70. 2. Виноградов И . М . Основы теории чисел . М .: Наука . 1972. 3. Карацуба А . А . Основы аналитической т еории чисел . М .: Наука . 1983 г. 4. Кнут Д . Искусство программирования на ЭВМ . Т .2: Получисленные алгоритмы . М .: Мир . 1977. 5. Ахо А .. Хопкрофт Дж .. Ульман Дж . Построение и анализ вычисли тельных алгоритмов . М .: Мир . 1979. 6. Варновский Н . П . Криптография и теория сложности // Математи ческое просвещение . Сер . 3. № 2. 1998. С . 71-86. 7. Василенко О . Н . Современные способы проверки простоты чисел // Кибернетический сборник , вып . 25. 1988. С . 162-188. 8. Прахар К . Распределение простых чисел . М .: Мир . 1967. 9.Б оревич З.И . Шафаревич И.Р . Теория чисел . М .: Наука . 1964. 10. Кострикин А.И . Введение в алгебру . М .: Наука . 1977. 11. Брассар Дж . Современная криптология . Мир ПК . № 3. 1997. ПРИЛОЖЕНИЕ 1 Листинг программы Модуль Key . pas Function Prost(n:integer):Boolean; var k:Boolean; i:integer; begin k:=true; if n<>2 then for i:=2 to trunc(sqrt(n))+1 do if (n/i)=trunc(n/i) then begin k:=False; Break; end; Prost:=k; end; ________________________________________________________ Function Evklid( Num1,Num2:integer):integer; var r,q1,p1:array of integer; i,n,k:integer; begin if Num1>=Num2 then begin SetLength(r,10); r[0]:=Num1; r[1]:=Num2; end else begin SetLength(r,10); r[0]:=Num2; r[1]:=Num1; end; i:=1; while r[i]<>0 do begin inc(i); r[i]:=r[i-2] mod r[i-1]; end; n:=i-2; SetLength(q1,n+1); for i:=0 to n do q1[i]:=r[i] div r[i+1]; SetLength(p1,n+2); p1[0]:=1; p1[1]:=q1[0]; k:=length(q1); if k>1 then for i:=2 to k do p1[i]:=q1[i-1]*p1[i-1]+p1[i-2]; R esult:=trunc(power(-1,k-1))*p1[k-1] mod Num2; end; ________________________________________________________ Function HOD(Num1,Num2:integer):integer; var r:array of integer; i:integer; begin if Num1>=Num2 then begin SetLength(r,Num2); r[0]:=Nu m1; r[1]:=Num2; end else begin SetLength(r,Num1); r[0]:=Num2; r[1]:=Num1; end; i:=1; While r[i]<>0 do begin inc(i); r[i]:=r[i-2] mod r[i-1]; end; Result:=r[i-1]; end; ________________________________________________________ Function ModDegree(Num,Degree,n:integer):integer; var x:array of integer; i:integer; begin SetLength(x,n); x[1]:=Num mod n; for i:=2 to Degree do x[i]:=x[i-1]*Num mod n; Result:=x[Degree]; end; ПРИЛОЖЕНИЕ 2 Главная форма программы ПРИЛОЖЕНИЕ 3 Форма базы данных абонентов ПРИЛОЖЕНИЕ 4 Форма нахождения простых чисел и генерации ключей
1Архитектура и строительство
2Астрономия, авиация, космонавтика
 
3Безопасность жизнедеятельности
4Биология
 
5Военная кафедра, гражданская оборона
 
6География, экономическая география
7Геология и геодезия
8Государственное регулирование и налоги
 
9Естествознание
 
10Журналистика
 
11Законодательство и право
12Адвокатура
13Административное право
14Арбитражное процессуальное право
15Банковское право
16Государство и право
17Гражданское право и процесс
18Жилищное право
19Законодательство зарубежных стран
20Земельное право
21Конституционное право
22Конституционное право зарубежных стран
23Международное право
24Муниципальное право
25Налоговое право
26Римское право
27Семейное право
28Таможенное право
29Трудовое право
30Уголовное право и процесс
31Финансовое право
32Хозяйственное право
33Экологическое право
34Юриспруденция
 
35Иностранные языки
36Информатика, информационные технологии
37Базы данных
38Компьютерные сети
39Программирование
40Искусство и культура
41Краеведение
42Культурология
43Музыка
44История
45Биографии
46Историческая личность
47Литература
 
48Маркетинг и реклама
49Математика
50Медицина и здоровье
51Менеджмент
52Антикризисное управление
53Делопроизводство и документооборот
54Логистика
 
55Педагогика
56Политология
57Правоохранительные органы
58Криминалистика и криминология
59Прочее
60Психология
61Юридическая психология
 
62Радиоэлектроника
63Религия
 
64Сельское хозяйство и землепользование
65Социология
66Страхование
 
67Технологии
68Материаловедение
69Машиностроение
70Металлургия
71Транспорт
72Туризм
 
73Физика
74Физкультура и спорт
75Философия
 
76Химия
 
77Экология, охрана природы
78Экономика и финансы
79Анализ хозяйственной деятельности
80Банковское дело и кредитование
81Биржевое дело
82Бухгалтерский учет и аудит
83История экономических учений
84Международные отношения
85Предпринимательство, бизнес, микроэкономика
86Финансы
87Ценные бумаги и фондовый рынок
88Экономика предприятия
89Экономико-математическое моделирование
90Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
Умирает Путин, попадает в рай, и там захотелось ему увидеть Ельцина. Он подходит к апостолу Петру и спрашивает, где можно увидеть своего предшественника. Тот, покачав головой, отвечает, что Ельцина в раю никто не видел и советует поискать его в чистилище, но и там Путин его не находит. Тогда, решив, что Ельцин в аду, Путин спускается туда, находит там Сатану и спрашивает у него:
- Простите, Ельцин, случайно, не у вас?
- Нет, здесь его никогда не было. А ты не искал еще ниже?
- Еще ниже?! Простите, но после рая, чистилища и ада что может быть еще ниже?
- Как что? Бар!
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

Обратите внимание, диплом по математике "Применение алгоритма RSA для шифрования потоков данных", также как и все другие рефераты, курсовые, дипломные и другие работы вы можете скачать бесплатно.

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2016
Рейтинг@Mail.ru