Shamir Secret Sharing

В криптографии под "secret sharing" подразумевается алгоритм распределения фрагментов информации между группой людей, чтобы в случае важной необходимости, они могли собраться и восстановить обратно. Звучит сложно, попробую переформулировать

По сути это типа мультисига, где у вас есть k/n, всего n частей и k достаточно чтобы подписать (или узнать в нашем случае) секретную информацию.

Пример для маленьких

Допустим, у нас есть секретное слово solana (не очень хорошее, но такая фантазия больная). Можем сделать простейшее разделение на 6 слов и разделить между 6 людьми:

s?*, ?o*, ??l*, ???a*, ????n*, ?????a*

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

Можно добавить усложнение, пусть там все эти символы представлены в виде цифирок ascii и существует HE (Homomorphic encryption). Так уже схема чуток лучше, но 6 цифр и примерное понимание больной фантазии автора дают возможность подобрать.

Shamir's Secret Sharing Scheme

И тут на сцену выходит невероятно продуктивный Шамир, отец кучи всего в криптографии, и в 1979 году выдает SSS со следующими параметрами:

Разбивая информацию на n частей, вам будет достаточно лишь k чтобы восстановить ее
Если данных недостаточно (Не k известно, а k-1), то не восстановить
Другие недостающие параметры не подобрать просто так (если конечно там не слова из словаря с пробелами между ними, тогда есть шансы), только изначальный владелец знает

Принцип работы Вундер Вафли

Основа основ множества криптографических алгоритмов есть Lagrange Interpolation. Что это такое:

Есть у нас 1 точка, ладно.

Есть две точки, построим прямую (y = ax + b).

Есть три точки, построим параболу (y = ax^2 + bx + c)

Есть три точки, есть четыре точки и т.д.

Идея в том, что мы можем построить многочлен минимальной степени (из двух точек можно и 3-4 сделать степень, но точности не добавит), принимающий заданные значения в заданном наборе точек.

Для примера:

Есть у нас две точки: (0,0), (1,1). Можно по формулам геометрии 8 класса посчитать и построить прямую, а можно увидеть что y=x. Вот наша "кривая" прямая линия с максимальной степенью 1. А также можно увидеть, что сюда подходит y=x^2, y=x^3, .. y=x^n, а также вот эти все и их в итоге можно построить сколько угодно, но начиная со 2 максимальной степени. С минимальной = 1 только один, y=x.

Пока звучит легко, да? Но не сильно связано с нашей секретной задачей спрятать по всему миру нашу seed-phrase с 0.01 битком, согласен.

Основная идея

Пусть у нас есть какая-то кривая, допустим y=x^2+x+1 (называется парабола)

Чтобы нам ее построить, нам нужно иметь как минимум любые три точки, которые на ней лежат
Если у нас есть 4 точки, то мы все равно получим ту же самую кривую
Но если у нас их недостаточно, то мы не построим ее и не получим секрет

Алгоритм

Допустим у наш секретный ключ - 4, 5 ключей генерируем, и для расшифровки достаточно любых 3.

Создаем полином y = a0 + a1*x + a2*x^2 (из k точек строится k-1 степень полином)
Пусть a0 - наш секрет = 4, a1 - случайное - 2, a2 - случайное - 1
Генерируем из него 5 точек (1, 7), (2, 12), (3, 19), (4, 28), (5, 39).
Поздравляю, вы чудесны, вы получили какие-то рандомные точки, которые можете кому-то разослать (желательно чтобы эти люди не сразу же восстановили ваш секрет).

Как же по ним восстановить?

Можно через лагранжа считать тут формулки, но тогда слишком много текста, порисуем картиночки

https://www.desmos.com/calculator/kqi9wezbvx тут все рисуночки

Имея 3 точки, мы получаем следующую кривую

(там сверху есть все вычисления, если вдруг кому-то интересно по ссылке)
и вот снизу видим нашу точку

наше скрытое число
Но что будет, если у нас есть только две точки? (Все варианты перебирать не стал, оставил один)
https://www.desmos.com/calculator/imggo3qwgi

Теперь вообще другая точка.

А если хоть одна будет лишняя, будет вообще другая кривая.

Перебирать в итоге достаточно непросто (на самом деле в бесконечном поле в принципе еще хоть как-то, а в конечном гораздо сложнее, так как разрозненные точки и график скачет туда сюда).

Для тех, кто вдруг решил захотеть потыкать ручками, вот есть код на расте (не бейте если там не фулл тру rustacean)
https://github.com/valpaq/sss