1.7. Схемы разделения секрета

Первый путь - сделать несколько копий этих данных и хранить их в разных местах.

Второй путь - разделить секрет на несколько частей и хранить их в разных местах, при необходимости собирая вместе. Самый простой способ разделить секрет j на и частей - выбрать п-1 случайное число , а п-ю часть определить так:

sn = s © s{ © s2 ©...© . Каждое число sni = 1,п носит название

доли секрета (share). Доли создает носитель секрета s. Иногда это один из п участников, получающих доли, иногда - постороннее лицо, которое в этом случае называется дилером. Каждая доля s( должна быть передана соответствующему участнику конфиденциально. Если эту долю видят и другие участники протокола, эта схема уже не работает. Для восстановления секрета s необходимо присутствие всех п сторон, имеющих доли секрета, которые должны выполнить операцию сложения: s = Sj © s2 ©... © sn. Так приходим к идее схем

разделения секрета (secret sharing scheme) - сокращенно СРС. Такая схема обеспечивает высокую конфиденциальность (чтобы восстано-вить секрет, надо получить все его доли), но низкую надежность (если потеряна хотя бы одна доля, восстановить секрет уже будет невозможно).

Мы хотим построить более гибкую схему. Пусть есть п участни-ков криптосистемы. Мы хотим, чтобы любые t из них могли восста-новить секрет, но никакие г-1 из них не смогли бы получить ин-формацию о секрете. Число t (tИзвестны несколько математических методов реализации такой схемы.

Схема Шамира (A. Shamir, 1979) основана на хорошо известном математическом факте, который заключается в том, что через любые t точек на плоскости можно провести бесконечное множество кри-вых, описываемых многочленом г-го порядка, но через любые я-1 различные точки можно провести только единственную кривую, описываемую многочленом t-го порядка. Так, через любую точку на плоскости проходит бесконечное множество прямых линий, но через две различные точки - только единственная. Через любые две точки можно провести бесконечное множество парабол, но через любые три различные точки - только одну и т. д. Таким образом, если каждому из участников криптосистемы «выдать» по одной точке, то восстановить кривую можно будет только при достаточном коли-честве участников.

Схема Блейкли (A. Blackley, 1979) основана на следующих гео-метрических фактах. Одна прямая на плоскости описывает беско-нечное множество точек, но любые две непараллельные прямые задают единственную точку их пересечения. Любые две некомпланарные плоскости в трехмерном пространстве пересекаются по прямой, которая задает бесконечное множество точек, но любые три неком-планарные плоскости пересекаются в единственной точке. Эти на-блюдения по аналогии можно продолжить и в пространствах больших размерностей. Если каждому из участников криптосистемы «выдать» по одному уравнению плоскости (или гиперплоскости в пространствах размерности больше трех), то определить единственную точку их пересечения можно будет опять-таки при достаточном числе этих уравнений. В схеме Блейкли увеличение числа участни-ков сопровождается ростом размерности пространства, в котором решается задача, что усложняет решение системы уравнений.

В криптосистемах широко используется пороговая СРС Шамира, так как она допускает удобную геометрическую интерпретацию

74 Запечников С. В. Криптографические протоколы и их применение

и легко обобщается для многочленов над конечными полями.

Интерполируемость. По данным t точкам многочлена: (х,, у,),...,(х,,_у,), где все х,,...,х, различны, yt = / (х,-), можно найти его коэффициенты a0,ait...,at_x. Алгоритм, делающий это, называется алгоритмом интерполяции.

2. Секретность. По данным любым f-І точкам полинома: где у. =/(х;.), никто не может ничего предполагать об а0 - свободном члене f(x).

Эти свойства делают многочлены над конечными полями инст-рументом для построения пороговых криптосистем.

Рассмотрим (t,n)-nopozoeyro СРС Шамира над полем Zp, где р - большое простое число. Схема включает несколько протоколов.

Фаза инициализации. Дилер D выбирает п различных ненулевых элементов поля Zp, которые обозначаются х,-, 1 < / < л, р > п +1; это

точки, к которым «привязаны» участники. Часто выбирают х} = і,

т. е. просто всем участникам схемы присваиваются порядковые но-мера. D передает х\ участнику Pt. Распределение долей:

D хочет разделить секретный ключ К Є Zp \ D секретно, случайно и независимо друг от друга выбирает t-І элемент поля av...,at_lt где af є Zp .

D конструирует многочлен степени, меньшей либо равной t-1,

/-і

и вычисляет для / = 1,л : у} =a(xj), где а (х) = К + ^атхт (mod р),

т=]

т. е. К = а(о). Коэффициенты многочлена дилер хранит в секрете.

Дилер по секретному и аутентичному каналу рассылает каждую ИЗ долей Уі соответствующему участнику Pi для всех / = 1,л .

1. Базовые криптографические протоколы 75

Восстановление секрета возможно двумя способами. I способ. Предположим, участники Р^Pt хотят восстановить

секретный ключ К. Они имеют , уч j и знают, что yif = а{х^ = l,t, где a(x)e Zp [jc] - неизвестный многочлен, вы-бранный D. Так как имеет степень, меньшую либо равную t-1, а(х) может быть записан в виде

а(х)-aQ + ахх + ... +

где а- неизвестные элементы поля Zp и а0 = К.

Они получают систему t линейных уравнений с t неизвестными над полем Zp:

/-і

«1=1

Если уравнения линейно независимы, система имеет единственное решение.

Утверждение. (г,л)-пороговая СРС Шамира позволяет одно-значно восстанавливать секрет любой группе из t участников схемы и обеспечивает совершенную секретность (теоретико-информационную стойкость) против попытки вычисления секрета любой группой из j участников, обладающих неограниченной вычислительной мощностью (jДоказательство. У каждого участника схемы есть пара точек:

{хіґУі]1Уі, =a[xiJ)j = l't > где a(x) = a0+a1x + ...+al^xf~l, ай = К. По-лучается следующая система линейных уравнений, решаемая в Zp\

aQ +alXii +a2xl + = yk,

а0 +a]Xi_ +а2х* +... + а1_1х'.~1 = у.,

или в матричной форме:

1 xit xl

В левой части системы стоит матрица коэффициентов А, имеющая специальный вид: каждая j-я ее строка состоит из коэффициентов х, , последовательно возводимых во все степени от 0 до ґ-1.

v

так называемая матрица Вандермонда. Ее определитель вычисляется по формуле

вычисля-

ется в поле Zp. Произведение ненулевых элементов в поле всегда от-лично от нуля. Следовательно, detАФО. Следовательно, система имеет единственное решение над полем Zp, а значит, любая группа из t участников может однозначно восстановить ключ К - а0.

Пусть теперь группа из t-1 участников Р^Р^ ( пытается вы-числить К.

Следовательно, для каждого предполагаемого значения ключа

существует полином

эффициенты которого получены из решения системы.

Таких поли-номов существует столько же, сколько может быть различных зна-чений ключа К = у0

можно с вероятностью 1/2'*' и соответствует понятию о теоретико- информационной безопасности криптосистемы по Шеннону. Ут-верждение доказано.

II способ. Восстановить разделенный секрет можно и другим, более простым способом. Воспользуемся интерполяционной формулой Лагранжа

Х-Х; 'і

1 1 Мы имеем t пар чисел , ) у = 1,/, и доказали, что много-член единственный. Следовательно, формула Лагранжа даст нам единственно верный результат.

Формулу можно упростить, так как участникам группы не нужно вычислять все коэффициенты многочлена, а только свободный член К = д(0):

7=1 1<*Обозначим коэффициенты интерполяции в формуле Лагранжа:

1 &kОни могут быть вычислены предварительно, так как все ximixik общеизвестны. Остается вычислить ключ как линейную ком-бинацию г долей секрета:

К - Іb,yh ¦

7=1