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

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


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

СОДЕРЖАНИЕ

|Введение |5 |

| |10 |

|1.Постановка задачи | |

|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, RC6 и др.), а в 2000 году после

открытого международного конкурса был принят новый национальный стандарт

шифрования США - AES.

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

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

Современные компьютерные сети не исключение. К сожалению, в сетевых

операционных системах (Windows NT/XP, Novell и т.д.) иностранного

производства, как следствие, из-за экспортных соображений уровень

алгоритмов шифрования заметно снижен.

Задача: исследовать современные методы шифрования и их приложимость к

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

шифрования и программный продукт, демонстрирующий работу этих алгоритмов

при передаче данных в сети.

2. АЛГОРИТМ RSA

Труды Евклида и Диофанта, Ферма и Эйлера, Гаусса, Чебышева и Эрмита

содержат остроумные и весьма эффективные алгоритмы решения диофантовых

уравнений, выяснения разрешимости сравнений, построения больших по тем

временам простых чисел, нахождения наилучших приближений и т.д. В последние

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

широкому распространению ЭВМ, исследования по алгоритмическим вопросам

теории чисел переживают период бурного и весьма плодотворного развития.

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

практически во все сферы человеческой деятельности. Немыслима без них и

современная криптография. Шифрование и дешифрование текстов можно

представлять себе как процессы переработки целых чисел при помощи ЭВМ, а

способы, которыми выполняются эти операции, как некоторые функции,

определённые на множестве целых чисел. Всё это делает естественным

появление в криптографии методов теории чисел. Кроме того, стойкость ряда

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

теоретико-числовых задач.

Но возможности ЭВМ имеют определённые границы. Приходится разбивать

длинную цифровую последовательность на блоки ограниченной длины и шифровать

каждый такой блок отдельно. Мы будем считать в дальнейшем, что все

шифруемые целые числа неотрицательны и по величине меньше некоторого

заданного (скажем, техническими ограничениями) числа m. Таким же условиям

будут удовлетворять и числа, получаемые в процессе шифрования. Это

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

Шифрующая функция при этом может рассматриваться как взаимнооднозначное

отображение колец вычетов

[pic]

а число [pic] представляет собой сообщение [pic] в зашифрованном виде.

Простейший шифр такого рода - шифр замены, соответствует отображению

[pic] при некотором фиксированном целом k. Подобный шифр использовал еще

Юлий Цезарь. Конечно, не каждое отображение [pic] подходит для целей

надежного сокрытия информации.

В 1978 г. американцы Р. Ривест, А. Шамир и Л. Адлеман (R.L.Rivest.

A.Shamir. L.Adleman) предложили пример функции [pic], обладающей рядом

замечательных достоинств. На её основе была построена реально используемая

система шифрования, получившая название по первым буквам имен авторов

-система RSA. Эта функция такова, что

1) существует достаточно быстрый алгоритм вычисления значений [pic];

2) существует достаточно быстрый алгоритм вычисления значений обратной

функции [pic];

3) функция [pic] обладает некоторым «секретом», знание которого

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

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

требующей для своего решения столь много времени, что по его

прошествии зашифрованная информация перестает представлять интерес для лиц,

использующих отображение [pic] в качестве шифра.

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

Технологическом институте, посвящённого системе RSA. была послана

известному популяризатору математики М. Гарднеру, который в 1977 г. в

журнале Scientific American опубликовал статью посвящённую этой системе

шифрования. В русском переводе заглавие статьи Гарднера звучит так: Новый

вид шифра, на расшифровку которого потребуются миллионы лет. Именно эта

статья сыграла важнейшую роль в распространении информации об RSA,

привлекла к криптографии внимание широких кругов неспециалистов и

фактически способствовала бурному прогрессу этой области, произошедшему в

последовавшие 20 лет.

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

Пусть [pic] и [pic] натуральные числа. Функция [pic] реализующая

схему RSA, устроена следующим образом

[pic].

(1)

Для расшифровки сообщения [pic] достаточно решить сравнение

[pic]. (2)

При некоторых условиях на [pic] и [pic] это сравнение имеет единственное

решение [pic].

Для того, чтобы описать эти условия и объяснить, как можно найти

решение, нам потребуется одна теоретико-числовая функция, так называемая

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

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

простых с [pic]. Так [pic] и [pic] для любого простого числа [pic] и

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

[pic] и [pic]. Эти свойства позволяют легко вычислить значение [pic], если

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

Если показатель степени [pic] в сравнении (2) взаимно прост с [pic],

то сравнение (2) имеет единственное решение. Для того, чтобы найти его,

определим целое число [pic], удовлетворяющее условиям

[pic]. (3)

Такое число существует, поскольку [pic], и притом единственно. Здесь и

далее символом [pic] будет обозначаться наибольший общий делитель чисел

[pic] и [pic]. Классическая теорема Эйлера, утверждает, что для каждого

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

следовательно.

[pic].

(4)

Таким образом, в предположении [pic], единственное решение сравнения (2)

может быть найдено в виде

[pic].

(5)

Если дополнительно предположить, что число [pic] состоит из различных

простых сомножителей, то сравнение (5) будет выполняться и без

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

делится на [pic], а из (2) следует, что [pic]. Подобно (4), теперь легко

находим [pic]. А кроме того, имеем [pic]. Получившиеся сравнения в силу

[pic] дают нам (5).

Функция (1), принятая в системе RSA, может быть вычислена достаточно

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

и [pic], лишь с заменой показателя степени [pic] на [pic]. Таким образом,

для функции (1) будут выполнены указанные выше свойства 1) и 2).

Для вычисления функции (1) достаточно знать лишь числа [pic] и [pic].

Именно они составляют открытый ключ для шифрования. А вот для вычисления

обратной функции требуется знать число [pic]. оно и является «секретом», о

котором речь идёт в пункте в). Казалось бы. ничего не стоит. зная число

[pic]. разложить его на простые сомножители, вычислить затем с помощью

известных правил значение [pic] и, наконец, с помощью (3) определить нужное

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

быстро, за исключением первого. Именно разложение числа [pic] на простые

множители и составляет наиболее трудоемкую часть вычислений. В теории чисел

несмотря на многолетнюю её историю и на очень интенсивные поиски в течение

последних 20 лет, эффективный алгоритм разложения натуральных чисел на

множители так и не найден. Конечно, можно, перебирая все простые числа до

[pic], и. деля на них [pic], найти требуемое разложение. Но, учитывая, что

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

что при [pic], записываемом 100 десятичными цифрами, найдётся не менее

[pic] простых чисел, на которые придётся делить [pic] при разложении его на

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

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

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

эффективные способы разложения целых чисел на множители, чем простой

перебор простых делителей, но и они работают очень медленно.

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

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

как

[pic],

(6)

то единственное условие на выбор показателя степени [pic] в отображении (1)

есть

[pic].

(7)

Итак, лицо, заинтересованное в организации шифрованной переписки с

помощью схемы RSA, выбирает два достаточно больших простых числа [pic] и

[pic]. Перемножая их, оно находит число [pic]. Затем выбирается число

[pic], удовлетворяющее условиям (7), вычисляется с помощью (6) число [pic]

и с помощью (3) - число [pic]. Числа [pic] и [pic] публикуются, число [pic]

остается секретным. Теперь любой может отправлять зашифрованные с помощью

(1) сообщения организатору этой системы, а организатор легко сможет

расшифровывать их с помощью (5).

Для иллюстрации своего метода Ривест, Шамир и Адлеман зашифровали

таким способом некоторую английскую фразу. Сначала она стандартным образом

(а=01, b=02, .... z=26, пробел=00) была записана в виде целого числа [pic],

а затем зашифрована с помощью отображения (1) при

m=11438162575788886766932577997614661201021829672124236256256184293570

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


ИНТЕРЕСНОЕ



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