Системы с открытым ключом: алгоритм шифрования RSA

Понятие и история изобретения криптосистемы с открытым ключом. Свойства односторонней функции и сложность раскрытия шифра. Описание алгоритма RSA: шифрование и дешифрование. Возможные атаки, способы взлома, обоснование и практическая реализация RSA.
Краткое сожержание материала:

Размещено на

Нижегородский государственный университет им. Н. И. Лобачевского

Факультет вычислительной математики и кибернетики

Кафедра информатизации и автоматизации научных исследований

Курсовая работа

Системы с открытым ключом: алгоритм шифрования RSA

Выполнил: Скульский М. А.

Научный руководитель: Фомина И. А.

Н. Новгород, 1997 г.

Оглавление

Введение

Понятие криптосистемы с открытым ключом

Описание алгоритма RSA

Возможные атаки на RSA

Практическая реализация RSA

Обоснование алгоритма

Комментарии к программе

Текст программы

Литература

Введение

Основной целью построения криптографических систем всегда была защита информации при ее передаче и хранении. Эта проблема остается актуальной и до сегодняшнего дня, однако же развитие вычислительных систем придало ей новое качество: вопрос уже не просто в том, чтобы, скажем, Александр мог послать письмо Борису, не опасаясь, что оно будет прочитано Сергеем. Сетевые компьютерные системы могут включать в себя сотни и даже тысячи пользователей; в такой ситуации классическая симметричная схема оказывается неэффективной. Новым требованием к криптосистемам также является обеспечение аутентификации сообщения - доказательство того, что Борис получил именно то сообщение, которое ему отправил Александр, и что оно не было подделано или изменено злоумышленником в процессе передачи. Кроме того, приходится мириться с тем, что к зашифрованной информации потенциально может иметь доступ довольно большое количество людей - например, маршрут любого сообщения, проходящего через Internet, в принципе невозможно предсказать, оно может пройти через несколько десятков узлов прежде чем попадет к своему адресату. Так что, если прежде наиболее надежным подходом к защите информации был все-таки амбарный замок, то теперь задача все более усложняется противоречивыми требованиями одновременно надежности и секретности передачи и легкости доступа к информации.

Традиционная криптографическая схема выглядит следующим образом. Александр и Борис оба знают некий ключ, с помощью которого они могут обмениваться зашифрованными сообщениями так, что любое третье лицо, даже если ему удастся перехватить шифровку, не сможет ничего в ней понять. Такая схема называется симметричной, так как и адресат, и отправитель используют один и тот же ключ для шифрования и дешифрования. Давайте попробуем применить ее к какой-нибудь простой распределенной задаче. Пусть у нас есть некое сетевое устройство - например, ядерная ракетная установка, - принимающая команды по сети. Конечно, не от всех, а только от имеющих соответствующие права доступа. Пусть у нашего устройства есть некий ключ, которым должны быть зашифрованы все команды, подаваемые на него. Этот ключ, так как систему мы предполагаем симметричной, необходимо сообщить всем пользователям. Теперь предположим, что Александр зашифровал сообщение “Стреляй в Бориса” и отправил его нашему устройству. Другой пользователь, Сергей, подкупленный Борисом, перехватил это сообщение и, зная ключ, с легкостью расшифровал его, сообщив о содержании Борису. Казалось бы, проблема легко решается введением разных паролей для разных пользователей. Ну а если доступ к данному устройству должен быть более или менее свободным?

Теперь давайте представим себе сеть из, например, ста пользователей и сервера баз данных. Между пользователями и сервером происходит некий обмен информацией, причем всем пользователям совершенно необязательно и, более того, нежелательно знать информацию, хранимую и запрашиваемую на сервере другими пользователями. Разумеется, необходимо защитить сам сервер - так, чтобы каждый пользователь имел доступ только к своей информации. Но ведь все это происходит в одной сети, и все данные передаются по одним и тем же проводам, а если это, скажем, что-нибудь типа Token Ring, то информация от сервера до владельца последовательно проходит через все станции, находящиеся между ними в кольце. Следовательно, ее необходимо шифровать. Можно опять ввести для каждого пользователя свой пароль, которым и шифровать весь информационный обмен с сервером. Но как отличить одного пользователя от другого? Один вариант - перед началом работы спрашивать у пользователя этот самый пароль и сверять с хранящимся на сервере. Но тогда он с легкостью может быть перехвачен в том же самом канале связи. Другой вариант - пароль не спрашивать, а верить тому, что пользователь говорит о себе. Так как пароль секретный, то даже сказав серверу “Я - Александр!”, злоумышленник не сможет расшифровать получаемые данные. Но зато он сможет получить столько материала для взлома шифра, сколько ему захочется - при этом часто можно предсказать ответ сервера на какой-то специфический вопрос и получить сразу шифр и соответствующий оригинальный текст. Согласитесь, это очень продвигает нас в взломе сервера.

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

Понятие криптосистемы с открытым ключом

Концепция криптосистем с открытым ключом была предложена в 1976 г Уайтфилдом Диффи и Мартином Хеллманом в качестве решения проблемы распределения ключей. В соответствии с ней, каждая сторона получает пару ключей - открытый и закрытый. Открытый ключ распространяется свободно, в то время как закрытый держится в тайне. Исходный текст шифруется открытым ключом адресата и передается ему. Обратный процесс в принципе не может быть выполнен с помощью открытого ключа, для расшифровки получатель использует закрытый ключ, который известен только ему. Таким образом, кто угодно может посылать шифрованные сообщения, для этого ему не надо знать ничего тайного, но при этом только владелец закрытого ключа сможет их прочитать.

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

Обратную функцию очень сложно вычислить, не зная закрытого ключа;

Закрытый ключ невозможно найти из открытого;

Сложность вычисления должна катастрофически возрастать с возрастанием длины ключа.

Существует большое количество функций, которые считаются односторонними, однако отсутствие полиномиального решающего алгоритма ни для одной не доказана. Поэтому при использовании любой системы с открытым ключом всегда остается риск того что в будущем обнаружится быстрый алгоритм нахождения обратной функции без закрытого ключа. На самом деле, корнем любой такой функции является какая-нибудь математическая проблема, традиционно считающаяся трудной. Если удается доказать, что раскрытие шифра эквивалентно разрешение этой проблемы, то проблема надежности шифра зависит от справедливости гипотезы P--№ NP. Наиболее часто используются:

Разложение больших чисел на простые множители - RSA;

Вычисление дискретного логарифма (логарифма в конечном поле) - система Эль-Гамаля;

Вычисление квадратных корней в конечном поле - система Рабина;

Вычисление дискретного логарифма над эллиптическими кривыми;

Задача о камнях;

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

Описание алгоритма RSA

Выберем достаточно большие простые числа p и q;

Вычислим n=pq, называемый модулем;

Выберем e<n взаимно простое с j=(p-1)(q-1); е называется открытой экспонентой;

Найдем d | res(p-1)(q-1)(ed)=1 (то есть, ed=1 mod ?); d называется закрытой экспонентой;

Теперь (n, d) - закрытый ключ; (n, e) - открытый ключ;

Шифрование: ;

Дешифрование:

Здесь m - целое число, .

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

Возможные атаки на RSA

Главным и наиболее очевидным способом сломать RSA является отыскание закрытого ключа по данному открытому. Это позволило бы злоумышленнику читать все сообщения, зашифрованные этим ключом. Сделать это можно, например, разложив n на простые множители p и q. После этого отыскание d является тривиальной задачей. Надежность RSA основывается на трудности разложения n.

Лучшим алгоритмом, применяемым для факторизации на сегодняшний день, является NFS (Number Field Sieve - числовое решето), вычислительная сложно...