Криптосистема Эль-Гамаля

Система Эль-Гамаля – это криптосистема с открытым ключом, основанная на проблеме логарифма. Система включает как алгоритм шифрования, так и алгоритм цифровой подписи.

Множество параметров системы включает простое число p и целое число g, степени которого по модулю p порождают большое число элементов Z_p. У пользователя A есть секретный ключ a и открытый ключ y, где y = g^a (mod p). Предположим, что пользователь B желает послать сообщение m пользователю A. Сначала B выбирает случайное число k, меньшее p. Затем он вычисляет

y₁ = g^k (mod p) и y₂ = m Е (y^k (mod p)),

где Е обозначает побитовое "исключающее ИЛИ". B посылает A пару (y₁, y₂).

После получения шифрованного текста пользователь A вычисляет

m = (y₁^a mod p) Е y₂.

Известен вариант этой схемы, когда операция Е заменяется на умножение по модулю p. Это удобнее в том смысле, что в первом случае текст (или значение хэш-функции) необходимо разбивать на блоки той же длины, что и число y^k (mod p). Во втором случае этого не требуется и можно обрабатывать блоки текста заранее заданной фиксированной длины (меньшей, чем длина числа p).

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

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

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

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

x = (x₀, x₁, ..., x_n–1), x О Z_n , 0 Ј i < n,

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

N = c₀+c₁ n_A+....

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

,

получая зашифрованное сообщение N'. В силу выбора чисел d_A и e_A, отображение является взаимно однозначным, и обратным к нему будет отображение

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

Для того чтобы найти отображение , обратное по отношению к , требуется знание множителей n_A = p_Aq_A. Время выполнения наилучших из известных алгоритмов разложения при n > 10¹⁴⁵ на сегодняшний день выходит за пределы современных технологических возможностей.