Система шифрования RSA

 

Рассмотрим асимметричную систему шифрования RSA, названную по имени ее авторов Ривеста Р.Л., Шамира А. и Адлемана Л.. В данной системе односторонняя функция строится на основе произведения двух очень больших (сотни десятичных цифр) простых числе p и q: . В то время как выбор двух больших простых чисел и вычисление их произведения не вызывает особых затруднений, обратная задача – разложение произведения на простые множители (факторизация) приводит к значительным вычислительным и временным затратам. Сложность факторизации числа иллюстрирует следующий факт. Для разложения числа, содержащего около 130 десятичных цифр, потребовалась бы работа 1600 ЭВМ в течение 8 месяцев. Следовательно, произведение, как часть ключа шифрования, может быть сделано общедоступным, в то время как множители, которые могут «разоблачить» ключ дешифрования, соответствующий ключу шифрования, остаются секретными.

Пусть , где p и q – простые числа, т. е. не имеющие делителей кроме 1 и самих себя. Несмотря на то, что n общедоступно, p и q являются скрытыми из-за большой сложности разложения n на множители. В теории чисел известна функция Эйлера , которая определяет количество положительных чисел, меньших n и взаимно простых с n. Так, для рассматриваемого произведения функция Эйлера вычисляется как

.

Важной особенностью функции Эйлера является то, что для любого целого x из интервала (0, n –1) и любого целого k имеет место следующее соотношение

. (13.5)

Затем выбирается два целых числа и d, взаимно простые с , такие, что удовлетворяют равенству

или , (13.6)

где k – некоторое натуральное число.

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

.

Очевидно, что в указанной трансформации проявилась односторонняя функция, присущая системе RSA.

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

,

где учтено соотношение (13.5).

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

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

Пример 13.4.1. Пусть абонент B выбирает свои ключи согласно описанному алгоритму: , т.е. и . Пусть в качестве , взаимно простого числа с , выбирается . Затем определяется значение , удовлетворяющее условию

или .

Отметим, что для вычисления , как правило, используется разновидность алгоритма Евклида для вычисления . Применение его дает . Таким образом, ключ для шифрования , для расшифрования – .

Предположим, что абонент A направляет сообщение вида, (что может быть номером секретного шифра в книге шифров) абоненту B. Зная открытый ключ абонента B, абонент A осуществляет следующие вычисления

.

Абонент B, приняв сообщение y, производит вычисления с использованием своего секретного ключа

,

т.е. правильно восстановлен номер шифр, который используется при шифровании открытого текста.