Линейное разделение секрета
Начнем с предложенной Шамиром элегантной схемы разделения секрета для пороговых структур доступа. Пусть К = GF(q) — конечное поле из q элементов (например, q = p — простое число и К = Zp) и q > n. Сопоставим участникам n различных ненулевых элементов поля {a1, …, an} и положим a0 = 0. При распределении секрета s0
дилер СРС генерирует k–1 независимых равномерно распределенных на GF(q) случайных величин fj (j = 1, …, k–1) и посылает і-му учаснику (і = 1, ..., n) “его” значение si = f(ai) многочлена f(x) = f0
+ f1x + … + fk-1xk-1, где f0 = s0. Поскольку любой многочлен степени k-1 однозначно восстанавливается по его значениям в произвольных k точках (например, по интерполяционной формуле Лагранжа), то любые k участников вместе могут восстановить многочлен f(x) и, следовательно, найти значение секрета как s0 = f(0). По этой же причине для любых k–1 участников, любых полученных ими значений проекций si и любого значения секрета s0 существует ровно один “соответствующий” им многочлен, т.е. такой, что si = f(ai) и s0 = f(0). Следовательно, эта схема является совершенной в соответствии с определением 2. “Линейность” данной схемы становится ясна, если записать “разделение секрета” в векторно-матричном виде:
s = fH, (18.3)
где s = (s0, …, sn), f = (f0, …, fk–1), k× (n+1) — матрица H = (hij) = (aij-1) и h00 = 1. Заметим, что любые k столбцов этой матрицы линейно независимы, а максимально возможное число столбцов матрицы H равно q, чтобы добиться обещанного значения q+1 надо добавить столбец, соответствующий точке “бесконечность”.
Возьмем в (18.3) в качестве H произвольную r × (n + 1)-матрицу с элементами из поля K. Получаемую СРС, будем называть одномерной линейной СРС. Она является совершенной комбинаторной СРС со структурой доступа Г, состоящей из множеств А таких, что вектор h0
представим в виде линейной комбинации векторов {hj: j Î A}, где hj — это j-ый столбец матрицы H.
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий