Исследование современных методов шифрования - Курсовая работа

На начальном этапе для защиты информации использовались методы кодирования и стеганографии, которые родственны, но не тождественны криптографии. Другой шифр, полибианский квадрат, авторство которого приписывается греческому писателю Полибию, является общей моноалфавитной подстановкой, которая проводится с помощью случайно заполненной алфавитом квадратной таблицейдля греческого алфавита размер составляет 5x5). Данный шифр, получивший имя дипломата XVI века Блеза Вижинера, состоял в последовательном «сложении» букв исходного текста с ключом (процедуру можно облегчить с помощью специальной таблицы). Его работа «Трактат о шифре» (1466) считается первой научной работой по криптологии. Ему принадлежат два небольших, но важных открытия: способ заполнения полибианского квадрата (первые позиции заполняются с помощью легко запоминаемого ключевого слова, остальные - оставшимися буквами алфавита) и шифрование пар букв (биграмм).К сожалению, в сетевых операционных системах (Windows NT/XP, Novell и т.д.) иностранного производства, как следствие, изза экспортных соображений уровень алгоритмов шифрования заметно снижен.Труды Евклида и Диофанта, Ферма и Эйлера, Гаусса, Чебышева и Эрмита содержат остроумные и весьма эффективные алгоритмы решения диофантовых уравнений, выяснения разрешимости сравнений, построения больших по тем временам простых чисел, нахождения наилучших приближений и т.д. В последние два десятилетия, благодаря в первую очередь запросам криптографии и широкому распространению ЭВМ, исследования по алгоритмическим вопросам теории чисел переживают период бурного и весьма плодотворного развития. Шифрование и дешифрование текстов можно представлять себе как процессы переработки целых чисел при помощи ЭВМ, а способы, которыми выполняются эти операции, как некоторые функции, определенные на множестве целых чисел. Мы будем считать в дальнейшем, что все шифруемые целые числа неотрицательны и по величине меньше некоторого заданного (скажем, техническими ограничениями) числа m. Шифрующая функция при этом может рассматриваться как взаимнооднозначное отображение колец вычетов а число представляет собой сообщение в зашифрованном виде.Классическая теорема Эйлера, утверждает, что для каждого числа , взаимно простого с , выполняется сравнение и, следовательно. Если дополнительно предположить, что число состоит из различных простых сомножителей, то сравнение (5) будет выполняться и без предположения . Казалось бы. ничего не стоит. зная число . разложить его на простые сомножители, вычислить затем с помощью известных правил значение и, наконец, с помощью (3) определить нужное число . Затем выбирается число , удовлетворяющее условиям (7), вычисляется с помощью (6) число и с помощью (3) - число . Числа и публикуются, число остается секретным.Существует довольно эффективный способ убедиться, что заданное число является составным, не разлагая это число на множители. Согласно малой теореме Ферма, если число простое, то для любого целого , не делящегося на , выполняется сравнение Или попробовать выбирать эти числа случайным образом на отрезке . Такие числа называются числами Кармайкла. Так как 560 делится на каждое из чисел 2, 10, 16, то с помощью малой теоремы Ферма легко проверить, что 561 есть число Кармайкла.Выберем случайным образом число , , и проверим для этого числа указанные выше свойства 1) и 2) п.2. Из сказанного выше следует, что составное число не будет определено как составное после однократного выполнения шагов 1-3 с вероятностью не большей . Миллер предложил детерминированный алгоритм определения составных чисел, имеющий сложность , однако справедливость его результата зависит от недоказанной в настоящее время так называемой расширенной гипотезы Римана. Согласно этому алгоритму достаточно проверить условия 1) и 2) п.2 для всех целых чисел , . Функция называется характером Дирихле по модулю , или просто характером, если эта функция периодична с периодом , отлична от нуля только на числах, взаимно простых с , и мультипликативна, т. е. для любых целых выполняется равенство .Затем проверим число на отсутствие малых простых делителей, разделив его на малые простые числа; испытаем некоторое количество раз с помощью алгоритма 5. В этом случае появляется надежда на то, что - простое число, и следует попытаться доказать простоту с помощью тестов теоремы 2. Если при выбранном эти соотношения выполняются, то, согласно следствию из теоремы 2, можно утверждать, что число простое. Это означает, что, выбирая случайным образом числа на промежутке , при простом можно с вероятностью большей, чем , найти число , для которого будут выполнены условия теоремы 2, и тем доказать, что действительно является простым числом. Начав с какого-нибудь простого числа, скажем, записанного 10 десятичными цифрами (простоту его можно проверить, например, делением на маленькие табличные простые числа), и повторив указанную процедуру достаточное число раз. можно построить простые числа нужной величины.В этом пункте мы предполагаем лишь, что нам задано нек

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

1. ПОСТАНОВКА ЗАДАЧИ

2. АЛГОРИТМ RSA

2.1 Система шифрования RSA

3. КАЧЕСТВЕННАЯ ТЕОРИЯ АЛГОРИТМА RSA

3.1 Алгоритм, доказывающий непростоту числа

3.2 Нахождение больших простых чисел

3.3 Проверка большого числа на простоту

4. ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ АЛГОРИТМА

4.1 Реализованные алгоритмы

4.2. Анализ результатов

5. ВЫВОДЫ

5.1 Алгоритм

5.2 Алгоритм и программа

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

ПРИЛОЖЕНИЕ