Схема Бломса - Википедия - Bloms scheme

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

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

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

Протокол

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

Настройка протокола

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

Например:

${ displaystyle { begin {align} k & = 3 p & = 17 D & = { begin {pmatrix} 1 & 6 & 2 6 & 3 & 8 2 & 8 & 2 end {pmatrix}} mathrm {mod} 17 end {выровнено}}}$

Вставка нового участника

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

${ Displaystyle I _ { mathrm {Алиса}}, I _ { mathrm {Боб}} в 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 {align} g _ { mathrm {Alice}} & = DI _ { mathrm {Alice}} g _ { mathrm {Bob}} & = DI _ { mathrm {Bob}} end { выровнено}}}$

С помощью ${ displaystyle D}$ как описано выше:

${ displaystyle { begin {align} 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 {align}}}$

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

Вычисление общего ключа между Алисой и Бобом

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

Она вычисляет общий ключ ${ Displaystyle scriptstyle к _ { mathrm {Алиса / Боб}} = g _ { mathrm {Алиса}} ^ {T} I _ { mathrm {Боб}}}$, куда ${ displaystyle scriptstyle T}$ обозначает матрица транспонировать. Боб делает то же самое, используя свой закрытый ключ и ее идентификатор, давая тот же результат:

${ displaystyle k _ { mathrm {Alice / Bob}} = k _ { mathrm {Alice / Bob}} ^ {T} = (g _ { mathrm {Alice}} ^ {T} I _ { mathrm {Bob}} ) ^ {T} = (I _ { mathrm {Алиса}} ^ {T} D ^ {T} I _ { mathrm {Боб}}) ^ {T} = I _ { mathrm {Боб}} ^ {T} DI _ { mathrm {Алиса}} = k _ { mathrm {Боб / Алиса}}}$

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

${ displaystyle { begin {align} 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 {Боб / Алиса }} & = { 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 {align}}}$

Сопротивление атаке

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

Рекомендации