Shamir’s Secret Sharing

Shamir’s Secret Sharing (схема разделения секрета Шамира) — это криптографический алгоритм, предназначенный для разделения секретного значения (например, ключа шифрования, пароля или цифровой подписи) на несколько частей, называемых долями (shares), таким образом, что для восстановления исходного секрета требуется определённое минимальное количество долей. Схема была предложена израильским криптографом Ади Шамиром в 1979 году и является одним из фундаментальных методов пороговой криптографии.

История

Схема разделения секрета была впервые опубликована Ади Шамиром в статье «How to Share a Secret» в 1979 году. Работа Шамира стала ответом на практическую потребность в безопасном хранении криптографических ключей: если ключ хранится в одном месте, он может быть утерян или скомпрометирован; если же он хранится у нескольких лиц, необходимо решить проблему доверия и доступности. Шамир предложил математически строгий метод, основанный на интерполяции многочленов, который позволяет восстановить секрет при наличии любых k долей из n (где k ≤ n), при этом любое количество долей меньше k не даёт никакой информации о секрете. Схема Шамира стала одним из первых и наиболее известных решений задачи разделения секрета, наряду с методом Блэкли, основанным на пересечении гиперплоскостей.

Принцип работы

Схема Шамира основана на свойстве многочленов степени k-1: для однозначного определения такого многочлена необходимо k точек на его графике. Если секрет S представляется как свободный член многочлена (значение при x=0), то для восстановления S требуется найти k точек, принадлежащих этому многочлену.

Основные параметры

Схема характеризуется двумя целыми числами:

• n — общее количество долей, на которые делится секрет.
• k — пороговое значение, минимальное количество долей, необходимое для восстановления секрета (k ≤ n).

Алгоритм разделения (дилер)

1. Выбирается простое число p, большее, чем максимальное возможное значение секрета S и всех коэффициентов многочлена. Обычно p — большое простое число, например, 2^127 - 1 или 2^255 - 19.
2. Секрет S представляется как целое число в диапазоне [0, p-1].
3. Случайным образом выбираются k-1 коэффициентов a₁, a₂, ..., a_{k-1} из диапазона [0, p-1]. Коэффициенты должны быть независимыми и равномерно распределёнными.
4. Строится многочлен степени k-1:

f(x) = S + a₁·x + a₂·x² + ... + a_{k-1}·x^{k-1} (mod p)

1. Для каждого из n участников вычисляется значение многочлена в точке x_i (x_i — уникальный ненулевой идентификатор участника, обычно от 1 до n):

share_i = f(x_i) mod p

1. Каждому участнику выдаётся пара (x_i, share_i). Сами по себе эти значения не раскрывают секрет.

Алгоритм восстановления

Для восстановления секрета необходимо собрать любые k долей (x_i, share_i). Восстановление выполняется с помощью интерполяции многочлена по методу Лагранжа:

1. Вычисляется значение многочлена в точке x=0, что даёт секрет S:

S = Σ_{i=1}^{k} share_i · L_i(0) mod p где L_i(0) — коэффициенты Лагранжа: L_i(0) = Π_{j=1, j≠i}^{k} (0 - x_j) / (x_i - x_j) mod p

1. Деление в поле GF(p) выполняется как умножение на мультипликативное обратное число.

Свойства

Идеальная секретность

Схема Шамира обладает свойством идеальной секретности: любое количество долей меньше k не даёт никакой информации о секрете. Даже зная k-1 долю, можно с равной вероятностью получить любой возможный секрет из поля GF(p). Это свойство является строгим математическим следствием того, что через k-1 точек можно провести бесконечно много многочленов степени k-1, каждый из которых даёт своё значение в точке x=0.

Гибкость

Схема позволяет легко изменять пороговое значение k и количество долей n без изменения самого секрета. Для этого достаточно пересчитать доли для нового многочлена с тем же свободным членом.

Масштабируемость

Схема работает для любых n и k (k ≤ n), при этом вычислительная сложность восстановления секрета составляет O(k²) операций в поле GF(p).

Применение

Хранение криптографических ключей

Shamir’s Secret Sharing широко используется для безопасного хранения мастер-ключей в системах шифрования. Например, корпоративный ключ доступа к базе данных может быть разделён на 5 долей, из которых для восстановления требуется 3. Это позволяет избежать единой точки отказа и снижает риск утечки ключа.

Системы управления ключами (KMS)

В облачных и локальных системах управления ключами (например, HashiCorp Vault, AWS KMS) схема Шамира применяется для разделения мастер-ключа, который используется для шифрования остальных ключей. В Vault используется реализация, называемая «Shamir’s Secret Sharing with unseal keys».

Криптовалюты и блокчейн

В некоторых криптовалютных кошельках (например, в мультиподписных кошельках Bitcoin) схема Шамира используется для создания пороговых схем подписи. Также она применяется в системах хранения seed-фраз (например, в кошельке Trezor).

Безопасное хранение паролей

Схема может использоваться для разделения пароля администратора или суперпользователя на несколько частей, хранящихся у разных лиц. Например, пароль от корневого аккаунта сервера может быть разделён на 3 доли, из которых для восстановления требуется 2.

Многосторонние вычисления (MPC)

Shamir’s Secret Sharing является основой для многих протоколов безопасных многосторонних вычислений, где участники совместно вычисляют функцию, не раскрывая свои входные данные.

Варианты и модификации

Схема с проверяемым разделением (Verifiable Secret Sharing, VSS)

В классической схеме Шамира участники должны доверять дилеру, что он честно разделил секрет. В VSS добавляются доказательства (например, с использованием гомоморфных коммитментов), позволяющие участникам проверить, что их доли действительно соответствуют одному многочлену.

Прокси-восстановление (Proactive Secret Sharing)

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

Схема с аутентификацией (Authenticated Secret Sharing)

Добавляет механизмы аутентификации долей, чтобы предотвратить подмену долей злоумышленником.

Схема Блэкли

Альтернативный метод разделения секрета, основанный на пересечении гиперплоскостей в многомерном пространстве. В отличие от схемы Шамира, схема Блэкли не является идеально секретной в строгом смысле, но также широко используется.

Критика и ограничения

Зависимость от простого числа

Схема требует работы в конечном поле GF(p), что накладывает ограничения на размер секрета и требует аккуратного выбора p. Если p выбрано слишком маленьким, секрет может быть восстановлен перебором.

Доверие к дилеру

В классической версии дилер, разделяющий секрет, знает исходный секрет и может его раскрыть или скомпрометировать. Для решения этой проблемы используются протоколы с распределённым генерацией секрета.

Вычислительная сложность

Хотя восстановление секрета выполняется за O(k²), при больших k (например, k > 100) и больших простых числах (например, 256-битных) вычисления могут быть ресурсоёмкими.

Уязвимость к коллизиям

Если злоумышленник получает k долей, он может восстановить секрет. Поэтому схема требует надёжного хранения долей и их защиты от несанкционированного доступа.

Пример

Пусть секрет S = 1234, p = 1613 (простое число), n = 5, k = 3.

1. Выбираются случайные коэффициенты: a₁ = 166, a₂ = 94.
2. Многочлен: f(x) = 1234 + 166·x + 94·x² mod 1613.
3. Доли:

• x=1: f(1) = 1234 + 166 + 94 = 1494 mod 1613 = 1494
• x=2: f(2) = 1234 + 332 + 376 = 1942 mod 1613 = 329
• x=3: f(3) = 1234 + 498 + 846 = 2578 mod 1613 = 965
• x=4: f(4) = 1234 + 664 + 1504 = 3402 mod 1613 = 176
• x=5: f(5) = 1234 + 830 + 2350 = 4414 mod 1613 = 1188

1. Для восстановления секрета по долям (1, 1494), (3, 965), (5, 1188) вычисляются коэффициенты Лагранжа:

• L₁(0) = (0-3)(0-5) / ((1-3)(1-5)) = 15 / 8 mod 1613 = 15 * 202 = 3030 mod 1613 = 1417
• L₂(0) = (0-1)(0-5) / ((3-1)(3-5)) = 5 / (-4) mod 1613 = 5 * 1209 = 6045 mod 1613 = 1206
• L₃(0) = (0-1)(0-3) / ((5-1)(5-3)) = 3 / 8 mod 1613 = 3 * 202 = 606 mod 1613 = 606

1. Секрет: S = 1494·1417 + 965·1206 + 1188·606 mod 1613 = 2117598 + 1163790 + 720328 = 4001716 mod 1613 = 1234.

Источники

• Shamir, A. (1979). «How to Share a Secret». Communications of the ACM.
• Menezes, A. J., van Oorschot, P. C., Vanstone, S. A. (1996). «Handbook of Applied Cryptography».
• Stinson, D. R. (2005). «Cryptography: Theory and Practice».