7.2. Криптосистема rsа

Криптосистема RSA, разработанная в 1977 году, получила свое название в честь ее создателей: Рона Ривеста, Ади Шамира и Леонарда Эйдельмана.

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

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

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

В настоящее время алгоритм RSA используется во многих стандартах, среди которых SSL, S-HТTP, S-MIME, S/WAN, STT и PCT. Кроме того, алгоритм RSA реализуется как в виде самостоятельных криптографических продуктов (PGP), так и в качестве встроенных средств в некоторых приложениях (Интернет‑браузеры от Microsoft и Netscape).

Напомним ряд положений элементарной теории чисел, лежащих в основе этого алгоритма.

Наибольшим общим делителем двух целых чисел и называется наибольшее целое число, которое делит как так и . Обозначения: или НОД. Числа и называются взаимно простыми, если .

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

Пусть и . Тогда существуют целые числа являющиеся решением уравнения .

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

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

Построенное число называется числом, обратным к по модулю и обозначается через . Такое число в диапазоне является единственным.

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

Рассмотрим степени числа по модулю , где и взаимно просты.

Пусть . Степени 1,2,…10, числа 2 таковы: 2,4,8,5,10,9,7,3,6,1.

Аналогично, степени числа 3 равны 3,9,5,4,1,3,9,5,4. В каждом случае имеется периодичность. Наименьшая длина периода для числа по модулю называется порядком (показателем, периодом) числа по модулю .

Порядок числа по модулю обозначается .

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

Из определения следует, что для простого числа и, кроме того, .

Функция Эйлера является мультипликативной: если , то .

Теорема Эйлера. Если , то .

Доказательство. При теорема верна. Пусть и – все вычеты по модулю , взаимно простые с модулем (по определению, ).

Пусть – один из таких вычетов. Тогда множества и совпадают.

Поэтому . Умножив обе части сравнения на , получим

Из теоремы Эйлера следует малая теорема Ферма: , где – простое, .

Случай можно учесть в выражении .

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

Пусть , тогда .

Таким образом, если , где неравные простые числа, то .

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

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

Построение ключа при известных легко осуществимо. При наличии соответствующих параметров функции и также легко вычисляются.

Если известны и , но и неизвестны, то представляет собой одностороннюю функцию с секретом.

Построение по заданным и равносильно разложению числа на сомножители. В случае, когда и – достаточно большие простые числа, то разложение практически невозможно. Это и является причиной стойкости криптосистемы RSA.

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

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

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

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

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

1. Выберем простые числа: , .

2. Вычислим и .

3. Выберем случайное значение , .

5. Вычислим секретный ключ

Открытый ключ – .

Зашифруем сообщение: .

, , .

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

Секретный ключ для учебной системы легко найти перебором. На практике это невыполнимо, т.к. реальный размер модуля (длина битового представления) находится в диапазоне от 512 до 4096 битов.

Основные усилия в ходе практической реализации RSA приходятся на генерацию случайных больших простых чисел.

Есть очевидный путь решения задачи: случайно выбрать большое нечетное число и проверить его делимость на множители в диапазоне .

В случае неуспеха выбираем число и так далее. Однако при больших такой подход неосуществим.

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

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

Другая проблема – какой длины следует использовать ключи?

Полезно привести длины параметров RSA в битах [41], установленные и рекомендуемые французскими специалистам для практических приложений.

1. Сомножители RSA – модуля должны выбираться случайно и быть одинаковой длины.

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

3. Длина открытого ключа должна быть строго более 16 битов.

4. До 2010 года разрешается использовать значения модуля длиной не менее 1536 битов, однако рекомендуется – не менее 2048 битов.

5. С 2010 года по 2020 год разрешается использовать значения модуля длиной не менее 2048 битов.

6. После 2020 года предполагается использовать значения модуля длиной не менее 4096 битов.

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

Следует учитывать, что, по сравнению с тем же алгоритмом DES, для RSA требуется в тысячи и десятки тысяч раз большее время.