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

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

(ах² + Ьх + Щтойр

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

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

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

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

F(x) = (7x ² + 5x +ll) modl3

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

к_х = F(l) = 7 + 8 + 11=0 (mod 13)

к₂ = 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)

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

fl*2² + ft*2 + M = 3 (modl3)

fl*3² + ft*3 + M = 7 (modl3)

fl*5² + ft*5 + M = 5 (modl3)

Решением будут а = 1, 6 = 8 и М = 11. Итак, М получено.

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

F(x) = ах⁵ + bx⁴ + ex³ + dx² + ex + M (mod/;)

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

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

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

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

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