- Схема Асмута
-
Схема Асмута — Блума — пороговая схема разделения секрета, построенная с использованием простых чисел. Позволяет разделить секрет (число) между
сторонами таким образом, что его смогут восстановить любые
участников.
Описание
Пусть
- некоторый секрет, который требуется разделить. Выбирается простое число
, большее
. Выбирается
взаимно простых друг с другом чисел
, таких что:
Выбирается случайное число
и вычисляется
Вычисляются доли:
Участникам раздаются
Теперь, используя китайскую теорему об остатках можно восстановить секрет
имея
и более долей.
Пример
Предположим нам нужно разделить секрет
между 4-мя участниками таким образом, чтобы любые 3 из них могли этот секрет восстановить (а два участника — не могли бы). То есть нужно реализовать (3,4)-пороговую схему.
В качестве простого числа выберем
, в качестве взаимно простых -
. Проверяем, что:
Выбираем случайное число
и вычисляем:
Вычисляем доли:
Теперь попробуем восстановить исходный секрет, имея на руках доли
,
,
. Составим систему уравнений:
Мы можем восстановить
, используя китайскую теорему об остатках.
Зная
мы восстанавливаем секрет.
В данном примере, т.к. 155<17*19, то 2 участника спокойно восстановят секрет:) M' должно быть больше произведения долей неавторизованных участников.
Литература
- Шнайер Б. Схема Асмута-Блума // Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — С. 589—590. — 816 с. — 3000 экз. — ISBN 5-89392-055-4
- C. Asmuth, J. Bloom A modular approach to key safeguarding // Information Theory, IEEE Transactions on. — 1983. — В. 2. — Т. 29. — ISSN 0018-9448.
Категория:- Разделение секрета
Wikimedia Foundation. 2010.