Shamir Secret Sharing

Гаманець — це застосунок або пристрій для отримання й надсилання біткоїнів. Анна хоче резервну копію, яка витримає втрату частини записів. Вона обирає три з п’яти: створюються п’ять різних часток, а будь-які три правильні частки одного набору відновлюють секрет. Дві можна втратити, три — вже ні. Необхідна кількість називається порогом; загалом k із n означає k потрібних часток із n створених і допускає втрату n−k. Але поріг не розпізнає згоди Анни. Якщо хтось отримає три частки або їхні власники домовляться, вони відновлять той самий секрет. Нижчий поріг полегшує відновлення, водночас зменшуючи групу, здатну зробити це без Анни. [1] [6]

Анна мало виграє, зберігаючи всі п’ять файлів в одному хмарному обліковому записі. Його втрата чи злам зачеплять усі частки одночасно. Резервування потребує продуманого розміщення, запису методу та параметрів і перевірки відновлення на надійному пристрої. Якщо план призначений і для спадкоємців, вони мають розуміти, що шукати та як безпечно з цим поводитися. Новий випадковий поділ того самого секрету S створює новий набір; старі й нові частки не змішують. Проте достатній старий набір і далі відновлює S. Повторний поділ не скасовує вже розкриту придатну копію та не змінює самого секрету. [1] [4]

За звичайного відновлення весь секрет знову з’являється на одному пристрої. Якщо пристрій скомпрометований, нападник може отримати секрет саме тоді. Якщо це Private Key, секретне числове значення для створення цифрового підпису, що дозволяє витратити кошти, його власник згодом може підписувати без додаткових часток. Multisig натомість вимагає кількох підписів відповідно до умов конкретного витрачання. Існує й порогове підписання: додатковий протокол MPC, безпечне спільне обчислення кількох учасників, дозволяє часткам брати участь у створенні підпису без збирання всього ключа. NIST розрізняє ці випадки. Сама частка Шаміра такого протоколу підписання не створює. [3] [5] [6]

Дві програми зі словом Shamir у назві не обов’язково читають частки одна одної. Мають збігатися математичні операції, кодування значень, ідентифікатори часток і належність до набору. SLIP-39 — конкретний стандарт на основі методу: він додає список слів, метадані, тобто допоміжні відомості, групи, шифрування та перевірки помилок. Загальний принцип не є інструкцією вручну ділити наявну Seed Phrase. Перш ніж довірити такій копії гаманець, треба знати підтримуваний формат і перевірити, що запланована процедура справді його відновлює. [2]

У схемі три з п’яти зрозуміло, що означає втратити дві частки. Але пошкоджена чи підроблена частка може змусити базове обчислення повернути інший секрет замість повідомлення про недостатню кількість. Сам метод не підтверджує походження часток і чесність їхнього творця. Виявлення та виправлення помилок і verifiable secret sharing, способи перевірки правильності поділу, є додатковими шарами з власними припущеннями. SLIP-39, наприклад, додає контрольну суму та перевірний відбиток digest. Це не означає, що всі застосунки Shamir Secret Sharing мають однакові перевірки або що правильна сума доводить надійне походження копії. [2] [5]

В ідеальній схемі менше ніж k повних часток не дають нападнику нової інформації про S навіть за необмежених обчислювальних можливостей. Частка не є видимою третиною початкових слів. Ця властивість вимагає правильної випадковості: числа для поділу обирають незалежно та з однаковою ймовірністю. Передбачувані числа, їхнє повторне використання чи витік із пам’яті пристрою змінюють ситуацію. Додаткові перевірні дані, як-от digest у SLIP-39, теж треба оцінювати окремо. А слабкий початковий пароль можна вгадати іншими шляхами й після поділу його резервної копії. [1] [2]

Візьмімо малий секрет S=5 і правило f(x)=5+3*x mod 17. mod 17 означає остачу від ділення на 17. Три частки — пари (1,8), (2,11), (3,14): перше число позначає позицію, друге — обчислене значення. З перших двох отримуємо приріст 3 і початковий секрет 8−3=5. Будь-яка з трьох можливих пар точок відновить ту саму п’ятірку. Водночас точка (1,8) сама по собі сумісна з будь-яким S від 0 до 16, якщо обрати приріст a=8−S mod 17. Ці малі числа лише пояснюють ідею, а не пропонують резервну копію для справжнього гаманця. [1]

Загальне правило — f(x)=S+a1*x+…+a(k−1)*x^(k−1). Цей вираз називається поліномом; S — секрет, а решта коефіцієнтів — незалежні, рівномірно випадкові елементи скінченного поля, середовища з точними правилами додавання та множення. Частка має вигляд (x,f(x)), де кожне x відмінне від інших і ненульове: x=0 прямо розкрило б S. Із k точок інтерполяція Лагранжа обчислює f(0), тобто секрет. Дві копії тієї самої точки не додають інформації. У простому полі GF(p) звичайне ділення замінює множення на обернений за модулем елемент, добуток якого з дільником дорівнює 1. GF(256) також рахує інакше, ніж прості остачі за модулем 256; плутати ці операції не можна. [1]