Разделение секрета Шамира

Разделение

Представим ситуацию – вам нужно обеспечить безопасность содержимого банковской ячейки. Со своей стороны, банк уже сделал всё возможное, чтобы никто посторонний не смог до него добраться. Поэтому и снабдил вас единственным ключом, предоставляющим доступ к содержимому. Вот только этот ключ у вас могу украсть, вы его можете потерять, а при неправильном, например, ношении – он может самостоятельно испортиться. И придётся проходить долгую процедуру восстановления доступа. Не говоря о том, что чтобы получить содержимое в своё распоряжение, вам, как единственному владельцу ключа, придётся каждый раз лично присутствовать при посещении банка.

Возможный вариант – сделать копию ключа и передать её доверенному лицу. Теперь шанс потери доступа уменьшается, но повышается риск в случае кражи. Тоже не слишком хорошее решение.

Ещё один вариант – разделить начальный ключ на 2 части. Теперь вору придётся украсть обе, чтобы обеспечить себе доступ. Но при потере любой из этих частей – снова придётся проходить процедуру восстановления доступа.

Поэтому оптимальный вариант – создать такую схему хранения ключа или его фрагментов, чтобы от недееспособности одного из участников этой схемы не менялась её функциональность. Именно эту проблему и решает методика, называемая «Разделение секрета Шамира».

Что это такое?

Автор идеи – израильский криптограф Ади Шамир. В 1970 году им была опубликована научная работа «Как разделить секрет», в которой описывалась пороговая схема, позволяющая получать доступ к разделённой на n частей информации, обладая только k частями. k само собой меньше n. При этом даже наличие k-1 частей не даёт никакого представления о ключе и не облегчает его подбор. То есть – ещё и семантическая безопасность.

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

Конкретно в ситуации с распределением секрета Шамира используется так называемый интерполяционный многочлен Лагранжа. Он позволяет определить то самое количество точек k, которое нужно для определения всей функции.

В практическом виде это выглядит так. Есть дилер, который предлагает услуги хранения информации. Он же предоставляет приватный ключ, который затем разбивается на некое количество частей. Каждая эта часть выдаётся одному из участников. Теперь для получения доступа к информации, k таких человек должны объединить свои усилия. При этому им не обязательно всем присутствовать в одном месте – точка отказа будет создаваться дистанционно, после обмена информацией.

Метод немного напоминает мультисиг-кошелёк (кошелёк с несколькими электронными подписями), но есть и существенные различия. РСШ работает офлайн, а мультисиг – исключительно в рамках работающей сети. Кроме того, для мультисиг необходим одновременный доступ участников, а в ситуации РСШ его можно растянуть по времени. Считается, что РСШ удобнее для физических лиц, а кошелёк с мультиподписями – для крупных предприятий.

Конкретные преимущества РСШ

  • Возможность многомерного контроля доступа. Для каждой из отдельных и самих по себе бесполезных частей секрета можно обеспечить контролируемое хранение. Это избавляет от необходимости доверять конкретным людям.
  • Данный способ подходит для хранения абсолютно любой информации (приватные ключи, корневые ключи серверов, различные сертификаты, типа PGP/GPG), в то время, как мультисиг в этом плане более ограниченный.
  • Возможность работы с блокчейном. Увы, система мультисиг поддерживается не во всех случаях, а с помощью РСШ можно спокойно разбивать на части любые сид-фразы. Кроме того, отпадает необходимость в единой точке доступа (отказа).
  • Сохранение конфиденциальности информации даже в случае попадания отдельных фрагментов в руки злоумышленников.
  • Используется только один приватный ключ, поэтому – меньше операций и связанных с ними комиссионных сборов.
  • Упрощённое изменение схемы доступа. Если один фрагмент окажется скомпрометированным – вы просто создаёте такое же количество новых фрагментов и снова раздаёте их доверенным лицам, удалив «старые».
  • Повышенная стойкость с точки зрения теории информации. Если у злоумышленника нет всех нужных фрагментов, даже неограниченная вычислительная мощность не позволит ему подобрать ключ.

Проблемы РСШ и их решения

  • Стандартный размер. Длина любого фрагмента секрета соответствует длине самого секрета, так что, зная один фрагмент, можно делать некоторые предположения о величине зашифрованных данных. Решает предварительным наполнением зашифрованной информации произвольными числами.
  • Отсутствие проверяемых схем. По сути, зная один фрагмент секрета, злоумышленник сможет аппаратным путём воспроизвести аналогичные по длине. Они не дадут права воспользоваться информацией, но затруднят восстановление правильного секрета. Поэтому очень часто в данных алгоритмах используют дополнительные проверяемые схемы разделения секрета, например – схему Фельмана.

Разделение секрета Шамира – крайне удобный способ обеспечения доступа к защищённой информации. Однако не стоит забывать, что его лучше сочетать с дополнительными методами защиты, такими, как проверка постоянного времени выполнения, отсутствие сохранения введённых данных на диске, рациональное хранение каждого отдельного фрагмента и много чего ещё.