Секрет Shamir's
В нашем предыдущем посте мы узнали о некоторых распространенных мультиподписях и их реализации. В этом посте мы углубимся в технический аспект Shamir's Secret Sharing, криптографической схемы, которая позволяет восстановить закрытый ключ даже в отсутствие некоторых держателей акций.
«Основная идея схемы основана на конечных полях и интерполяционной теореме Лагранжа с k точками в двумерной плоскости (x, y), которая представляет собой алгебраическую форму оценки неизвестного значения между промежутками известных точек»
Shamir Secret Sharing (SSS) известен как алгоритм распределения ключей. Он был предложен израильским криптографом Ади Шамиром в 1979 году. В SSS криптографический ключ или любой другой секрет/сообщение делится на части, называемые акциями. Эти доли затем распределяются среди группы доверенных или ненадежных людей, которые являются частью операции. Важной особенностью SSS является то, что для восстановления секрета ему не нужны все доли от всех сторон. Только часть распределенных акций может привести вас к исходному секрету или сообщению. Настоящая цель этой схемы — повысить практичность и удобство, когда любое действие требует разрешения от нескольких сторон.
До предложения SSS все держатели секрета должны представить свою долю для восстановления первоначального секрета. Эти акционеры иногда теряли акции, отказывались предоставить их, их украли или они умерли. Однако распределение и изъятие акций у разных акционеров нецелесообразно и неэффективно. Эти ситуации создавали серьезную проблему в прошлом при расшифровке секрета.
Служба SSS полностью устранила эту проблему, и для создания секрета в исходной форме требуется лишь небольшая часть общих ресурсов. SSS — эффективное решение для управления ключами шифрования. Криптовалюты и блокчейны сильно зависят от SSS для обеспечения безопасности ключей.
Чтобы получить исходный секрет, минимально необходимое количество долей называется порогом. Например:
1. Вам нужно закодировать секрет А.
2. Его нужно разделить на N частей: A1, A2, A3, A4,…….,An .
3. После деления пользователь выберет число K в качестве порога для расшифровки сообщения. Это означает, что нам нужно как минимум K общих ресурсов, чтобы вернуть исходное сообщение. Секрет A не может быть расшифрован с помощью K-1 .
4. Когда у нас есть доли, равные значению K или больше, это единственный случай, когда мы можем расшифровать наш секрет A. это известно как пороговая схема (K, N).
С математической точки зрения, количество точек, необходимых для определения секрета, должно быть равно или больше степени используемого многочлена. Например, мы должны взять его с точки зрения линий и кривых на графике. Двух точек достаточно, чтобы найти прямую на графике, 3 точек достаточно, чтобы нарисовать параболу, а 4 точек достаточно, чтобы построить кубическую кривую на графике. Но вам не нужно глубоко погружаться в эти графики и концепции абстрактной алгебры, позвольте мне показать вам простой пример для лучшего понимания.
Предположим, у нас есть число 1834 (S) в качестве секрета, и мы хотим разделить его на 4 (N) доли с порогом 3 (K) .
Итак, нам нужно 4 балла в качестве доли для распределения. Кроме того, нам нужно выбрать два целых положительных числа, потому что мы имеем дело с квадратичными многочленами, а согласно уравнению квадратных многочленов нам нужно два целых числа для его вычисления. Кроме того, нам нужно более двух общих ресурсов для извлечения секрета. Пусть эти два случайных положительных целых числа равны 56 и 83.
Здесь a0 = S, a1 = 56, a2 = 83.
Вставляем значения и у нас остается:
Y = 1834 + 56x + 83 X^2 Уравнение 1
Теперь мы будем использовать это уравнение для расчета наших 4 акций для распределения.
X = 1, подставляя значение X в уравнение 1
Y = 1834 + 56 (1) + 83 (1) ^ 2
X = 2, подставляя значение X в уравнение 1
Y = 1834 + 56 (2) + 83 (2) ^ 2
X = 3, подставляя значение X в уравнение 1
Y = 1834 + 56 (3) + 83 (3) ^ 2
X = 4, подставляя значение X в уравнение 1
Y = 1834 + 56 (4) + 83 (4) ^ 2
Теперь у нас есть все 4 доли (N) для распределения. Только три из них необходимы (K), чтобы получить секрет, который составляет 1834 (s).
Давайте построим только общие числа 1, 2 и 4, чтобы получить 4-ю точку в 2D-пространстве. Посмотрите на рисунок 1 ниже, где нанесены три точки.
Мы использовали только 3 доли (1, 2 и 4) для построения графика параболы в 2D-пространстве. На следующем увеличенном рисунке мы ясно видим, что график пересекает ось Y, когда X = 0 и Y = 1834, что является нашим секретом.
Как вы можете видеть на рисунке 2, с помощью трех долей мы получили наш секрет, который равен 1834. Лучшей практикой для SSS является использование числа только из конечных полей, что сделает граф разбросанным и несвязанным. Это не позволит злоумышленнику провести криптоанализ или сделать обоснованное предположение.
Если противник обнаружил количество долей меньше порога K, он не сможет получить секрет, несмотря на более высокую вычислительную мощность. Это называется полной секретностью, и с этой точки зрения SSS можно назвать обобщением одноразового блокнота.
Несмотря на то, что SSS предлагает теоретическую безопасность, у SSS есть некоторые недостатки в виде целостности общего ресурса, когда участник будет получать или доставлять общий ресурс, отсутствие стандартизации до сих пор и единая точка отказа при разделении или повторном объединении ключей на одном компьютере. С другой стороны, SSS может добавить дополнительный уровень безопасности вашим ключам шифрования, и вышеупомянутых недостатков недостаточно, чтобы преодолеть преимущества SSS.
В следующей статье мы обсудим другую схему, которая устраняет единственную точку отказа SSS.
https://web.mit.edu/6.857/OldStuff/Fall03/ref/Shamir-HowToShareASecret.pdf
https://www.youtube.com/watch?v=iFY5SyY3IMQ&t=328s