Основы современной криптографии

       

Криптосистема Ривеста-Шамира-Эйделмана


Система Ривеста-Шамира-Эйделмана (Rivest, Shamir, Adlеman – RSA) представляет собой криптосистему, стойкость которой основана на сложности решения задачи разложения числа на простые сомножители. Кратко алгоритм можно описать следующим образом:

Пользователь A выбирает пару различных простых чисел pA

и qA , вычисляет nA = pAqA

и выбирает число dA, такое что НОД(dA, j(nA)) = 1, где j(n) – функция Эйлера (количество чисел, меньших n и взаимно простых с n. Если n= pq, где p и q – простые числа, то j(n) = (p ? 1)(q ? 1)). Затем он вычисляет величину eA, такую, что dAЧeA = 1 (mod j(nA)), и размещает в общедоступной справочной таблице пару (eA, nA), являющуюся открытым ключом пользователя A.

Теперь пользователь B, желая передать сообщение пользователю A, представляет исходный текст

x = (x0, x1, ..., xn–1), x О Zn , 0 Ј i < n,

по основанию nA:

N = c0+c1 nA+....

Пользователь В зашифровывает текст при передаче его пользователю А, применяя к коэффициентам сi отображение

:

,

получая зашифрованное сообщение N'. В силу выбора чисел dA и eA, отображение

является взаимно однозначным, и обратным к нему будет отображение

Пользователь А производит расшифрование полученного сообщения N', применяя

.

Для того чтобы найти отображение

, обратное по отношению к
, требуется знание множителей nA = pAqA. Время выполнения наилучших из известных алгоритмов разложения при n > 10145 на сегодняшний день выходит за пределы современных технологических возможностей.



Содержание раздела