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

Широковещательная передача сообщения

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

Криптография с несколькими ключами позволяет решить эту задачу намного проще. Мы будем использовать трех агентов: Алису, Боба и Кэрол. Вы выдадите Алисе ключ KA и KB, Бобу - KB и Кс, Кэрол - Кс и KA. Теперь вы сможете говорить с любым нужным подмножеством агентов. Если вы хотите, чтобы сообщение могла пр о-читать только Алиса, зашифруйте его ключом Кс. Когда Алиса получит сообщение, она расшифрует его, посл е-довательно используя ключи KA и KB. Если вы хотите послать сообщение только Бобу, зашифруйте его ключом Ка, а сообщение для Кэрол - ключом KB. Если вы хотите, чтобы посланное сообщение могли прочитать Алиса и Боб, зашифруйте его ключами KA и Кс.

Для трех агентов это не слишком впечатляет, но для 100 преимущество достаточно ощутимо. Индивидуал ь-ные сообщения означают использование отдельного ключа для каждого агента (всего 100 ключей) и каждого сообщения. Передача сообщений всем возможным подмножествам означает использование 2 100-2 различных ключей (исключены случаи сообщения всем агентам и никому из них) . Для схемы, использующий криптографию с несколькими открытыми ключами, нужно только одно шифрованное сообщение и сто различных ключей . Недостатком этой схемы является то, что вам также придется широковещательно передавать, какое подмнож е-ство агентов может читать сообщение, иначе каждому их них придется перебирать все возможные комбинации ключей в поисках подходящей. Даже только перечисление имен получателей может быть весьма внушительным. Кроме того, каждому агенту придется хранить немаленький объем информации о ключах, по крайней мере при прямолинейной реализации этой схемы .

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

Табл. 3-3.

Шифрование сообщения в трехключевой системе.

Шифруется ключами Должно быть расшифровано ключами ~КАKB и Kc

KbКа и Кс

КсКа и Кв

Ка и КвКс

Ка и КсКв

Кв и KcKA

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

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

Предлагаемая схема называется разделением секрета. Есть способы взять сообщение и разделить его на части [551]. Каждая часть сама по себе ничего не значит, но сложите их - и вы получите сообщение . Если это

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

По простейшей схеме сообщение делится между двумя людьми. Вот протокол, используя который Трент д е-лит сообщение между Алисой и Бобом :

(1)Трент генерирует строку случайных битов, R, такой же длины, что и сообщение, M.

(2)Трент выполняет "исключающее или" (XOR) над M и R, создавая S. R ® M = S

(3)Трент передает Алисе R, а Бобу - S.

Чтобы получить сообщение, Алисе и Бобу нужно выполнить единственное действие:

(4)Алиса и Боб выполняют операцию над имеющимися у них частями, восстанавливая сообщение. R ® S = M

Этот метод при правильном выполнении абсолютно безопасен. Каждая часть в отдельности абсолютно бе с-смысленна. Что существенно, Трент шифрует сообщение одноразовым блокнотом и дает шифротекст одному человеку, а блокнот - другому. Одноразовые блокноты, обладающие абсолютной безопасностью, обсуждаются в разделе 1.5. Никакие вычислительные средства не смогут восстановить сообщение только по одной его части .

Эту схему легко расширить на большее число людей . Чтобы разделить сообщение между более чем двумя людьми, выполните операцию XOR с большим числом строк случайных битов . В следующем примере Трент делит сообщение на четыре части :

(1)Трент генерирует три строки случайных битов, R, S и T, такой же длины, что и сообщение, M.

(2)Трент выполняет "исключающее или" (XOR) над M и созданными тремя строками, создавая U. M ® R ® S ® T = U

(3)Трент передает Алисе R, Бобу - S, Кэрол - T, а Дэйву - U. Вместе Алиса, Боб, Кэрол и Дэйв могут восстановить сообщение :

(4)Алиса, Боб, Кэрол и Дэйв собираются вместе и вычисляют: R ® S ® T ® U = M

Это арбитражный протокол. Трент обладает абсолютной властью и может делать все, что он хочет . Он может раздать чепуху и утверждать, что это настоящие части секретной информации, никто не сможет это пров е-рить, пока, собравшись вместе, участники протокола не попробуют прочитать письмо . Он может выдать части секрета Алисе, Бобу, Кэрол и Дэйву и позже заявить всем, что только Алиса, Кэрол и Дэйв нужны для восст а-новления секрета, застрелив при этом Боба. Но это не является проблемой, так как делимый секрет принадлежит Тренту.

Однако, одна проблема у этого протокола существует. Если любая из частей будет потеряна, а Трента не б у-дет поблизости, пропадет и все сообщение . Если Кэрол, обладая частью рецепта соуса, перейдет работать к ко н-куренту, оставив свою часть секрета у себя, значит, остальным не повезло. Она не сможет восстановить рецепт, но не смогут, собравшись, и Алиса, Боб и Дэйв . Ее часть также критична для восстановления сообщения, как и любая другая. Все, что известно Алисе, Бобу и Дэйву - это длина сообщения, и ничего больше . Это истинно, так как у R, S, T, U и M одинаковая длина, следовательно, каждому из участников известна длина M. Помните, сообщение M делится не в обычном смысле этого слова, а подвергается операции XOR со случайными величинами.

3.7 Совместное использование секрета

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

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

Можно сделать еще сложнее. Пусть только генерал у и паре полковников разрешено запустить ракету, но е с-ли генерал занят игрой в гольф, то запустить ракету имеют право только пять полковников . Сделайте контрольное устройство с пятью ключами. Выдайте генералу три ключа, а полковникам по одному. Генерал вместе с двумя полковниками или пять полковников смогут запустить ракету. Однако ни генерал в одиночку, ни четыре полковника не смогут этого сделать.

Более сложная схема совместного использования, называемая пороговой схемой, может решить и эти задачи, и более сложные - математически. На ее простейшем уровне вы можете взять любое сообщение (секретный рецепт, коды запуска, ваш список для прачечной и т.п.) и разделить его на n частей, называемых тенями или долями, так, что по любым m из них можно восстановить сообщение. Более точно, это называется (ш,п)-пороговой схемой.

Используя (3,4)-пороговую схему, Трент может разделить свой секретный рецепт между Алисой, Бобом, К э-рол и Дэйвом так, что любые трое из них могут сложить свои тени вместе и восстановить сообщение . Если Кэрол в отпуске, то Алиса, Боб и Дэйв смогут восстановить сообщение. Если Боб попал под автобус, то сообщение смогут восстановить Алиса, Кэрол и Дэйв. Но если Боб попал под автобус, а Кэрол в отпуске, то Алиса и Дэйв самостоятельно не смогут восстановить сообщение .

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

Эта идея была независимо выдвинута Ади Шамиром [1414] и Джорджем Блэкли (George Blakley) [182] и интенсивно была изучена Гусом Симмонсом (Gus Simmons) [1466]. Множество различных алгоритмов обсуждается в разделе 23.2.

Совместное использование с мошенниками

Существует множество способов обмануть пороговую схему. Вот только несколько из них. Сценарий 1 : Полковники Алиса, Боб и Кэрол сидят в изолированном бункере где-то глубоко под землей. Однажды они получают закодированное сообщение от президента: "Запустить ракеты. Мы собираемся стереть с лица Земли любые следы исследований противника в области нейронных сетей ". Алиса, Боб и Кэрол открывают свои тени, но Кэрол вводит случайное число. Он на самом деле пацифист и не хочет, чтобы ракеты были запущены . Поскольку Кэрол не ввела правильное тени, секретная информация, которую они хотели получить, оказалась неправильной. Ракеты остались в своих шахтах. И самое плохое, никто не знает почему. Даже объединившись Алиса и Боб не смогут доказать, что тень Кэрол неправильна.

Сценарий 2: Полковники Алиса и Боб сидят в бункере вместе с Мэллори. Мэллори ложно выдает себя за полковника. От президента приходит то же самое сообщение и все открывают свои тени . "Ха-ха-ха!" кричит Мэллори. "Я подделал это сообщение президента. Теперь я знаю обе ваших доли." Он убегает вверх по лестнице и исчезает прежде, чем его успеют поймать .

Сценарий 3: Полковники Алиса, Боб и Кэрол сидят в бункере вместе с Мэллори, который снова замаскировался. (Помните, у Мэллори нет правильной тени.) От президента приходит то же самое сообщение и все о т-крывают свои тени. Мэллори открывает свою тень, только услышав все остальные . Так как для восстановления секрета требуется только три тени, он может быстро создать правильную тень и открыть ее. Итак, он не только заполучил секрет, но и никто не догадался, что он не является частью этой системы . Некоторые протоколы, которые позволяют бороться с подобными мошенниками, рассматриваются в разделе 23.2.

Совместное использование секрета без Трента

Банк хочет, чтобы его подвал могли открыть трое из пяти офицеров, введя свои ключи . Это выглядит как типичная (3,5)-пороговая схема, но с одной тонкостью. Никто не знает секрета целиком. Трента, которые делит секрет на пять частей, нет. Существуют протоколы, используя которые пять офицеров могут создать секрет и поделить его на части так, что никто из офицеров не узнает секрета, пока он не будет восстановлен . В этой книге я не рассматриваю эти протоколы, подробности см. в [756].

Совместное использование секрета без раскрытия долей

У этих схем есть одна проблема. Когда участники протокола собираются, чтобы восстановить секрет, они открывают свои части. Но раскрытие секрета не всегда желательно . Если разделяемый секрет является закрытым ключом (например, к цифровой подписи), то каждый из n участников может выполнить частичную подпись