Протокол надежно защищен от взлома со стороны Алисы, потому что у нее нет возможности узнать, какой из двух ключей 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) Алиса пос1лает Бобу подписанное сообщение с вероятностью p = a.

(4) Боб пос1лает Алисе подписанное сообщение с p = a + b.

(5) Пусть p - это вероятность из сообщения, полученного Алисой от Боба на предыдущем этапе . Алиса посылает Бобу подписанное сообщение с p = p + a или 1, смотря что меньше.

(6) Пусть p - это вероятность из сообщения, полученного Бобом от Алисы на предыдущем этапе . Боб пос1ла-ет Алисе подписанное сообщение с 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 пар сообщений, Li и например, "Это левая половина моей г-ой подписи" и "Это правая половина моей i-ой подписи". Идентификатор, i, меняется от 1 до n. В каждое сообщение, вероятно, также будет входить цифровая подпись контракта и метка времени . Контракт считается подписанным, если другая сторона может предъявить обе половины, Li и Ri, одной пары подписей.

(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 битов, ей останется перебрать 216, или 65536, ключей для дешифровки сообщения, а эта задача, опр е-деленно, по силам современным компьютерам . Но Боб получит ровно столько же битов ее ключей (или, в ху д-шем случае, на один бит меньше) , следовательно, он сможет сделать то же самое . У Алисы нет другого выбора, кроме как продолжать следовать протоколу.