bloms_scheme.tex

\subsection{Схема Блома распределения парных ключей}
\selectlanguage{russian}

Рассмотрим распределение ключей по \textbf{схеме Блома}\index{распределение секрета!Блома} (Blom), в которой каждые два пользователя из общего числа $N$ пользователей имеют доступ к общему секретному ключу, ключи различных пар различны.

По-прежнему,
    \[ \{ U_1, U_2, \dots, U_N \} \]
легальные пользователи, $\Z_p$ -- кольцо целых чисел.

Построим симметричный многочлен
    \[ f(x,y) = \sum_{i=1}^k \sum_{j=1}^k a_{ij} x^i y^j, \]
    \[ a_{ij} \in \Z_p, ~ a_{ij} = a_{ji}. \]

Возьмем набор чисел $r_1, r_2, \dots, r_N$, где $r_i$ -- открытый ключ пользователя $U_i$, ~ $r_i \in \Z_p$.

Каждый пользователь $U_i$ получает многочлен $f(x,y)$ и вместо $y$ подставляет свое значение $r_i$, так что получается $N$ многочленов $f(x, r_i), ~ i = 1, 2, \dots, N$.

Каждые два участника коалиции должны иметь общий ключ. Пусть, например, $U_1$ и $U_2$ хотят создать общий ключ. Тогда пользователь $U_1$, используя $f(x, r_1)$ и зная $r_2$, вычисляет
    \[ K_{21} = f(r_2, r_1). \]

Пользователь $U_2$, используя $f(x, r_2)$ и зная $r_1$, вычисляет
    \[ K_{12} = f(r_1, r_2). \]

Так как для выбранного многочлена справедливо равенство
    \[ f(r_1, r_2) = f(r_2, r_1), \]
то
    \[ K_{12} = K_{21}. \]
Таким образом, два участника коалиции создали общий ключ. Таким же образом поступают и другие пары пользователей. Третий пользователь, не участник коалиции, не может подобрать ключ, так как это представляет собой трудную задачу в вычислительном смысле.

%\section{Пример предварительного распределения ключей и разделения секрета в схеме Блома в виде многочленов}
\example
В схеме распределения ключей Блома для $N=4$ пользователей доверенный центр выбирает:
\begin{enumerate}
    \item модуль $p = 17$ поля $\GF{p}$;
    \item свой секретный симметричный многочлен от двух переменных
        \[ f(x,y) = a + b (x + y) + c x y \mod p \]
        над полем $\GF{p}$;
    \item открытые ключи для каждого пользователя
        \[ r_1 = 5, ~ r_2 = 9, ~ r_3 = 14, ~ r_4 = 3; \]
    \item вычисляет и секретно раздает многочлен $S_i(x)$ каждому пользователю $U_i$:
        \[ \begin{array}{l}
            S_1(x) = f(x, r_1) = 1 + 2x \mod p, \\
            S_2(x) = f(x, r_2) = 3 + 10x \mod p, \\
            S_3(x) = f(x, r_3) = 14 + 3x \mod p, \\
            S_4(x) = f(x, r_4) = 0 + 15x \mod p. \\
        \end{array} \]
\end{enumerate}
Найдем ключи и восстановим секретный многочлен доверенного центра.

Секретные сеансовые ключи пользователей равны
    \[ K_{ij} = K_{ji} = S_i(r_j) = S_j(r_i): \]
\[ \begin{array}{lcl}
    K_{12} = K_{21} = 2, & & K_{13} = K_{31} = 12, \\
    K_{14} = K_{41} = 7, & & K_{23} = K_{32} = 7, \\
    K_{24} = K_{42} = 16, & & K_{34} = K_{43} = 6. \\
\end{array} \]

По любым 3 многочленам пользователей можно восстановить секретный многочлен Центра. Коэффициенты секретного многочлена Центра равны $a=7, b=9, c=2$.
\exampleend

%\section{Схема предварительного распределения ключей и разделения секрета Блома}
%
%Центр выбирает секретную симметрическую $(k \times k)$-матрицу $F$ над полем $\GF{p}$, где $p$ -- простое. Каждому пользователю $i$ Центр создает и выдает открытый ключ $P_i$, который является $k$-мерным вектором над $\GF{p}$, и секретный ключ $S_i = F \cdot P_i$, $k$-мерный вектор.
%
%Когда два пользователя $i$ и $j$ хотят создать секретный сессионный ключ для обмена сообщениями, они обмениваются открытыми ключами $P_i, P_j$ и вычисляют секретный сессионный ключ $K_{ij} = S_i P_j^T = S_j P_i^T$.
%
%%Если известны открытые ключи $k$ пользователей, то...
%%TODO
%
%%Схема Блома используется в High-bandwidth Digital Content Protection (HDCP), разрботанной Intel для применения в DVD плеерах и телевидении высокой четкости.