Криптографические протоколы

Криптографические протоколы

___________________________________________________________________________

Московский Государственный Институт Электроники и Математики

___________________________________________________________________________

Курсовая работа

на тему «Криптографические протоколы»

Студенты группы М8-08

Расин Вадим

Клочков Павел

г.Москва

2000 г.

Криптографические протоколы

Протокол - это последовательность шагов, которые предпринимают две

или большее количество сторон для совместного решения некоторой задачи.

Следует обратить внимание на то, что все шаги предпринимаются в порядке

строгой очередности и ни один из них не может быть сделан прежде, чем

закончится предыдущий.

Кроме того, любой протокол подразумевает участие двух сторон. В одиночку

можно смешать и выпить коктейль, но к протоколу эти действия не будут иметь

никакого отношения. Поэтому придется угостить кого-нибудь сделанным

коктейлем, чтобы его приготовление и дегустация стали настоящим протоколом.

И наконец, протокол обязательно предназначен для достижения какой-то цели,

иначе это не протокол, а пустое времяпрепровождение.

У протоколов есть также и другие отличительные черты:

• каждый участник протокола должен быть заранее оповещен о шагах,

которые ему предстоит предпринять;

• все участники протокола должны следовать его правилам добровольно,

без принуждения;

• необходимо, чтобы протокол допускал только однозначное толкование,

а его шаги были совершенно четко определены и не допускали возможности их

неправильного понимания;

• протокол должен описывать реакцию участников на любые ситуации,

которые могут возникнуть в ходе его реализации. Иными словами, недопустимым

является положение, при котором для возникшей ситуации протоколом не

определено соответствующее действие.

Криптографическим протоколом называется протокол, в основе которого

лежит криптографический алгоритм. Однако целью криптографического протокола

зачастую является не только сохранение информации в тайне от посторонних.

Участники криптографического протокола могут быть близкими друзьями, у

которых нет друг от друга секретов, а могут являться и непримиримыми

врагами, каждый из которых отказывается сообщить другому, какое сегодня

число. Тем не менее им может понадобиться поставить свои подписи под

совместным договором или удостоверить свою личность. В этом случае

криптография нужна, чтобы предотвратить или обнаружить подслушивание

посторонними лицами, а также не допустить мошенничества. Поэтому часто

криптографический протокол требуется там, где его участники не должны

сделать или узнать больше того, что определено этим протоколом.

Зачем нужны криптографические протоколы

В повседневной жизни нам приходится сталкиваться с протоколами

буквально на каждом шагу - играя в любые игры, или делая покупки в

магазинах, или голосуя на выборах. Многими протоколами нас научили

пользоваться родители, школьные учителя и друзья. Остальные мы сумели

узнать самостоятельно.

В настоящее время люди все чаще контактируют друг с другом при помощи

компьютеров. Компьютеры же, в отличие от большинства людей, в школу не

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

состоянии. Поэтому компьютеры приходится снабжать формализованными

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

Например, если в магазине не окажется кассового аппарата, вы все равно

окажетесь в состоянии купить в нем необходимую для себя вещь. Компьютер же

такое кардинальное изменение протокола может поставить в полный тупик.

Большинство протоколов, которые люди используют при общении друг с

другом с глазу на глаз, хорошо себя зарекомендовали только потому, что их

участники имеют возможность вступить в непосредственный контакт.

Взаимодействие с другими людьми через компьютерную сеть, наоборот,

подразумевает анонимность. Будете ли вы играть с незнакомцем в преферанс,

не видя, как он тасует колоду и раздает карты? Доверите ли вы свои деньги

совершенно постороннему человеку, чтобы он купил вам что-нибудь в магазине?

Пошлете ли вы свой бюллетень голосования по почте, зная, что с ним сможет

ознакомиться кто-то из почтовых работников и потом рассказать всем о ваших

нетрадиционных политических пристрастиях? Думаю, что нет.

Глупо считать, что компьютерные пользователи ведут себя более честно,

чем абсолютно случайные люди. То же самое касается и сетевых

администраторов, и проектировщиков компьютерных сетей. Большинство из них и

в самом деле достаточно честны, однако остальные могут причинить вам

слишком большие неприятности. Поэтому так нужны криптографические

протоколы, использование которых позволяет защититься от непорядочных

людей.

Распределение ролей

Чтобы описание протоколов было более наглядным, их участники будут

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

таблицу). Антон и Борис принимают участие во всех двухсторонних протоколах.

Как правило, начинает выполнение шагов, предусмотренных протоколом, Антон,

а ответные действия предпринимает Борис. Если протокол является трех- или

четырехсторонним, исполнение соответствующих ролей берут на себя Владимир и

Георгий.

Об остальных персонажах подробнее будет рассказано несколько позже.

Протоколы с арбитражем

Арбитр является незаинтересованным участником протокола, которому

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

действия для завершения очередного шага протокола. Это значит, что у

арбитра нет личной заинтересованности в достижении тех или иных целей,

преследуемых участниками протокола, и он не может выступить на стороне

одного из них. Участники протокола также принимают на веру все, что скажет

арбитр, и беспрекословно следуют всем его рекомендациям.

В протоколах, которым мы следуем в повседневной жизни, роль арбитра

чаще всего играет адвокат. Однако попытки перенести протоколы с адвокатом в

качестве арбитра из повседневной жизни в компьютерные сети наталкиваются на

существенные препятствия:

• Легко довериться адвокату, про которого известно, что у него

незапятнанная репутация и с которым можно установить личный контакт. Однако

если два участника протокола не доверяют друг другу, арбитр, не облаченный

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

ли будет пользоваться у них большим доверием.

• Расценки на услуги, оказываемые адвокатом, известны. Кто и каким

образом будет оплачивать аналогичные услуги арбитра в компьютерной сети?

• Введение арбитра в любой протокол увеличивает время, затрачиваемое

на реализацию этого протокола.

• Поскольку арбитр контролирует каждый шаг протокола, его участие в

очень сложных протоколах может стать узким местом при реализации таких

протоколов. Соответствующее увеличение числа арбитров позволяет избавиться

от данного узкого места, однако одновременно увеличиваются и расходы на

реализацию протокола.

• В силу того, что все участники протокола должны пользоваться

услугами одного и того же арбитра, действия злоумышленника, который решит

нанести им ущерб, будут направлены, в первую очередь, против этого арбитра.

Следовательно, арбитр представляет собой слабое звено в цепи участников

любого протокола с арбитражем.

Несмотря на отмеченные препятствия, протоколы с арбитражем находят

широкое применение на практике.

Протокол с судейством

Чтобы снизить накладные расходы на арбитраж, протокол, в котором

участвует арбитр, часто делится на две части. Первая полностью совпадает с

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

возникновения разногласий между участниками. Для разрешения конфликтов

между ними используется особый тип арбитра - судья.

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

протокола, которому остальные его участники доверяют при принятии решений.

Однако в отличие от арбитра, судья участвует отнюдь не в каждом шаге

протокола. Услугами судьи пользуются, только если требуется разрешить

сомнения относительно правильности действий участников протокола. Если

таких сомнений ни у кого не возникает, судейство не понадобится.

В компьютерных протоколах с судейством предусматривается наличие

данных, проверив которые доверенное третье лицо может решить, не

смошенничал ли кто-либо из участников этого протокола. Хороший протокол с

судейством также позволяет выяснить, кто именно ведет себя нечестно. Это

служит прекрасным превентивным средством против мошенничества со стороны

участников такого протокола.

Самоутверждающийся протокол

Самоутверждающийся протокол не требует присутствия арбитра для

завершения каждого шага протокола. Он также не предусматривает наличие

судьи для разрешения конфликтных ситуаций. Самоутверждающийся протокол

устроен так, что если один из его участников мошенничает, другие смогут

моментально распознать нечестность, проявленную этим участником, и

прекратить выполнение последующих шагов протокола.

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

протокол на все случаи жизни. Однако на практике в каждом конкретном случае

приходится конструировать свой специальный самоутверждающийся протокол.

Разновидности атак на протоколы

Атаки на протоколы бывают направлены против криптографических

алгоритмов, которые в них задействованы, против криптографических методов,

применяемых для их реализации, а также против самих протоколов. Для начала

предположим, что используемые криптографические алгоритмы и методы являются

достаточно стойкими, и рассмотрим атаки собственно на протоколы.

Лицо, не являющееся участником протокола, может попытаться подслушать

информацию, которой обмениваются его участники. Это пассивная атака на

протокол, которая названа так потому, что атакующий (будем именовать его

Петром) может только накапливать данные и наблюдать за ходом событий, но не

в состоянии влиять на него. Пассивная атака подобна криптоаналитической

атаке со знанием только шифртекста. Поскольку участники протокола не

обладают надежными средствами, позволяющими им определить, что они стали

объектом пассивной атаки, для защиты от нее используются протоколы, дающие

возможность предотвращать возможные неблагоприятные последствия пассивной

атаки, а не распознавать ее.

Атакующий может попытаться внести изменения в протокол ради

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

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

информацию, которая хранится в компьютере и используется участниками

протокола для принятия решений. Это активная атака на протокол, поскольку

атакующий (назовем его Зиновием) может вмешиваться в процесс выполнения

шагов протокола его участниками.

Итак, Петр пытается собрать максимум информации об участниках

протокола и об их действиях. У Зиновия же совсем другие интересы -

ухудшение производительности компьютерной сети, получение

несанкционированного доступа к ее ресурсам, внесение искажений в базы

данных. При этом и Петр, и Зиновий не обязательно являются совершенно

посторонними лицами. Среди них могут быть легальные пользователи, системные

и сетевые администраторы, разработчики программного обеспечения и даже

участники протокола, которые ведут себя непорядочно или даже вовсе не

соблюдают этот протокол.

В последнем случае атакующий называется мошенником. Пассивный мошенник

следует всем правилам, которые определены протоколом, но при этом еще и

пытается узнать о других участниках больше, чем предусмотрено этим

протоколом. Активный мошенник вносит произвольные изменения в протокол,

чтобы нечестным путем добиться для себя наибольшей выгоды.

Защита протокола от действий нескольких активных мошенников

представляет собой весьма нетривиальную проблему. Тем не менее при

некоторых условиях эту проблему удается решить, предоставив участникам

протокола возможность вовремя распознать признаки активного мошенничества.

А защиту от пассивного мошенничества должен предоставлять любой протокол

вне зависимости от условий, в которые поставлены его участники.

Доказательство с нулевым разглашением конфиденциальной информации

Антон: "Я знаю пароль для входа в компьютерную сеть Центробанка

и рецепт приготовления „Байкала"".

Борис: "Нет, не знаешь!"

Антон: "Нет, знаю!"

Борис: "Чем докажешь?"

Антон: "Хорошо, я тебе все расскажу".

Антон долго шепчет что-то на ухо Борису.

Борис: "Действительно интересно! Надо сообщить об этом

газетчикам!"

Антон: "Ё-моё..."

К сожалению, в обычных условиях Антон может доказать Борису, что знает

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

Но тогда Борис автоматически узнает эту тайну и сможет поведать о ней

первому встречному. Есть ли у Антона возможность помешать Борису это

сделать?

Конечно, есть. В первую очередь, Антону не следует доверять свою тайну

Борису. Но как тогда Антон сможет убедить Бориса в том, что действительно

входит в число посвященных?

Антону надо воспользоваться протоколом доказательства с нулевым

разглашением конфиденциальной информации. С помощью этого протокола Антон

окажется в состоянии доказать Борису, что он обладает некой секретной

информацией, однако разглашать данную информацию перед Борисом будет совсем

не обязательно.

Доказательство носит интерактивный характер. Борис задает Антону серию

вопросов. Если Антон знает секрет, то ответит правильно на все заданные ему

вопросы. Если не знает, вероятность правильного ответа на каждый из

вопросов будет невелика. После примерно 10 вопросов Борис будет точно

знать, обманывает ли его Антон. При этом шансы Бориса извлечь для себя

какую-либо полезную информацию о сути самого секрета практически равны

нулю.

Протокол доказательства с нулевым разглашением конфиденциальной

информации

Использование доказательства с нулевым разглашением конфиденциальной

информации можно пояснить на конкретном примере.

Предположим, что имеется пещера, точка входа в пещеру обозначена

буквой A, в точке B пещера разветвляется на две половины - C и D (см.

рисунок). У пещеры есть секрет: только тот, кто знает волшебные слова,

может открыть дверь, расположенную между C и D.

Антону волшебные слова известны, Борису - нет. Антон хочет доказать Борису,

что знает волшебные слова, но так, чтобы Борис по-прежнему оставался в

неведении относительно этих слов. Тогда Антон может воспользоваться

следующим протоколом:

1. Борис стоит в точке A.

2. По своему выбору Антон подходит к двери либо со стороны точки

C, либо со стороны точки D.

3. Борис перемещается в точку B.

4. Борис приказывает Антону появиться или (а) - через левый

проход к двери, или (б) - через правый проход к двери.

5. Антон подчиняется приказу Бориса, в случае необходимости

используя волшебные слова, чтобы пройти через дверь.

6. Шаги 1-5 повторяются n раз, где n - параметр протокола.

Допустим, что у Бориса есть видеокамера, с помощью которой он

фиксирует все исчезновения Антона в недрах пещеры и все его последующие

появления с той или иной стороны. Если Борис покажет записи всех n

экспериментов, произведенных им совместно с Антоном, смогут ли эти записи

послужить доказательством знания Антоном волшебных слов для другого

человека (например, для Владимира)?

Вряд ли. Владимир никогда не сможет полностью удостовериться в том,

что Антон каждый раз предварительно не сообщал Борису, с какой стороны он

направится к двери, чтобы потом Борис приказывал ему выходить именно с той

стороны, с какой Антон зашел. Или что из сделанной видеозаписи не вырезаны

все неудачные эксперименты, в ходе которых Антон появлялся совсем не с той

стороны, с какой ему приказывал Борис.

Это означает, что Борис не в состоянии убедить Владимира, лично не

присутствовавшего при проведении экспериментов в пещере, в том, что Антон

действительно подтвердил там свое знание секрета. А значит, использованный

Антоном протокол доказательства характеризуется именно нулевым разглашением

конфиденциальной информации. Если Антон не знает волшебные слова,

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

узнать и Борис. Если Антону известны волшебные слова, то Борису не поможет

даже подробная видеозапись проведенных экспериментов. Во-первых, поскольку

при ее просмотре Борис увидит только то, что уже видел живьем. А во-вторых,

потому что практически невозможно отличить сфальсифицированную Борисом

видеозапись от подлинной.

Протокол доказательства с нулевым разглашением срабатывает в силу

того, что, не зная волшебных слов, Антон может выходить только с той

стороны, с которой зашел. Следовательно, только в 50 % всех случаев Антон

сумеет обмануть Бориса, сумев выйти именно с той стороны, с которой тот

попросит. Если количество экспериментов равно n, то Антон успешно пройдет

все испытания только в одном случае из 2n. На практике можно ограничиться

n=16. Если Антон правильно исполнит приказ Бориса во всех 16 случаях,

значит, он и вправду знает волшебные слова.

Пример с пещерой является очень наглядным, но имеет существенный

изъян. Борису будет значительно проще проследить, как в точке B Антон

поворачивает в одну сторону, а потом появляется с противоположной стороны.

Протокол доказательства с нулевым разглашением здесь попросту не нужен.

Поэтому предположим, что Антону известны не какие-то там волшебные

слова типа "Сезам, откройся". Нет, Антон владеет более интересной

информацией - он первым сумел справиться с труднорешаемой задачей. Чтобы

доказать этот факт Борису, Антону совсем не обязательно публично

демонстрировать свое решение. Ему достаточно применить следующий протокол

доказательства с нулевым разглашением конфиденциальной информации:

1. Антон использует имеющуюся у него информацию и

сгенерированное случайное число, чтобы свести труднорешаемую

задачу к другой труднорешаемой задаче, изоморфной исходной

задаче. Затем Антон решает эту новую задачу.

2. Антон задействует протокол предсказания бита для найденного

на шаге 1 решения, чтобы впоследствии, если у Бориса возникнет

необходимость ознакомиться с этим решением, Борис мог бы

достоверно убедиться, что предъявленное Антоном решение

действительно было получено им на шаге 1.

3. Антон показывает новую труднорешаемую задачу Борису.

4. Борис просит Антона

или (а) - доказать, что две труднорешаемые задачи (старая и

новая) изоморфны,

или (б) - предоставить решение, которое Антон должен был найти

на шаге 1, и доказать, что это действительно решение задачи, к

которой Антон свел исходную задачу на том же шаге.

5. Антон выполняет просьбу Бориса.

6. Антон и Борис повторяют шаги 1-6 n раз, где n - параметр

протокола.

Труднорешаемые задачи, способ сведения одной задачи к другой, а также

случайные числа должны по возможности выбираться так, чтобы у Бориса не

появилось никакой информации относительно решения исходной задачи даже

после многократного выполнения шагов протокола.

Не все труднорешаемые задачи могут быть использованы при

доказательстве с нулевым разглашением конфиденциальной информации, однако

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

отыскание в связном графе цикла Гамильтона (замкнутого пути, проходящего

через все вершины графа только один раз) и определение изоморфизма графов

(два графа изоморфны, если они отличаются только названиями своих вершин).

Параллельные доказательства с нулевым разглашением конфиденциальной

информации

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

конфиденциальной информации требует, чтобы Антон и Борис последовательно

повторили его шаги n раз. Можно попробовать выполнять действия,

предусмотренные этим протоколом, одновременно:

1. Антон использует имеющуюся у него информацию и n

сгенерированных случайных чисел, чтобы свести труднорешаемую

задачу к n другим труднорешаемым задачам, изоморфным исходной

задаче. Затем Антон решает эти n новых задач.

2. Антон задействует протокол предсказания бита для найденных на

шаге 1 n решений, чтобы впоследствии, если у Бориса возникнет

необходимость ознакомиться с этими решениями, Борис мог бы

достоверно убедиться, что предъявленные Антоном решения

действительно были получены им на шаге 1.

3. Антон показывает n новых труднорешаемых задач Борису.

4. Для каждой из n новых труднорешаемых задач Борис просит

Антона

или (а) - доказать, что она изоморфна исходной труднорешаемой

задаче,

или (б) - предоставить решение этой задачи, которое Антон должен

был найти на шаге 1, и доказать, что оно действительно является

ее решением.

5. Антон выполняет все просьбы Бориса.

На первый взгляд параллельный протокол обладает тем же свойством

нулевого разглашения конфиденциальной информации, что и обычный. Однако

строгого доказательства этого факта еще не найдено. А пока с полной

определенностью можно сказать лишь одно: некоторые интерактивные протоколы

доказательства с нулевым разглашением в некоторых ситуациях можно выполнять

параллельно, и от этого они не утрачивают свойство нулевого разглашения

конфиденциальной информации.

Неинтерактивные протоколы доказательства с нулевым разглашением

конфиденциальной информации

Постороннее лицо, не участвующее в выполнении шагов интерактивного

протокола доказательства с нулевым разглашением конфиденциальной

информации, невозможно убедить в том, в чем в ходе реализации протокола

убеждается Борис, а именно - что Антон действительно владеет

конфиденциальной информацией. Чтобы преодолеть этот недостаток, потребуется

применить неинтерактивный протокол, в котором вместо Бориса используется

однонаправленная функция:

1. Антон использует имеющуюся у него информацию и n сгенерированных

случайных чисел, чтобы свести труднорешаемую задачу к n другим

труднорешаемым задачам, изоморфным исходной задаче. Затем Антон решает

эти n новых задач.

2. Антон задействует протокол предсказания бита для найденных на шаге

1 n решений.

3. Антон подает n обязательств, полученных им на шаге 2, на вход

однонаправленной функции.

4. Для каждой i-й труднорешаемой задачи, к которой Антон свел исходную

задачу на шаге 1, он берет i-й бит значения, вычисленного с помощью

однонаправленной функции, и

(а) если этот бит равен 1, то Антон доказывает, что исходная и i-я

задачи изоморфны, или

(б) если этот бит равен 0, то Антон помещает в общедоступную базу

данных решение i-й задачи, вычисленное на шаге 1.

5. Антон передает в общедоступную базу данных все обязательства,

которые были получены им на шаге 2.

6. Борис, Владимир или любое другое заинтересованное лицо могут

проверить правильность выполнения шагов 1-5 Антоном.

Удивительно, но факт: Антон предоставляет в общее пользование

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

секретом, и в то же время не содержат никакой информации о сути самого

секрета.

Роль Бориса в этом протоколе исполняет однонаправленная функция. Если

Антон не знает решения труднорешаемой задачи, он все равно может выполнить

действия, предусмотренные или пунктом (а), или пунктом (б) шага 4

протокола, но отнюдь не обоими пунктами сразу. Поэтому, чтобы смошенничать,

Антону придется научиться предсказывать значения однонаправленной функции.

Однако, если функция действительно является однонаправленной, Антон не

сможет ни догадаться, какими будут ее значения, ни повлиять на нее с тем,

чтобы на ее выходе получилась нужная Антону битовая последовательность.

В отличие от интерактивного протокола, здесь требуется большее

количество итераций. Поскольку генерация случайных чисел возложена на

Антона, подбором этих чисел он может попытаться добиться, чтобы на выходе

однонаправленной функции получилась битовая последовательность нужного ему

вида. Ведь даже если Антон не знает решения исходной труднорешаемой задачи,

он всегда в состоянии выполнить требования или пункта (а), или пункта (б)

шага 4 протокола.

Тогда Антон может попытаться догадаться, на какой из этих пунктов

падет выбор, и выполнить шаги 1-3 протокола. А если его догадка неверна, он

повторит все сначала. Именно поэтому в неинтерактивных протоколах необходим

больший запас прочности, чем в интерактивных. Рекомендуется выбирать n=64

или даже n=128.

Доказано, что в общем случае любое математическое доказательство может

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

разглашением конфиденциальной информации. А это означает, что теперь

математику вовсе не обязательно публиковать результаты своих научных

исследований. Он может доказать своим коллегам, что нашел решение какой-то

математической проблемы, не раскрывая перед ними сути найденного решения.

Удостоверение личности с нулевым разглашением конфиденциальной

информации

В повседневной жизни людям регулярно приходится удостоверять свою

личность. Обычно они делают это путем предъявления паспортов, водительских

прав, студенческих билетов и других подобных документов. Такой документ

обычно имеет некоторую индивидуальную отличительную особенность, которая

позволяет однозначно связать его с определенным лицом. Чаще всего это

фотография, иногда - подпись, реже - отпечатки пальцев или рентгеновский

снимок зубов. Можно ли делать то же самое с помощью криптографии?

Конечно. В этом случае для удостоверения личности Антона используется

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

разглашением конфиденциальной информации, Антон может продемонстрировать

любому, что знает свой тайный ключ, и тем самым однозначно идентифицировать

себя. Идея цифровой идентификации весьма заманчива и таит в себе массу

разнообразных возможностей, однако у нее есть ряд существенных недостатков.

Во-первых, злоумышленник Зиновий под фальшивым предлогом может

попросить Антона предъявить свое цифровое удостоверение личности.

Одновременно с помощью современных средств связи Зиновий инициализирует

процесс идентификации Антона совсем в другом месте и будет переадресовывать

все запросы из этого места Антону, а данные им ответы - пересылать обратно.

Например, Зиновий может связаться с ювелирным магазином и, выдав себя за

Антона, оплатить из его кармана весьма дорогую покупку.

Во-вторых, Зиновий может запросто обзавестись несколькими тайными

ключами, а следовательно, и заиметь соответствующее число цифровых

удостоверений личности. Одно из них он использует единственный раз для

финансовой аферы и больше им пользоваться не будет. Свидетелем преступления

станет лицо, которому Зиновий предъявит свое "одноразовое" удостоверение

личности, однако доказать, что это был именно Зиновий, не удастся. Ведь

предусмотрительный Зиновий никогда не удостоверял таким образом свою

личность прежде. Не станет он делать этого и впредь. А свидетель сможет

только показать, какое удостоверение личности было предъявлено

преступником. Однозначно связать это удостоверение с личностью Зиновия

будет нельзя.

В-третьих, Антон может попросить Зиновия одолжить на время его

цифровое удостоверение личности. Мол, Антону надо съездить в Соединенные

Штаты, а поскольку он - бывший сотрудник советской разведки, работавший

против США, американское правительство наотрез отказывает ему во въездной

визе. Зиновий с радостью соглашается: после отъезда Антона он может пойти

практически на любое преступление, поскольку обзавелся "железным" алиби. С

другой стороны, ничто не мешает совершить преступление Антону. Кто поверит

лепету Зиновия о том, что он одолжил свое цифровое удостоверение личности

какому-то другому человеку?

Избавиться от перечисленных недостатков помогают дополнительные меры

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

Зиновий, проверяя цифровое удостоверение личности Антона, мог одновременно

общаться с внешним миром по телефону или радио. Если Зиновия поместить в

экранированную комнату без всяких средств связи, никакого мошенничества не

было бы.

Чтобы исключить вторую форму мошенничества, необходимо ввести

ограничение на количество ключей, которые человеку разрешается

использовать, чтобы удостоверить свою личность (как правило, такой ключ

должен существовать в единственном числе).

И наконец, чтобы не допустить третий вид мошенничества, требуется либо

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

у каждого фонарного столба, как это делается в тоталитарных государствах),

либо дополнить средства цифровой идентификации другими идентификационными

методами (например, проверкой отпечатков пальцев).

Неосознанная передача информации

Предположим, что Борис безуспешно пытается разложить на простые

множители 700-битовое число. При этом ему известно, что данное число

является произведением семи 100-битовых множителей. На помощь Борису

приходит Антон, который случайно знает один из множителей. Антон предлагает

Борису продать этот множитель за 1000 рублей - по 10 рублей за бит. Однако

у Бориса имеются в наличии лишь 500 рублей. Тогда Антон выражает желание

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

купив эти 50 бит, он все равно не сможет убедиться, что они действительно

являются частью искомого множителя, пока не узнает все его биты целиком.

Чтобы выйти из тупика, Антон и Борис должны воспользоваться протоколом

неосознанной передачи информации. В соответствии с ним Антон передает

Борису несколько шифрованных сообщений. Борис выбирает одно из них и

отсылает все сообщения обратно. Антон расшифровывает выбранное Борисом

сообщение и снова отсылает Борису. При этом Антон остается в неведении

относительно того, какое именно сообщение выбрал для себя Борис.

Протокол неосознанной передачи информации не решает всех проблем,

которые стоят перед Антоном и Борисом, желающими заключить сделку о купле-

продаже одного из множителей 700-битового числа. Чтобы сделка стала

честной, Антон должен будет доказать Борису, что проданные 50 бит

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

раскладывается это число. Поэтому Антону скорее всего придется

дополнительно воспользоваться еще и протоколом доказательства с нулевым

разглашением информации.

Следующий протокол позволяет Антону послать два сообщения, одно из

которых будет принято Борисом, но какое именно, Антон так и не узнает.

1. Антон генерирует две пары ключей, состоящих из открытого и тайного

ключа, и отсылает оба открытых ключа Борису.

2. Борис генерирует ключ для симметричного алгоритма (например, для

DES-алгоритма), шифрует этот ключ при помощи одного из открытых

ключей, присланных Антоном, и отсылает обратно Антону.

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

тайных ключей, сгенерированных им на шаге 1, и получает две битовых

последовательности. Одна из них является подлинным ключом для DES-

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

4. Антон шифрует два сообщения по DES-алгоритму, используя в качестве

ключей обе битовые последовательности, которые были получены им на

шаге 3, и отсылает результаты шифрования Борису.

5. Борис расшифровывает оба присланных Антоном сообщения на ключе,

сгенерированном на шаге 2, и обретает два открытых текста сообщения,

один из которых представляет собой настоящую тарабарщину, а второй -

содержательное послание.

Теперь у Бориса имеется одно из двух сообщений Антона, однако

последний не может со всей определенностью сказать, какое именно. К

сожалению, если в протоколе не предусмотреть дополнительный

проверочный шаг, у Антона будет возможность смошенничать (например,

зашифровать на шаге 4 два идентичных сообщения). Поэтому необходим еще

один, заключительный шаг протокола:

6. После того как отпала надобность хранить в секрете второе сообщение

(к примеру, у Бориса нашлись еще 500 рублей, чтобы выкупить у Антона

оставшуюся половину множителя), Антон предоставляет Борису свои тайные

ключи, чтобы тот мог убедиться в честности Антона.

Протокол защищен от атаки со стороны Антона, поскольку на шаге 3 Антон

не в состоянии отличить произвольную битовую последовательность от

подлинного ключа DES-алгоритма, сгенерированного Борисом. Протокол также

обеспечивает защиту от атаки со стороны Бориса, так как у того нет тайных

ключей Антона, чтобы определить битовую последовательность, использованную

Антоном в качестве ключа DES-алгоритма для шифрования второго сообщения.

Конечно, протокол неосознанной передачи информации отнюдь не

гарантирует, что Антон не пошлет Борису какие-нибудь бессмысленные послания

(типа "Борис - лох" или "Мяу-мяу") вместо битов одного из семи простых

множителей, на которые раскладывается исходное 700-битовое число. Или что

Борис вообще захочет с ними ознакомиться и примет участие в выполнении

шагов этого протокола.

На практике протокол неосознанной передачи информации используется

довольно редко. Обычно он служит в качестве одного из строительных блоков

для построения других протоколов.

Анонимные совместные вычисления

Иногда бывает так, что группе людей требуется совместно вычислить

некоторую функцию от многих переменных. Каждый участник вычислительного

процесса является источником значений одной или нескольких переменных этой

функции. Результат вычислений становится известен всем членам группы,

однако ни один из них не в состоянии выяснить что-либо о значениях,

поданных на вход функции другим членом группы.

Вычисление средней зарплаты

Допустим, что начальник отдела приказал своим подчиненным подсчитать

среднюю зарплату в отделе. Начальник осведомлен о зарплате любого

сотрудника, но слишком занят более важными делами, чтобы отвлекаться на

подобные пустяки. Каждый сотрудник прекрасно знает собственную зарплату, но

категорически не желает сообщать о ней сослуживцам. Чтобы сотрудники отдела

могли просуммировать свои оклады, сохранив их в тайне от других, им следует

воспользоваться следующим протоколом:

1. Антон генерирует случайное число, прибавляет его к своей зарплате,

шифрует полученную сумму при помощи открытого ключа Бориса и затем

передает то, что у него получилось, Борису.

2. На своем тайном ключе Борис расшифровывает результат, вычисленный

Антоном, прибавляет к нему свою зарплату, шифрует полученную сумму при

помощи открытого ключа Владимира и затем передает то, что у него

получилось, Владимиру.

3. На своем тайном ключе Владимир расшифровывает результат,

вычисленный Борисом, прибавляет к нему свою зарплату, шифрует

полученную сумму при помощи открытого ключа Георгия и затем передает

то, что у него получилось, Георгию.

4. На своем тайном ключе Георгий расшифровывает результат, вычисленный

Владимиром, прибавляет к нему свою зарплату, шифрует полученную сумму

при помощи открытого ключа Антона и затем передает то, что у него

получилось, Антону.

5. На своем тайном ключе Антон расшифровывает результат, вычисленный

Георгием, вычитает из него случайное число, сгенерированное на шаге 1,

делит на количество сотрудников отдела и получает искомую среднюю

зарплату в отделе.

Точность вычисления средней зарплаты зависит от честности каждого

сотрудника. Если хотя бы один из участников протокола соврет относительно

своего жалованья, итоговое значение будет неверным. Особенно большими

потенциальными возможностями для злоупотреблений обладает Антон. На шаге 5

он может вычесть любое число, какое только придет ему в голову, и никто не

заметит подделки. Поэтому необходимо обязать Антона воспользоваться какой-

либо из схем предсказания бита. Однако если от Антона потребуется раскрыть

перед всеми случайное число, сгенерированное им на шаге 1, зарплату Антона

узнает Борис. Это значит, что начальнику отдела все же придется отвлечься и

выполнить вычисления, предусмотренные шагом 2 протокола, самому. Ведь он и

так в курсе размера оплаты труда Антона.

Как найти себе подобного

Антон любит играть с резиновыми куклами, изготовители которых

потрудились на славу, тщательно скопировав в натуральную величину

определенные особенности анатомического строения женщины. А Борису нравится

во всех красочных подробностях наблюдать за жизнью соседей из

многоквартирного дома напротив при помощи современных оптических

приспособлений. Оба тщательно скрывают свои пристрастия от родственников,

друзей и коллег по работе, но очень хотели бы найти людей, которые

разделяют их интересы.

Фирма "Совместные анонимные вычисления" готова оказать необходимую

помощь Антону, Борису и им подобным в подборе таких же чудаков, как они

сами. Сотрудники фирмы составили всеобъемлющий список всех человеческих

чудачеств, каждое из которых снабжено уникальным идентификатором из семи

цифр. Обратившись в фирму, Антон и Борис принимают участие в выполнении

шагов некоторого протокола, после чего узнают, испытывают ли они склонность

к одним и тем же чудачествам. При положительном ответе они смогут связаться

друг с другом и слиться во взаимном экстазе. Если ответ будет

отрицательным, об их необычных пристрастиях не узнает никто, включая

Страницы: 1, 2, 3