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]