Алгоритмы разделения секрета
Тени получаются с помощью вычисления многочлена в 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 2 + 5x + 11) mod 13 Пятью тенями являются: k1 = F(1) = 7 + 8 + 11≡ 0 (mod 13) k 2 = F(2) = 28 + 16 + 11≡ 3 (mod 13) k3 = F(3) = 63 + 24 + 11≡ 7 (mod 13) k 4 = F(4) = 112 + 32 + 11≡ 12 (mod 13) k 5 = F(5) = 175 + 40 + 11≡ 5 (mod 13) Чтобы восстановить M по трем теням, например, k 2, k 3 и k 5, решается система линейных уравнений: a*2 2 + b*2 + M = 3 (mod 13) a*3 2 + b*3 + M = 7 (mod 13) a*5 2 + b*5 + M = 5 (mod 13) Решением будут a = 7, b = 8 и M = 11. Итак, M получено. Эту схему разделения можно легко реализовать для больших чисел . Если вы хотите разбить сообщение на 30 равных частей так, чтобы восстановить сообщение можно было, объединив любые шесть из них , выдайте каждому из 30 человек значения многочлена пятой степени. F(x) = ax 5 + bx 4 + cx 3 + dx 2 + ex + M (mod p) Шесть человек могут шесть неизвестных (включая M), но пятерым не удастся узнать ничего об M. Наиболее впечатляющим моментом совместного использования секрета является то, что, если коэффициенты выбраны случайным образом, пять человек даже при помощи бесконечных вычислительных мощностей не смогут узнать ничего, кроме длины сообщения (которая и так им известна).
Slaidy.com
