Алгоритм RSA

В основе стойкости алгоритма RSA лежит сложность задачи факторизации (разложения на простые множители) очень больших (сотни бит в двоичном представлении) чисел. Современное состояние алгоритмов факторизации позволяет решать эту задачу для чисел длиной до 430 бит. Исходя из этого, ключ длиной в 512 бит считается надежным для защиты данных сроком до 10 лет, в 1024 бита – безусловно надежным.

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

1. Выбираются случайным образом два очень больших простых числа:

p и q

2. Вычисляется число n = p×q.

3. Вычисляется функция Эйлера от числа n – j(n).

Функция Эйлера для произвольного натурального числа x равна количеству натуральных чисел, которые меньше него и взаимно просты с ним (т.е. их наибольшие общие делители равны 1). Исходя из теоремы Эйлера, в данном случае функция вычисляется достаточно просто:

j(n) = (p–1)×(q–1)

4. Случайным образом выбирается некоторое большое число d > 1, которое является взаимно простым с функцией Эйлера:

НОД(d, j(n)) = 1

5. Вычисляется число e, которое удовлетворяет следующим условиям:

1 < e < j(n); e×d = 1(mod j(n))

Числа n, e и d называются, соответственно, модулем, экспонентой шифрования и экспонентой расшифрования.

6. Выбирается размер i блока шифруемых данных. В двоичных разрядах он должен удовлетворять условию: 2^i–1 < n < 2ⁱ. А также для однозначного расшифрования требуется, чтобы значение любого шифруемого блока было строго меньше n.

7. Происходит шифрование сообщения w в шифртекст c по следующему правилу:

c = w^e mod n

8. Расшифрование происходит по формуле:

w = c^d mod n

Открытый ключ в данном случае представляют числа n и e.

Закрытый ключ образуют числа p, q, j(n) и d. Очевидно, что знание хотя бы одного из этих значений приводит к вычислению всех остальных.

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