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

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

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

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

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

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

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

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

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

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

Предположим, что у каждого агента по 10 псевдонимов, выбранных ими самими и больше никому неизвес т-ных. Предположим также, что агентам все равно, под каким именем они получат дипломатическую неприко с-новенность. Также предположим, компьютер управления называется Agencys 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 подписывает оставшийся документ и пос1лает его ВОВу.

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

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

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

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

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

Табл. 5-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) обоими ключами одно и то же сообщение .

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