Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10 | Следующая страница реферата

4) проверяется, содержит ли найденное множество делители [pic]. Если при этом делители не обнаружены, утверждается, что [pic] - простое

число.

Если число [pic] составное, оно обязательно имеет простой делитель
[pic], меньший [pic], который сам содержится среди возможных остатков.
Именно на этом свойстве основано применение пункта 4) алгоритма.

Сумма Якоби

[pic] определяется для двух характеров [pic] модулю [pic]. Если характеры имеют порядок [pic], то соответствующая сумма Якоби принадлежит кольцу [pic].
Поскольку числа [pic], участвующие в алгоритме, сравнительно невелики, то вычисления с суммами Якоби производятся в полях существенно меньшей степени, чем вычисления с суммами Гаусса. Это главная причина, по которой суммы Якоби предпочтительнее для вычислений. При [pic] выполняется классическое соотношение

[pic] связывающее суммы Гаусса с суммами Якоби и позволяющее переписать сравнение теоремы 3 в терминах сумм Якоби. Так. при [pic] и [pic] соответствующее сравнение, справедливое для простых [pic], отличных от 2,3,7, принимает вид

[pic], где [pic] и [pic] - некоторый корень кубический из 1.

В 1984 г. было внесено существенное усовершенствование в алгоритм, позволившее освободиться от требования неделимости чисел [pic] на квадраты простых чисел. В результате, например, выбрав число [pic] и взяв [pic] равным произведению простых чисел [pic] с условием, что [pic] делится на
[pic], получим [pic], что позволяет доказывать простоту чисел [pic], записываемых сотней десятичных знаков. При этом вычисления будут проводиться в полях, порождённых корнями из 1 степеней 16, 9, 5 и 7.

Персональный компьютер с процессором Pentium-150. пользуясь реализацией этого алгоритма на языке UBASIC, доказал простоту записываемого
65 десятичными знаками, большего из простых чисел в примере Ривеста, Шамира и Адлемана за 8 секунд. Сравнение этих 8 секунд и 17 лет, потребовавшихся для разложения на множители предложенного в примере числа, конечно, впечатляет.

Отметим, что опенка сложности этого алгоритма представляет собой трудную задачу аналитической теории чисел. Как уже указывалось, количество операций оценивается величиной [pic]. Однако соответствующие числа [pic] и
[pic], возникающие в процессе доказательства, не могут быть явно указаны в зависимости от [pic]. Доказано лишь существование чисел [pic] и [pic], для которых достигается оценка. Впрочем, есть вероятностный вариант алгоритма, доказывающий простоту простого числа [pic] с вероятностью большей [pic] за
[pic] арифметических операций. А в предположении расширенной гипотезы
Римана эта опенка сложности может быть получена при эффективно указанных
[pic] и[pic].

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

Представленный выше алгоритм шифрования был реализован с помощью интегрированного пакета фирмы Borland Delphi 5.0. Выбор данного языка программирования обоснован тем что, он предоставляет такие возможности, как объектно-ориентированный подход к программированию, основанный на формах, интеграция с программированием для Windows и компонентная технология. Среду визуального программирования Delphi 5 позволяет с помощью компонентного подхода к созданию приложений, быстро и качественно "собрать" интерфейс программы и большую часть времени использовать именно на реализацию составленного алгоритма.

Программа построена по технологии клиент/сервер, т.е. клиент передает по сети данные из стандартного потока ввода (с клавиатуры), предварительно зашифровав, сервер, получая поток данных, автоматически его расшифровывает.

Программный продукт состоит из двух приложений. Первое приложение представляет собой программу генерации ключей. Она выводит все простые числа заданного диапазона, из которых потом выбираются числа [pic] и [pic].
Там же находятся открытый и закрытый ключи, которые сохраняются на диске.
Второе приложение, основная программа, производит соединение между двумя компьютерами и, отправляя сообщение, шифрует его. Это приложение клиент.
Приложение сервер получает сообщение и расшифровывает его. Так же во второй программе содержится небольшая база данных абонентов, хранящая в себе имена абонентов, IP адреса и их открытые ключи.

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

В программном продукте были реализованы основные алгоритмы схемы
RSA. Функция ModDegree производит вычисление [pic]. Функция Prost находит все простые числа заданного диапазона. Функция Evklid реализует алгоритм
Евклида и находит закрытый ключ [pic]. Функция HOD производит вычисление наибольшего общего делителя и находит открытый ключ [pic].
Вышеперечисленные функции представлены в приложении 1.

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

Результатом работы созданной программы являются зашифрованные и расшифрованные сообщения.

Для тестирования программы использовался пример приведенный в [11]
[pic], [pic], [pic] и [pic]. Также [pic] и [pic].

5. ВЫВОДЫ

Перейдем к обсуждению выводов после детального просмотра специфики метода, реализованного программного продукта на основе построенного алгоритма, а также представленного анализа результатов по обработанному материалу.

5.1 Алгоритм

Использованный алгоритм RSA имеет ряд преимуществ:

1) алгоритм RSA является ассиметричным, т.е. он основывается на распространении открытых ключей в сети. Это позволяет нескольким пользователям обмениваться информацией, посылаемой по незащищенным каналам связи;

2) пользователь сам может менять как числа [pic], [pic], так и открытый и закрытый ключ по своему усмотрению, только потом он должен распространить открытый ключ в сети. Это позволяет добиваться пользователю нужной ему криптостойкости.

Рекомендуем скачать другие рефераты по теме: оценка реферата, диплом на тему.





Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10 | Следующая страница реферата