реферат, рефераты скачать
 

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


для него выполнимость соотношений

[pic].

(12)

Если при выбранном [pic] эти соотношения выполняются, то, согласно

следствию из теоремы 2, можно утверждать, что число [pic] простое. Если же

эти условия нарушаются, нужно выбрать другое значение [pic] и повторять эти

операции до тех пор, пока такое число не будет обнаружено.

Предположим, что построенное число [pic] действительно является

простым. Зададимся вопросом, сколь долго придётся перебирать числа [pic],

пока не будет найдено такое, для которого будут выполнены условия (12).

Заметим, что для простого числа [pic] первое условие (12), согласно малой

теореме Ферма, будет выполняться всегда. Те же числа [pic], для которых

нарушается второе условие (12), удовлетворяют сравнению [pic]. Как

известно, уравнение [pic] в поле вычетов [pic] имеет не более [pic]

решений. Одно из них [pic]. Поэтому на промежутке [pic] имеется не более

[pic] чисел, для которых не выполняются условия (12). Это означает, что,

выбирая случайным образом числа [pic] на промежутке [pic], при простом

[pic] можно с вероятностью большей, чем [pic], найти число [pic], для

которого будут выполнены условия теоремы 2, и тем доказать, что [pic]

действительно является простым числом.

Заметим, что построенное таким способом простое число [pic] будет

удовлетворять неравенству [pic], т. е. будет записываться вдвое большим

количеством цифр, чем исходное простое число [pic]. Заменив теперь число

[pic] на найденное простое число [pic] и повторив с этим новым [pic] все

указанные выше действия, можно построить еще большее простое число. Начав с

какого-нибудь простого числа, скажем, записанного 10 десятичными цифрами

(простоту его можно проверить, например, делением на маленькие табличные

простые числа), и повторив указанную процедуру достаточное число раз. можно

построить простые числа нужной величины.

Обсудим теперь некоторые теоретические вопросы, возникающие в связи с

нахождением числа [pic], удовлетворяющего неравенствам [pic], и такого, что

[pic] - простое число. Прежде всего, согласно теореме Дирихле, доказанной

еще в 1839 г., прогрессия [pic], [pic] содержит бесконечное количество

простых чисел. Нас интересуют простые числа, лежащие недалеко от начала

прогрессии. Опенка наименьшего простого числа в арифметической прогрессии

была получена в 1944 г. Ю. В. Линником. Соответствующая теорема утверждает,

что наименьшее простое число в арифметической прогрессии [pic] не

превосходит [pic], где [pic] - некоторая достаточно большая абсолютная

постоянная.

Таким образом, в настоящее время никаких теоретических гарантий для

существования простого числа [pic] не существует. Тем не менее опыт

вычислений на ЭВМ показывает, что простые числа в арифметической прогрессии

встречаются достаточно близко к её началу. Упомянем в этой связи гипотезу о

существовании бесконечного количества простых чисел [pic] с условием, что

число [pic] также простое, т. е. простым является уже первый член

прогрессии.

Очень важен в связи с описываемым методом построения простых чисел

также вопрос о расстоянии между соседними простыми числами в арифметической

прогрессии. Ведь убедившись, что при некотором [pic] число [pic] составное,

можно следующее значение [pic] взять равным [pic] и действовать так далее,

пока не будет найдено простое число [pic]. И если расстояние между

соседними простыми числами в прогрессии велико, нет надежды быстро

построить нужное число [pic]. Перебор чисел [pic] до того момента, как мы

наткнемся на простое число [pic] окажется слишком долгим. В более простом

вопросе о расстоянии между соседними простыми числами [pic] и [pic] в

натуральном ряде доказано лишь, что [pic], что, конечно, не очень хорошо

для наших целей. Вместе с тем существует так называемая гипотеза Крамера

(1936 г.), что [pic], дающая вполне приемлемую опенку. Примерно такой же

результат следует и из расширенной гипотезы Римана. Вычисления на ЭВМ

показывают, что простые числа в арифметических прогрессиях расположены

достаточно плотно.

В качестве итога обсуждения в этом пункте подчеркнём следующее: если

принять на веру, что наименьшее простое число, а также расстояние между

соседними простыми числами в прогрессии [pic] при [pic] оцениваются

величиной [pic], то описанная схема построения больших простых чисел имеет

полиномиальную опенку сложности. Кроме того, несмотря на отсутствие

теоретических опенок времени работы алгоритмов, отыскивающих простые числа

в арифметических прогрессиях со сравнительно большой разностью, на практике

эти алгоритмы работают вполне удовлетворительно. На обычном персональном

компьютере без особых затрат времени строятся таким способом простые числа

порядка [pic].

Конечно, способ конструирования простых чисел для использования в

схеме RSA должен быть массовым, а сами простые числа должны быть в каком-то

смысле хорошо распределёнными. Это вносит ряд дополнительных осложнений в

работу алгоритмов.

Наконец, отметим, что существуют методы построения больших простых

чисел, использующие не только простые делители [pic], но и делители чисел

[pic]. В основе их лежит использование последовательностей целых чисел,

удовлетворяющих линейным рекуррентным уравнениям различных порядков.

Отметим, что последовательность [pic], члены которой присутствуют в

формулировке малой теоремы Ферма, составляет решение рекуррентного

уравнения первого порядка [pic].

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

Есть некоторое отличие в постановках задач предыдущего и настоящего

пунктов. Когда мы строим простое число [pic], мы обладаем некоторой

дополнительной информацией о нем, возникающей в процессе построения.

Например, такой информацией является знание простых делителей числа [pic].

Эта информация иногда облегчает доказательство простоты [pic].

В этом пункте мы предполагаем лишь, что нам задано некоторое число

[pic], например, выбранное случайным образом на каком-то промежутке, и

требуется установить его простоту, или доказать, что оно является

составным. Эту задачу за полиномиальное количество операций решает

указанный в п. 3 алгоритм Миллера. Однако, справедливость полученного с его

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

Если число [pic] выдержало испытания алгоритмом 5 для 100 различных

значений параметра [pic], то, по-видимому, можно утверждать, что оно

является простым с вероятностью большей, чем [pic]. Эта вероятность очень

близка к единице, однако всё же оставляет некоторую тень сомнения на

простоте числа [pic]. В дальнейшем в этом пункте мы будем считать, что

заданное число [pic] является простым, а нам требуется лишь доказать это.

В настоящее время известны детерминированные алгоритмы различной

сложности для доказательства простоты чисел. Мы остановимся подробнее на

одном из них, предложенном в 1983 г. в совместной работе Адлемана.

Померанца и Рамели. Для доказательства простоты или непростоты числа [pic]

этот алгоритм требует [pic] арифметических операций. Здесь [pic] -

некоторая положительная абсолютная постоянная. Функция [pic] хоть и

медленно, но всё же возрастает с ростом [pic], поэтому алгоритм не является

полиномиальным. Но всё же его практические реализации позволяют достаточно

быстро тестировать числа на простоту. Существенные усовершенствования и

упрощения в первоначальный вариант алгоритма были внесены в работах X.

Ленстры и А. Коена. Мы будем называть описываемый ниже алгоритм алгоритмом

Адлемана - Ленстры.

В основе алгоритма лежит использование сравнений типа малой теоремы

Ферма, но в кольцах целых чисел круговых полей, т. е. полей. порождённых

над полем [pic] числами [pic] - корнями из 1. Пусть [pic] - простое

нечётное число и [pic] — первообразный корень по модулю [pic], т. е.

образующий элемент мультипликативной группы поля [pic], которая пиклична.

Для каждого целого числа [pic], не делящегося на [pic], можно определить

его индекс, [pic], называемый также дискретным логарифмом, с помощью

сравнения [pic]. Рассмотрим далее два простых числа [pic], [pic] с

условием, что [pic] делится на [pic], но не делится на [pic].

Следующая функция, определённая на множестве целых чисел.

[pic]

является характером по модулю [pic] и порядок этого характера равен [pic].

Сумма

[pic]

называется суммой Гаусса. Формулируемая ниже теорема 3 представляет собой

аналог малой теоремы Ферма, используемый в алгоритме Адлемана - Ленстры.

Теорема 3. Пусть [pic] - нечетное простое число, [pic]. Тогда в

кольце [pic] выполняется сравнение

[pic].

Если при каких-либо числах [pic] сравнение из теоремы 3 нарушается. можно

утверждать, что [pic] составное число. В противном случае, если сравнение

выполняется, оно даёт некоторую информацию о возможных простых делителях

числа [pic]. Собрав такую информацию для различных [pic], в конце концов

удаётся установить, что [pic] имеет лишь один простой делитель и является

простым.

В случае [pic] легко проверить, что сравнение из теоремы 3

равносильно хорошо известному в элементарной теории чисел сравнению

[pic], (13)

где [pic] - так называемый символ Якоби. Хорошо известно также, что

последнее сравнение выполняется не только для простых [pic], но и для любых

целых [pic], взаимно простых с [pic]. Заметим также, что для вычисления

символа Якоби существует быстрый алгоритм, основанный на законе взаимности

Гаусса и. в некотором смысле, подобный алгоритму Евклида вычисления

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

выполнимость нескольких сравнений типа (13) даёт некоторую информацию о

возможных простых делителях числа [pic].

Пример (X. Ленстра). Пусть [pic] — натуральное число, [pic]. для

которого выполнены сравнения

[pic], (14)

а кроме того с некоторым целым числом [pic] имеем

[pic].

(15)

Как уже указывалось, при простом [pic] сравнения (14) выполняются для

любого [pic], взаимно простого с [pic], а сравнение (15) означает, что

[pic] есть первообразный корень по модулю [pic]. Количество первообразных

корней равно [pic], т. е. достаточно велико. Таким образом, число [pic] с

условием (15) при простом [pic] может быть найдено достаточно быстро с

помощью случайного выбора и последующей проверки (15).

Докажем, что из выполнимости (14-15) следует, что каждый делитель

[pic] числа [pic] удовлетворяет одному из сравнений

[pic] или [pic].

(16)

Не уменьшая общности, можно считать, что [pic] - простое число. Введем

теперь обозначения [pic], где [pic] и [pic] - нечётные числа. Из (15) и

сравнения [pic] следует, что [pic]. Далее, согласно (14). выполняются

следующие сравнения

[pic],

означающие (в силу того, что символ Якоби может равняться лишь -1 или +1),

что

[pic].

При [pic] это равенство означает, что [pic] при [pic], и, следовательно,

[pic]. Если же [pic], то имеем [pic] и [pic]. Этим (16) доказано.

Информация такого рода получается и в случае произвольных простых

чисел [pic] и [pic] с указанными выше свойствами.

Опишем схему алгоритма Адлемана - Ленстры для проверки простоты

[pic]:

1) выбираются различные простые числа [pic] и различные простые

нечётные [pic] такие, что

1) для каждого [pic] все простые делители числа [pic] содержатся

среди [pic] и [pic] не делятся на квадрат простого числа;

1) [pic].

2) для каждой пары выбранных чисел [pic], [pic] проводятся тесты, подобные

сравнению из теоремы 3. Если [pic] не удовлетворяет какому-либо из

этих тестов - оно составное. В противном случае

3) определяется не очень большое множество чисел, с которыми только и могут

быть сравнимы простые делители [pic]. А именно, каждый простой делитель

[pic] числа [pic] должен удовлетворять сравнению вида

[pic], [pic].

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], так и

открытый и закрытый ключ по своему усмотрению, только потом он должен

распространить открытый ключ в сети. Это позволяет добиваться пользователю

нужной ему криптостойкости.

При всех этих преимуществах данный алгоритм имеет существенный

недостаток – невысокая скорость работы. Алгоритм 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];

Result:=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]:=Num1;

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

Главная форма программы

[pic]

ПРИЛОЖЕНИЕ 3

Форма базы данных абонентов

[pic]

ПРИЛОЖЕНИЕ 4

Форма нахождения простых чисел и генерации ключей

[pic]

Страницы: 1, 2, 3


ИНТЕРЕСНОЕ



© 2009 Все права защищены.