Що таке Shamir Secret Sharing

Переглядаючи фільми, ми часто можемо побачити розділення ключів. Наприклад, щоб запустити ракету потрібно два ключі, або для відкриття банківського сховища. Ці ключі можуть бути у двох різних людей і якщо хтось один захоче виконати якусь дію, без наявності другого ключа він не зможе це зробити.

В криптографії одним з способів розділення доступу на декілько людей є Shamir Secret Sharing.

Shamir Secret Sharing

Shamir Secret Sharing дозволяє розділити секрет на частини так, що:

• Секрет можна відновити лише якщо зібрати ≥ k частин
• Менше ніж k частин не дають жодної інформації про секрет

Загальна формула:

$$f(x) = S + a_1 * x + a_2 * x^2 + ... + a_\text{k-1} * x^\text{k-1} \mod p$$

де:

• S - це секрет, який представлений як число
• a₁...aₖ₋₁ - випадкові числа
• p - велике просте число, яке створює кінцеве поле

Тепер нам потрібно створити мінімум k ключів. Кожен ключ - це координати x та y на графіку функції:

$$\text{share}_i = (x_i,\ f(x_i))$$

Відновлення секрету

Відновити секрет можна використовуючи цю страшну формулу:

$$f(0) = S \\[4pt] \Downarrow \\[4pt] S = \sum_{i=1}^{k} y_i \ * \ \prod_{\substack{j=1 \\ j \ne i}}^{k} \frac{0 - x_j}{x_i - x_j}$$

Але ми будемо робити це за допомогою SageMath, щоб не робити розрахунки самостійно.

Чому це працює?

Нехай наш секрет це число 42:

$$S = 42$$

Оберемо випадкові параметри і візьмемо k = 4. Тоді наша формула буде мати вигляд:

$$f(x) = 42 + 6x + 8x^2 - 7x^3$$

У реальних системах коефіцієнти a₁...aₖ₋₁ повинні генеруватися криптографічно випадковим чином у межах кінцевого поля p.

Якщо ми зобразимо нашу функцію на графіку, то побачимо:

Якщо ми подивимося на графік то побачимо, що в нас є 4 (залежить від k) основні точки, знаючи які ми зможемо його відновити:

Якщо в нас буде менше точок - то ми не зможемо відновити графік. Кількість кривих, які ми можемо побудувати - нескінченно велика.

Практика

Візьмемо функцію з минулого розділу з кінцевим полем 151:

$$f(x) = 42 + 6x + 8x^2 - 7x^3 \mod 151$$

Сформуємо 4 ключа, за x ми можемо взяти будь-яке число у діапазоні від 1 до p-1:

$$f(1) = 49 \\ f(2) = 30 \\ f(3) = 94 \\ f(4) = 48$$

Можна створити і більше ключей, а кількість потрібна для відновлення секрету не зміниться.

Тепер в нас є точки які ми можемо роздати різним людям:

(1, 49)
(2, 30)
(3, 94)
(4, 48)

Відновити секрет ми можемо за допомогою SageMath:

p = 151
shares = [(1, 49),  (2, 30),  (3, 94),  (4, 48)]

F = FiniteField(p)
P = F['x']

reconstructed_polynomial = P.lagrange_polynomial(shares)
secret = reconstructed_polynomial(0)

print(secret)

В результаті отримаємо 42.

Якщо ми передамо менше ніж 4 точки, або хоча б якась з них буде записана неправильно - ми не зможемо отримати секрет.

Резюме

Сьогодні ми зрозуміли що таке Shamir Secret Sharing і розібралися як це може допомогти нам розділити якийсь секрет на декількох людей, так що для його отримання потрібна участь декількох з них.

Завдання для самоперевірки

Спробуйте сховати текст таким чином, закодуйте його за допомогою ASCII та створіть ключі. Відтворіть початковий текст за допомогою цих ключів.