1.3.2.2 Алгоритм шифрования RSA
RSA
– криптографический алгоритм с открытым ключом,
основывающийся на вычислительной сложности задачи факторизации больших
целых чисел. RSA является первым алгоритмом шифрования с открытым
ключом. Название системы происходит от первых букв фамилий ее авторов –
Рональд Ривест, Ади Шамир и Леонард Адлеман – трех ученых из
Массачусетского технологического института.
После изучения опубликованной в 1976 году статьи Уитфилда Диффи и
Мартина Хеллмана «Новые направления в криптографии», которая заложила
основы криптографии с открытым ключом, Ривест, Шамир и Адлеман
приступили к поискам математической функции, которая позволяла бы
реализовать модель системы, описанной в статье. После работы над более чем
40 возможными вариантами, ученым удалось обнаружить алгоритм,
основывающийся на том, насколько легко находить большие простые числа и
насколько сложно раскладывать на множители произведение двух больших
простых чисел.
Для шифрования используется простая операция возведения в степень
по модулю N. Для расшифрования необходимо вычислить функцию Эйлера от
числа N, для этого необходимо знать разложение числа N на простые
множители (в этом состоит задача факторизации). В криптографической
системе RSA открытый и закрытый ключи состоят из пары целых чисел.
Закрытый ключ хранится в секрете, а открытый сообщается другому участнику,
или где-то публикуется[15].
Система базируется на следующих фактах:
При известных числах b и d вычисление числа a из сравнения
(2.1)
По составному модулю n – это простая задача;
23
Вычисление неизвестного числа b при известных числах d и a из
сравнения по составному модулю n
(2.2)
является трудной задачей;
Если известно, что p и q простые числа и n = pq, то вычислить n
легко, а найти разложение n на простые множители трудно;
Если известно разложение n = pq на простые множители, то задача
вычисления числа b из уравнения
(2.3)
выполнима.
Теоретической основой криптосистемы RSA является теорема Эйлера:
для любых натуральных и взаимно простых чисел n и a справедливо равенство
(2.4)
Здесь
есть функция Эйлера – количество взаимно простых с n
натуральных чисел от 1 до n.
Из теории чисел известно, что если p и q простые числа, а n = pq, то
(2.5)
Кроме того, из теоремы Эйлера следует, что если некоторое число e
взаимно просто с
, то уравнение
(2.6)
или иначе
(2.7)
однозначно разрешается относительно d. Решение легко определяется
расширенным алгоритмом Евклида.
Итак, если известно, что
24
(2.8)
а x – передаваемая информация, то справедливо равенство
(2.9)
Фактически, последнее соотношение является основой для формулировки
системы RSA.
Достарыңызбен бөлісу: |