Системы с открытым ключом: алгоритм шифрования RSA
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
м Диффи и Мартином Хеллманом в качестве решения проблемы распределения ключей. В соответствии с ней, каждая сторона получает пару ключей - открытый и закрытый. Открытый ключ распространяется свободно, в то время как закрытый держится в тайне. Исходный текст шифруется открытым ключом адресата и передается ему. Обратный процесс в принципе не может быть выполнен с помощью открытого ключа, для расшифровки получатель использует закрытый ключ, который известен только ему. Таким образом, кто угодно может посылать шифрованные сообщения, для этого ему не надо знать ничего тайного, но при этом только владелец закрытого ключа сможет их прочитать.
Системы с открытым ключом базируются на использовании так называемых односторонних функций - функций, вычислить значения которых во много раз проще, чем значения их обратной функции. Особенно важен подкласс односторонних функций-ловушек - так называются односторонние функции, вычисление которых в обратную сторону возможно при наличии некоторой дополнительной информации, и очень трудно иначе. Открытый ключ является параметром при вычислении односторонней функции; закрытый же представляет информацию, необходимую для вычисления обратной. Хорошая односторонняя функция должна обладать следующими очевидными свойствами:
Обратную функцию очень сложно вычислить, не зная закрытого ключа;
Закрытый ключ невозможно найти из открытого;
Сложность вычисления должна катастрофически возрастать с возрастанием длины ключа.
Существует большое количество функций, которые считаются односторонними, однако отсутствие полиномиального решающего алгоритма ни для одной не доказана. Поэтому при использовании любой системы с открытым ключом всегда остается риск того что в будущем обнаружится быстрый алгоритм нахождения обратной функции без закрытого ключа. На самом деле, корнем любой такой функции является какая-нибудь математическая проблема, традиционно считающаяся трудной. Если удается доказать, что раскрытие шифра эквивалентно разрешение этой проблемы, то проблема надежности шифра зависит от справедливости гипотезы 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 - числовое решето), вычислительная сложность которого оценивается как O(exp(1.9223(ln n)1/3 (ln ln n)2/3)). Алгоритм этот сравнительно новый - при разложении знаменитого числа RSA-129, полученного в марте 1994, еще использовалось менее эффективное квадратичное решето, а не NFS. RSA-129 - это 129-значное число, разложение которого считалось весьма желательным с 1977 года. Для осуществления этого проекта через Internet было задействовано 1600 компьютеров (в том числе два факса), работавших в течение восьми месяцев. По некоторым оценкам использование NFS могло бы сократить этот срок в три-четыре раза. Таким образом, если 130 знаков примерно составляют предел для квадратичного решета, то использование NFS поднимает планку до 140-150 знаков. Модуль длиной 512 бит содержит около 155 знаков, поэтому для практически большинства приложений этого достаточно. По мнению фирмы RSA Data Security разложение такого числа будет стоить порядка $1,000,000 и займет около восьми месяцев. Также по ее мнению ключ длиной 768 бит останется неразложимым примерно до 2004 года.
Другим способом сломать RSA является отыскание способа вычисления корней степени e по модулю n. Так как , то даст нам исходное сообщение m. Этот способ не является эквивалентным разложению n, так как он не дает нам закрытого ключа d. Тем не менее само по себе вычисление корней над полями Галуа представляет собой сложную задачу. Известна теорема Рабина о том, что вычисление эквивалентно факторизации n, так что на самом деле практически не предпринималось попыток раскрытия шифра в этом направлении.
Все прочие способы не дают возможности раскрытия всех сообщений, зашифрованных данным ключом. Однако существуют