Характеристика системы шифрования RSA. Установление больших простых чисел. Исследование алгоритма нахождения делителей многочлена в кольце. Проверка большого числа на простоту. Особенность использования среды визуального программирования Delphi 5.
Аннотация к работе
На начальном этапе для защиты информации использовались методы кодирования и стеганографии, которые родственны, но не тождественны криптографии. Другой шифр, полибианский квадрат, авторство которого приписывается греческому писателю Полибию, является общей моноалфавитной подстановкой, которая проводится с помощью случайно заполненной алфавитом квадратной таблицейдля греческого алфавита размер составляет 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 десятичными цифрами (простоту его можно проверить, например, делением на маленькие табличные простые числа), и повторив указанную процедуру достаточное число раз. можно построить простые числа нужной величины.В этом пункте мы предполагаем лишь, что нам задано нек