Метод RSA

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

шифрование алфавит алгоритм модуль

Курсовая работа по Алгебре

на тему «Метод RSA»

Введение

Проблема защиты информации путем ее преобразования, исключающего ее прочтение посторонним лицом, волновала человеческий ум с давних времен. История криптографии - ровесница истории человеческого языка. Более того, первоначально письменность сама по себе была криптографической системой, так как в древних обществах ею владели только избранные. Священные книги древнего Египта, древней Индии тому примеры.

С широким распространением письменности криптография стала формироваться как самостоятельная наука. Первые криптосистемы встречаются уже в начале нашей эры. Так, Цезарь в своей переписке использовал уже более-менее систематический шифр, получивший его имя, в котором шифровались сообщения методом замены букв, на определённое количество цифр.

Бурное развитие криптографические системы получили в годы первой и второй мировых войн. Появление вычислительных средств в послевоенные годы ускорило разработку и совершенствование криптографических методов. Вообще история криптографии крайне увлекательна, и достойна отдельного рассмотрения.

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

С одной стороны, расширилось использование компьютерных сетей, в частности, глобальной сети Интернет, по которым передаются большие объемы информации государственного, военного, коммерческого и частного характера, не допускающего возможность доступа к ней посторонних лиц.

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

Все это постоянно подталкивает исследователей на создание новых криптосистем и тщательный анализ уже существующих.

Так в 1978 году три американских инженера предложили новый метод шифрования, который был назван по первым буквам их фамилий. В данной работе пойдёт речь о методе шифрования RSA.

1. Основные теоретические положения

Чтобы реализовать систему шифрования RSA, предназначенную для одного пользователя, необходимо выбрать два различных простых числа p и q и вычислить их произведение n = p•q. Простые числа p и q должны держаться в секрете, в то время как число n становится частью открытого ключа.

Сообщение (которое можно считать целым числом) шифруется путем возведения в некоторую степень по модулю n. Поэтому сначала мы должны найти способ представить текст сообщения в виде списка классов по модулю n. Это, в действительности, еще не процесс шифрования, а только подготовка сообщения к тому, чтобы его можно было зашифровать.

Для простоты предположим, что текст сообщения содержит только слова, записанные заглавными буквами. Таким образом, сообщение, в конечном счете, -- последовательность букв и пробелов. Первый шаг состоит в замене каждой буквы сообщения числом, которое выбирается из следующей таблицы:

Таблица 1 -- Соответствие букв алфавита и двухразрядных десятичных чисел

Пробел между словами заменяется на число 99. Проделав эту процедуру, мы получим число, возможно очень большое, если сообщение было длинным. Однако, это еще не окончательное число, к которому мы стремимся, а всего лишь набор классов по модулю n. И теперь нам нужно разбить численное представление сообщения на кусочки, каждый из которых -- натуральное число, не превосходящее n. Эти кусочки принято называть блоками сообщения.

Например, численное представление девиза «ПОЗНАЙ СЕБЯ» выглядит так:

2524172310199927151141

Выбрав простые p = 149 и q = 157, мы получим произведение n = 23393. Поэтому численное представление сообщения, выписанное выше, нужно разбить на блоки, меньшие, чем 23 393.

Приведем одно из таких разбиений.

2524 - 1723 - 10199 - 9271 - 511 - 41

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

При расшифровании сообщения, зашифрованного системой RSA, получают последовательность блоков. Затем их соединяют вместе и получают численное представление сообщения. И только после замены чисел буквами в соответствии с приведенной таблицей можно будет прочесть исходное сообщение.

Обратите внимание на то, что каждая буква таблицы шифруется двузначным числом. Так делается для предотвращения путаницы. Предположим, мы пронумеровали буквы по порядку, начиная с 1, т.е. А соответствует 1, Б -- 2, и так далее. В этом случае мы не сможем точно сказать, обозначает ли блок 12 пару букв АБ, или только одну букву Л, двенадцатую букву алфавита.

Сообщение, подготовленное к зашифрованию, состоит из последовательности блоков, каждый из которых -- число, меньшее, чем n. Теперь обсудим, как шифруется каждый блок. Для этого нам потребуется число n, равное произведению простых р и q, и натуральное число, обратимое по модулю ц(n), т.е. число e, удовлетворяющее условию:

НОД(e, ц(n)) = 1

Напомним, что по известным р и q число ц(n) легко вычисляется. Действительно,

ц(n) = (p -1) • (q - 1)

Пара (n,e) называется открытым ключом криптосистемы RSA, которую мы описываем. Пусть b -- блок сообщения, то есть целое число, удовлетворяющее неравенству 0 ? b ? n - 1. Символом Е(b) мы будем обозначать блок зашифрованного сообщения, соответствующий b. Он вычисляется по следующему правилу:

Е(b) = вычет be по модулю n

Заметим, что каждый блок сообщения шифруется отдельно. Поэтому зашифрованное сообщение, фактически, состоит из отдельных зашифрованных блоков. Более того, мы не можем объединить эти блоки в одно большое число, поскольку в результате расшифровать сообщение станет невозможно. Вскоре мы увидим причину этого.

Вернемся к примеру, который начали рассматривать в первом параграфе. Мы зафиксировали р = 149 и q = 157, так что п = 23393 и ц(n) = 23088. Теперь нужно выбрать число е. Напомним, что оно должно быть взаимно простым с ц(n). Наименьшее простое число, не делящее 23088, равно 5. Положим е = 5. Чтобы закодировать первый блок сообщения, нам предстоит определить вычет числа 25245 по модулю 23393. С помощью программы символьных вычислений (или калькулятора, если хватит терпения) мы получим, что искомый вычет равен 22752. Итак, Е(2524) = 22752. Все же зашифрованное сообщение представляется следующей последовательностью блоков:

22752 - 6198 - 14204 - 23191 - 10723 - 14065

Посмотрим, как дешифруются блоки сообщения. Чтобы приступить к дешифрованию, нам необходимо знать п и обратный элемент к е по модулю ц(n). Последний из них -- это натуральное число, которое мы будем обозначать через d. Пара (ц(n), d) называется секретным ключом системы шифрования RSA. Если а -- блок зашифрованного сообщения, то соответствующее ему дешифрованное сообщение D(a) получается в результате операции:

D(a) = вычет ad по модулю n

Прежде чем вернуться к примеру, необходимо дать некоторые комментарии. Во-первых, вычислить d очень легко, если знать ц(n) и е. Действительно, секретный ключ определяется с помощью расширенного алгоритма Евклида. Во-вторых, если b -- блок исходного сообщения, то мы вправе ожидать равенства D(E(b)) = b. Другими словами, расшифровывая блок сообщения, мы надеемся узнать соответствующий блок исходного.

Для взлома RSА-криптосистемы необходимо разложить n на множители, потому что для дешифрования сообщения нужно знать р и q. Однако после того, как работа системы подробно описана, ясно, что последнее утверждение не совсем точно. Чтобы прочесть шифровку, кроме самого n, нужно знать только d, обратный к е элемент по модулю ц(n). Поэтому для взлома системы достаточно вычислить d при известных n и е. Оказывается, это вычисление равносильно разложению числа n на множители.

В обсуждаемом примере п = 23393 и е = 5. Для определения d применим расширенный алгоритм Евклида к числам ц(n) = 23088 и 5.

Таким образом, 23088 • 2 + 5 • (-9235) = 1. Следовательно, обратным к 5 по модулю 23 088 будет -9235 и d = 23088 - 9235 = 13853 -- наименьшее натуральное число, сравнимое с -9235 по модулю 23088. Значит, для расшифрования блока сообщения мы должны возвести его в степень 13853 по модулю 23393. В нашем примере первый зашифрованный блок -- это 22752. Вычисляя вычет числа 2275213853 по модулю 23393, получим D(22752) = 2524. Заметьте, что даже при таких малых числах требования, предъявляемые при работе RSA-криптосистемы, превышают возможности большинства карманных калькуляторов.

Как мы уже отмечали ранее, шаги, описанные выше, приводят к работающей криптосистеме, только если в результате дешифрования каждого блока шифрованного сообщения будет восстанавливаться соответствующий блок исходного. Предположим, что мы имеем дело с системой RSA, имеющей открытый ключ (n,е) и секретный ключ (ц(n),d). Нам нужно показать, что для любого целого числа b, удовлетворяющего неравенству 0 ? b ? п - 1, выполняется тождество D(E(b)) = b.

На самом деле, достаточно доказать, что

D(E(b)) = b (mod n)

Действительно, как b, так и D(E(b)) -- неотрицательные целые числа, меньшие n. Поэтому они сравнимы по модулю n тогда и только тогда, когда они равны. Это, в частности, объясняет, почему мы разбиваем численное представление сообщения на блоки, меньшие п. Кроме того, отсюда видно, что блоки зашифрованного сообщения необходимо записывать отдельно: в противном случае наши рассуждения не будут работать. Из рецептов шифрования и дешифрования следует, что

D(E(b)) = (be)d = bed (mod n)

Поскольку элементы d и e взаимно обратны по модулю ц(n), найдется такое натуральное k, что e•d = 1 + k•ц(n). Более того, по условию, числа e и d больше 2 и ц(n) > 0. Следовательно, к > 0. Подставляя 1 + k•ц(n) вместо произведения e•d, получаем

bed ? b1+kц(n) ? (bц(n))k b (mod n)

Теперь воспользуемся теоремой Эйлера, которая утверждает, что bц(n) ? 1 (mod n). Отсюда bed = b (mod n), т.е. D(E(b)) = b (mod n) [1].

2. Реализация алгоритма шифрования в КГС RSA и моделирование атаки путем факторизации модуля

В рамках данной курсовой работы будет показано как работает метод RSA на простом наглядном примере. Для начала обратимся к рисунку, чтобы понять суть этого метода.

На данном рисунке наглядно показано, как абонент А передаёт сообщение абоненту Б. Сообщение обозначим за E.

Для того чтобы передать зашифрованное сообщение, надо выполнить ряд действий.

Для начало выберем два простых числа p и q. p=13, q=3. Для дальнейшего выполнения задачи нам нужно знать их произведение. n=p*q. n=39.

Далее надо найти ц(n)- это часть открытого числа. Находится по функции Эйлера.

ц(n) = (p -1) • (q - 1). ц(n)=24

Так же найдём е-число которое тоже является частью открытого ключа, оно должно быть взаимно простым с ц(n). Наименьшее простое число, которое не делятся на 24 это 5.

Значит е=5. ц(n)=24. Открытый ключ.

Теперь займёмся сообщением которое мы хотим передать абоненту В. Данное сообщение состоит из 4-х букв. БАБА. Из таблицы-1 на стр 4, возьмём значение для численного представления данного слова. 11101110. Для того чтобы приступить к шифрованию сообщения нужно разделить численное представление на блоки, которые будут меньше полученного произведения n=65. В итоге получаем разбиение 11-10-11-10.

Каждый блок обозначим за Е(b).

После выполнения данных действий приступим к шифрованию данного слова. Вычисляем по следующему правилу:

Е(b) = вычет be по модулю n

115(mod 39)= 161051(mod 39)= 20

105(mod 39)= 100000(mod 39)= 29

Реализовав данное действие, мы получили зашифрованное сообщение, которое теперь имеет вид 20-29-20-29.

Для дешифрования используется ц(n) и d, которые являются закрытым ключом. d- это обратный элемент к е по модулю ц(n). Для

Заключение

Метод RSA основывается на сложности факторизации больших чисел, что даёт основание для поиска новых эффективных методов разложения числа на множители.

На данный момент существует много алгоритмов факторизации чисел (обобщённого решета числового поля), метод факторизации на основе эллиптических кривых и других.

В целях безопасности электронного документооборота при использовании метода RSA необходимо использовать модули шифрования N, стойкие к известным способам разложения.

Система RSA используется для защиты программного обеспечения и в схемах цифровой подписи.

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

Список использованной литературы

Ященко В. В. Введение в криптографию. - М.: 2000. - 271 с.

Коблиц Н. Курс теории чисел и криптографии. - М.: Научное издательство

ТВП, 2001. - 254 с.

Баричев С.Г., Гончаров В.В., Серов Р.Е. Основы современной криптографии. - М.: Горячая линия - Телеком, 2001. - 120 с.

Коутинхо С. Введение в теорию чисел. Алгоритм RSA. - М.: Постмаркет. - 2001. - 323 с.

Ростовцев А. Г., Маховенко Е. Б. Введение в криптографию с открытым ключом. - СПб.: Мир и Семья, - 2001. -336 с.

Размещено на Allbest.ru