Отправитель и получатель. Сообщения и шифрование 11 глава

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

2. Виктор не может обмануть Пегги. Он не получает ни малейшего намека на доказательство кроме того факта, что доказательство известно Пегги. В частности, Виктор не может продемонстрировать доказательство никому другому, не доказав все сам с самого начала.

У доказательств с нулевым знанием есть дополнительное условие:

3. Виктор не узнает от Пегги ничего такого, чего он не смог бы узнать и самостоятельно кроме того факта, что доказательство известно Пегги.

Существует заметная математическая разница между доказательствами с минимальным раскрытием и доказательствами с нулевым знанием. Это различие находится вне рамок данной книги, но более искушенные читатели могут проштудировать другую литературу. Понятия изложены в in [626, 619, 622]. Дальнейшая проработка этих идей, основанная на различных математических предположениях, выполнена в [240, 319, 239].

Существуют различные типы доказательств с нулевым знанием:

— Совершенное. Существует имитатор, который создает стенограммы, полностью соответствующие реальным стенограммам (примеры с гамильтоновым циклом и изоморфизмом графов).

— Статистическое. Существует имитатор, который создает стенограммы, полностью соответствующие реальным стенограммам, кроме фиксированного числа исключений.

— Вычислительное. Существует имитатор, который создает стенограммы, неотличимые от реальных.

— Неиспользующее. Имитатора может и не быть, но мы можем доказать, что Виктор не узнает никакой информации из доказательства (параллельный пример)

Годы тяжелой работы, как теоретической, так и прикладной, присели к появлению доказательств с минимальным раскрытием и нулевым знанием. Майк Берместер (Mike Burmester) и Иво Десмедт изобрели широковещательно интерактивное доказательство, где владелец секрета может широковещательно передавать большой группе контролеров интерактивное доказательство с нулевым знанием [280]. Криптографы доказали, что все, что может быть доказано с помощью интерактивного доказательства, может быть доказано и с помощью интерактивного доказательства с нулевым знанием [753, 137].

Хорошей обзорной статьей по данной теме является [548]. Дополнительные математические подробности, варианты, протоколы и приложения ищите в [590, 619, 240, 319, 620, 113,241, 152, 8, 660, 238, 591, 617, 510, 592, 214, 104, 216, 832, 97, 939, 622, 482, 615, 618, 215, 476, 71]. Много чегобыло написано по этому вопросу.

5.2 Использование доказательства с нулевым знанием для идентификации

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

Использовать доказательства с нулевым знанием для доказательства идентичности было впервые предложено Уриелем Файгом (Uriel Feige), Амосом Фиатом (Amos Fiat) и Ади Шамиром [566, 567]. Закрытый ключ Алисы становится функцией ее "идентичности". Используя доказательство с нулевым знанием, она доказывает, что она знает свой закрытый ключ и, таким образом, свою идентичность. Соответствующие алгоритмы можно найти в разделе 23.11.

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

Проблема гроссмейстера

Вот как Алиса, даже не зная правил шахмат, может обыграть гроссмейстера. (Иногда это называется проблемой гроссмейстера.) Она посылает вызов Гарри Каспарову и Анатолию Карпову, предлагая играть в одно время, в одном и том же мести, но в раздельных комнатах. Она играет белыми против Каспарова и черными против Карпова. Ни один гроссмейстер не знает о другом.

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

На самом деле Каспаров играет с Карповым, а Алиса просто посредник, повторяющий ходы одного гроссмейстера на доске другого. Однако, если Карпов и Каспаров не знают о присутствии друг друга, каждый из них будет поражен игрой Алисы.

Этот способ мошенничества может быть использовать против доказательства личности с нулевым знанием [485, 120]. Когда Алиса доказывает свою личность Мэллори, Мэллори может одновременно доказать Бобу, что он-то и есть Алиса.

Обман, выполненный мафией

Обсуждая свой протокол идентификации с нулевым знанием, Ади Шамир сказал [1424]: "Я могу ходить в принадлежащий мафии магазин хоть миллион раз подряд, а они все еще не смогут выдать себя за меня."

Вот как мафия сможет это сделать. Алиса ест в ресторанчике Боба, принадлежащем мафии. Кэрол делает покупки в дорогом ювелирном магазине Дэйва. Боб и Кэрол - мафиози, переговаривающиеся по потайному радиоканалу. Алиса и Дэйв не подозревают о мошенничестве.

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

Обман, выполненный террористами

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

Когда Дэйв задает Кэрол вопросы в соответствии по протоколу с нулевым знанием, Кэрол передает их Алисе, которая и отвечает на вопросы. Кэрол повторяет эти ответы Дэйву. Carol recites these answers to Dave. По сути, Свою личность Дэйву доказывает Алиса, а Кэрол выступает в роли линии связи. Когда протокол завершается, Дэйв считает, что Кэрол - это Алиса, и разрешает ей въехать в страну. Спустя три дня Кэрол всплывает у правительственного здания вместе с микроавтобусом, набитом взрывчаткой.

Предлагаемые решения

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

Тотас Бот (Thomas Both) и Иво Десмедт предложили другое решение, использующее точные часы [148]. Если каждый этап протокола должен происходить в заданное время, у мошенников не останется времени для обмена информацией. В случае с проблемой гроссмейстера это соответствует предложению ограничить время обдумывания хода одной минутой - у Алисы не останется времени бегать из комнаты в комнату. В истории с мафией у Боб и Кэрол не хватит времени передавать друг другу ответы и вопросы.

Обман с несколькими личностями

Существуют и другие способы злоупотребить доказательствами идентичности с нулевым знанием, также рассматриваемые в [485, 120]. В ряде реализаций проверка при регистрации человеком своего ключа не производится. Следовательно, у Алисы может быть несколько закрытых ключей и, таким образом, несколько личностей. Это может здорово помочь ей, если она захочет мошенничать с налогами. Алиса также может совершить преступление и скрыться. В первых, она создает несколько личностей, одна из которых не используется. Затем, она использует эту личность для совершения преступления так, чтобы свидетель идентифицировал ее как эту личность. Затем, она немедленно прекращает пользоваться этой личностью. Свидетель знает личность преступника, но Алиса никогда больше не будет использовать эту личность - ее невозможно проследить.

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

Прокат паспортов

Алиса хочет поехать в Заир, но правительство этой страны не дает ей визы. Кэрол предлагает сдать свою личность Алисе "напрокат". (Первым это предложил Боб, но возник ряд очевидных проблем.) Кэрол продает Алисе свой закрытый ключ и Алиса едет в Заир, выдавая себя за Кэрол.

Кэрол получает не только плату за свою личность, но и идеальное алиби. Она совершает преступление, пока Алиса находится в Заире. "Кэрол" доказала свою личность в Заире, как она могла совершить преступление дома?

Конечно, развязаны руки и у Алисы. Она может совершить преступление либо перед отъездом, либо сразу же после возвращения, около дома Кэрол. Сначала она покажет, что она - Кэрол (имея закрытый ключ Кэрол, ей не составит труда сделать это), затем она совершит преступление и убежит. Полиция будет искать Кэрол. Кэрол будет утверждать, что сдала свою личность напрокат Алисе, но кто поверит в такую невероятную историю?

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

Доказательство членства

Алиса хочет доказать Бобу, что она является членом суперсекретной организации, но не хочет раскрывать свою личность. Эта проблема, близкая проблеме доказательства личности, но отличающаяся от нее, была изучена в [887, 906, 907, 1201, 1445]. Ряд решений связан с проблемой групповых подписей (см. раздел 4.6).

5.3 Слепые подписи

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

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

Полностью слепые подписи

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

(1) Алиса берет документ и умножает его на случайное число. Это случайное число называется маскирующим множителем.

(2) Алиса посылает замаскированный документ Бобу.

(3) Боб подписывает замаскированный документ.

(4) Алиса удаляет маскирующий множитель, получая оригинальный документ, подписанный Бобом.

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

Может ли боб смошенничать? Может ли он получить какую-нибудь информацию о том, что пописывает? Если множитель осторожности действительно случаен и делает замаскированный документ действительно случайным, то нет. Замаскированный документ, подписываемый Бобом на этапе, (2) ничем не похож на оригинальный документ Алисы. Замаскированный документ с подписью Боба на нем на этапе (3) ничем не похож на подписанный документ этапа (4). Даже если Боб заполучит документ со своей подписью после окончания протокола, он не сможет доказать (себе или кому-то другому), что он подписал его в этом конкретном протоколе. Он знает, что его подпись правильна. Он может, как и любой другой, проверить свою подпись. Однако, у него нет никакой возможности связать подписанный документ и любую информацию, полученную при выполнении протокола. Если он подписал, используя этот протокол, миллион документов, у него не будет способа узнать когда какой документ он подписал. Полностью слепые подписи обладают следующими свойствами:

1. Подпись Боба под документом правильна и служит доказательством того, что Боб подписал этот документ. Она убедит Боба в том, что он подписал этот документ, когда документ будет впоследствии показан Бобу. Она также обладает всеми свойствами цифровых подписей, обсуждаемых в разделе 2.6.

2. Боб не может связать подписанный документ с процессом подписания документа. Даже если у него хранятся записи обо всех сделанных им слепых подписях, он не сможет определить, когда он подписал конкретный документ.

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

Слепые подписи

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

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

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

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

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

В следующем сценарии действует группа агентов контрразведки. Их личности засекречены, даже само Управление контрразведки не знает, кто они такие. Директора Управления хочет выдать каждому агенту подписанный документ следующего содержания: "Податель этого подписанного документа, (вставьте имя, под которым действует агент), обладает полной дипломатической неприкосновенностью". У каждого из агентов есть свой список псевдонимов, поэтому Управление не может просто раздать подписанные документы. Агенты не хотят передавать свои псевдонимы в Управление, так как враг мог вскрыть компьютер Управления. С другой стороны, Управление не хочет слепо подписывать документы, предоставленные агентом. Хитрый агент может представить сообщение, подобное следующему: "Агент (имя) вышел в отставку, и ему назначена ежегодная пенсия в миллион долларов. Подписано, Президент". В этом случае могут быть полезны слепые подписи.

Предположим, что у каждого агента по 10 псевдонимов, выбранных ими самими и больше никому неизвестных. Предположим также, что агентам все равно, под каким именем они получат дипломатическую неприкосновенность. Также предположим, компьютер управления называется Agency's Large Intelligent Computing Engine (Большая Интеллектуальная Вычислительная Машина Управления), или ALICE, а нашим конкретным агентом является Bogota Operations Branch (Сектор операций в Боготе): BOB.

(1) BOB готовит nдокументов, каждый из которых использует различный псевдоним, дающих ему дипломатическую неприкосновенность.

(2) BOB маскирует каждый из документов отличным маскирующим множителем.

(3) BOB отправляет nдокументов ALICE.

(4) ALICE случайным образом выбирает n-1 документ и просит BOB'а прислать маскирующий множитель для каждого из выбранных документов.

(5) BOB посылает ALICE соответствующие маскирующие множители.

(6) ALICE открывает (т.е., удаляет маскирующий множитель) n-1 документ и убеждается в том, что они корректны - и не являются разрешением на выплату пенсии.

(7) ALICE подписывает оставшийся документ и посылает его BOB'у.

(8) Агент удаляет маскирующий множитель и читает свой новый псевдоним: "Малиновая полоса." Подписанный документ дает ему дипломатическую неприкосновенность под этим именем.

Этот протокол надежно защищен от мошенничества BOB'а. Чтобы смошенничать, он должен точно угадать, какой документ ALICE не будет проверять. Вероятность этого - 1 шанс из n - не слишком велика. ALICE знает это и чувствует себя уверенно, подписывая документ, который она не сможет проверить. Для этого документа рассматриваемый протокол полностью совпадает с предыдущим протоколом полностью слепой подписи, сохраняя все свойства анонимности.

Существует трюк, который еще больше уменьшает вероятность мошенничества BOB'а. На этапе (4) ALICE случайным образом выбирает n/2документов для проверки, и BOB присылает ей соответствующий маскирующие множители на этапе (5). На этапе (7) ALICE перемножает все непроверенные документы и подписывает получившийся мегадокумент. На этапе (8) BOB удаляет все маскировочные множители. Подпись ALICE будет правильной, только если ею подписано произведение n/2идентичных документов. Чтобы смошенничать, BOB'у нужно точно угадать, какое подмножество документов будет проверять ALICE. Вероятность этого гораздо ниже, чем вероятность угадать единственный документ, который ALICE не проверяла.

BOB может смошенничать по другому. Он может создать два различных документа, один из которых ALICE согласна подписать, а другой - нет. Затем он может попытаться найти два различных маскирующих множителя, которые преобразуют указанные документы к одинаковому виду. Таким образом, если ALICE захочет проверить документ, BOB передаст ей маскирующий множитель, преобразующий документ к невинному виду. Если ALICE не захочет просмотреть документ и подпишет его, он применит тот маскирующий множитель, который преобразует замаскированный подписанный документ в документ, являющийся целью мошенничества. Хотя теоретически это и возможно, математика конкретных алгоритмов делает пренебрежимо малой вероятность для BOB'а найти такую пару. Действительно, она может быть столь низкой, как и вероятность Боба создать необходимую подпись под произвольным документом самостоятельно. Этот вопрос обсуждается ниже в разделе 23.12.

Патенты. Владельцем патентов на ряд особенностей слепых подписей является Чаум (Chaum) (см. Табл. -1).

Табл. -1. Патенты Чаума на слепые подписи

5.4 Личностная криптография с открытыми ключами

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

Эту проблему решают личностные криптосистемы, иногда называемые системами с Неинтерактивным разделением ключей (Non-Interactive Key Sharing, NIKS) [1422]. Открытый ключ Боба основывается на его имени и сетевом адресе (телефонном номере, почтовом адресе или чем-то подобном). В обычной криптографии с открытыми ключами Алисе нужен подписанный сертификат, связывающий личность Боба и его открытый ключ. В личностной криптографии открытый ключ Боба и есть его личность. Это действительно свежая идея является почти совершенной для почтовой системы - Если Алиса знает адрес Боба, она может безопасно посылать ему почту, что делает криптографию прозрачной, насколько это вообще возможно.

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

При разработке математики таких схем, обеспечение безопасности которых оказалось зверски сложным, был выполнен большой объем работы - главным образом в Японии. Многие предложенные решения содержат выбор Трентом случайного числа для каждого пользователя - по моему, это угрожает самой идее таких систем. Ряд алгоритмов, рассматриваемых в главах 19 и 20, могут быть личностными. Подробности алгоритмов и криптосистем можно найти в [191, 1422, 891, 1022, 1515, 1202, 1196, 908, 692, 674, 1131, 1023, 1516, 1536, 1544, 63, 1210, 314, 313, 1545, 1539, 1543, 933, 1517, 748, 1228]. Алгоритм, который не использует случайных чисел, описан в [1035]. Система, обсуждаемая в [1546, 1547, 1507], ненадежна против вскрытия с использованием выбранного открытого ключа, то же самое можно сказать и о системе, предложенной как NIKS-TAS [1542, 1540, 1541, 993, 375, 1538]. По правде говоря, среди предложенного нет ничего одновременно практичного и безопасного.

5.5 Рассеянная передача

Криптограф Боб безнадежно пытается разложить на множители 500-битовое число n. Он знает, что оно является произведением пяти 100-битовых чисел, и ничего больше. (Вот проблема. Если он не восстановит ключ, ему придется работать сверхурочно, и он не попадет на еженедельную игру с Алисой в мысленный покер.) Что же делать? И вот появляется Алиса:

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

Боб заинтересован, но только за 50 долларов. Алиса не хочет сбрасывать цену и предлагает продать Бобу половину битов за половину стоимости. "Это заметно сократит тебе работу", -.

"Но как я узнаю, что твое число действительно является множителем n. Если ты покажешь мне число и позволишь мне убедиться, что оно действительно является множителем, я соглашусь с твоими условиями", - говорит Боб.

Они в патовой ситуации. Алиса не может убедить Боба в том, что она знает сомножитель n, не раскрыв его, а Боб не хочет покупать 50 битов, которые вполне могут оказаться бесполезными.

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

В следующем протоколе Алиса посылает Бобу одно из двух сообщений. Боб получает сообщение, но какое - Алиса не знает.

(1) Алиса генерирует две пары открытый ключ/закрытый ключ, всего четыре ключа. Она посылает оба открытых ключа Бобу.

(2) Боб выбирает ключ симметричного алгоритма (например, DES). Он выбирает один из открытых ключей Алисы и шифрует с его помощью свой ключ DES. Он посылает шифрованный ключ Алисе, не сообщая, какой из ее открытых ключей он использовал для шифрования.

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

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

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

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

(6) Когда протокол завершится, и станут известны оба возможных результата передачи, Алиса должна передать Бобу свои закрытые ключи, чтобы он убедиться в отсутствии мошенничества. В конце концов, она могла зашифровать на этапе (4) обоими ключами одно и то же сообщение.

В этот момент, конечно же Боб сможет узнать и второе сообщение.

Протокол надежно защищен от взлома со стороны Алисы, потому что у нее нет возможности узнать, какой из двух ключей DES является настоящим. Оба из них она использует для шифрования своих сообщений, но Боб может успешно расшифровать только одно из них - до этапа (6). Протокол защищен и от взлома со стороны Боба, потому что до этапа (6) он не сможет получить закрытый ключ Алисы, чтобы определить ключ DES, которым зашифровано другое сообщение. На вид этот протокол может показаться просто усложненным способом бросать "честную" монету по модему, но он интенсивно используется во многих сложных протоколах.

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

В литературе можно найти и другие протоколы рассеянной передачи. Некоторые из них неинтерактивны, т.е. Алиса публикует свои два сообщения, а Боб может прочесть только одно из них. Он может сделать это, когда захочет, ему не нужно для этого связываться с Алисой [105].

В действительности на практике никто не использует протокол рассеянной передачи, но это понятие является важным блоком при построении других протоколов. Хотя существует много типов рассеянной передачи - у меня есть два секрета, а вы получаете один, у меня есть n секретов, а вы получаете один, у меня есть один секрет, который вы получаете с вероятностью 1/2 и так далее - все они эквивалентны [245, 391, 395].

Рассеянные подписи

Честно говоря, я не могу придумать, чего их можно использовать, но существует два типа рассеянных подписей [346]: