Схема Блома

Схема Блома — в криптографии, схема распределения ключей.

В схеме Блома доверенная сторона раздаёт каждому участнику открытый и закрытый ключ. Участники, обмениваясь между собой только открытыми ключами по незащищённым каналам связи, могут сгенерировать секретный сеансовый ключ для общения между собой.

Надёжность схемы напрямую зависит от размера секретной матрицы, используемой в схеме. Для восстановления секретной матрицы (точнее, любой выполняющей аналогичную функцию) необходимо иметь число ключей, равное количеству строк матрицы.

Схема используется в протоколе HDCP в целях защиты видео от копирования.

Описание протокола

Инициализация

Доверенная сторона выбирает симметричную матрицу <math>D_{k,k}</math> над конечным полем <math>GF\left( p \right)</math>.

Добавление участника

Когда новый участник хочет присоединиться к группе, доверенная сторона выбирает для него новый открытый ключ, который представляет собой вектор (столбец) <math>I</math> размера <math>k</math>. Далее доверенная сторона вычисляет закрытый ключ <math>g</math>:

<math>g=D_{k,k}I</math>

Открытый и закрытый ключ сообщаются участнику по надёжному каналу без прослушивания.

Установление сессии

Если два участника хотят установить между собой секретный канал, они посылают друг другу по открытому каналу свои открытые ключи. Далее каждый из них умножает свой закрытый ключ на открытый ключ другой стороны. Если <math>I_A, g_A</math> — открытый и закрытый ключ одной стороны, <math>I_B, g_B</math> — ключи другой стороны, то:

<math>\begin{align}

s_A &= (g^t_A I_B)^t &= (I^t_A D I_B)^t &= I^t_B D I_A\\
s_B &= (g^t_B I_A)^t &= (I^t_B D I_A)^t &= I^t_A D I_B\\
s_A &= s_B \\

\end{align}</math>

В результате у них получится одно и тоже число (это следует из симметричности матрицы <math>D</math>), которое и будет использоваться как общий сеансовый ключ.

Надёжность схемы

Для вычисления общего секретного ключа двух сторон нужно знать секретную матрицу. Её можно восстановить, если получить <math>k</math> линейно независимых идентификаторов.

Пример

Инициализация

Доверенный центр выбирает размер конечного поля и секретную матрицу:

<math>\begin{align}

p &= 17\\
D &= \begin{pmatrix} 1&6&2\\6&3&8\\2&8&2\end{pmatrix}\ \mathrm{mod}\ 17

\end{align}</math> Алиса и Боб выбирают себе идентификаторы (также могут выдаваться доверенным центром):

<math>I_{\mathrm{Alice}} = \begin{pmatrix} 3 \\ 10 \\ 11 \end{pmatrix}, I_{\mathrm{Bob}} = \begin{pmatrix} 1 \\ 3 \\ 15 \end{pmatrix}</math>

Доверенный центр вычисляет Алисе и Бобу закрытые ключи:

<math>\begin{align}

g_{\mathrm{Alice}} &= DI_{\mathrm{Alice}} &= \begin{pmatrix} 1&6&2\\6&3&8\\2&8&2\end{pmatrix}\begin{pmatrix} 3 \\ 10 \\ 11 \end{pmatrix} &= \begin{pmatrix} 0\\0\\6\end{pmatrix}\ \mathrm{mod}\ 17\\
g_{\mathrm{Bob}} &= DI_{\mathrm{Bob}} &= \begin{pmatrix} 1&6&2\\6&3&8\\2&8&2\end{pmatrix}\begin{pmatrix} 1 \\ 3 \\ 15 \end{pmatrix} &= \begin{pmatrix} 15\\16\\5\end{pmatrix}\ \mathrm{mod}\ 17

\end{align}</math>

Вычисление общего секретного ключа

Пусть теперь Алисе и Бобу нужно вычислить общий секретный ключ. Алиса передаёт Бобу свой идентификатор, а Боб — свой Алисе. После чего каждая из сторон вычисляет секретный ключ, умножая свой закрытый ключ на идентификатор второй стороны:

<math>\begin{align}

k_{\mathrm{Alice / Bob}} &= g_{\mathrm{Alice}}^t I_{\mathrm{Bob}} &= \begin{pmatrix} 0\\0\\6 \end{pmatrix}^t \begin{pmatrix} 1\\3\\15 \end{pmatrix} &= 0 \times 1 + 0 \times 3 + 6 \times 15 &= 5\ \mathrm{mod}\ 17\\
k_{\mathrm{Bob / Alice}} &= g_{\mathrm{Bob}}^t I_{\mathrm{Alice}} &= \begin{pmatrix} 15\\16\\5 \end{pmatrix}^t \begin{pmatrix} 3\\10\\11 \end{pmatrix} &= 15 \times 3 + 16 \times 10 + 5 \times 11& = 5\ \mathrm{mod}\ 17

\end{align}</math>

Отрывок, характеризующий Схема Блома

– Я видела княжну, – отвечала она. – Я слышала, что ее сватали за молодого Ростова. Это было бы очень хорошо для Ростовых; говорят, они совсем разорились.
– Нет, Ростову вы знаете?
– Слышала тогда только про эту историю. Очень жалко.
«Нет, она не понимает или притворяется, – подумал Пьер. – Лучше тоже не говорить ей».
Княжна также приготавливала провизию на дорогу Пьеру.
«Как они добры все, – думал Пьер, – что они теперь, когда уж наверное им это не может быть более интересно, занимаются всем этим. И все для меня; вот что удивительно».
В этот же день к Пьеру приехал полицеймейстер с предложением прислать доверенного в Грановитую палату для приема вещей, раздаваемых нынче владельцам.
«Вот и этот тоже, – думал Пьер, глядя в лицо полицеймейстера, – какой славный, красивый офицер и как добр! Теперь занимается такими пустяками. А еще говорят, что он не честен и пользуется. Какой вздор! А впрочем, отчего же ему и не пользоваться? Он так и воспитан. И все так делают. А такое приятное, доброе лицо, и улыбается, глядя на меня».
Пьер поехал обедать к княжне Марье.
Проезжая по улицам между пожарищами домов, он удивлялся красоте этих развалин. Печные трубы домов, отвалившиеся стены, живописно напоминая Рейн и Колизей, тянулись, скрывая друг друга, по обгорелым кварталам. Встречавшиеся извозчики и ездоки, плотники, рубившие срубы, торговки и лавочники, все с веселыми, сияющими лицами, взглядывали на Пьера и говорили как будто: «А, вот он! Посмотрим, что выйдет из этого».
При входе в дом княжны Марьи на Пьера нашло сомнение в справедливости того, что он был здесь вчера, виделся с Наташей и говорил с ней. «Может быть, это я выдумал. Может быть, я войду и никого не увижу». Но не успел он вступить в комнату, как уже во всем существе своем, по мгновенному лишению своей свободы, он почувствовал ее присутствие. Она была в том же черном платье с мягкими складками и так же причесана, как и вчера, но она была совсем другая. Если б она была такою вчера, когда он вошел в комнату, он бы не мог ни на мгновение не узнать ее.
Она была такою же, какою он знал ее почти ребенком и потом невестой князя Андрея. Веселый вопросительный блеск светился в ее глазах; на лице было ласковое и странно шаловливое выражение.
Пьер обедал и просидел бы весь вечер; но княжна Марья ехала ко всенощной, и Пьер уехал с ними вместе.
На другой день Пьер приехал рано, обедал и просидел весь вечер. Несмотря на то, что княжна Марья и Наташа были очевидно рады гостю; несмотря на то, что весь интерес жизни Пьера сосредоточивался теперь в этом доме, к вечеру они всё переговорили, и разговор переходил беспрестанно с одного ничтожного предмета на другой и часто прерывался. Пьер засиделся в этот вечер так поздно, что княжна Марья и Наташа переглядывались между собою, очевидно ожидая, скоро ли он уйдет. Пьер видел это и не мог уйти. Ему становилось тяжело, неловко, но он все сидел, потому что не мог подняться и уйти.
Княжна Марья, не предвидя этому конца, первая встала и, жалуясь на мигрень, стала прощаться.
– Так вы завтра едете в Петербург? – сказала ока.