Визуализация деления секретов Шамира

Что такое схема разделения секрета Шамира?

Представьте, что вы хотите хранить пароль так, что никто его не знает. Но если несколько человек соберутся вместе, то пароль можно восстановить и применить.

По идее можно разрезать пароль на несколько частей и каждому владельцу дать только свой кусочек. Но что если один из владельцев не сможет передать свою часть по какой-то причине? Значит, владельцев должно быть больше, чем обязательных частей пароля. Например, 10 владельцев, где любые 6 из них могут восстановить пароль.

Именно такую схему разделения пароля (секрета) и придумал израильский математик Ади Шамир. В честь него она и названа.

Подробный алгоритм деления секретов Шамира описан в Википедии.
Мы же визуализируем идею, на которой он работает.

Полиномы

Полином — это функция вида

f (x) = \sum_{i = 0}^{n} a_{i} x^{i}

Где a_i — какие-то коэффициенты

Например:

5 — полином степени 0.
3x + 6 — полином степени 1.
6x² + 3x + 6 — полином степени 2.
19x³ + 17x² + 15x + 13 — полином степени 3.

Полезное свойство полиномов степени N

График полинома первой степени — прямая. Сколько таких прямых проходит через одну точку?

Бесконечно много.

А через две точки проходит только одна прямая.

График полинома второй степени — парабола. Сколько парабол проходит через одну точку?

Бесконечно много.

А через две точки? Снова бесконечно много.

А через три? Три точки задают единственную параболу.

То есть для восстановления полинома степени n достаточно n + 1 точек с разными x.

Переход к разделению секрета

На этом свойстве и основан принцип разделения секрета Шамира. Графики показывают восстановление полинома на обычных числах. В самой схеме для защиты секрета используют арифметику конечного поля.

Мы хотим разделить секретное число S на 5 частей так, чтоб любые 3 части могли восстановить его обратно
Заведём любую параболу, проходящую через точку (0, S)
Возьмём 5 точек с разными ненулевыми x и раздадим их 5 владельцам
Любые 3 части воссоздадут единственную исходную параболу
Посчитав значение этой параболы при x = 0, мы узнаем секрет S

А как кодировать строки?

Строки - это последовательность байтов. Байт в компьютере - это число от 0 до 255. Для каждого байта повторяется разделение секрета.

А как кодировать действительно длинные сообщения?

На практике длинное сообщение можно зашифровать с помощью AES, а затем разделить ключ по схеме Шамира. У AES-128 ключ занимает 16 байт.

Вместе с зашифрованным сообщением передают доли ключа.

Конкретный пример: 3 из 5 секретов восстанавливают исходный секрет

Как мы получили эти точки?

Алгоритм wiki говорит: для порога k нужен многочлен степени k − 1.
Для обязательных 3 частей секрета это полином степени 3-1 = 2.
Это парабола f(x) = ax² + bx + C. Свободный член C — наш секрет. Коэффициенты a и b выберем случайно, и получим какую-то параболу, проходящую через нашу точку.

Возьмём случайные a = 3 и b = 7 и наш секрет C = 15.
Получаем параболу f(x) = 3x² + 7x + 15.

Теперь подставим в неё пять разных значений x и получим точки, которые раздадим хранителям секрета:

f(1) = 25. Точка (1, 25)
f(2) = 41. Точка (2, 41)
f(3) = 63. Точка (3, 63)
f(4) = 91. Точка (4, 91)
f(5) = 125. Точка (5, 125)

А если хочу минимум 100 из 500 секретов собрать?

Значит нужен полином степени 99, для которого посчитаем 500 точек.

То есть он будет вида: ax⁹⁹ + bx⁹⁸ + ... + kx + S