Идея в том, что Алисе придется играть честно, потому что вероятность обмануть Боба слишком мала . В конце протокола у обеих сторон есть n подписанных пар сообщений, любое из которых достаточно для правильной подписи.

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

Протоколы этого типа имеют два слабых места [138]. Во первых, проблема возникает, если вычислительная мощь одной стороны гораздо больше, чем у другой . Если, например, Алиса может выполнить вскрытие грубым взломом быстрее Боба, то она рано прекратит передачу битов на этапе (8) и раскроет ключи Боба самостоятельно. Бобу, которому для таких же действий просто не хватит времени, не повезет .

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

Эти проблемы существуют также для протоколов разделов 5.8 и 5.9.

5.8 Электронная почта с подтверждением

Такой же протокол одновременной рассеянной передачи, использованный для подписания контракта, с н е-большими изменениями используется для электронной почты с подтверждением [529]. Пусть Алиса хочет послать сообщение Бобу, но не хочет, чтобы он прочитал его, не расписавшись в получении . В реальной жизни это обеспечивается неприветливыми почтовыми служащими , но то же самое может быть сделано при помощи криптографии. Эту проблему первым рассмотрел Уитфилд Диффи в [490].

На первый взгляд, эту проблему мог бы решить протокол одновременного подписания контракта. Алиса просто копирует свое сообщение ключом DES. Ее половина протокола выглядит примерно так: "Это левая половина ключа DES: 32f5", а половина протокола Боба - так: "Это левая половина моей квитанции." Все остальное не меняется.

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

Решение этой проблемы потребует некоторой коррекции протокола :

(1) Алиса шифрует свое сообщение случайным ключом DES и посылает его Бобу.

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

(3) Алиса шифрует сообщение-заглушку каждым из своих 2n ключей.

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

(5) Боб создает n пар случайных ключей DES.

(6) Боб создает пару сообщений, образующих правильную квитанцию. Хорошим вариантами могут служить "Это левая половина моей квитанции" и "Это левая половина моей квитанции" с добавлением какой-нибудь строки случайных битов. Он создает n пар квитанций, нумеруя каждую. Как и в предыдущем пр о-токоле квитанция считается правильной, если Алиса может предъявить обе половины квитанции (с одним и тем же номером) и все ее ключи шифрования.

(7) Боб шифрует каждую свою пару сообщений парами ключей DES, г-ую пару сообщений - г-ой парой ключей, левое сообщение - левым ключом в паре , а правое - правым . в паре.

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

(9) Алиса и Боб посылают друг другу все пары ключей, используя протокол рассеянной передачи . То есть,

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

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

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

(12) Алиса и Боб повторяют этап (11) для вторых битов всех 2n ключей DES, затем третьих битов и так далее, пока все биты всех ключей DES не будут переданы.

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

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

Этапы (5)-(8) для Боба и (9)-(12) для обеих сторон не меняются по сравнению с протоколом подписания ко н-тракта. Отличие - в сообщениях-заглушках Алисы . Они предоставляют Бобу возможность проверить правил ь-ность ее рассеянной передачи на этапе (10), что заставляет ее оставаться честной на этапах (11)-(13). И, как и для протокола одновременного подписания контракта , для выполнения протокола требуются обе половины о д-ного из сообщений Алисы.

5.9 Одновременный обмен секретами

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

(1) Алиса: "Я скажу, если ты скажешь мне первым."

(2) Боб: "Я скажу, если ты скажешь мне первой."

(3) Алиса: "Нет, ты первый."

(4) Боб: "Ну, хорошо. Боб шепчет Алисе.

(5) Алиса: "Ха, а я тебе не скажу."

(6) Боб: "Это не честно."

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

Алиса выполняет этапы (1)-(4), используя в качестве сообщения A. Боб выполняет эти же действия, используя в качестве своего сообщения B. Алиса и Боб выполняют рассеянную передачу на этапе (9) , расшифровывают на этапе (10) те половинки, которые могут, и выполняют необходимые итерации на этапах (11) и (12). Чтобы защититься от Евы, они должны шифровать свои сообщения . Наконец, и Алиса, и Боб расшифровывают оставшиеся половины пар сообщения и выполняют XOR для любой пары ключей, чтобы получить ключи, которыми зашифрованы оригинальные сообщения.

Этот протокол позволяет Алисе и Бобу одновременно обмениваться секретами, но не гарантирует качества переданных секретов. Алиса может пообещать Бобу план лабиринта Минотавра и прислать ему схему Босто н-ского метро. Боб получит только тот секрет, который Алиса пришлет ему. Другие протоколы описаны в [1286, 195, 991, 1524, 705, 753, 259, 358, 415].

Глава 6

Эзотерические протоколы 6.1 Безопасные выборы

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

1. Голосовать могут только те, кто имеет на это право .

2. Каждый может голосовать не более одного раза.

3. Никто не может узнать, за кого проголосовал конкретный избиратель .

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

5. Никто не может тайно изменить чей-то голос.

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

7. Каждый знает, кто голосовал, а кто нет.

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

Упрощенный протокол голосования №1

(1) Каждый голосующий шифрует свой бюллетень открытым ключом Центральной избирательной комиссии

(ЦИК).

(2) Каждый голосующий посылает свой бюллетень в ЦИК.

(3) ЦИК расшифровывает бюллетени, подводит итоги и опубликовывает результаты голосования .

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

Упрощенный протокол голосования №«2

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

(2) Каждый голосующий шифрует свой бюллетень открытым ключом ЦИК .

(3) Каждый голосующий посылает свой бюллетень в ЦИК.

(4) ЦИК расшифровывает бюллетени, проверяет подписи, подводит итоги и опубликовывает результаты г о-лосования.

Этот протокол обладает свойствами 1 и 2: Только правомочные избиратели могут голосовать, и никто не может голосовать более одного раза - ЦИК может записывать бюллетени, полученные на этапе (3). Каждый бюллетень подписан закрытым ключом голосующего, поэтому ЦИК знает, кто голосовал, а кто нет, и, как гол о-совал каждый избиратель. Если получен бюллетень, который не подписан правомочным пользователем, или бюллетень, подписанный избирателем, который уже проголосовал , то такой бюллетень игнорируется комиссией. Кроме того, из-за цифровой подписи никто не может изменить бюллетень другого избирателя, даже если сумеет перехватить его на этапе (2).

Проблема этого протокола в том, что подпись добавляется к бюллетеню, ЦИК знает, кто за кого голосовал . Шифрование бюллетеней открытым ключом ЦИК мешает посторонним злоупотреблять протоколом и узнавать, кто за кого голосовал, но вам придется полностью доверять ЦИК Это как будто в кабинке для голосования вам через плечо заглядывает электронный судья.

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