Шифрование с открытым ключом (асимметричное)

Есть два ключа: $e$ - для шифрования и $d$ - для дешифрования. $e$ известнен $A$. $R$ генерирует пару ключей $e$ и $d$ и публикует ключ $e$. И предлагает шифровать сообщения себе этим ключом.

Условие корректности: $Pr\{D(E(x, e), d) = x\} \simeq 1$.
Условие надежности: $(e, E(x, e))$ и $(e, E(x', e))$ вычислительно не отличимы.

Инструмент: одностороние перестановки с секретом (trapdoor one-way permutations). В одну сторону их вычислить легко, в другую - трудно, но легко с секретом.

Формальное определение

4 функции:

• $K$ - генератор номера функции и секрета

• $S$ - выбор случайной точки $0.0$

• $F$ - вычисление значение функции

• $B$ - при известном значении секрета вычисляет преобразования

Все эти функции полиномиальные, две из них обязательно вероятностные.

Теорема

Если существует одностороняя перестановка с секретом, то существует односторонняя перестановка с секретом и трудным битом.

Замечание

Теорема доказывается аналогично теоремы с прошлого занятия (секрет останется тем же самым).

Примеры (предположительные):

1. Функция Рабина
   $x \mapsto x^2 (mod\ pq)$, где $p, q$ - простные числа вида $4k + 3$, $x$ - квадратичный вычет.
   Открытый ключ - $p * q$, закрытый ключ - $(p, q)$.
   Если секрет известен, то по $z = x^2$ можно восстановить $x$. А $x = t^2$. Поэтому $z^{\frac{p + 1}{4}} = t^{p + 1} \equiv t^2 \equiv x (mod\ p)$
   $z^{\frac{q + 1}{4}} \equiv x (mod\ q)$. Из последних двух сравнений по китайской теореме об остатках можно найти $x$.

2. Функция RSA:
   $x \mapsto x^z (mod\ pq)$, где $p, q$ - простые, $(z, \varphi(pq)) = 1$
   Секрет $u$ берем из $z\cdot u = 1\ (mod\ \varphi(p, q))$
   $(x^z)^u = x^{x\cdot u} = x^{\varphi(pq)\cdot k + 1} \equiv x\cdot 1^k = x\ (mod pq)$

Оба примера основываются на том, что предположительно нельзя быстро раскладывать на простые множители.

Построение схемы шифрования с открытым ключом:
$1$ бит $b \in \{0, 1\}$. Пусть $q_{\alpha}(x)$ - одностороняя перестановка с секретом,
$h_{\alpha}(x)$ - трудный бит для этой перестановки. $$b \mapsto (g_{\alpha(x)}, h_{\alpha}(x) \oplus b)$$

Проверим условие надежности:
$(g_{\alpha(x)}, h_{\alpha}(x) \oplus b)$ - псевдо-случайная строка длины $n + 1$ (ибо если $h_{\alpha}$ - трудный бит, то и $h_{\alpha} \oplus 1$ - трудный бит)
Если много битов:
$$b_1, \ldots, b_k \mapsto (b_1 \oplus h_{\alpha}(x), b_1 \oplus h_{\alpha}(g_{\alpha}(x))), \ldots, b_k \oplus h_{\alpha}(g_{\alpha}^{k - 1}(x), g_{\alpha}^k(x))$$ Доказательство надежности похоже на доказательство вычислимой неотличимости в генераторах. Нужно идти с конца.