Схема Асмута — Блума — пороговая схема разделения секрета, построенная с использованием простых чисел. Позволяет разделить секрет (число) между сторонами таким образом, что его смогут восстановить любые участников.

Описание

Пусть - некоторый секрет, который требуется разделить. Выбирается простое число , большее . Выбирается взаимно простых друг с другом чисел , таких что:

Выбирается случайное число и вычисляется

Вычисляются доли:

Участникам раздаются

Теперь, используя китайскую теорему об остатках можно восстановить секрет имея и более долей.

Пример

Предположим нам нужно разделить секрет между 4-мя участниками таким образом, чтобы любые 3 из них могли этот секрет восстановить (а два участника — не могли бы). То есть нужно реализовать (3,4)-пороговую схему.

В качестве простого числа выберем , в качестве взаимно простых - . Проверяем, что:

Выбираем случайное число и вычисляем:

Вычисляем доли:

Теперь попробуем восстановить исходный секрет, имея на руках доли , , . Составим систему уравнений:

Мы можем восстановить , используя китайскую теорему об остатках.

Зная мы восстанавливаем секрет.

Литература

• Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = 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. — 0018-9448.