Разделение секретов Шамира , сформулированное Ади Шамиром , является одной из первых схем обмена секретами в криптографии . Он основан на полиномиальной интерполяции над конечными полями .
Объяснение высокого уровня
Shamir's Secret Sharing (SSS) используется для защиты секрета распределенным способом, чаще всего для защиты других ключей шифрования. Секрет разделен на несколько частей, называемых долями . Эти доли используются для восстановления первоначального секрета.
Чтобы разблокировать секрет через обмен секретами Шамира, вам нужно минимальное количество акций. Это называется порогом и используется для обозначения минимального количества акций, необходимых для разблокировки секрета. Давайте рассмотрим пример:
Проблема: компании XYZ необходимо защитить пароль своего хранилища. Можно было бы использовать что-нибудь стандартное, например AES, но что, если держатель ключа недоступен или умирает? Что, если ключ будет взломан злоумышленником или его владелец станет мошенником и использует свою власть над хранилищем в своих интересах?
Здесь на помощь приходит SSS. Его можно использовать для шифрования пароля хранилища и генерации определенного количества акций, при этом определенное количество акций может быть выделено каждому руководителю в компании XYZ. Теперь, только если они объединят свои акции, они смогут разблокировать хранилище. Пороговое значение может быть соответствующим образом установлено для количества руководителей, поэтому к хранилищу всегда могут получить доступ уполномоченные лица. Если одна или две акции попадут в чужие руки, они не смогут открыть пароль, если другие руководители не будут сотрудничать.
Математическая формулировка
Shamir's Secret Sharing - идеальный и совершенный -пороговая схема . В такой схеме цель - разделить секрет(например, комбинация сейфа ) в фрагменты данных (известные как акции ) таким образом, чтобы:
- Знание любого или больше штук делает легко вычислимый. То есть полный секрет может быть реконструирован из любой комбинации фрагменты данных.
- Знание любого или меньше кусочки листьев полностью неопределенный, в том смысле, что возможные значения для кажется таким же вероятным, как со знанием шт. Это секрет не может быть восстановлен менее чем шт.
Если , то каждый кусочек оригинального секрета требуется, чтобы восстановить секрет.
Основная идея схемы основана на интерполяционной теореме Лагранжа , а именно на том, чтоточек достаточно , чтобы однозначно определить многочлен от степени меньше или равно. Например, 2 точки достаточно для определения прямой , 3 точки достаточно для определения параболы , 4 точек для определения кубической кривой и так далее. Мы принимаем наш секрет можно представить как элемент конечного поля . Выбираем наугад элементы , из и построим многочлен . Построим любой указывает на это, например, набор получить . Каждому участнику дается балл (ненулевое целое число, входящее в многочлен, и соответствующий целочисленный выход). Учитывая любое подмножество этих пар можно найти с использованием интерполяции с одной из возможных формулировок, как показано ниже:
.
Применение
Пример
Следующий пример иллюстрирует основную идею. Обратите внимание, однако, что вычисления в примере выполняются с использованием целочисленной арифметики, а не с использованием арифметики с конечным полем . Поэтому приведенный ниже пример не обеспечивает полной секретности и не является истинным примером схемы Шамира . Итак, мы объясним эту проблему и покажем правильный способ ее реализации (используя арифметику конечных полей).
Подготовка
Предположим, что наш секрет - 1234 .
Мы хотим разделить секрет на 6 частей , где любое подмножество из 3 частей достаточно, чтобы восстановить секрет. Наугад получаем номера: 166 и 94.
- где секрет
Таким образом, наш полином для получения секретных долей (точек):
Строим шесть точек от полинома:
Мы даем каждому участнику отдельный балл (оба а также ). Потому что мы используем вместо точки начинаются с и нет . Это необходимо, потому что это секрет.
Реконструкция
Для восстановления секрета достаточно 3-х точек.
Рассмотреть возможность .
Будем вычислять базисные полиномы Лагранжа :
Следовательно
Напомним, что секрет в свободном коэффициенте, а это значит, что , и мы закончили.
Вычислительно эффективный подход
Учитывая, что цель использования полиномиальной интерполяции - найти константу в исходном полиноме использование полиномов Лагранжа «как есть» неэффективно, поскольку вычисляются неиспользуемые константы.
Оптимизированный подход к использованию полиномов Лагранжа для поиска определяется следующим образом:
Проблема
Хотя упрощенная версия метода, продемонстрированная выше, в которой используется целочисленная арифметика, а не арифметика с конечным полем, работает нормально, существует проблема безопасности: Ева получает много информации о с каждым что она находит.
Предположим, она находит 2 точки а также , у нее все еще нет баллов, поэтому теоретически она не должна была получать больше информации о . Но она сочетает информацию из двух пунктов с общедоступной информацией: и она :
- заполняет -формула с и ценность
- заполняет (i) значениями с а также
- заполняет (i) значениями с а также
- делает (iii) - (ii): и переписывает это как
- знает это поэтому она начинает заменять в (iv) с 0, 1, 2, 3, ..., чтобы найти все возможные значения для:
- заменяет по (iv) в (ii):
- заменяет в (vi) значениями, найденными в (v), так что она получает что приводит ее к информации:
- Теперь ей нужно угадать только 150 чисел вместо бесконечного числа натуральных чисел.
Решение
Геометрически эта атака использует тот факт, что мы знаем порядок полинома и, таким образом, получаем представление о путях, которые он может пройти между известными точками. Это уменьшает возможные значения неизвестных точек, поскольку они должны лежать на гладкой кривой.
Эту проблему можно решить, используя арифметику конечных полей. Поле размераиспользуется. График показывает полиномиальную кривую над конечным полем, в отличие от обычной гладкой кривой, она кажется очень неорганизованной и несвязной.
На практике это всего лишь небольшое изменение, это просто означает, что мы должны выбрать простое число. это больше, чем количество участников, и каждый (в том числе ) и мы должны вычислить точки как вместо .
Поскольку каждый, кто получает балл, также должен знать ценность , он может считаться публично известным. Следовательно, следует выбрать значение для это не так уж мало.
В этом примере мы выбираем , поэтому наш многочлен принимает вид что дает баллы:
На этот раз Ева не получит никакой информации, когда найдет (пока у нее не будет точки).
Снова предположим, что Ева находит а также , на этот раз общедоступная информация: так она:
- заполняет -формула с и ценность а также :
- заполняет (i) значениями с а также
- заполняет (i) значениями с а также
- делает (iii) - (ii): и переписывает это как
- знает это поэтому она начинает заменять в (iv) с 0, 1, 2, 3, ..., чтобы найти все возможные значения для:
На этот раз она не может остановиться, потому что может быть любым целым числом (даже отрицательным, если ), поэтому существует бесконечное количество возможных значений для . Она знает что всегда уменьшается на 3, поэтому если делится на она могла сделать вывод но поскольку это главное, она не может прийти к такому выводу и поэтому не получила никакой информации.
Пример Python
"" " Следующая реализация Python Shamir's Secret Sharing передана в общественное достояние на условиях CC0 и OWFa: https://creativecommons.org/publicdomain/zero/1.0/ http://www.openwebfoundation.org/legal / the-owf-1-0-соглашения / owfa-1-0См. Несколько нижних строк для использования. Проверено на Python 2 и 3. "" "from __future__ импортное подразделение из __future__ import print_functionимпорт случайного импорта functools# 12th Mersenne Prime # (для этого приложения мы хотим, чтобы известное простое число было как можно # ближе к нашему уровню безопасности; например, желаемый уровень безопасности 128 # битов - слишком большой, и весь зашифрованный текст большой; слишком маленький и # безопасность скомпрометированы) _PRIME = 2 ** 127 - 1 # 13 Мерсенна 2 ** 521 - 1_RINT = functools . частичный ( случайный . SystemRandom () . randint , 0 )def _eval_at ( poly , x , prime ): "" "Вычисляет полином (кортеж коэффициентов) в x, используемый для генерации пула шамира в make_random_shares ниже. " "" аккумулятор = 0 для коэфф в обратном ( поли ): аккумулятор * = x Accum + = коэфф Accum % = простое возвращение AccumЗащиту make_random_shares ( секрет , минимум , акция , премьер = _PRIME ): «» « Генерирует случайный Шамир бассейн для данного секрета, возвращается разделить точки. „“» , если минимум > акции : повышение ValueError ( „Бассейн секрет будет взыскан.“ ) poly = [ секрет ] + [ _RINT ( простое число - 1 ) для i в диапазоне ( минимум - 1 )] points = [( i , _eval_at ( poly , i , prime )) для i в диапазоне ( 1 , доли + 1 ) ] возвратные баллыdef _extended_gcd ( a , b ): "" " Деление на целые числа по модулю p означает нахождение значения, обратного знаменателю по модулю p, а затем умножение числителя на это обратное значение (Примечание: обратное значение для A - это B, такое что A * B% p == 1) это можно вычислить с помощью расширенного алгоритма Евклида http://en.wikipedia.org/wiki/Modular_multiplicative_inverse#Computation "" " x = 0 last_x = 1 y = 1 last_y = 0, а b ! = 0 : quot = a / / b a , b = b , a % b x , last_x = last_x - quot * x , x y , last_y = last_y - quot * y , y вернуть last_x , last_ydef _divmod ( num , den , p ): "" "Вычислить num / den по модулю простого p Чтобы объяснить, что это означает, возвращаемое значение будет таким, что верно следующее: den * _divmod (num, den, p)% p == num "" " inv , _ = _extended_gcd ( den , p ) return num * invdef _lagrange_interpolate ( x , x_s , y_s , p ): "" " Найти значение y для данного x, учитывая n (x, y) точек; k точек будут определять полином до k-го порядка. " "" k = len ( x_s ) assert k == len ( set ( x_s )), "точки должны быть разными" def PI ( vals ): # PI в верхнем регистре - произведение входных данных совокупность = 1 для v в vals : amp * = v return amp nums = [] # избегать неточного деления dens = [] для i в диапазоне ( k ): others = list ( x_s ) cur = others . pop ( i ) nums . Append ( PI ( х - о для о в других )) DenS . Append ( ПИ ( текущ - O для вывода в других )) ден = ПИ ( вертепы ) NUM = сумма ([ _divmod ( НУМС [ я ] * ден * y_s [ я ] % р , притоны [ я ], р ) для I в диапазон ( k )]) return ( _divmod ( num , den , p ) + p ) % pЗащиту recover_secret ( акции , простые = _PRIME ): «» « Восстановление в тайне от точек доли . (х, у точек на многочлен) „“» если Len ( акций ) < 2 : Raise ValueError ( „нужно как минимум две акции“ ) x_s , y_s = застежка - молния ( * акция ) возвращение _lagrange_interpolate ( 0 , x_s , y_s , премьер )Защита основные (): "" "Основная функция" "" секрет = 1234 акций = make_random_shares ( секрет , минимум = 3 , акции = 6 ) печать ( 'Secret:' , секретный ) печати ( 'Акции:' ) , если акции : для акций в акции : печать ( '' , доля ) печать ( 'секретно извлекает из минимального подмножества акций:' , recover_secret ( акции [: 3 ])) печать ( 'секретно извлекает из другого минимального подмножества акций:' , recover_secret ( акции [ - 3 :]))если __name__ == '__main__' : main ()
Характеристики
Некоторые полезные свойства Шамира пороговые схемы бывают:
- Безопасность : теоретическая информационная безопасность .
- Минимальный : размер каждого фрагмента не превышает размера исходных данных.
- Расширяемый : когда фиксируется, части могут быть динамически добавлены или удалены, не затрагивая другие части.
- Динамический : безопасность можно легко повысить, не меняя секрета, но время от времени меняя полином (сохраняя тот же свободный член) и создавая новые акции для участников.
- Гибкость : в организациях, где важна иерархия, мы можем предоставить каждому участнику разное количество элементов в зависимости от их важности внутри организации. Например, президент может открыть сейф в одиночку, тогда как для его открытия требуются 3 секретаря.
Известная проблема в схеме совместного использования секретов Шамира - это проверка правильности извлеченных общих ресурсов в процессе восстановления, известная как проверяемое совместное использование секретов . Поддающееся проверке разглашение секретов направлено на проверку того, что акционеры честны и не предоставляют поддельные акции.
Смотрите также
- Обмен секретами
- Полином Лагранжа
- Гомоморфный обмен секретами - упрощенный децентрализованный протокол голосования.
- Правило двух человек
- Частичный пароль
Рекомендации
- Шамир, Ади (1979), "Как поделиться секретом", массовых коммуникаций ACM , 22 (11): 612-613, DOI : 10,1145 / 359168,359176 , S2CID 16321225.
- Лю, К.Л. (1968), Введение в комбинаторную математику , Нью-Йорк: McGraw-Hill.
- Dawson, E .; Донован, D. (1994), "Широта схемы секрет совместного Шамира", Компьютеры и безопасность , 13 : 69-78, DOI : 10,1016 / 0167-4048 (94) 90097-3.
- Knuth, DE (1997), Искусство компьютерного программирования , II: получисловые алгоритмы (3-е изд.), Addison-Wesley, p. 505.
- Benzekki, К. (2017), "А Проверяемость Secret Sharing подход для безопасного хранения MultiCloud", в Повсеместный сети , Lecture Notes в области компьютерных наук, Касабланка: Springer, 10542 : 225-234, DOI : 10.1007 / 978-3-319- 68179-5_20 , ISBN 978-3-319-68178-8.
Внешние ссылки
- Секретный Sharing Шамира в Crypto ++ библиотеки
- Секретный Sharing схема Шамира (SSSS) - это GNU GPL реализация
- sharedsecret - реализация на Go
- s4 - онлайн-инструмент для обмена секретами Шамира, использующий алгоритм обмена секретами Шамир Корпус Хаши