Разделение секрета Шамира: полиномиальная математика

Схема разделения секрета Шамира (1979) кодирует секрет как ординату пересечения с осью y (f(0)) случайного полинома степени (k-1) над конечным полем. Любые k точек однозначно определяют полином (интерполяция Лагранжа); менее k точек ничего не раскрывают.

Чтобы разделить секрет S с порогом k между n сторонами: выберите простое число p > S и n. Выберите случайные коэффициенты a_1, ..., a_{k-1}. Определите f(x) = S + a_1*x + a_2*x^2 + ... + a_{k-1}*x^{k-1} (mod p). Сторона i получает долю (i, f(i)).

Секрет S=7, p=17, k=2 (линейный полином). Выберите a_1=3. f(x)=7+3x mod 17. Доли: (1,10), (2,13), (3,16). Любые две точки определяют прямую. f(0)=7. Одна точка: бесконечно много возможных прямых, нулевая информация о S.

Имея k точек (x_1,y_1),...,(x_k,y_k), восстановите f(0) с помощью интерполяции Лагранжа: S = sum_i y_i * prod_{j≠i} (0-x_j)/(x_i-x_j) mod p. Все арифметические операции выполняются по модулю. Без вычислений с плавающей точкой — точное восстановление над конечным полем.

from functools import reduce def lagrange(shares, p): xs = [s[0] for s in shares] ys = [s[1] for s in shares] result = 0 for i, (xi, yi) in enumerate(shares): num = reduce(lambda a,b: a*b%p, [(-xj)%p for j,xj in enumerate(xs) if j!=i], 1) den = reduce(lambda a,b: a*b%p, [(xi-xj)%p for j,xj in enumerate(xs) if j!=i], 1) result = (result + yi * num * pow(den, p-2, p)) % p return result

Для k-1 долей через эти k-1 точек для каждого возможного значения секрета S существует ровно один многочлен степени k-1. Поэтому при знании k-1 долей каждое значение S из [0, p-1] равновероятно — никакой информации не раскрывается.

p должно быть больше секрета и n. Распространённый выбор: p = 2^127-1 (простое число Мерсенна) для 128-битных секретов. Это гарантирует, что все доли помещаются в 128 бит, а арифметические операции выполняются эффективно. В качестве альтернативы можно использовать p=2^521-1 для 512-битных секретов.

Базовая схема SSS не обеспечивает целостность долей: злоумышленник может передать ложную долю, что приведёт к неправильному восстановлению секрета. Feldman VSS (проверяемое разделение секрета) публикует обязательства g^{a_i} mod p, позволяя проверять доли, не раскрывая многочлен.

Доли можно периодически обновлять: создать новый многочлен с тем же секретом S и распределить новые доли, после чего старые доли становятся недействительными. Злоумышленник, скомпрометировавший участника после обновления, получает бесполезную старую долю. Такой подход используется в системах управления ключами с длительным сроком действия.

ssss (командная строка Linux), python-secret-sharing, hashicorp/vault использует SSS для механизма запечатывания, а аппаратный кошелёк Trezor использует SSS для резервного копирования исходной фразы кошелька (SLIP-39). Все они работают над полями больших простых чисел.

SSS требует доверенного участника, который создаёт и распределяет доли (этот участник знает секрет). Если доверенного участника нет, требуется DKG (распределённая генерация ключа). Восстановление раскрывает секрет тому, кто владеет k долями; этого можно избежать с помощью MPC или пороговых подписей.

В разделении секрета Шамира (3,5) какое минимальное количество долей необходимо для восстановления секрета?

SSS Шамира представляет секреты как точки пересечения многочлена с осью y. Интерполяция Лагранжа восстанавливает секрет по k долям. Для менее чем k долей обеспечивается совершенная теоретико-информационная безопасность. Далее: визуальное и аддитивное разделение секрета.