Система Orphus

Возможность использования односторонних функций в криптографии

Применение односторонних функций с потайным входом

RSA

Возьмем число n = p \cdot q, где p и q простые числа. Считается, что для данного числа n вычисление p и q является математически трудной задачей.

Рассмотрим функцию шифрования RSA

E(m) = m^e~\bmod~n,

где e — взаимно простое с (p-1)(q-1).

Числа p и q являются потайным входом, зная которые легко вычислить обратную функцию E^{-1}.

Функция Рабина

Пусть n=p\cdot q, где p и q - простые числа. Рассмотрим функцию

f(x) = x^2~\bmod~n.

Рабин показал, что вычислить функцию f^{-1} легко тогда и только тогда, когда разложение на множители числа n является простой задачей.

Схема Эль-Гамаля

Данная схема была предложена Тахером Эль-Гамалем в 1984 году. Она основывается на задаче дискретного логарифмирования.

Алгоритм

  1. Алиса выбирает простое чисто p и произвольное число a.
  2. Алиса вычисляет свой открытый ключ (a,b), где b=a^{c}, 1<c<p
  3. Боб выбирает 1<d<p и шифрует сообщение m: (m_1,m_2) = (a^d, m\cdot b^d)
  4. Алиса расшифровывает сообщение m = m_2\cdot(m_1^{c})^{-1}.

Система Orphus

Комментарии