Схема разделения секрета Шамира

---

Схема интерполяционных полиномов Лагранжа (схема разделения секрета Шамира или схема Шамира) — схема разделения секрета, широко используемая в криптографии. Схема Шамира позволяет реализовать ${\displaystyle (k,n)}$ — пороговое разделение секретного сообщения (секрета) между ${\displaystyle n}$ сторонами так, чтобы только любые ${\displaystyle k}$ и более сторон (${\displaystyle k}$ ≤ ${\displaystyle n}$) могли восстановить секрет. При этом любые ${\displaystyle k-1}$ и менее сторон не смогут восстановить секрет.

В 1979 году израильский криптоаналитик Ади Шамир предложил пороговую схему разделения секрета между ${\displaystyle n}$ сторонами, которая позволяет проводить разделение таким образом, что^[1]:

Для интерполяции многочлена степени ${\displaystyle k-1}$ требуется ${\displaystyle k}$ точек. К примеру, для задания прямой достаточно двух точек, для задания параболы — трех точек, и так далее.

Основная идея данной схемы состоит в том, что интерполяция невозможна, если известно меньшее число точек^[1].

Если мы хотим разделить секрет между ${\displaystyle n}$ людьми таким образом, чтобы восстановить его могли только ${\displaystyle k}$ человек (${\displaystyle k}$ ≤ ${\displaystyle n}$), мы «прячем» его в формулу многочлена степени ${\displaystyle k-1}$. Восстановить этот многочлен и исходный секрет можно только по ${\displaystyle k}$ точкам. Количество же различных точек многочлена не ограничено (на практике оно ограничивается размером числового поля, в котором ведутся расчёты)^[2].

Пусть нужно разделить секрет ${\displaystyle M}$ между ${\displaystyle n}$ сторонами таким образом, чтобы любые ${\displaystyle k}$ участников могли бы восстановить секрет (то есть нужно реализовать ${\displaystyle (k,n)}$-пороговую схему).

---