Как читать эту книгу 7 страница

Е_В(S_А(А, В, K, Т_А)), S_T(А, K_А), S_T(В, K_В)

Теперь Боб не сможет повторно послать Кэрол старое сообщение, потому что оно явно предназначено для сеанса связи между Алисой и Бобом.

Woo-Lam

В этом протоколе также используется криптография с открытыми ключами [1610, 1611]:

(1) Алиса посылает Тренту сообщение, состоящее из ее имени и имени Боба.

А, В

(2) Трент посылает Алисе открытый ключ Боба, K_B, подписанный закрытым ключом Трента, T.

S_T(K_B)

(3) Алиса проверяет подпись Трента. Затем она посылает Бобу свое имя и случайное число, шифрованное открытым ключом Боба.

А, Е_В(R_В)

(4) Боб посылает Тренту свое имя, имя Алисы и случайное число Алисы, шифрованное открытым ключом Трента, K_Т.

А, В, (R_A)

(5) Трент посылает Бобу открытый ключ Алисы, K_А, подписанный закрытым ключом Трента. Он также посылает Бобу случайное число Алисы, случайный сеансовый ключ, имена Алисы и Боба, подписав все это закрытым ключом Трента и зашифровав открытым ключом Боба.

S_Т(K_А), (S_Т (R_A, К, А, В))

(6) Боб проверяет подписи Трента. Затем он посылает Алисе вторую часть сообщения Трента, полученного на этапе (5), и новое случайное число, зашифровав все открытым ключом Алисы.

(S_Т (R_A, К, А, В), R_В)

(7) Алиса проверяет подпись Трента и свое случайное число. Затем она посылает Бобу второе случайное число, шифрованное сеансовым ключом.

Е_К(R_В)

(8) Боб расшифровывает свое случайное число и проверяет, что оно не изменилось.

Другие протоколы

В литературе описано множество протоколов. Протоколы X.509 рассматриваются в разделе 24.9, KryptoKnight - в разделе 24.6, а Шифрованный обмен ключами (Encrypted Key Exchange) - в разделе 22.5.

Другим новым протоколом с открытыми ключами является Kuperee [694]. Ведется работа на протоколами, использующими маяки - заслуживающие доверия узлы сети, которые непрерывно и широковещательно передают достоверные метки времени [783].

Выводы

Из приведенных протоколов, как из тех, которые вскрываются, так и из надежных, можно извлечь ряд важных уроков:

— Многие протоколы терпят неудачу, так как их разработчики пытались быть слишком умными. Они оптимизировали протоколы, убирая важные элементы - имена, случайные числа и т.п. - и пытаясь сделать протоколы как можно более прозрачными [43, 44].

— Оптимизация - эта манящая ловушка - сильно зависит от сделанных предположений. Пример: наличие достоверного времени позволяет вам реализовать многие вещи, невозможные в противном случае.

— Выбираемый протокол зависит от архитектуры используемых средств связи. Хотите ли вы минимизировать размер сообщений или их количество? Могут ли сторона взаимодействовать каждый с каждым или круг их общения будет ограничен?

Именно подобные вопросы и привели к созданию формальных методов анализа протоколов.

3.4 Формальный анализ протоколов проверки подлинности и обмена ключами

Проблема выделения безопасного сеансового ключа для пары компьютеров (или людей) в сети настолько фундаментальна, что стала причиной многих исследований. Некоторые исследования заключались в разработке протоколов, подобных рассматриваемым в разделах 3.1, 3.2 и 3.3. Это, в свою очередь, привело к появлению более важной и интересной задачи: формальному анализу протоколов проверки подлинности и обмена ключами. Иногда прорехи в протоколах, кажущихся вполне надежными, обнаруживались спустя много лет после их разработки, и разработчикам потребовались средства, позволяющие сразу же проверять безопасность протокола. Хотя большая часть этого инструментария применима и к более общим криптографическим протоколам, особое внимание уделялось проверке подлинности и обмену ключами. Существует четыре основных подхода к анализу криптографических протоколов [1045]:

1. Моделирование и проверка работы протокола с использованием языков описания и средств проверки, не разработанных специально для анализа криптографических протоколов.

2. Создание экспертных систем, позволяющих конструктору протокола разрабатывать и исследовать различные сценарии.

3. Выработка требований к семейству протоколов, используя некую логику для анализа понятий "знание" и "доверие".

4. Разработка формальных методов, основанных на записи свойств криптографических систем в алгебраическом виде.

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

Первый из подходов пытается доказать правильность протокола, рассматривая его как обычную компьютерную программу. Ряд исследователей представляют протокол как конечный автомат [1449, 1565], другие используют расширения методов исчисления предиката первого порядка [822], а третьи для анализа протоколов используют языки описания [1566]. Однако, доказательство правильности отнюдь не является доказательством безопасности, и этот подход потерпел неудачу при анализе многих "дырявых" протоколов. И хотя его применение поначалу широко изучалось, с ростом популярности третьего из подходов работы в этой области были переориентированы.

Во втором подходе для определения того, может ли протокол перейти в нежелательное состояние (например, потеря ключа), используются экспертные системы. Хотя этот подход дает лучшие результаты при поиске "дыр", он не гарантирует безопасности и не предоставляет методик разработки вскрытий. Он хорош для проверки того, содержит ли протокол конкретную "дыру", но вряд ли способен обнаружить неизвестные "дыры" в протоколе. Примеры такого подхода можно найти в [987, 1521], а в [1092] обсуждается экспертная система, разработанная армией США и названная Следователем (Interrogator ).

Третий подход гораздо популярнее. Он был впервые введен Майклом Бэрроузом (Michael Burrows), Мартином Абэди (Martin Abadi) и Роджером Неедхэмом. Они разработали формальную логическую модель для анализа знания и доверия, названную БАН-логикой[283, 284]. БАН-логика является наиболее широко распространена при анализе протоколов проверки подлинности. Она рассматривает подлинность как функцию от целостности и новизны, используя логические правила для отслеживания состояния этих атрибутов на протяжении всего протокола. Хотя были предложены различные варианты и расширения, большинство разработчиков протоколов до сих пор обращаются к оригинальной работе.

БАН-логика не предоставляет доказательство безопасности, она может только рассуждать о проверке подлинности. Она является простой, прямолинейной логикой, легкой в применении и полезной при поиске "дыр". Вот некоторые предложения БАН-логики:

Алиса считает X. (Алиса действует, как если бы X являлось истиной.)

Алиса видит X. (Кто-то послал сообщение, содержащее X, Алисе, которая может прочитать и снова передать X - возможно после дешифрирования.)

Алиса сказала X. (В некоторый момент времени Алиса послала сообщение, которое содержит предложение X. Не известно, как давно было послано сообщение, и было ли оно послано в течение текущего исполнения протокола. Известно, что Алиса считала X, когда говорила X.)

X ново. (X никогда не было послано в сообщении до текущего выполнения протокола.)

И так далее. БАН-логика также предоставляет правила для рассуждения о доверии протоколу. Для доказательства чего-либо в протоколе или для ответа на какие-то вопросы к логическим предложениям о протоколе можно применить эти правила. Например, одним из правил является правило о значении сообщения:

ЕСЛИ Алиса считает, что у Алисы и Боба общий секретный ключ, K, и Алиса видит Х, шифрованное K, и Алиса не шифровала X с помощью K,ТО Алиса считает, что Боб сказал X.

Другим является правило подтверждения метки времени:

ЕСЛИ Алиса считает, что X могло быть сказано только недавно, и, что Боб X когда-то сказал X, ТО Алиса считает, что Боб считает X.

БАН-анализ делится на четыре этапа:

(1) Преобразуйте протокол к идеальной форме, используя описанные выше предложения.

(2) Добавьте все предположения о начальном состоянии протокола.

(3) Присоедините логические формулы к предложениям, получая утверждения о состоянии системы после каждого предложения.

(4) Примените логические постулаты к утверждениям и предположениям, чтобы раскрыть состояние доверия участников протокола.

Авторы БАН-логики "рассматривают идеализированные протоколы как более ясные и полные описания, чем традиционные, найденные в литературе..." [283, 284]. Другие исследователи не так оптимистичны и подвергают это действие критике, так как при этом реальный протокол может быть искажен [1161, 1612]. Дальнейшие споры отражены в [221, 1557]. Ряд критиков пытается показать, что БАН-логика может и получить очевидно неправильные характеристики протоколов [1161] - см. контрдоводы в [285, 1509] - и что БАН-логика занимается только доверием, а не безопасностью [1509]. Подробное обсуждение приведено в [1488, 706, 1002].

Несмотря на эту критику БАН-логика достигла определенных успехов. Ей удалось обнаружить "дыры" в нескольких протоколах, включая Needham-Schroeder и раннюю черновую версию протокола CCITT X.509 [303]. Она обнаружила избыточность во многих протоколах, включая Yahalom, Needham-Schroeder и Kerberos. Во многих опубликованных работах БАН-логика используется для заявления претензии о безопасности описываемых протоколов [40, 1162, 73].

Были опубликованы и другие логические системы, некоторые из них разрабатывались как расширения БАН-логики [645, 586, 1556, 828], а другие основывались на БАН-логике для исправления ощутимых слабостей [1488, 1002]. Из них наиболее успешной оказалась CNY [645], хотя у нее есть ряд изъянов [40]. В [292,474] к БАН-логике с переменным успехом были добавлены вероятностные доверия. Другие формальные логики описаны в [156, 798,288]. [1514] пытается объединить черты нескольких логик. А в [1124, 1511] представлены логики, в которых доверия изменяются со временем.

Четвертый подход к анализу криптографических протоколов предлагает моделировать протокол как алгебраическую систему, выразить состояние знания участников о протоколе и затем проанализировать достижимость определенных состояний. Этот подход пока не привлек столько внимания, как формальная логика, но состояние дел меняется. Он впервые был использован Майклом Мерриттом [1076], который показал, что для анализа криптографических протоколов можно использовать алгебраическую модель. Другие подходы рассмотрены в [473, 1508, 1530, 1531, 1532, 1510, 1612].

Анализатор протоколов Исследовательской лаборатория ВМС (Navy Research Laboratory, NRL), возможно, является наиболее успешным применением этих методов [1512, 823, 1046, 1513]. Он был использован для поиска как новых, так и известных "дыр" во множестве протоколов [1044, 1045, 1047]. Анализатор протоколов определяет следующие действия:

— Принять (Боб, Алиса, M, N). (Боб принимает сообщение M как пришедшее от Алисы в течение локального раунда Боба N.)

— Узнать (Ева, M). (Ева узнает M.)

— Послать (Алиса, Боб, Q, M). (Алиса посылает M Бобу в ответ на запрос, Q.)

— Запросить (Боб, Алиса, Q, N). (Боб посылает Q Алисе в течение локального раунда Боба N.)

Используя эти действия, можно задать требования. Например:

— Если Боб принял сообщение M от Алисы в какой-то прошедший момент времени, то Ева не знает M в какой-то прошедший момент времени.

— Если Боб принял сообщение M от Алисы в течение локального раунда Боба N, то Алиса послала M Бобу в ответ на запрос Боба в локальном раунде Боба N.

Для анализа Анализатором протоколов NRL исследуемый протокол должен быть описан с помощью приведенных конструкций. Затем выполняются четыре фазы анализа: определение правил перехода для честных участников, описание операций, возможных и для полностью честных, и для нечестных участников, описание базовых блоков протокола и описание правил преобразования. Смысл всего этого в том, чтобы показать, что данный протокол удовлетворяет необходимым требованиями. Использование инструментов, подобных Анализатору протоколов NRL, в итоге могло бы привести к созданию протокола, который был бы обоснованно признан безопасным.

Хотя формальные методы в основном применяются к уже существующим протоколам, сегодня есть тенденция использовать их и при проектировании протоколов. Ряд предварительных шагов в этом направлении сделан в [711]. Это же пытается сделать и анализатор протоколов NRL [1512, 222, 1513].

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

3.5 Криптография с несколькими открытыми ключами

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

Эта концепция была обобщены Конном Бойдом (Conn Boyd) [217]. Представьте себе вариант криптографии с открытыми ключами, использующий три ключа: K_A, K_Bи K_C, распределение которых показано в Табл. -2.

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

Табл. -2.
Распределение ключей в трехключевой системе.

Алиса	KA
Боб	KB
Кэрол	KС
Дэйв	KA и KB
Эллен	KB и Kc
Франк	KС и KA

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

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

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

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

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

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

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

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

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

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

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

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

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

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

R Å M = S

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

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

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

R Å S = M

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

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

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

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

M Å R Å S Å T = U

(1) Трент передает Алисе R, Бобу - S, Кэрол - T, а Дэйву - U.

Вместе Алиса, Боб, Кэрол и Дэйв могут восстановить сообщение:

(4) Алиса, Боб, Кэрол и Дэйв собираются вместе и вычисляют:

R Å S Å T Å U = M

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

У этих схем есть одна проблема. Когда участники протокола собираются, чтобы восстановить секрет, они открывают свои части. Но раскрытие секрета не всегда желательно. Если разделяемый секрет является закрытым ключом (например, к цифровой подписи), то каждый из n участников может выполнить частичную подпись документа. После n-ой частичной подписи документ оказывается подписан совместно используемым закрытым ключом, а ни один из участников не может узнать содержания части, используемой другим участником. Смысл в том, что вы можете повторно использовать секрет, и для работы с ним вам не понадобится надежный посредник. Дальнейшее развитие эта идея получила в работах Иво Десмедта (Yvo Desmedt) и Йера Френкеля (Yair Frankel) [483, 484].

Подтверждаемое совместное использование секрета

Трент передает Алисе, Бобу, Кэрол и Дэйву часть секрета (или, по крайней мере, заявляет, что он это делает). Единственный способ убедиться, что их части правильны - это попытаться восстановить секрет. Может быть, Трент послал Бобу поддельную часть, или часть Боба случайно испортилась при передаче по линиям связи. Подтверждаемое совместное использование секрета позволяет каждому из участников лично убедиться, что их часть правильна, без необходимости восстанавливать секрет [558, 1235].

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

Секрет делится среди 50 человек так, чтобы любые 10 могли собраться вместе и восстановить секрет. Это нетрудно. Но, можем ли мы реализовать ту же схему совместного использования секрета, добавив требование, чтобы 20 человек могли собраться вместе и помешать остальным, независимо от их числа, восстановить секрет? Оказывается, что да [153].