§ 8.6. Посвящение в тайну

Бенджамен Франклин (Franklin) однажды сказал: «Трое могут хранить тайну, если двое из них мертвы.» В этом параграфе мы изучаем безопасную систему допуска живых к секретным сведениям, основанную на китайской теореме об остатках. Представьте себе следующую ситуацию. Подвал банка

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

Рассмотрим эту проблему в более общем виде. Для того, чтобы открыть подвал банка, необходимо знать код, который можно считать натуральным числом s. Мы хотим распределить этот код между старшими кассирами так, чтобы каждый из них знал что-то об s. Назовем такую частичную информацию фрагментом кода. Более того, открыть подвал должно быть невозможно, если в банке присутствуют менее к старших кассиров, где — натуральвгое число, меньшее Мы добьемся этого условия, распределив информацию о коде таким образом, что

• число s легко определяется, если известно к или более фрагментов;

• число s трудно определимо, если известно менее к фрагментов.

Фрагменты кода, сообщаемые каждому из старших кассиров, — это, в действительности, элементы множества , состоящего из упорядоченных пар натуральных чисел. Чтобы построить , выберем сначала множество из попарно взаимно простых чисел. Пусть произведение наименьших к из них, произведение к — 1 наибольших. Будем говорить, что к является порогом для если Из этого условия следует, что произведение любых k (или более) элементов из всегда больше, чем а произведение (или менее) его элементов — всегда меньше М.

Предположим, код s выбран так, что , а множество состоит из пар где вычет числа s по модулю Эти пары и являются теми фрагментами кода,

которые сообщаются старшим кассирам. Тот факт, что множество имеет порог обеспечивает неравенство для каждого В частности, для любого

Что произойдет, если к или более старших кассиров находятся в банке? В этом случае известны пар из множества . Обозначив эти пары через рассмотрим систему сравнений:

Элементы множества попарно взаимно просты. Значит, по китайской теореме об остатках, эта система имеет решение Но совпадает ли Это как раз та причина, по которой мы накладывали требование: имеет порог к. Поскольку то наше требование влечет:

Но s тоже удовлетворяет системе (6.1), и по китайской теореме об остатках

А так как натуральные числа, меньшие то

Предположим теперь, что в банке находится менее к старших кассиров. Несмотря на то, что теперь меньше мы все равно сможем решить систему (6.1). Пусть наименьшее неотрицательное решение, тогда Но произведение меньшего, чем к количества элементов из всегда меньше так что Следовательно, решения системы не достаточно для восстановления кода s. Однако как так решения системы (6.1), поэтому

где у — некоторое натуральное число. Неравенство

влечет

Приходим к выводу: если то для восстановления кода s нам предстоит отыскивать недостающий множитель у среди более чем

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

Для завершения разбора задачи осталось осветить один вопрос: можно ли найти множество удовлетворяющее всем необходимым требованиям? Ответ на него положителен, но нуждается в результатах о распределении простых чисел, которые выходят за рамки данной книги. Этот вопрос детально обсуждается в [32].

Сделаем обзор рассмотренной конструкции. Для нее требуются начальные данные: число старших кассиров, имеющих доступ в подвал банка, и наименьшее число к из них, присутствие которых в банке достаточно для открытия подвала. Первое число определяет размер множества а второе — его порог к. Далее нам нужно подобрать множество из элементов с порогом к (эту часть конструкции мы подробно не обсуждали), и вычислить определенные выше. Напомним, что нужно выбирать с таким расчетом, чтобы число о котором мы говорили, было как можно больше; в противном случае код может быть разгадан простым перебором. Код натуральное число, которое выбирается лежащим между Теперь можно вычислить элементы множества и сообщить их сотрудникам. Конечно, безопасность этой схемы зависит от того, насколько велико уменьшающее вероятность, что одновременно к кассиров из одного банка окажутся

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

Рассмотрим пример. Допустим, что в банке работают 5 старших кассиров и из соображений безопасности по крайней мере двое из них должны присутствовать при открытии подвала. Значит, должно состоять из пяти элементов, а его порог равен 2. Выбрав элементы среди малых простых чисел, получим:

Произведение двух наименьших чисел этого множества равно . С другой стороны, поскольку произведение к — 1 наибольших простых из в действительности равно его максимальному элементу. Таким образом, имеет порог 2. Код s может быть любым целым числом, лежащим между 23 и 143. Пусть Тогда

Наконец, что будет, если в банке присутствуют старшие кассиры с фрагментами (17,13) и Код из их фрагментов получается как наименьшее число, удовлетворяющее системе:

Легко увидеть, что таким числом будет 30. Этот код корректен, он позволяет открыть подвал.

Упражнения

(см. скан)

(см. скан)

(см. скан)