ФЭНДОМ


Файл:Secretsharing-3-point.png

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

В схеме разделения секрета участвуют один дилер и n игроков. Изначально секрет находится у дилера, затем дилер вычисляет доли секрета и раздает их участникам, каждому участнику по одной доле. Обычно для схемы разделения секрета определен порог t: любая группа из t или более игроков, собравшись вместе, может восстановить секрет, но никакая группа из менее чем t игроков не сможет. Такую схему разделения секрета называют (t, n)-пороговая схема (англ. (t, n)-threshold scheme).

Мотивация Править

Надежная схема разделения секрета позволяет распределить доли секрета так, что любая коалиция из менее чем t игроков не сможет получить абсолютно никакой информации о секрете. Рассмотрим наивную схему разделения секрета, в которой секретное слово «пароль» делится на доли «па----», «--ро--» и «----ль». Допустим у хакера нету ни одной доли секрета, тогда ему придется пробовать все возможные шестибуквенные пароли, а это 336=1,2 млрд комбинаций. Если хакер смог заполучить одну долю, то ему теперь придется угадать только четыре буквы, а это 334=1,2 млн комбинаций, что существенно меньше. Такая система ненадежна, так как коалиция из меньше чем t игроков может получить значительную информацию о секрете.

Тривиальная схема Править

Существует множество (t, n)-схем для которых t=n, то есть для восстановления секрета нужны все доли, например:

  • Закодируем секрет как целое число s. Дадим всем игрокам кроме одного по случайному числу ri, а последнему игроку дадим число rn=s-r1-r2-…-rn-1. Для восстановления секрета нужно сложить все числа ri.
  • Закодируем секрет как байт s. Дадим всем игрокам кроме одного по случайному байту ri, а последнему игроку дадим байт rn=s XOR r1 XOR r2 XOR … XOR rn-1. Для восстановления секрета нужно применить ко всем числам ri операцию XOR.

Когда объем используемой памяти некритичен, то можно использовать схемы такого рода для любого подмножества игроков применяя такую схему для каждой возможной коалиции игроков. Например, есть три игрока: Алиса, Боб и Кэрол. Чтобы создать схему в которой любые два игрока смогут восстановить секрет, мы можем создать три разных (2,2) схемы. Каждая схема даст нам две доли секрета. Две доли первой схемы дадим Алисе и Бобу, две доли второй схемы — Бобу и Кэрол, а две доли третьей схемы — Алисе и Кэрол. Однако такой подход очень быстро становится неэффективным вместе с ростом n u t.

Пример t≠n Править

Допустим, совет директоров компании Кока-Кола хочет защитить секретную формулу их напитка. Президент компании должен иметь доступ к формуле, а также любые 3 из 12 членов совет директоров должны суметь собравшись вместе получить формулу. Такую задачу можно решить (3,15) схемой разделения секрета, где президент получит 3 доли секрета, а каждый член совета директоров — по одной доле.

Схема Блэкли Править

Две непараллельные прямые на плоскости пересекаются в одной точке. Три "непараллельные" плоскости в пространстве пересекаются тоже в одной точке. Вообще n n-мерных гиперплоскостей всегда пересекаются в одной точке. Одна из координат этой точки будет секретом. Если закодировать секрет как несколько координат точки, то уже по одной доле секрета (одной гиперплоскости) можно будет получить какую-то информацию о секрете, то есть о взаимозависимости координат точки пересечения.

Одна доля Две доли - пересекаются вдоль плоскости Три доли - пересекаются в точке
Схема Блэкли в трех измерениях: каждая доля секрета — это плоскость, а секрет — это одна из координат точки пересечения плоскостей. Двух плоскостей недостаточно для определения точки пересечения.

С помощью схемы Блэкли можно создать (t, n)-схему разделения секрета для любых t u n: для этого надо положить размерность пространства равную t, и каждому из n игроков дать одну гиперплоскость, проходящую через секретную точку. Тогда любые t из n гиперплоскостей будут однозначно пересекаться в секретной точке. Схема Блэкли менее эффективна чем схема Шамира: в схеме Шамира каждая доля такого же размера как и секрет, а в схеме Блэкли каждая доля в t раз больше. Существуют улучшения схемы Блэкли, позволяющие повысить ее эффективность.

Схема Шамира Править

Основная идея схемы Шамира заключается в том, что двух точек достаточно для задания прямой, трех точек — для задания параболы, четырех точек — для кубической параболы, и так далее. Чтобы задать многочлен степени n требуется n+1 точек. Допустим, мы хотим создать (k, n)-пороговую схему Шамира (k<n) для разделения секретного числа S. Выберем k-1 случайных коэффициэнтов a1, …, ak-1, а также пусть a0=S. Возьмем многочлен f(x) = a0 + a1x + a2x2 + … + ak-1xk-1. Долями секрета будут являться n пар: (i, f(i)), где i=1…n. Имея k долей секрета можно вычислить все коэффициента многочлена, например с помощью интерполяционного многочлена Лагранжа, а значит и секрет S=a0.


da:Secret Sharing

de:Secret Sharing en:Secret sharing fr:Secret réparti he:חלוקת סוד nl:Secret sharing pl:Dzielenie sekretu

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

Также на ФЭНДОМЕ

Случайная вики