Криптография 2е издание Протоколы, алгоритмы и исходные тексты на языке С
 Скачать 3.25 Mb.
|
|
Алиса находится в Заире. "Кэрол" доказала свою личность в Заире, как она могла совершить преступление д о- ма? Конечно, развязаны руки и у Алисы. Она может совершить преступление либо перед отъездом, либо сразу же после возвращения, около дома Кэрол . Сначала она покажет, что она - Кэрол (имея закрытый ключ Кэрол, ей не составит труда сделать это), затем она совершит преступление и убежит. Полиция будет искать Кэрол . Кэрол будет утверждать, что сдала свою личность напрокат Алисе, но кто поверит в такую невероятную ист о- рию? Проблема в том, что Алиса доказывает не свою личность, а то, что ей известна некоторая секретная инфо р- мация. Именно связь между этой информацией и личностью и служит предметом злоупотребления . Решение защищенных от воровства детей защитило бы от такого мошенничества, как и создание полицейского госуда р- ства, в котором все граждане должны очень часто доказывать свою личность (в конце дня, на каждом углу и т.д.). Помочь решить эту проблему могут биометрические методы - отпечатки пальцев, снимки сетчатки глаза, запись голоса и т.п. Доказательство членства Алиса хочет доказать Бобу, что она является членом суперсекретной организации, но не хочет раскрывать свою личность. Эта проблема, близкая проблеме доказательства личности, но отличающаяся от нее, была из у- чена в [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) (см. 4-й). Табл. 5-1. Патенты Чаума на слепые подписи № патента США Дата Название 4759063 19.07.88 Blind Signature Systems [323] (Системы слепых подписей) 4759064 19.07.88 Blind Unanticipated Signature Systems [324] (Системы слепых неожиданных подписей) 4914698 03.03.90 One-Show Blind Signature Systems [326] (Системы слепых подписей, показываемых один раз) 4949380 14.08.90 Returned-Value Blind Signature Systems [328] (Системы слепых подписей с возвра- щаемым значением) 4991210 05.02.91 Unpredictable Blind Signature Systems [331] (Системы непредсказуемых слепых под- писей) 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]. 5.6 Рассеянные подписи Честно говоря, я не могу придумать, чего их можно использовать, но существует два типа рассеянных по д- писей [346]: 1. У Алисы есть n различных сообщений. Боб может выбрать одно из них, чтобы Алиса его подписала, и у Алисы не будет способа узнать, что же она подписала . 2. У Алисы есть единственное сообщение. Боб может выбрать один из n ключей, которым Алиса под- пишет сообщение, и Алиса не сможет узнать, какой ключ она использовала . Идея изящна, я уверен, что где-нибудь она найдет применение . 5.7 Одновременная подпись контракта Подпись контракта с помощью посредника Алиса и Боб хотят заключить контракт. Они достигли согласия на словах, но никто не хочет ставить свою подпись, пока не поставлена подпись другого . При личной встрече это не вызывает затруднений - оба подпис ы- вают вместе. На расстоянии они могут обратиться к посреднику . (1) Алиса подписывает копию контракта и посылает ее Тренту . (2) Боб подписывает копию контракта и посылает ее Тренту . (3) Трент посылает сообщение и Алисе, и Бобу, сообщающее, что другой партнер подписал контракт . (4) Алиса подписывает две копии контракта и посылает их Бобу . (5) Боб подписывает обе копии контракта, сохраняет одну для себя, и посылает другую Алисе . (6) Алиса и Боб сообщают Тренту, что у каждого из них есть подписанная обоими партнерами копия контра к- та. (7) Трент уничтожает свои две копии контракта, с единственной подписью под каждым . Этот протокол работает, потому что Трент защищает любую из сторон от мошенничества другой . Если Боб попытается отказаться от подписи под контрактом на этапе (5), Алиса может обратиться к Тренту за копией контракта, уже подписанного Бобом. Если Алиса попытается отказаться от подписи под контрактом на этапе (4), Боб может сделать то же самое. Когда Трент сообщает, что он получил оба контракта на этапе (3), Алиса и Боб узнают, что другой партнер уже подписал контракт . Если Трент не получит оба контракта на этапах (1) и (2), он уничтожает имеющуюся у него копию, и ни одна из сторон не связана более обязательствами контракта . Одновременная подпись контракта без посредника (лицом к лицу) Если Алиса и Боб встречаются лицом к лицу , они могут подписать контракт следующим образом [1244]: (1) Алиса пишет первую букву своего имени и передает контракт Бобу. (2) Боб пишет первую букву своего имени и передает контракт Алисе. (3) Алиса пишет вторую букву своего имени и передает контракт Бобу. (4) Боб пишет вторую букву своего имени и передает контракт Алисе. (5) Это продолжается до тех пор, пока Алиса и Боб не напишут свои имена полностью. Если пренебречь очевидной проблемой протокола (имя Алисы длиннее имени Боба), то он работает дост а- точно хорошо. Написав только одну букву из подписи, Алиса знает, что никакой судья не станет заставлять ее выполнять условия контракта. Но написанная буква - это акт доброй воли, и Боб отвечает аналогичным дейс т- вием. Когда каждая из сторон напишет несколько букв подписи, судья вероятно сможет убедиться, что обе стороны подписали контракт. Хотя, если вглядеться, ситуация весьма туманна . Конечно же, то, что контракт не вступает в силу после написания первых букв, так же очевидно как и то, что контракт становится действующим после того, как стороны напишут свои имена. В каком месте протокола стороны оказываются связанными контрактом? Написав половину своих имен? Две трети? Три четверти? Так как ни Алиса, ни Боб не знают точно, с какого момента начинает действовать контракт, то у каждого из них на протяжении всего протокола есть опасение, что для него или для нее контракт уже вступил в силу . Не существует этапа протокола, на котором Боб смог бы сказать : "Вы написали четыре буквы подписи, а я только три. Вы связаны контрактом, а я нет." У Боба нет причин прекращать выполнение протокола . Более того, чем дольше стороны выполняют протокол, тем больше вероятность того, что судья решит, что контракт вступил в силу. И снова, нет причины прерывать протокол. В конце концов, они оба хотели подписать контракт, они пр о- сто не хотели подписывать его раньше другого партнера. Одновременная подпись контракта без посредника (без личной встречи) В этом протоколе используется такая же неопределенность [138]. Алиса и Боб по очереди движутся детскими шажками к подписанию протокола. В этом протоколе Алиса и Боб обмениваются рядом подписанных сообщений вида : "Я согласен, что с веро- ятностью p я связан условиями контракта." Получатель сообщения может предъявить его судье и, с вероятностью p, судья признает контракт подписан- ным. (1) Алиса и Боб согласовывают дату окончания подписания контракта . (2) Алиса и Боб договариваются о различии вероятностей, которым они собираются пользоваться. Например, Алиса может решить, что ее вероятность быть связанной условиями контракта не должна превышать в е- роятность Боба больше, чем на 2 процента . Обозначим различие Алисы как a, различие Боба - как b. (3) Алиса посылает Бобу подписанное сообщение с вероятностью p = a. (4) Боб посылает Алисе подписанное сообщение с p = a + b. (5) Пусть p - это вероятность из сообщения, полученного Алисой от Боба на предыдущем этапе . Алиса посы- лает Бобу подписанное сообщение с p' = p + a или 1, смотря что меньше. (6) Пусть p - это вероятность из сообщения, полученного Бобом от Алисы на предыдущем этапе . Боб посыла- ет Алисе подписанное сообщение с p' = p + b или 1, смотря что меньше. (7) Алиса и Боб продолжают выполнять этапы (5) и (6) до тех пор, пока они оба не получат сообщения с p = 1 или пока не наступит согласованная на этапе (1) дата . По мере выполнения протокола и Алиса, и Боб соглашаются, что они оказываются связанными контрактом со все большей и большей вероятностью. Например, Алиса может определить свое a как 2 процента, а Боб свое b - как 1 процент. (Лучше бы они выбрали большие приращения, а то мы застрянем на этом месте.) В первом сообщении Алиса сообщает, что она связана контрактом с вероятностью 2 процента . Боб может ответить, что он связан контрактом с вероятностью 3 процента . Следующее сообщение Алисы может утверждать, что она связ а- на контрактом с вероятностью 5 процента и так далее, пока вероятности обоих не достигнут 100 процентов . Если и Алиса, и Боб завершили протокол к оговоренной дате , то все прекрасно. В противном случае, любая из сторон может предъявить контракт судье вместе с подписанным последним сообщением другой стороны. Прежде, чем просмотреть контракт, судья случайным образом выбирает число между 0 и 1. Если это число меньше вероятности, подписанной второй стороной, то обе стороны связаны контрактом. Если это число больше вероятности, подписанной второй стороной, то обе стороны не связаны контрактом. (Затем судья сохраняет ис- пользованное число на случай решения другого вопроса, касающегося того же контракта .) Именно это и означа- ет "быть связанным контрактом с вероятностью p". Это базовый протокол, но могут использоваться и дополнительные усложнения . Судья может принимать ре- шение в отсутствие одной из сторон. Решение судьи связывает контрактом либо обе стороны, либо ни одну из них. Не существует ситуации, когда одна из сторон связана контрактом, а другая - нет . Более того, протокол завершится, как только одна из сторон захочет иметь хоть немного большую, чем другая, вероятность быть св я- занной контрактом. Одновременная подпись контракта без посредника (с помощью криптографии) Этот криптографический протокол использует тот же принцип детских шажков [529]. Для определенности используется DES, хотя вместо него может быть любой симметричный алгоритм . (1) И Алиса, и Боб случайным образом выбирают 2n ключей DES, сгруппированных попарно. В парах нет ничего особенного, это просто способ группировки для данного протокола . (2) И Алиса, и Боб создают n пар сообщений, L i и R i , например, "Это левая половина моей i-ой подписи" и "Это правая половина моей i-ой подписи". Идентификатор, i, меняется от 1 до n. В каждое сообщение, ве- роятно, также будет входить цифровая подпись контракта и метка времени . Контракт считается подписан- ным, если другая сторона может предъявить обе половины , L i и R i , одной пары подписей. (3) И Алиса, и Боб шифруют свои пары сообщений парами ключей DES, левое сообщение - левым ключом в паре , а правое - правым. (4) Алиса и Боб посылают друг другу свои пачки из 2n шифрованных сообщений, поясняя, какие сообщения какими половинами каких пар являются . (5) Алиса и Боб посылают друг другу все пары ключей, используя протокол рассеянной передачи для каждой пары. То есть, Алиса посылает Бобу независимо для каждой из n пар ключей либо ключ, использованный для шифрования левого сообщения, либо ключ, использованный для шифрования правого сообщения . Боб делает то же самое. Они могут посылать свои половинки по очереди, или сначала один может послать все 100, а потом другой - это не имеет значения . Теперь и у Алисы, и у Боба есть по одному ключу из каждой пары, но никто не знает, какие из половинок получил партнер . (6) Алиса и Боб, используя полученные ключи, расшифровывают те половинки сообщений, которые они м о- гут расшифровать. Они убеждаются, что расшифрованные сообщения правильны . (7) Алиса и Боб посылают друг другу первые биты всех 2n ключей DES. (8) Алиса и Боб повторяют этап (7) для вторых битов всех 2n ключей DES, затем третьих битов и так далее, пока все биты всех ключей DES не будут переданы. (9) Алиса и Боб расшифровывают оставшиеся половинки сообщений, и контракт подписан . (10) Алиса и Боб обмениваются закрытыми ключами, использованными для протокола рассеянной передачи на этапе (5), и каждый из них убеждается в отсутствии мошенничества . Почему Алисе и Бобу нужно выполнить всю эту нудную последовательность действий? Предположим, что Алиса хочет смошенничать, и посмотрим, что получится . На этапах (4) и (5) Алиса могла бы разрушить прото- кол, послав Бобу ничего не значащие строки . Боб обнаружил бы это на этапе (6) при попытке расшифровать полученные половинки. Боб с полной безопасностью может остановиться до того, как Алиса сможет расшифр о- вать любую из пар сообщений Боба. Если бы Алиса была очень хитрой, она могла бы разрушить только половину протокола . Она могла бы по- слать одну половинку из каждой пары правильно, а вместо второй отправить бессмысленные строки . Вероят- ность Боба получить правильную половинку составит только 50 процентов , поэтому в половине случаев мошен- ничество Алисы удастся, но только для одной пары . Если бы использовались только две пары, этот способ м о- шенничества удастся в 25 процентах случаев . Вот почему n должно быть велико. Алисе необходимо точно уга- дать результат n протоколов рассеянной передачи, ее вероятность добиться этого составляет 1 шанс из 2 n . Если n = 10, у Алисы 1 шанс из 1024 обмануть Боба. Алиса также может отправить Бобу случайные биты на этапе (8). Возможно, Боб не узнает, что она послала ему случайные биты, пока не получит весь ключ и не попытается расшифровать половинки сообщения . Но сно- ва вероятность на стороне Боба. Он уже получил половину ключей, и Алиса не знает какую. Если n достаточно велико, Алиса наверняка пришлет ему бессмысленный бит для ключа, который у него уже есть, и он немедле н- но узнает, что она пытается его обмануть. Возможно, Алиса будет выполнять этап (8) до тех пор, пока она не получит достаточно битов ключей для вскрытия грубым взломом, и затем прекратит передачу битов . Длина ключа DES - 56 битов. Если она получила 40 из 56 битов, ей останется перебрать 2 16 , или 65536, ключей для дешифровки сообщения, а эта задача, опр е- деленно, по силам современным компьютерам . Но Боб получит ровно столько же битов ее ключей (или, в ху д- шем случае, на один бит меньше), следовательно, он сможет сделать то же самое . У Алисы нет другого выбора, кроме как продолжать следовать протоколу. Идея в том, что Алисе придется играть честно, потому что вероятность обмануть Боба слишком мала . В кон- це протокола у обеих сторон есть 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, i-ую пару сообщений - i-ой парой клю- чей, левое сообщение - левым ключом в паре , а правое - правым . в паре. (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). Проблема этого протокола в том, что подпись добавляется к бюллетеню, ЦИК знает, кто за кого голосовал . Шифрование бюллетеней открытым ключом ЦИК мешает посторонним злоупотреблять протоколом и узнавать, кто за кого голосовал, но вам придется полностью доверять ЦИК Это как будто в кабинке для голосования вам через плечо заглядывает электронный судья . Два следующих примера показывают, как трудно обеспечить хотя бы первые три требования к протоколу безопасного голосования. Голосование со слепыми подписями Нам нужно как-то отделить бюллетень от голосующего, сохранив процедуру идентификации личности . Именно это можно сделать с помощью протокола слепой подписи . (1) Каждый избиратель создает 10 наборов сообщений , каждый набор содержит правильный бюллетень для каждого возможного результата (например, если бюллетенем является один из ответов "да"-"нет", то ка ж- дый набор состоит из двух бюллетеней, одного для "да", а другого для "нет" ). Каждое сообщение содержит также случайным образом созданный идентификационный номер, достаточно большой, чтобы избежать путаницы с другими избирателями. (2) Каждый избиратель лично маскирует все сообщения (см. раздел 5.3) и посылает их в ЦИК вместе с ма с- кирующим множителями. (3) ЦИК по своей базе данных проверяет, что пользователь не присылал раньше для подписания свои зама с- кированные бюллетени. ЦИК открывает 9 из наборов, проверяя, что они правильно сформированы . Затем она индивидуально подписывает каждое сообщение набора и посылает их обратно избирателю, сохраняя имя избирателя в своей базе данных. (4) Избиратель снимает маскировку с сообщений и получает набор бюллетеней, подписанных ЦИК . (Эти бюллетени подписаны, но не зашифрованы, поэтому избиратель легко увидит, какой из бюллетеней - "да", а какой - "нет". ) (5) Каждый избиратель выбирает один из бюллетеней (о, демократия!) и шифрует его открытым ключом ЦИК. (6) Избиратель отправляет свой бюллетень. (7) ЦИК расшифровывает бюллетени, проверяет подписи, проверяет по базе данных уникальность идентиф и- кационного номера, сохраняет последовательный номер и подводит итоги. Она опубликовывает результ а- ты голосования вместе с каждым последовательным номером и соответствующим бюллетенем . Мэллори, избиратель-жулик, не может обмануть эту систему. Протокол слепой подписи обеспечивает еди н- ственность его бюллетени. Если он попытается отправить тот же бюллетень дважды, ЦИК обнаружит дублир о- вание последовательных номеров на этапе (7) и не будет учитывать второй бюллетень. Если он попытается по- лучить несколько бюллетеней на этапе (2), ЦИК обнаружит это на этапе (3). Мэллори не может создать свои собственные бюллетени, потому что он не знает закрытого ключа комиссии . По той же причине он не может перехватить и изменить чужие бюллетени. Протокол "разрезать и выбрать" на этапе (3) должен обеспечить уникальность бюллетеней. Без этого этапа Мэллори мог бы создать точно такой же, за исключением идентификационного номера, набор бюллетеней и заверить их все в ЦИК. Мошенническая ЦИК не сможет узнать, как голосовал конкретный избиратель. Так как протокол слепой подписи маскирует последовательные номера бюллетеней до момента подведения итогов , ЦИК не сможет уста- новить связь между подписанным ею замаскированным бюллетенем и подытоживаемым бюллетенем . Опубли- кование перечня последовательных номеров и связанных с ними бюллетеней позволяет пользователям убедит ь- ся, что их бюллетени были правильно учтены. Но проблемы все еще остаются. Если этап (6) не анонимен, и ЦИК может записать, кто какой бюллетень прислал, то она сможет узнать, кто за кого голосовал . Однако, это невозможно, если комиссия получает бюлл е- тени в запечатанной урне для голосования и считает их позже . Хотя ЦИК и не сможет установить связь между избирателями и их бюллетенями, она сможет создать большое количество подписанных и правильных бюлл е- теней и смошенничать, прислав их сама себе . И если Алиса обнаружит, что ЦИК подменила ее бюллетень, она не сможет доказать этого. Аналогичный протокол, пытающийся устранить эти проблемы, описан в [1195, 1370]. Голосование с двумя Центральными комиссиями Одним из решений является разделить ЦИК пополам . Ни у одной из них не будет достаточно власти, чтобы смошенничать по своему усмотрению. В следующем протоколе используется Центральное управление регистрации (ЦУР), занимающееся прове р- кой пользователей, и отдельная ЦИК для подсчета бюллетеней [1373]. (1) Каждый избиратель отправляет письмо в ЦУР, запрашивая регистрационный номер. (2) ЦУР возвращает избирателю случайный регистрационный номер. ЦУР ведет список регистрационных номеров. Кроме того, ЦУР хранит список получателей регистрационных номеров на случай, если кто-то попытается проголосовать дважды. (3) ЦУР отправляет список регистрационных номеров в ЦИК. (4) Каждый избиратель выбирает случайный идентификационный номер. Он создает сообщение с этим ном е- ром, регистрационным номером, полученным в ЦУР, и своим бюллетенем. Он посылает это сообщение в ЦИК. (5) ЦИК проверяет регистрационные номера по списку, полученному от ЦУР на этапе (3). Если регистрац и- онный номер есть в списке, ЦИК вычеркивает его (чтобы избежать повторного голосования). ЦИК доба в- ляет идентификационный номер к списку тех, кто проголосовал за определенного кандидата, и прибавляет единичку к соответствующему итоговому числу. (6) После того, как все бюллетени будут получены, ЦИК публикует результаты вместе со списками, содерж а- щими идентификационные номера и соответствующие бюллетени. Как и в предыдущем протоколе каждый избиратель может увидеть список идентификационных номеров и найти в нем свой собственный. Так он может убедиться, что его бюллетень учтен . Конечно, все сообщения, ко- торыми обмениваются участники протокола должны быть зашифрованы и подписаны, чтобы помешать кому- нибудь выдать себя за другого или перехватить сообщения . ЦИК не может изменить бюллетени, потому что каждый избиратель будет искать свой регистрационный н о- мер. Если избиратель не находит свой регистрационный номер или находит его в итоговом списке с другим р е- зультатом голосования, он немедленно узнает, что произошел обман. ЦИК не может добавить бюллетень в у р- ну, которая находится под наблюдением ЦУР . ЦУР знает, сколько избирателей зарегистрировалось, их регис т- рационные номера и обнаружит любые изменения. Мэллори, не обладающий избирательными правами, может попытаться смошенничать, угадав правильный регистрационный номер. Угроза этого может быть минимизирована, если множество возможных регистрацио н- ных номеров намного больше, чем множество реальных регистрационных номеров : 100-битовое число для мил- лиона избирателей. Конечно же, регистрационные номера должны генерироваться случайным образом . Несмотря на это, ЦУР должна быть заслуживающим доверия органом власти - ведь она может зарегистр и- ровать неправомочных избирателей. Она также может зарегистрировать правомочных избирателей несколько раз. Этот риск может быть сведен к минимуму, если ЦУР опубликует список зарегистрировавшихся избират е- лей (но без их регистрационных номеров). Если число избирателей в этом списке меньше, чем число подсчи- танных бюллетеней, то что-то не так. Однако, если зарегистрировалось больше избирателей, чем было прислано бюллетеней, то это, возможно, означает, что ряд зарегистрировавшихся избирателей не проголосовал . Многие, зарегистрировавшись, не утруждаются бросить в урну свой бюллетень . Этот протокол беззащитен перед сговором ЦИК и ЦУР. Если они действуют вместе, они могут объединить свои базы данных и узнать, кто за кого голосует . Голосование с одной Центральной комиссией Чтобы избежать опасности сговора между ЦУР и ЦИК можно использовать более сложный протокол [1373]. Этот протокол идентичен предыдущему с двумя изменениями : — ЦУР и ЦИК являются единой организацией, и — для анонимного распределения регистрационных номеров на этапе (2) используется ANDOS (см. раздел 4.13). Так как протокол анонимного распределения ключей не позволяет ЦИК узнать, у какого избирателя какой регистрационный номер, У ЦИК нет способа связать регистрационные номера и полученные бюллетени . Но ЦИК должна быть надежным органом, чтобы не выдавать регистрационных номеров неправомочным избират е- лям. Эту проблему также можно решить с помощью слепых подписей . Улучшенное голосование с одной Центральной комиссией В этом протоколе также используется ANDOS [1175]. Он удовлетворяет всем шести требованиям хорошего протокола голосования. Он не удовлетворяет седьмому требованию, но обладает двумя свойствами, дополня ю- щими перечисленные в начале раздела шесть свойств : 7. Избиратель может изменить свое мнение (т.е., аннулировать свой бюллетень и проголосовать заново ) в течение заданного периода времени. 8. Если избиратель обнаруживает, что его бюллетень посчитан неправильно, он может установить и и с- править проблему, не рискуя безопасностью своего бюллетеня . Вот этот протокол: (1) ЦИК публикует список всех правомочных избирателей . (2) В течение определенного срока каждый избиратель сообщает в ЦИК, собирается ли он голосовать . (3) ЦИК публикует список избирателей, участвующих в выборах . (4) Каждый избиратель получает идентификационный номер , I, с помощью протокола ANDOS. (5) Каждый избиратель генерирует пару открытый ключ/закрытый ключ : k, d. If Если v - это бюллетень, то избиратель создает и посылает в ЦИК следующее сообщение : I,E k (I, v) Это сообщение должно быть послано анонимно . (6) ЦИК подтверждает получение бюллетеня, публикуя : E k (I, v) (7) Каждый избиратель посылает ЦИК: I, d (8) ЦИК расшифровывает бюллетени. В конце выборов она публикует их результаты и, для каждого варианта выбора, список соответствующий значений E k (I, v). (9) Если избиратель обнаруживает, что его бюллетень подсчитан неправильно, он протестует, посылая ЦИК : I, E k (I, v), d (10) Если избиратель хочет изменить свой бюллетень с v на v', он посылает ЦИК: I, E k (I, v'), d Другой протокол голосования использует вместо ANDOS слепые подписи, но по сути мало чем отличается [585]. Этапы (1) - (3) являются предварительными. Их цель состоит в том, чтобы узнать и опубликовать всех действительных избирателей. Хотя некоторые из них, вероятно, не примут участи в голосовании, это уменьшает возможность ЦИК добавить поддельные бюллетени . На этапе (4) два избирателя могут получить один и тот же идентификационный номер . Эта возможность мо- жет быть минимизирована, если число возможных идентификационных номеров будет гораздо больше, чем число реальных избирателей. Если два избирателя присылают бюллетени с одинаковым идентификатором, ЦИК генерирует новый идентификационный номер, I', выбирает одного из избирателей и публикует : I',E k (I, v) Владелец этого бюллетеня узнает о произошедшей путанице и посылает свой бюллетень снова, повторяя этап (5) с новым идентификационным номером. Этап (6) дает каждому избирателю возможность проверить, что ЦИК правильно получила его бюллетень . Если его бюллетень неправильно подсчитан, он может доказать это на этапе ( 9). Предполагая, что бюллетень избирателя на этапе (6) правилен, сообщение, которое он посылает на этапе (9) доказывает, что его бюллетень был неправильно подсчитан. Одной из проблем этого протокола является то, что жульническая ЦИК сможет воспользоваться людей, к о- торые сообщили о намерении голосовать на этапе (2), но не голосовали в действительности . Другой проблемой является сложность протокола ANDOS. Авторы рекомендуют разбивать избирателей на меньшие группы, н а- пример избирательные округа. Еще одной, более серьезной проблемой является то, что ЦИК может не подсчитать какой-нибудь бюллетень . Эта проблема неразрешима: Алиса утверждает, что ЦИК намеренно пренебрег ее бюллетенем, а ЦИК утве р- ждает, что Алиса никогда не голосовала. Голосование без Центральной избирательной комиссии В следующем протоколе ЦИК не используется, избиратели следят друг за другом . Этот протокол, созданный Майклом Мерриттом [452, 1076, 453], настолько громоздок, что возможность его реализации больше чем для пяти человек сомнительна, но все же познакомиться с ним будет полезно . Алиса, Боб, Кэрол и Дэйв голосуют (да/нет или 0/1) по какому-то вопросу . Пусть у каждого избирателя есть открытый и закрытый ключи. Пусть также все открытые ключи известны всем . (1) Каждый голосующий решает, как голосовать, и делает следующее: (a) Добавляет случайную строку к своему бюллетеню. (b) Шифрует результат этапа (а) открытым ключом Дэйва. (c) Шифрует результат этапа (b) открытым ключом Кэрол. (d) Шифрует результат этапа (c) открытым ключом Боба. (e) Шифрует результат этапа (d) открытым ключом Алисы. (f) Добавляет новую случайную строку к результату этапа ( e) и шифрует получившееся открытым клю- чом Дэйва. Он записывает значение случайной строки. (g) Добавляет новую случайную строку к результату этапа ( f) и шифрует получившееся открытым клю- чом Кэрол. Он записывает значение случайной строки. (h) Добавляет новую случайную строку к результату этапа ( g) и шифрует получившееся открытым клю- чом Боба. Он записывает значение случайной строки. (i) Добавляет новую случайную строку к результату этапа ( g) и шифрует получившееся открытым клю- чом Алисы. Он записывает значение случайной строки. Если E - это функция шифрования, R i - случайная строка, а V - бюллетень , то его сообщение будет выгля- деть следующим образом: E A (R 5 ,E B (R 4 ,E C (R 3 ,E D (R 2 ,E A (E B (E C (E D (V,R 1 )))))))) Каждый голосующий сохраняет промежуточные результаты на каждом этапе вычислений. Эти результаты будут использоваться на дальнейших этапах протокола для подтверждения, что бюллетень данного изб и- рателя будет учтен. (2) Каждый голосующий отправляет сообщение Алисе. (3) Алиса расшифровывает все бюллетени, используя свой закрытый ключ, и удаляет все случайные строки на этом уровне. (4) Алиса перетасовывает все бюллетени и посылает результат Бобу. Теперь каждый бюллетень будет выглядеть сл едующим образом: E B (R 4 ,E C (R 3 ,E D (R 2 ,E A (E B (E C (E D (V,R 1 ))))))) (5) Боб расшифровывает все бюллетени, используя свой закрытый ключ, проверяет, есть ли его бюллетень среди присланных бюллетеней, удаляет все случайные строки на этом уровне, тасует бюллетени и посыл а- ет результат Кэрол. Теперь каждый бюллетень будет выглядеть сл едующим образом: E C (R 3 ,E D (R 2 ,E A (E B (E C (E D (V,R 1 )))))) (6) Кэрол расшифровывает все бюллетени, используя свой закрытый ключ, проверяет, есть ли ее бюллетень среди присланных бюллетеней, удаляет все случайные строки на этом уровне, тасует бюллетени и посыл а- ет результат Дэйву. Теперь каждый бюллетень будет выглядеть сл едующим образом: E D (R 2 ,E A (E B (E C (E D (V,R 1 ))))) (7) Дэйв расшифровывает все бюллетени, используя свой закрытый ключ, проверяет, есть ли его бюллетень среди присланных бюллетеней, удаляет все случайные строки на этом уровне, тасует бюллетени и посыл а- ет результат Алисе. Теперь каждый бюллетень будет выглядеть сл едующим образом: E A (E B (E C (E D (V,R 1 )))) (8) Алиса расшифровывает все бюллетени, используя свой закрытый ключ, проверяет, есть ли ее бюллетень среди присланных бюллетеней, подписывает все бюллетени и посылает результат Бобу, Кэрол и Дэйву. Теперь каждый бюллетень будет выглядеть сл едующим образом: S A (E B (E C (E D (V,R 1 )))) (9) Боб проверяет и удаляет подписи Алисы. Он расшифровывает все бюллетени, используя свой закрытый ключ, проверяет, есть ли его бюллетень среди присланных бюллетеней, подписывает все бюллетени и п о- сылает результат Алисе, Кэрол и Дэйву. Теперь каждый бюллетень будет выглядеть сл едующим образом: S B (E C (E D (V,R 1 ))) (10) Кэрол проверяет и удаляет подписи Боба. Она расшифровывает все бюллетени, используя свой закрытый ключ, проверяет, есть ли ее бюллетень среди присланных бюллетеней, подписывает все бюллетени и п о- сылает результат Алисе, Бобу и Дэйву. Теперь каждый бюллетень будет выглядеть сл едующим образом: S C (E D (V,R 1 )) (11) Дэйв проверяет и удаляет подписи Кэрол. Он расшифровывает все бюллетени, используя свой закрытый ключ, проверяет, есть ли его бюллетень среди присланных бюллетеней, подписывает все бюллетени и п о- сылает результат Алисе, Бобу и Кэрол. Теперь каждый бюллетень будет выглядеть сл едующим образом: S D (V,R 1 ) (12) Все проверяют и удаляют подпись Дэйва. Они убеждаются, что их бюллетени находятся среди получе н- ных (находя свою случайную строку). (13) Все удаляют случайные строки из каждого бюллетеня и суммирует бюллетени. Этот протокол не только работает, он сам является своим арбитром . Алиса, Боб, Кэрол и Дэйв немедленно узнают, если кто-нибудь из них попытается мошенничать . Не нужно никаких ЦИК и ЦУР. Чтобы увидеть, как это работает, попытаемся смошенничать . Если кто-нибудь пытается добавить бюллетень, Алиса обнаружит эту попытку на этапе (3), когда она полу- чит бюллетеней больше чем количество людей, участвующих в голосовании . Если Алиса попытается добавить бюллетень, Боб обнаружит это на этапе (4). Более ловкой является подмена одного бюллетеня другим . Так как бюллетени шифруются различными о т- крытыми ключами, каждый может создать столько правильных бюллетеней, сколько нужно . Протокол дешиф- рирования состоит из двух частей: первая включает этапы (3)-(7), а вторая - этапы (8)-(11). Подмена голоса на различных этапах обнаруживается по разному. Если кто-нибудь заменит один бюллетень другим во второй части, его действия будут обнаружены неме д- ленно. На каждом этапе бюллетени подписываются и посылаются всем избирателям . Если один избиратель (или несколько) обнаруживает, что его бюллетеня больше нет среди набора бюллетеней , он немедленно пре- кращает выполнение протокола. Так как бюллетени подписываются на каждом этапе , и так как каждый может вернуться во второй части протокола на несколько шагов назад , то обнаружить мошенника, подменившего бю л- летени, легко. Замена одного бюллетеня другим в первой части протокола более тонка . Алиса не может сделать замену на этапе (3), потому что Боб, Кэрол и Дэйв обнаружат это на этапах (5), (6) или (7). Боб может попробовать на эта- пе (5). Если он заменит бюллетени Кэрол и Дэйва (помните, он не знает, какой бюллетень чей), Кэрол или Дэйв заметят это на этапах (6) или (7). Они не будут знать, кто подменил их бюллетени (хотя это должен быть кто-то, уже обработавший бюллетени), но они будут знать, что их голоса подменены . Если Бобу повезло, и ему удалось подменить бюллетень Алисы, она не заметит этого до второй части протокола. Тогда она обнаружит исчезновение своего голоса на этапе (8), но не сможет узнать, кто подменил бюллетень . В первой части бюлле- тени перетасовываются на каждом этапе и не подписываются, поэтому никто не сможет отработать протокол обратно и определить, кто подменил бюллетени. Другой формой мошенничества является попытка узнать, кто за кого проголосовал . Из-за перетасовки бюл- летеней в первой части никто не сможет отработать протокол обратно и связать бюллетени и голосующих . Уда- ление случайных строк в первой части также является решающим для сохранения анонимности. Если строки не удаляются, перемешивание голосов может быть инвертировано при помощи повторного шифрования получа е- мых голосов открытым ключом того, кто их тасовал . Когда протокол остановится, конфиденциальность бюлл е- теней сохранится. Более того, из-за начальной случайной строки, R 1 , даже одинаковые бюллетени шифруются по разному на каждом этапе протокола. Никто не может узнать значение бюллетеня до этапа (11). Каковы проблемы этого протокола? Во первых, для выполнения протокола нужны грандиозные вычисления . В приведенном примере в голосовании принимают участие только четверо, но и он уже сложен. Такой прото- кол не сможет работать при реальных выборах с десятками тысяч голосующих . Во вторых, Дэйв узнает резуль- таты выборов раньше остальных. Хотя он и не может повлиять на результат, он получает определенное пр е- имущество. С другой стороны такое также возможно и при централизованной схеме голосования . Третья проблема заключается в том, что Алиса может скопировать бюллетень другого участника, даже не зная его содержания заранее. Чтобы понять, почему это может стать проблемой, рассмотрим выборы для трех голосующих - Алисы, Боба и Евы. Еве не важны результаты выборов, но она хочет знать, как голосовала Алиса . Поэтому она копирует бюллетень Алисы, и результат выборов будет соответствовать бюллетеню Алисы . Другие схемы голосования Было предложено много сложных безопасных протоколов выборов . Их можно разделить на два типа. Суще- ствуют протоколы с перемешиванием, как "Голосование без Центральной избирательной комиссии ", в которых все бюллетени перемешиваются, чтобы никто не мог связать бюллетень и избир ателя. Также существуют протоколы с разделением , в которых личные бюллетени делятся между различными счетными комиссиями так, что ни одна из них не сможет обмануть избирателей [360, 359, 118, 115]. Эти про- токолы Эти протоколы защищают анонимность избирателей только, если различные "части" правительства (или кто бы не проводил голосование) не сговариваются против избирателя. (Идея разбить центральный орган на несколько частей, которые пользуются доверием, только когда они действуют параллельно, пришла из [316].) Один из протоколов с разделением предложен в [1371]. Основная идея состоит в том, что каждый избир а- тель делит свой бюллетень на несколько частей . Например, если бы бюллетень содержал "да" или "нет", 1 обо- значала бы "да", а 0 - "нет", избиратель мог бы создать несколько чисел, которые в сумме давали бы 0 или 1 . Эти доли посылаются счетным комиссиям, каждой по одной, и также шифруются и сохраняются . Каждый центр суммирует полученные доли (существуют протоколы, обеспечивающие правильность итога ), и окончательный итог является суммой всех промежуточных итогов . Существуют также протоколы, гарантирующие, что доли каждого избирателя будут сложены для получения 0 или 1. Другой протокол, предложенный Дэвидом Чаумом [322], позволяет проследить избирателя, который пытае т- ся мошенничать. Однако, выборы придется проводить повторно, исключив мешающего пользователя. Этот по д- ход не применим на практике для выборов с большим числом избирателей . Еще один, более сложный протокол, решающий некоторые из этих проблем можно найти в [770, 771]. Су- ществует даже протокол, использующий шифры со многими ключами [219]. Другой протокол, который, как утверждается, подходит для крупномасштабных выборов, приведен в [585]. А [347] позволяет избирателям не голосовать. Протоколы голосования работают, они даже облегчают продажу и покупку голосов . Когда покупатель может быть уверен, что продавец проголосует, как обещал, стимул купить голоса становится еще сильнее . Ряд прото- колов были спроектированы без подтверждения, не позволяя избирателю доказать кому-либо еще, что он пр о- голосовал определенным образом [117, 1170, 1372]. 6.2 Безопасные вычисления с несколькими участниками Безопасные вычисления с несколькими участниками представляют собой протокол, с помощью котор о- го группа людей может определенным образом вычислить функцию многих переменных . Каждый в группе обеспечивает одну или несколько переменных . Результат вычислений становится известным каждому в группе, но никому не известны значения , предоставленные другими членами группы, если это не является очевидным из результата вычислений. Ниже приведено несколько примеров: Протокол №l |