Шифрование и расшифрование по алгоритму RSA

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

Для современных криптографических систем защиты информации сформулированы следующие общепринятые требования:

– зашифрованное сообщение должно поддаваться чтению только при наличии ключа;

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

– должно быть не меньше общего числа возможных ключей;

– число операций, необходимых для расшифровывания информации путем перебора всевозможных ключей должно иметь строгую нижнюю оценку и выходить за пределы возможностей современных компьютеров (с учетом возможности использования сетевых вычислений);

– знание алгоритма шифрования не должно влиять на надежность защиты;

– незначительное изменение ключа должно приводить к существенному изменению вида зашифрованного сообщения даже при использовании одного и того же ключа;

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

– дополнительные биты, вводимые в сообщение в процессе шифрования, должен быть полностью и надежно скрыты в шифрованном тексте;

– длина шифрованного текста должна быть равной длине исходного текста;

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

– любой ключ из множества возможных должен обеспечивать надежную защиту информации;

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

1.3 Симметричные и асимметричные криптосистемы

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

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

В таких криптосистемах общедоступным является только ключ для процесса шифрования, а процедура дешифрования известна лишь обладателю секретного ключа. Например, когда я хочу, чтобы мне выслали сообщение, то генерирую открытый и секретный ключи. Открытый посылаю вам, вы шифруете им сообщение и отправляете мне. Дешифровать сообщение могу только я, так как секретный ключ я никому не передавал. Конечно, оба ключа связаны особым образом (в каждой криптосистеме по-разному), и распространение открытого  ключа не разрушает криптостойкость системы.

В асимметричных системах должно удовлетворяться следующее требование: нет такого алгоритма (или он пока неизвестен), который бы из криптотекста и открытого ключа выводил исходный текст.

1.4 Основные современные методы шифрования

Среди разнообразнейших способов шифровании можно выделить следующие основные методы:

– алгоритмы   замены  или  подстановки  – символы  исходного текста заменяются на символы другого (или того же) алфавита в соответствии с заранее определенной схемой, которая и будет ключом данного шифра. Отдельно этот метод в современных криптосистемах практически не используется из-за чрезвычайно низкой  криптостойкости.

– алгоритмы перестановки – символы оригинального текста меняются местами по определенному принципу, являющемуся секретным ключом. Алгоритм перестановки сам по себе обладает низкой криптостойкостью, но входит в качестве элемента в очень многие современные криптосистемы.

– алгоритмы гаммирования – символы исходного текста складываются с символами некой случайной последовательности. Самым распространенным примером считается шифрование файлов «имя пользователя.рwl», в которых операционная система Microsoft Windows 95 хранит пароли к сетевым ресурсам данного пользователя (пароли на вход в NT-серверы, пароли для DialUр-доступа в Интернет и т.д.). Когда пользователь вводит свой пароль при входе в Windows 95, из него по алгоритму шифрования RC4 генерируется гамма (всегда одна и та же), применяемая для шифрования сетевых паролей. Простота подбора пароля обусловливается в данном случае тем, что Windows всегда предпочитает одну и ту же гамму.

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

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

1.5 Алгоритм RSA

RSA – алгоритм шифрования данных с открытым ключом. Это во многом уникальная технология. Начну с того, что алгоритм был разработан уже почти тридцать лет назад (в 1977 году), но до сих пор не найдены достаточно эффективные способы его взлома. Более того, на сегодняшний день он стал стандартом «де-факто» сразу же в нескольких областях информационной безопасности. RSA используется буквально везде: в Интернете, локальных сетях, специальных системах обмена данными, кредитных картах и т. п. Кроме того, этот алгоритм был использован при разработке других технологий, а также оказался «узаконенным» в добром десятке как международных, так и национальных стандартах разных стран.

Следующим отличием RSA от многих других являются его авторы. Оказывается, этот алгоритм был создан не крупной компанией и не по заказу государственных организаций. Руку и голову к его разработке приложили только три ученых-математика: Ronald Rivest, Adi Shamir и Leonard Adleman. Кстати, именно отсюда и пошло название RSA (Rivest Shamir Adleman), а вовсе не от слов security и algorithm, как думают многие.

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

– возможности перехвата;

– подмены корреспондента;

– фальсификации данных.

Решение первой задачи достигается путем шифрования информации, двух других – с помощью цифровой подписи.

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

А теперь давайте рассмотрим сам алгоритм. Первое действие, которое необходимо выполнить, – это генерация публичного и секретного ключей. Осуществляется этот процесс следующим образом:

– выбираются два очень больших простых числа p и q. На сегодняшний день специалисты рекомендуют использовать комбинации длиной не менее чем в 100 десятичных цифр;

– полученные простые числа перемножаются, в результате чего получается число n;

– выбирается достаточно большое простое число e. Оно должно быть взаимно простым с результатом умножения значений p и q, уменьшенных на единицу ((p-1)*(q-1));

– вычисляется число d таким образом, чтобы e*d-1 нацело делилось на значение выражения (p-1)*(q-1).

Вот, собственно, и все. После выполнения этих вычислений, мы имеем три нужных нам значения: n, e и d. Из них и составляются ключи, представляющие собой пары из двух чисел. Первая – (e, n) – это открытый ключ. Он будет использован при шифровке сообщений. Вторая пара – (d, n) – секретный ключ. Он должен храниться в тайне и нужен для декодирования данных.

Ну а теперь перейдем к самому процессу шифрования. Собственно говоря, он состоит из одного действия. Каждый блок информации кодируется путем возведения его в степень e и умножения на модуль n. Полученный результат может быть преобразован обратно только одним способом. Для этого нужно зашифрованный блок возвести в степень d и умножить на модуль n. То есть получается, что для кодирования данных нужен публичный ключ, а для их расшифровки – закрытый. Что, собственно, нам и было нужно. При необходимости цифровой подписи сообщения выполняются обратные вычисления. То есть для ее создания используется вторая формула с секретным ключом, а для проверки – первая с публичным.

Скорость работы алгоритма RSA. Вообще, скорость шифрования и расшифровки информации – одна из самых «слабых» характеристик всех алгоритмов шифрования, основанных на принципе публичных ключей. И RSA не является исключением из правила. Причины этого лежат на «поверхности». Мы же с вами разобрали, как именно осуществляется процесс шифрования информации. Он представляет собой возведение числа в большую степень. В компьютере это реализуется путем многократного перемножения. Ну а если учесть, что сама операция умножения довольно длительная, то становится ясно, почему RSA – действительно медленный алгоритм. И это подтверждено многими исследованиями. Согласно им процесс шифрования одного и того же текста с помощью RSA занимает примерно в 100 раз больше времени, нежели при использовании алгоритма DES.

Но и это еще не все. Большинство симметричных алгоритмов отлично поддаются аппаратной реализации. При этом скорость шифрования в специализированных криптопроцессорах возрастает на 1-2 порядка. К сожалению, совсем по-другому обстоят дела в алгоритмах с открытыми ключами. Естественно, их тоже можно реализовать на аппаратном уровне. Но вот столь заметного выигрыша в скорости работы мы уже не получим. Поэтому, если взять устройства, в которых алгоритмы DES и RSA будут реализованы на аппаратном уровне, первый будет работать быстрее в 1000 –    10 000 раз.

Выход из этой ситуации есть. Давайте для примера рассмотрим принцип работы устройства Zaxus DataCryptor 2000, предназначенного для передачи секретной информации по открытым каналам связи. В нем реализованы на аппаратном уровне сразу два алгоритма шифрования. DES используется только для кодирования самой информации. Но для этого необходимо, чтобы оба устройства обладали идентичным ключом сессии. Этот ключ генерируется одним из них, но как же переслать его другому? А вот здесь-то и используется RSA. Этот алгоритм позволяет зашифровать и безопасно переслать ключ, необходимый для работы DES. Благодаря такой комбинации достигается хорошая надежность и высокая скорость передачи информации.

Способы взлома алгоритма RSA. Вообще-то, на сегодняшний день неизвестны действительно эффективные и универсальные способы взлома алгоритма RSA. Однако мы попытаемся рассмотреть хотя бы теоретические возможности этого. Самый очевидный на первый взгляд метод взлома – восстановление секретного ключа на основе публичного. Для этого достаточно разложить число n на сомножители p и q. Ну а зная последние и открытый ключ (то есть число e), можно легко вычислить и значение d. Однако на сегодняшний день не существует эффективных способов разложения n на множители. Конечно, с ростом мощности вычислительной техники эту процедуру можно провести простым перебором. Однако никто не мешает людям начать пользоваться числами большей длины. Так, например, на современном этапе достаточно взять p и q разрядностью в 100 знаков. Но какой же понадобится компьютер, если увеличить их длину до 150 или 200 цифр?

Другой вариант взлома RSA заключается в нахождении метода вычисления корня степени e из модуля n. А если злоумышленник вычислит это значение, то он получит возможность читать зашифрованные данные и подделывать электронные подписи, даже не зная секретного ключа. Однако нужно признать, что на сегодняшний день неизвестны методы, позволяющие взломать RSA подобным способом. Единственной возможностью для злоумышленника остается тот случай, когда на основе одного и того же показателя относительно небольшой величины шифруется достаточно много связанных сообщений. Это дает ему некоторые шансы на успешный взлом RSA.

Помимо рассмотренных вариантов взлома RSA существует ряд других возможных атак. Однако они позволяют раскрыть только одно зашифрованное сообщение. Кроме того, от этих атак существуют очень простые и эффективные способы защиты, которые присутствуют во всех современных программных и аппаратных реализациях. Поэтому они не представляют собой абсолютно никакой опасности для пользователей. Но для примера мы все-таки рассмотрим одну такую атаку. Она работает в том случае, когда кто-то отправляет одно и то же сообщение трем корреспондентам, каждый из которых использует общий показатель e=3. Перехватив эти сообщения, злоумышленник получает реальный шанс расшифровать их. Ну а защита от этого типа атаки очень проста и эффективна. Речь идет о добавлении перед каждым шифрованием к исходному сообщению нескольких бит, выбранных случайным образом.