Схема интерполяционных многочленов Лагранжа

Для создания пороговой схема Ади Шамир воспользовался уравнениями для многочленов в конечном поле [1414]. Выберем простое число p, которое больше количества возможных теней и больше самого большого из возможных секретов. Чтобы сделать секрет общим, сгенерируем произвольный многочлен степени m-1. Например, если нужно создать пороговую схему (3,n) (для восстановления M потребуется три тени), генерируется квадратичный многочлен

(ax² + bx+ M)mod p

где p - это случайное простое число, большее любого из коэффициентов. Коэффициенты aи bвыбираются случайным образом, они хранятся в тайне и отбрасываются после того, как распределяются тени. M- это сообщение. Простое число должно быть опубликовано. Тени получаются с помощью вычисления многочлена в nразличных точках:

k_i =F(x_i)

Другими словами, первой тенью может быть значение многочлена при x= 1, второй тенью - значение многочлена при x= 2, и т.д.

Так как в квадратичных многочленах три неизвестных коэффициента, a, b и M, для создания трех уравнений можно использовать любые три цели. Одной или двух теней не хватит, а четырех или пяти теней будет много.

Например, пусть Mравно 11. Чтобы создать пороговую схему (3, 5), в которой любые трое из пяти человек могут восстановить M, сначала получим квадратичное уравнение (7 и 8 - случайно выбранные числа chosen randomly):

F(x)= (7x ² + 5x+ 11) mod 13

Пятью тенями являются:

k₁= F(1)= 7 + 8 + 11º 0 (mod 13)

k₂= F(2)= 28 + 16 + 11º 3 (mod 13)

k₃= F(3)= 63 + 24 + 11º 7 (mod 13)

k₄= F(4)= 112 + 32 + 11º 12 (mod 13)

k₅= F(5)= 175 + 40 + 11º 5 (mod 13)

Чтобы восстановить Mпо трем теням, например, k₂, k₃и k₅, решается система линейных уравнений:

a*2² + b*2 + M= 3 (mod 13)

a*3² + b*3 + M= 7 (mod 13)

a*5² + b*5 + M= 5 (mod 13)

Решением будут a= 7, b= 8 и M= 11. Итак, Mполучено.

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

F(x) = ax⁵ + bx⁴ + cx³ + dx² + ex + M (mod p)

Шесть человек могут шесть неизвестных (включая M),но пятерым не удастся узнать ничего об M.

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

Векторная схема

Джордж Блэкли (George Blakley) изобрел схему, использующую понятие точек в пространстве [182]. Сообщение определяется как точка в m-мерном пространстве. Каждая тень - это уравнение (m-1)-мерной гиперплоскости, содержащей эту точку.

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

Asmuth-Bloom

В этой схеме используются простые числа [65]. Для (m, n)-пороговой схемы выбирается большое простое число p, большее M. Затем выбираются числа, меньшие p - d₁, d₂, . . . d_n, для которых:

1. Значения d_iупорядочены по возрастанию, d_i < d_i+1

2. Каждое d_iвзаимно просто с любым другим d_i

3. d₁*d₂* . . .*d_m > p*d_n-m+2*d_n-m+3*. . .*d_n

Чтобы распределить тени, сначала выбирается случайное число r и вычисляется

M' = M + rp

Тенями, k_i, являются

k_i= M'mod d_i

Объединив любые mтеней, можно восстановить M, используя китайскую теорему об остатках, но это невозможно с помощью любых m-1 теней. Подробности приведены в [65].