Схема Блома

Схема Блома — это симметричный пороговый протокол обмена ключами в криптографии . Схема была предложена шведским криптографом Рольфом Бломом в серии статей в начале 1980-х годов. ^{[1] [2]}

Доверенная сторона дает каждому участнику секретный ключ и открытый идентификатор, что позволяет любым двум участникам независимо создать общий ключ для общения. Однако, если злоумышленник может скомпрометировать ключи по крайней мере k пользователей, он может взломать схему и восстановить каждый общий ключ. Схема Блома является формой порогового разделения секрета .

Схема Блома в настоящее время используется схемой защиты от копирования HDCP (только версия 1.x) для генерации общих ключей для источников и приемников контента высокой четкости, таких как проигрыватели HD DVD и телевизоры высокой четкости . ^[3]

Протокол обмена ключами включает доверенную сторону (Трент) и группу пользователей. Пусть Алиса и Боб будут двумя пользователями группы.${\displaystyle \scriptstyle n}$

Трент выбирает случайную и секретную симметричную матрицу над конечным полем , где p — простое число. требуется, когда новый пользователь должен быть добавлен в группу совместного использования ключей.${\displaystyle \scriptstyle D_{k,k}}$ ${\displaystyle \scriptstyle GF(p)}$${\displaystyle \scriptstyle D}$

Например:

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

Новые пользователи Алиса и Боб хотят присоединиться к группе обмена ключами. Трент выбирает публичные идентификаторы для каждого из них; т.е. векторы k-элементов:

${\displaystyle I_{\mathrm {Alice} },I_{\mathrm {Bob} }\in GF^{k}(p)}$.

Например:

${\displaystyle I_{\mathrm {Alice} }={\begin{pmatrix}1\\2\\3\end{pmatrix}},I_{\mathrm {Bob} }={\begin{pmatrix}5\\3\\1\end{pmatrix}}}$

Затем Трент вычисляет их закрытые ключи:

${\displaystyle {\begin{aligned}g_{\mathrm {Alice} }&=DI_{\mathrm {Alice} }\\g_{\mathrm {Bob} }&=DI_{\mathrm {Bob} }\end{aligned}}}$

Используя, как описано выше:${\displaystyle D}$

${\displaystyle {\begin{aligned}g_{\mathrm {Alice} }&={\begin{pmatrix}1&6&2\\6&3&8\\2&8&2\end{pmatrix}}{\begin{pmatrix}1\\2\\3\end{pmatrix}}={\begin{pmatrix}19\\36\\24\end{pmatrix}}\ \mathrm {mod} \ 17={\begin{pmatrix}2\\2\\7\end{pmatrix}}\ \\g_{\mathrm {Bob} }&={\begin{pmatrix}1&6&2\\6&3&8\\2&8&2\end{pmatrix}}{\begin{pmatrix}5\\3\\1\end{pmatrix}}={\begin{pmatrix}25\\47\\36\end{pmatrix}}\ \mathrm {mod} \ 17={\begin{pmatrix}8\\13\\2\end{pmatrix}}\ \end{aligned}}}$

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

Теперь Алиса и Боб хотят общаться друг с другом. У Алисы есть идентификатор Боба и ее закрытый ключ .${\displaystyle \scriptstyle I_{\mathrm {Bob} }}$${\displaystyle \scriptstyle g_{\mathrm {Alice} }}$

Она вычисляет общий ключ , где обозначает транспонирование матрицы . Боб делает то же самое, используя свой закрытый ключ и ее идентификатор, что дает тот же результат:${\displaystyle \scriptstyle k_{\mathrm {Alice/Bob} }=g_{\mathrm {Alice} }^{T}I_{\mathrm {Bob} }}$${\displaystyle \scriptstyle T}$

${\displaystyle k_{\mathrm {Alice/Bob} }=k_{\mathrm {Alice/Bob} }^{T}=(g_{\mathrm {Alice} }^{T}I_{\mathrm {Bob} })^{T}=(I_{\mathrm {Alice} }^{T}D^{T}I_{\mathrm {Bob} })^{T}=I_{\mathrm {Bob} }^{T}DI_{\mathrm {Alice} }=k_{\mathrm {Bob/Alice} }}$

Каждый из них сгенерирует свой общий ключ следующим образом:

${\displaystyle {\begin{aligned}k_{\mathrm {Alice/Bob} }&={\begin{pmatrix}2\\2\\7\end{pmatrix}}^{T}{\begin{pmatrix}5\\3\\1\end{pmatrix}}=2\times 5+2\times 3+7\times 1=23\ \mathrm {mod} \ 17=6\\k_{\mathrm {Bob/Alice} }&={\begin{pmatrix}8\\13\\2\end{pmatrix}}^{T}{\begin{pmatrix}1\\2\\3\end{pmatrix}}=8\times 1+13\times 2+2\times 3=40\ \mathrm {mod} \ 17=6\end{aligned}}}$

Чтобы гарантировать, что по крайней мере k ключей должны быть скомпрометированы, прежде чем каждый общий ключ может быть вычислен злоумышленником, идентификаторы должны быть k-линейно независимыми: все наборы из k случайно выбранных идентификаторов пользователей должны быть линейно независимыми. В противном случае группа злонамеренных пользователей может вычислить ключ любого другого участника, идентификатор которого линейно зависит от их идентификатора. Чтобы гарантировать это свойство, идентификаторы предпочтительно должны быть выбраны из матрицы MDS-Code (матрица кода исправления ошибок с максимальным расстоянием разделения). Строки матрицы MDS будут идентификаторами пользователей. Матрицу MDS-Code можно выбрать на практике с использованием кодовой матрицы кода исправления ошибок Рида-Соломона (этот код исправления ошибок требует только легко понимаемой математики и может быть вычислен чрезвычайно быстро). ^[4]