Криптосистема Ривеста-Шамира-Эйделмана
Система Ривеста-Шамира-Эйделмана (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', применяя
Для того чтобы найти отображение
