Алгоритм RSA

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

Рассмотрим некоторые матем-е факты, на которых основан алгоритм. Согласно малой теореме Ферма, если р - простое число, то для любого х, взаимно простого с р, справедливо хp-1 = (mod р);

для любого х справедливо Xр= x(modp).

Функция ф(n) натурального аргумента n, равная количеству положительных целых чисел, меньших п и взаимно простых с r, называется функцией Эйлера. Для нее справедливы следующие соотношения:

φ(1)=1; φ(pr) = pr-1(p-1);

φ(ab) - φ(а)φ(b), где р - простое, r, а и b - натуральные, (а, b) = 1.

Эти свойства позволяют легко вычислять ф(n), когда известно разложение n на простые множители. Если натуральное число е удовлетворяет условию (е, φ(n)) = 1, то существует единственное натуральное число d < φ(n), для которого справедливо de ≡ 1 (mod φ(n)).

Пусть n = pq, где р и q - два больших различных простых числа, и (х, φ(n)) = 1. Тогда согласно теореме Эйлера для любого натурального х выполняется сравнение хed= x(mod n) и, следовательно, хed(mod n) = х при условии x < n.

Итак, выберем два больших различных простых числа р и q и число е, взаимно простое с числом (р - 1)(q -1). Вычислим n = pq и найдем d, такое, что de≡ 1 (mod (р-1)(q-1)).

Тогда рассматриваемая криптосистема выглядит следующим образом.

Криптосистема RSA:

Открытый ключ зашифрования: числа n и е.

Закрытый ключ расшифрования: числа р, q и d.

Алгоритм зашифрования сообщения р~:

Ek(р~) = р~e(mod n) = с.

Алгоритм расшифрования закрытого сообщения с:

Dk(c) = cd(mod n) =р~.

Единственный способ найти алгоритм расшифрования Dkпри известных е и n состоит в том, чтобы разложить на простые множители число n, найти р и q, а следовательно, и d. Правильный выбор разрядности чисел р и q (первоначально авторы RSA предлагали в качестве р и q использовать не менее чем 40-разрядные десятичные числа) делает задачу факторизации n практически неосуществимой.

Криптосистема с открытым ключом RSA часто используется не только для шифрования, но и для построения схемы электронной подписи. Пусть E_A (x) = x^C mod n - открытая функция зашифрования, а D_A (x) = x^D mod n - секретная функция расшифрования.

Дата добавления: 2015-03-29