Что такое схема Шамира
Схема разделения секрета Шамира (1979) делит секрет на N долей так, что любые M из них (порог) восстанавливают его, а любые M-1 не дают ни бита информации. Идея в том, что через M точек проходит ровно один многочлен степени M-1, а через M-1 точек - бесконечно много. Секрет это значение многочлена в нуле, доли это значения в точках 1..N. Остальные коэффициенты случайны, поэтому по M-1 долям любой секрет одинаково вероятен.
Зачем делить ключ
Классический сценарий - резервирование. Приватный ключ, мастер-пароль или фраза от кошелька не должны лежать в одном месте, но и потерять их нельзя. Делим «2 из 3» и раздаём доли разным людям или кладём в разные места (сейф, облако, дом родственника). Потеря одной доли не страшна, кража одной доли ничего не даёт. Для SSH-ключа вставьте его целиком, вместе со строками BEGIN и END, а ключ можно создать в генераторе SSH-ключей.
Чем отличается от разрезания ключа на куски
Если разрезать ключ на три части, каждая часть раскрывает треть секрета, а для восстановления нужны все три. Потерял один кусок - потерял ключ, а два куска сильно сужают перебор оставшейся части. В схеме Шамира одна доля (и любое число долей меньше порога) не раскрывает ничего, а порог гибкий: потеря N-M долей безопасна.
Как это устроено здесь
Секрет обрабатывается побайтово в поле GF(256) с полиномом AES 0x11b. Для каждого байта выбираются M-1 случайных коэффициентов (crypto.getRandomValues), доле с номером x достаётся значение многочлена в точке x. Восстановление - интерполяция Лагранжа в нуле. К секрету перед делением добавляются 4 байта контрольной суммы (начало SHA-256 секрета), они делятся вместе с ним. Поэтому одна доля не выдаёт хэш секрета, а при восстановлении ошибочный набор долей определяется: вместо мусора вы увидите сообщение.
Формат доли
bl2ss1-M-x-данные, где M - порог, x - номер доли (1..255), данные - значения доли для всех байт секрета и контрольной суммы в base64url. Пример: bl2ss1-2-1-Qm0x9kT2. Формат собственный, не совместим с ssss, Vault и другими программами.
Восстановление без сайта
Чтобы доли не зависели от этого сайта, ниже полный алгоритм восстановления. Декодируйте base64url в байты, возьмите M долей и вызовите функцию.
def mul(a, b):
r = 0
while b:
if b & 1:
r ^= a
a <<= 1
if a & 0x100:
a ^= 0x11b
b >>= 1
return r
def inv(a):
return next(x for x in range(1, 256) if mul(a, x) == 1)
def restore(points): # points = [(x, y_bytes), ...], any M shares
out = []
for i in range(len(points[0][1])):
s = 0
for xi, yi in points:
num = den = 1
for xj, _ in points:
if xj != xi:
num = mul(num, xj)
den = mul(den, xi ^ xj)
s ^= mul(yi[i], mul(num, inv(den)))
out.append(s)
return bytes(out) # the last 4 bytes are the checksumРезультат - секрет и 4 байта в конце. Проверьте, что они совпадают с первыми 4 байтами SHA-256 от секрета. Для надёжного пароля можно использовать генератор паролей.