Криптография 2е издание Протоколы, алгоритмы и исходные тексты на языке С

• Название: Криптография 2е издание Протоколы, алгоритмы и исходные тексты на языке С
• Дата: 29.04.2022
• Размер: 3.25 Mb.
• Имя файла: Shnayer_Prikladnaya-kriptografiya.352928.pdf
• Тип: Протокол; #504484
• страница: 9 из 78

Алиса может передать Бобу полномочия подписывать сообщения за нее, не передавая ему своего закрытого ключа?
Решением этого являются подписи по доверенности [1001]. Алиса передает Бобу полномочия так, чтобы имели место следующие свойства:
— Различимость. Кто угодно может отличить подписи по доверенности от обычных подписей.
— Неподдельность. Только сам подписывающий и назначенный им подписывающий по доверенности м о- жет создать правильную подпись по доверенности.
— Отличие подписи по доверенности. подписывающий по доверенности не может создать правильную подпись по доверенности, которую можно выдать за оригинальную подпись.
— Подтверждаемость. По подписи по доверенности контролер должен убедиться в согласии первон а- чального подписывающего с подписанным сообщением.
— Идентифицируемость. Первоначальный подписывающий может определить личность подписывающ е- го по доверенности по подписи по доверенности.
— Неотрицаемость. Подписывающий по доверенности не может снять им подпись по доверенности, п о- лученную пользователем
В некоторых случаях требуется строгая форма идентифицируемости - кто угодно должен иметь возможность определить личность подписывающего по доверенности по подписи по доверенности . Схемы подписи по дове- ренности, основанные на различных схемах цифровой подписи приведены в [1001].

4.6 Групповые подписи
Эта проблема была введена Дэвидом Чаумом ( David Chaum) в [330]:
У компании есть несколько компьютеров, подсоединенных к локальной сети . В каждом отделе компании есть свой при н- тер (также присоединенный к сети), и только один человек в отделе имеет право печатать на принтере своего отдела. Перед печатью, следовательно, принтер должен проверять, что данный сотрудник работает в этом отделе В то же время, компания хочет обеспечить тайну, имя пользователя не должно раскрываться. Если, однако, кто-то в конце дня обнаружит, что принтер используется слишком часто, у директора должна быть возможность найти того, кто использует принтер не по назначению и послать ему чек.
Решение этой проблемы называется групповой подписью. Групповые подписи обладают следующими сво й- ствами:
— Только члены группы могут подписывать сообщения.
— Получатель подписи может убедиться, что это - правильная подпись группы.
— Получатель подписи не может определить, кто именно из членов группы подписал документ.
— при споре подпись будет раскрыта для определения личности подписавшего.
Групповые подписи с надежным посредником
Следующий протокол использует заслуживающего посредника:
(1) Трент создает большую кучу пар открытый ключ/закрытый ключ и выдает каждому члену группы инд и- видуальный список уникальных закрытых ключей. Одинаковых ключей в списках нет. (Если в группе n членов, и каждый из них получает m пар ключей, то общее число пар ключей составит n*m.)
(2) Трент публикует главный список всех открытых ключей для группы в случайном порядке, сохраняя в се к- рете, какой ключ кому принадлежит.
(3) Когда член группы хочет подписать документ, он случайным образом выбирает ключ из своего списка.
(4) Когда кто-то хочет убедиться, что подпись принадлежит члену данной группы, он перебирает главный список в поисках подходящего открытого ключа и проверяет подпись.
(5) В случае споров обращаются к Тренту, который знает, какие ключи использует каждый член группы.
Проблема протокола состоит в том, что для него необходим надежный посредник. Трент знает закрытые ключи каждого и может подделывать подписи. Кроме того, должно быть достаточно велико, чтобы помешать попыткам анализа с целью поиска владельца каждого ключа.
Чаум [330] перечислил ряд других протоколов, в некоторых из них Трент не может подделать подписи, а в других от и не нужен вовсе. Еще один протокол [348] не только прячет личность подписывающего, но и позв о- ляет добавлять новых членов в группу. И еще один протокол можно найти в [1230].
4.7 Подписи с обнаружением подделки
Пусть Ева является могучим противником. У нее есть обширные компьютерные сети и залы, набитые ко м- пьютерами Крэй, на много порядков более мощных, чем доступные Алисе . Все эти компьютеры днем и ночью пыхтят, пытаясь взломать закрытый ключ Алисы. Наконец - успех. Теперь Ева может выдавать себя за Алису,
при желании подделывая ее подпись под документами.
Подписи с обнаружением подделки, введенные Биржитом Пфицманом (Birgit Pfitzmann) и Майклом
Уэйднером (Michael Waidner) [1240] предотвращают подобное мошенничество. Если после грубого взлома Ева подделывает подписи Алисы, Алиса сможет доказать подлог . Если Алиса подпишет документ, а потом объявит свою подпись подложной, правда может быть доказана судом .
Основная идея, стоящая за подписями с обнаружением подделки, состоит в том, что для каждому возможн о- му открытому ключу соответствует множество возможных закрытых ключей . Каждый из этих закрытых ключей дает множество различных цифровых подписей . Однако, у Алисы есть только один закрытый ключ, и она м о- жет рассчитать только одну подпись. Другие закрытые ключи ей неизвестны.
Ева хочет взломать закрытый ключ Алисы. (Ева также сможет быть Алисой, вычислив для себя второй з а- крытый ключ.) Она собирает подписанные сообщения и, используя множество своих суперкомпьютеров, пыт а- ется раскрыть ключ Алисы. Даже если ей удастся раскрыть подходящий закрытый ключ, таких ключей н а- столько много, что, скорее всего, она получит иной, чем у Алисы, ключ . Вероятность раскрытия ключа, принад- лежащего именно Алисе, настолько мала, что ею можно пренебречь.
Теперь, когда Ева подделает подпись под документом, используя найденный закрытый ключ, подделанная подпись будет отличаться от той подписи, которую поставила бы сама Алиса. При обращении в суд Алиса

предъявит две различных подписи под одним и тем же сообщением и открытый ключ (соответствующий ее з а- крытому ключу и закрытому ключу, найденному Евой), чтобы доказать подлог . С другой стороны, если Алиса не может предъявить две различные подписи, то подлога не было и Алиса должна отвечать за свою подпись .
Эта схема подписей противостоит взлому Евой подписи Алисы с помощью необычайно мощных вычисл и- тельных средств. Она ничего не сможет сделать с более вероятной попыткой Мэллори вломиться в дом Алисы и стащить ее закрытый ключ или с попыткой Алисы подписать документ, а затем "случайно" потерять свой з а- крытый ключ. Чтобы защититься от упомянутой попытки Мэллори, Алисе стоит купить себе хорошую сторож е- вую собаку, но подобные рекомендации выходят за рамки криптографии .
Дополнительную теорию и применения подписей с обнаружением подделки можно найти в [1239, 1241, 730,
731].
4.8 Вычисления с зашифрованными данными
Алиса хочет знать решение для некоторой функции f(x) для некоторого конкретного значения x. К несчастью,
ее компьютер сломан. Боб хочет вычислить для нее значение f(x), но Алиса не хочет, чтобы Боб знал ее x. Как

Алисе позволить Бобу провести вычисление f(x)и не сообщить ему x?
Это обычная проблема вычислений с зашифрованными данными, также известных как тайная инфор- мация прорицателя. (Прорицателем является Боб - он отвечает на вопрос .) Для некоторых функций существу- ют способы решить эту задачу, они обсуждаются в разделе 23.6.
4.9 Вручение битов
Алиса Великолепная, выдающаяся волшебница , сейчас продемонстрирует мощь своего искусства. Она уг а- дает карту, которую выберет Боб до того, как он ее выберет ! Следите за тем, как Алиса записывает свое пре д- сказание на кусочке бумаги. Восхищайтесь тем, как Алиса кладет этот кусочек бумаги в конверт и запечатывает его. Дрожите от того, как Алиса отдает запечатанный конверт случайному зрителю . "Выбери карту, Боб, любую карту." Он глядит на нее и показывает карту Алисе и зрителям . Это семерка бубен. Теперь Алиса забирает ко н- верт у зрителя и открывает его. Предсказание, записанное до того, как Боб выбрал карту, сообщает "семерка бубен"! Аплодисменты.
Для успеха этого трюка Алисе нужно подменить конверт в конце фокуса . Однако, криптографические прото- колы могут обеспечить защиту от любой ловкости рук. А какая в этом польза? Вот более приземленная ист ория.
Биржевой брокер Алиса хочет убедить инвестора Боба, что ее метод определять перспективные акции за- служивает внимания.
Боб:
"Подберите-ка для меня пяток акций. Если на них удастся заработать, я передам свой бизнес вам."
Алиса:
"Если я подберу пять акций для вас, вы сможете вложить в них деньги, не заплатив мне. Почему бы мне не показать вам пять акций, которые я подобрал в прошлом мес яце?"
Боб:
"Откуда я знаю, что вы не подменили результаты вашего выбора, узнав настоящие. Если вы сообщите мне о своем выборе сейчас, я буду уверен, что вы не подмените результат. Я не буду вкладывать деньги в эти акции, пока я не оплачу ваши услуги. Поверьте мне."
Алиса:
"Я лучше покажу вам свою подборку акций за прошлый месяц. Я не подменяла их. Поверьте мне."
Алиса хочет передать свое предсказание (т.е., бит или последовательность битов), но не хочет раскрывать свое предсказание до некоторого времени . Боб, с другой стороны, хочет удостовериться, что Алиса не сможет изменить свое мнение после того, как она сделала предсказание.
Вручение битов с помощью симметричной криптографии
Этот протокол вручения битов использует симметричную криптографию :
(1) Боб генерирует строку случайных битов, R, и посылает ее Алисе.
(2) Алиса создает сообщение, состоящее из своего бита, который она хочет вручить, b (в действительности,
это может быть и несколько битов), и случайную строку Боба. Она шифрует сообщение некоторым сл у- чайным ключом, K, и посылает его обратно Бобу.
E
K
(R,b)
Эта часть протокола представляет собой процедуру вручения . Боб не может расшифровать сообщение, п о- этому он не знает, что за бит прислала Алиса .
Когда для Алисы придет время раскрыть свой бит, протокол продолжается :
(3)
Алиса передает Бобу ключ.

(4)
Боб расшифровывает сообщения, узнавая бит. Он проверяет свою случайную строку, убеждаясь в пр а- вильности бита.
Без случайной строки Боба Алиса может тайно расшифровывать сообщение, посланное Бобу, используя множество ключей, подбирая тот, который позволит при дешифрировании отправленного сообщения изменить врученный бит. Так как у бита только два возможных значения, ее поиски наверняка увенчаются успехом после нескольких попыток. Случайная строка Боба не дает ей использовать этот способ вскрытия, ей придется искать новый ключ, который не только инвертирует врученный бит, но и сохранит нетронутой случайную строку Боба .
Если используется достаточно хороший алгоритм шифрования, вероятность удачного поиска чрезвычайно мала.
Алиса не может изменить свой бит после его вручения .
Вручение бита с помощью однонаправленных функций
Этот протокол использует однонаправленные функции:
(1) Алиса создает две случайных строки битов, R
1
и R
2
R
1
, R
2
(2) Алиса создает сообщение, состоящее из ее случайных строк и бита, который она хочет вручить (в действ и- тельности, это может быть и несколько битов).
(R
1
, R
2
, b)
(3) Алиса вычисляет однонаправленную функцию для сообщения и посылает результат вместе с одной из случайных строк Бобу.
H(R
1
, R
2
, b), R
1
Это сообщение Алисы является доказательством вручения. Использование однонаправленной функции на этапе (3) мешает Бобу, инвертируя функцию, определить бит .
Когда для Алисы придет время раскрыть свой бит, протокол продолжается :
(4)
Алиса отправляет Бобу первоначальное сообщение.
(R
1
, R
2
, b)
(5) Боб вычисляет однонаправленную функцию для сообщения и сравнивает его и R
1
со значением однона- правленной функции и случайной строкой, полученными на этапе (3). Если они совпадают, то бит прав и- лен.
Преимущество этого протокола перед предыдущим в том, что Бобу не нужно посылать никаких сообщений .
Алиса посылает Бобу одно сообщение для вручения бита, а другое - для его раскрытия .
Не нужна и случайная строка Боба, так как результат Алисиного вручения - это сообщение, обработанное однонаправленной функцией. Алиса не может смошенничать и подобрать другое сообщение (R
1
, R
2
, b'), для ко- торого H(R
1
, R
2
, b')= H(R
1
, R
2
, b). Посылая Бобу R
1
, она вручает значение b. Если Алиса не сохранит в секрете
R
2
, то Боб получит возможность вычислить H(R
1
, R
2
, b') и H(R
1
, R
2
, b), получая возможность увидеть, что же он получил от Алисы.
Вручение бита с помощью генератора псевдослучайной последовательности
Этот протокол даже проще [1137]:
(1) Боб создает строку случайных битов и посылает ее Алисе.
R
В
(2) Алиса создает стартовую последовательность для генератора псевдослучайных битов. Затем для каждого бита в строке случайных битов Боба она посылает Бобу либо:
(a) выход генератора, если бит Боба равен 0, или
(b) XOR выхода генератора и бита Боба, если Бит Боба равен 1.
Когда для Алисы придет время раскрыть свой бит, протокол продолжается :
(3)
Алиса посылает Бобу свою стартовую последовательность.
(4) Боб выполняет этап (2), убеждаясь, что Алиса действует честно.
Если строка случайных битов достаточно длинна, а генератор псевдослучайных битов непредсказуем , мо- шенничество Алисы практически невозможно .

Blob-объекты
Строки, которые Алиса посылает Бобу для вручения бита, иногда называют blob-объектами. Blob-объект - это последовательность битов, хотя протоколы этого и не требуют . Как сказал Жиль Брассар (Gilles Brassard),
"Они могли бы быть сделаны и из волшебной пыли, если бы это было полезным " [236]. Blob-объекты обладают следующими четырьмя свойствами:
1. Алиса может вручить blob-объекты. Вручая blob-объект, она вручает бит.
2. Алиса может открыть любой blob-объект, который она вручила. Когда она открывает blob-объект, она может убедить Боба в значении бита, который был вручен вместе с blob-объектом. Следовательно, она не может открыть произвольный blob-объект, например, ноль или единицу.
3. Боб не может знать, каким образом Алиса может открыть blob-объект, который она вручила. Это ос- тается справедливым, даже когда Алиса откроет другие blob-объекты.
4. Blob-объекты не несут никакой информации, кроме вручаемого Алисой бита. Сами по себе blob- объекты, также как и процесс, с помощью которого Алиса вручает и открывает их, не связаны не с чем другим, что Алиса хотела бы сохранить в секрете от Боба.
4.10 Подбрасывание "честной" монеты
Настало время процитировать Джо Килиана (Joe Kilian) [831]:
Алиса и Боб хотели сыграть в "орла и решку", но монеты у них не было. Алиса предложила простой способ подбрасывать монетку мысленно.
"Сначала вы задумываете случайный бит, затем я задумаю случайный бит. Затем мы выполняем над битами "исключающее или", - предложила она.
"Но если один из нас не будет задумывать биты случайным образом?", - спросил Боб.
"Это не важно. Если хотя бы один из битов действительно случаен, то и "исключающее или" битов должно быть действ и- тельно случайным", - ответила Алиса, и после минутного раздумья Боб согласился.
Немного спустя Алиса и Боб наткнулись на книгу по искусственному интеллекту, лежащую на обочине дороги. Алиса,
добропорядочная гражданка, сказала: "Один из нас должен подобрать эту книгу и сдать ее в бюро находок". Боб согласился,
и предложил использовать их протокол подбрасывания монетки, что бы определить, кто унесет книгу.
"Если полученный бит будет 0, то ты возьмешь книгу, а если 1 - то я", - сказала Алиса. " Какой у тебя бит?"
Боб ответил: "1".
"Ну вот, и у меня такой же", - лукаво заметила Алиса. - "Я думаю, у тебя сегодня неудачный день".
Очевидно, у протокола подбрасывания монетки есть серьезный дефект. Хотя это правда, что "исключающее или" дейс т- вительно случайного бита, x, и любого независимо распределенного бита , y, дает в результате действительно случайный бит,
протокол Алисы не гарантирует, что два бита будут распределены независимо. На самом деле нетрудно убедиться, что не с у- ществует мысленного протокола, который позволит двум независимым сторонам подбрасывать "честную" монетку. Алиса и
Боб горевали, пока не получили письмо от неизвестного студента с дипломом по криптографии. Информация в письме была слишком теоретической, чтобы ее можно было применить для чего-то земного, но конверт, в котором пришло письмо, оказа л- ся чрезвычайно полезным.
Когда Алиса и Боб в следующий раз захотели подбросить монетку, они изменили первоначальный протокол. Сначала бит задумал Боб, но вместо того, чтобы открыть его немедленно, он записывает свой бит на листке бумаги и кладет листок в конверт. Затем Алиса объявляет свой бит. Наконец, Алиса и Боб достают бит Боба из конверта и вычисляют случайный бит.
Этот бит уже действительно случаен, независимо от честности играющих. Алиса и Боб получили работающий протокол, с о- циально значимая мечта криптографов осуществилась, и все они жили долго и счастливо.
Эти конверты выглядят весьма похожими на blob-объекты вручения бита. Когда Мануэль Блам (Manuel
Blum) столкнулся с проблемой подбрасывания "честной" монеты по модему [194], он решил ее, используя про- токол вручения бита:
(1) Алиса вручает случайный бит, используя любую из схем вручения бита, описанную в разделе 4.9.
(2) Боб загадывает свой бит.
(3) Алиса раскрывает бит Бобу. Боб выигрывает бросок, если он правильно загадал бит.
В общем случае, нам нужен протокол со следующими свойствами :
— Алиса должна "бросить монету" до того, как Боб загадает свой бит.
— Алиса не должна иметь возможности изменить результаты своего броска, узнав бит Боба.
— У Боба не должно быть возможности узнать результат броска перед тем, как он сделает свое предпол о- жение.
Существует несколько возможностей выполнить это .
Бросок монеты с помощью однонаправленных функций
Если Алиса и Боб договорятся об однонаправленной функции, протокол прост :
(1) Алиса выбирает случайное число, x. Она вычисляет y=f(x), где f(x) - однонаправленная функция.

(2) Алиса посылает y Бобу.
(3) Боб предполагает, что x четно или нечетно, и посылает свое предположение Алисе.
(4) Если предположение Боба правильно, результатом броска является "орел", если неправильно - то "решка".
Алиса объявляет результат броска монеты и посылает x Бобу.
(5) Боб проверяет, что y=f(x).
Безопасность этого протокола обеспечивается однонаправленной функцией . Если Алиса сможет найти x и x',
такие что x - четно, а x' - нечетно, и y=f(x)= f(x'), то она каждый раз сможет обманывать Боба . Кроме того, наи- меньший значащий бит f(x) должен быть некоррелирован с x. В противном случае Боб сможет обманывать Ал и- су, по крайней мере иногда. Например, если f(x) в 75 процентах случаев четна, если x, у Боба будет преимущест- во. (Иногда наименьший значащий бит не является лучшим выбором для использования в приложении, потому что его вычисление может оказаться слишком простым .)
Бросок монеты с помощью криптографии с открытыми ключами
Этот протокол работает как с криптографией с открытыми ключами, так и с симметричной криптографией .
Единственное условие - переключение алгоритма. То есть :
D E E M
E
M
K
K
K
K
1 2
1 2
(
(
( )))
( )
=
В общем случае это свойство не выполняется для симметричных алгоритмов, но справедливо для некоторых алгоритмов с открытыми ключами (например, RSA с идентичными модулями). Этот протокол:
(1) И Алиса, и Боб создают пары открытый ключ/закрытый ключ.
(2) Алиса создает два сообщения, одно для "орла", а второе - для "решки". Эти сообщения должны включать некоторую случайную строку, чтобы она могла подтвердить их подлинность на последующих этапах пр о- токола. Алиса шифрует оба сообщения своим открытым ключом и посылает их Бобу в произвольном п о- рядке.
E
A
(M
1
), E
A
(M
2
)
(3) Боб, которые не может прочитать не одно сообщение, случайным образом выбирает одно из них. (Он м о- жет посчитать их с помощью "Эники-беники ели вареники", воспользоваться компьютером для взлома протоколы или обратиться к цыганке.) Он шифрует выбранное сообщение своим открытым ключом и п о- сылает его обратно Алисе.
E
В
(E
A
(M))
где M - M
1 или M
2
(4) Алиса, которая не может прочитать полученное сообщение, расшифровывает его своим закрытым ключом и посылает обратно Бобу.
D
A
(E
В
(E
A
(M)))= E
В
(M
1
), если M = M
1
, или E
В
(M
2
), если M = M
2
(5) Боб расшифровывает сообщение своим закрытым ключом, раскрывая результат броска монеты, и посыл а- ет расшифрованное сообщение Алисе.
D
В
(E
В
(M
1
)) или D
В
(E
В
(M
2
))
(6) Алиса читает результат броска монеты и проверяет, что случайная строка правильна.
(7) Алиса и Боб раскрывают пары своих ключей, чтобы каждый из сторон могла убедиться в отсутствии м о- шенничества.
Этот протокол самодостаточен. Любая сторона может немедленно обнаружить мошенничество другой, и не требуется третья сторона ни для участия в протоколе, ни в качестве арбитра после завершения протокола . Чтобы посмотреть, как это работает, давайте попытаемся смошенничать .
Если выиграть, смошенничав, хочет Алиса, у нее есть три возможных пути повлиять на результат. Во пе р- вых, она может зашифровать два сообщения для "орла" на этапе (2). Боб обнаружит это, когда Алиса раскроет свои ключи на этапе (7). Во вторых, она может использовать какой-то другой ключ для расшифровывания с о- общения на этапе (4). Это приведет к бессмыслице, которую Боб и обнаружит на этапе (5). В третьих, она может объявить неправильным сообщение на этапе (6). Боб также обнаружит это на этапе (7), когда Алиса не сможет доказать, неправильность сообщения. Конечно, Алиса может отказаться от участия в протоколе на любом этапе,
когда жульничество Алисы станет для Боба очевидным.
Если Боб захочет мошеннически выиграть, его положение ничуть не лучше. Он может неправильно заши ф- ровать сообщение на этапе (3), но Алиса обнаружит обман, взглянув на заключительное сообщение на этапе (6).

Он может заявить, что неправильно выполнил этап (5) из-за какого-то мошенничества со стороны Алисы, но эта форма жульничества вскроется на этапе (7) . Наконец, он может послать Алиса сообщение о "решке" на этапе
(5), независимо от расшифрованного сообщения, но Алиса сможет немедленно проверить достоверность соо б- щения на этапе (6).
Бросок монеты в колодец
Интересно отметить, что во всех этих протоколах Алиса и Боб узнают результат броска не одновременно . В
каждом протоколе есть момент, когда одна из сторон (Алиса в первых двух протоколах и Боб в последнем) у з- нает результат броска, но не может изменить его. Эта сторона может, однако, задержать раскрытие результата для второй стороны. Это называется броском монет в колодец. Представьте себе высохший колодец. Алиса стоит рядом с колодцем, А Боб - немного подальше. Боб бросает монету, и она падает в колодец. Алиса может теперь заглянуть в колодец и увидеть результат, но она не может спуститься вниз и изменить его . Боб не сможет увидеть результат, пока Алиса не позволит ему подойти и заглянуть в колодец .
Генерация ключей с помощью броска монеты
Реальным применением этого протокола служит генерация сеансового ключа. Протоколы броска монеты п о- зволяют Алисе и Бобу создать случайный сеансовый ключ так, что никто из них не сможет повлиять на то, к а- ким будет этот ключ. Если Алиса и Боб зашифруют свои сообщения, процедура генерации ключа к тому же ст а- нет безопасной от злоумышленника.
4.11 Мысленный покер
Протокол, аналогичный протоколу броска монеты с помощью открытых ключей, позволяет Алисе и Бобу и г- рать друг с другом в покер по электронной почте . Алиса вместо создания и шифрования двух сообщений, одн о- го для "орла", а другого - для "решки", создает 52 сообщения М
1
, М
2
, ..., М
52
, по числу карт в колоде. Боб слу- чайным образом выбирает пять из них, шифрует своим открытым ключом и посылает обратно Алисе. Алиса расшифровывает сообщения и посылает их обратно Бобу, который расшифровывает их для определения своей "руки". Затем он случайным образом выбирает еще пять сообщений и, не изменяя их, посылает Алисе. Она расшифровывает их, и эти соответствующие карты становятся ее "рукой". В течение игры эта же процедура применяется для сдачи игрокам дополнительных карт. В конце игры Алиса и Боб раскрывают свои карты и п а- ры ключей, чтобы каждый мог убедиться в отсутствии мошенничества .
Мысленный покер с тремя игроками
Покер интереснее, если в игре участвуют несколько человек. Базовый протокол мысленного покера легко может быть распространен на трех и более игроков . В этом случае криптографический алгоритм также должен быть коммутативным.
(1) Алиса, Боб и и Кэрол создают пары открытый ключ/закрытый ключ.
(2) Алиса создает 52 сообщения, по одному для каждой карты колоды. Эти сообщения должны включать н е- которую уникальную случайную строку, чтобы Алиса могла проверить их подлинность на последующих этапах протокола. Алиса шифрует все сообщения своим открытым ключом и посылает их Бобу в прои з- вольном порядке.
E
A
(M
n
)
(3) Боб, который не может прочитать не одно сообщение, случайным образом выбирает пять из них. Он ши ф- рует их своим открытым ключом и посылает обратно Алисе.
E
В
(E
A
(M
n
))
(4) Боб отправляет Кэрол оставшиеся 47 сообщений.
E
A
(M
n
)
(5) Кэрол, которая не может прочитать не одно сообщение, случайным образом выбирает пять из них. Она шифрует их своим открытым ключом и посылает Алисе.
E
С
(E
A
(M
n
))
(6) Алиса, которая не может прочитать ни одно из полученных сообщений, расшифровывает их своим закр ы- тым ключом и посылает обратно Бобу или Кэрол (в соответствии с тем, от кого она их получила).
D
A
(E
В
(E
A
(M
n
)))= E
В
(M
n
)
D
A
(E
С
(E
A
(M
n
)))= E
С
(M
n
)

(7) Боб и Кэрол расшифровывают сообщения своими ключами, чтобы узнать свои карты
D
В
(E
В
(M
n
))
D
C
(E
C
(M
n
))
(8) Кэрол случайным образом выбирает пять из оставшихся 42 сообщений и п осылает Алисе.
E
A
(M
n
)
(9) Алиса расшифровывает сообщения, чтобы узнать свои карты.
D
A
(E
A
(M
n
))
(10) В конце игры Алиса, Боб и Кэрол раскрывают свои карты и пары ключей, чтобы каждый мог убедиться в отсутствии мошенничества.
Дополнительные карты раздаются подобным же образом. Если карта нужна Бобу или Кэрол, любой из них берет зашифрованную колоду и повторяет протокол с Алисой, Если карта нужна Алисе, то тот, у кого сейчас находится зашифрованная колода, посылает ей случайную карту .
В идеале, этап (10) является обязательным. Свои "руки" в конце протокола должны открывать не все игроки,
а только те, которые не спасовали. Так как этап (10) в протокол только для контроля мошенничества, возможны какие-нибудь улучшения.
В покере интересно только, не смошенничал ли победитель . Все остальные могут мошенничать сколько вл е- зет, раз уж они все равно проигрывают. (В действительности это не совсем верно. Кто-то, проигрывая, может собирать данные о стиле игры в покер других игроков .) Итак, взглянем на случаи выигрыша различных игроков.
Если выигрывает Алиса, она раскрывает свою "руку" и свои ключи. Боб может использовать закрытый ключ
Алисы для проверки правильности действий Алисы на этапе (2), то есть проверить, что каждое из 52 сообщений соответствует отдельной карте. Кэрол может проверить, что Алиса не лжет о своей "руке", шифруя карты о т- крытым ключом Алисы и проверяя, что они соответствуют шифрованным сообщениям, которые она послала
Алисе на этапе (8).
Если выигрывают Боб или Кэрол, победитель раскрывает свои карты и ключи. Алиса может убедиться в правильности карт, проверив свои случайные строки . Она может также убедиться, что сданы были именно эти карты, шифруя их открытым ключом победителя и проверяя, что они совпадают с зашифрованными сообщ е- ниями, полученными на этапах (3) или (5).
Этот протокол не защищен от сговора игроков-мошенников. Алиса и другой игрок могут объединиться и безнаказанно вместе надувать третьего игрока . Следовательно, важно проверять все ключи и случайные строки каждый раз, когда игроки раскрывают свои карты . И если вы сидите за виртуальным столом с двумя игроками,
которые никогда одновременно не раскрывают свои карты, причем один из них сдает (в предыдущем протоколе это Алиса) кончайте игру.
Все это красиво в теории, но реализовать все это на компьютере весьма непросто. В реализации для трех и г- роков на трех различных Sparc-станциях восемь часов требуется только для тасования колоды, так что лучше поиграть в настоящий покер [513].
Вскрытия мысленного покера
Криптографы показали, что при использовании этими протоколами покера алгоритма с открытыми ключами
RSA происходит небольшая утечка информации [453, 573]. Конкретно, если двоичное представление карт явля- ется квадратичным остатком (см раздел 11.3), то зашифрованные карты также являются квадратичным оста т- ком. Это свойство может быть использовано для "крапления" некоторых карт - например, всех тузов . Это даст не много информации о сдачах, но в такой игре как покер даже чуть-чуть информации даст преимущество при длительной игре.
Шафи Голдвассер (Shafi Goldwasser) и Сильвия Микали (Silvia Micali) [624] разработали протокол умствен- ного покера для двух игроков, который решает эту проблему, хотя из-за своей сложности он скорее имеет тол ь- ко теоретическое значение. Обобщенный протокол покера для n игроков, устраняющий проблему утечки и н- формации, был разработан в [389].
Результаты других исследований протоколов игры в покер можно найти в [573, 1634, 389]. Усложненный протокол, позволяющий игрокам не раскрывать своих "рук", приведен в [390]. Дон Копперсмит (Don Copper- smith) рассматривает два способа мошенничества в умственном покере, использующем алгоритм RSA [370].

Анонимное распределение ключей
Хотя непохоже, чтобы кто-нибудь собирался использовать этот протокол для игры в покер по модему ,
Чарльз Пфлегер (Charles Pfleeger) рассматривает ситуацию, в которой этот тип протокола может оказаться п о- лезным [1244].
Рассмотрим проблему распределения ключей. Если предположить, что люди не могут сами генерировать свои ключи(ключи должны иметь определенную форму, или должны быть подписаны некоторой организацией,
или еще что-нибудь подобное), то для генерации и рассылки ключей придется создать Центр распределения ключей (Key Distribution Center, KDC). Проблема в том, что нужно найти такой способ распределения ключей,
что никто, включая сервер, не сможет понять, кому какой ключ достался . Следующий протокол решает эту про- блему:
(1) Алиса создает пару открытый ключ/закрытый ключ. В этом протоколе она сохраняет в секрете оба ключа.
(2) KDC генерирует непрерывный поток ключей.
(3) KDC шифрует ключи, один за другим, своим открытым ключом.
(4) KDC передает зашифрованные ключи, один за другим, по сети.
(5) Алиса случайным образом выбирает ключ.
(6) Алиса шифрует выбранный ключ своим открытым ключом.
(7) Алиса ждет какое-то время (достаточно большое, чтобы сервер не мог определить, какой ключ она выбр а- ла) и посылает дважды зашифрованный ключ в KDC.
(8) KDC расшифровывает дважды зашифрованный ключ с помощью своего закрытого ключа, получая ключ,
зашифрованный открытым ключом Алисы.
(9) Сервер посылает шифрованный ключ обратно Алисе.
(10) Алиса расшифровывает ключ с помощью своего закрытого ключа.
У находящейся где-то в середине протокола Евы нет ни малейшего представления о выбранном Алисой ключе. Она видит непрерывный поток ключей, создаваемых на этапе (4). Когда Алиса посылает ключ серверу на этапе (7), он шифруется ее открытым ключом, который также для этого протокола хранится в секрете . Спо- соба связать это сообщение с потоком ключей у Евы нет . Когда ключ возвращается Алисе сервером на этапе
(9), он также зашифрован открытым ключом Алисы . Ключ становится известным, только когда Алиса расши ф- ровывает его на этапе (10).
Если вы используете RSA, в этом протоколе происходит утечка информации со скоростью, по меньшей мере,
один бит на сообщение. Причиной этого снова являются квадратичные остатки . Если вы собираетесь использо- вать этот способ для распределения ключей, убедитесь, что эта утечка не приведет к каким-либо последствиям.
Кроме того, поток ключей, создаваемый KDC должен быть достаточно большим, чтобы противостоять вскр ы- тию грубым взломом. Конечно же, если Алиса не может верить KDC, то она не должна пользоваться его клю- чами. Мошенничающий KDC может предусмотрительно записывать все создаваемые им ключи. Тогда он см о- жет найти среди них ключ, выбранный Алисой .
Этот протокол также предполагает, что Алиса будет действовать честно. При использовании RSA существу- ет ряд действий, которые может предпринять Алиса, чтобы получить больше информации, чем ей удалось бы при другом методе шифрования. В нашем сценарии эта проблема не существенна, но при других обстоятельс т- вах она может стать важной.
4.12 Однонаправленные сумматоры
Алиса является членом организации "Заговорщики" . Иногда ей приходится встречаться с другими членами в плохо освещенных ресторанах и шептать секреты налево и направо . Беда в том, что рестораны настолько плохо освещены, что она не может быть уверена, что человек, сидящий напротив нее за столом, тоже член организ а- ции.
"Заговорщики" могут выбирать из нескольких решений . Каждый может носить с собой список членов орг а- низации. Это влечет за собой две следующих проблемы. Во первых, теперь каждый должен носить с собой большую базу данных, и, во вторых, им придется как следует охранять этот список членов . Другим способом является использование идентификационных карт, выпущенных надежным секретарем . Дополнительным пре- имуществом этого способа является то, что и посторонние смогут проверять членов организации (всякие скидки в местной бакалейной лавке), до для этого нужен надежный секретарь. Никому из "заговорщиков" нельзя дове- рять до такой степени.
Новым решением является использование однонаправленного сумматора [116]. Это что-то похожее на од-

нонаправленные хэш-функции, для которых выполняется требование коммутативности. То есть, можно хэш и- ровать базы данных членов организации в произвольном порядке и получать одно и то же значение . Более того,
можно добавлять новых членов в хэш-таблицу и получать новое хэш-значение, снова не зависящее от порядка .
Итак, вот что делает Алиса. Она выполняет расчет, используя множество всех имен членов организации, о т- личных от нее. Затем она сохраняет это полученное значение вместе со своим именем. Боб и другие члены д е- лают то же самое. Теперь, когда Алиса и Боб встречаются в плохо освещенном ресторане, они просто обмен и- ваются друг с другом вычисленными значениями и именами. Алиса убеждается, что результат, получаемый при добавлении имени Боба к значению Алисы, совпадает с результатом, получаемым при добавлении имени Ал и- сы к значению равно значению Боба. Боб делает то же самое. Теперь они оба знают, что собеседник - также член организации. И в то же время никто не сможет определить личности других членов организации .
Более того, рассчитанные значения каждого члена могут быть выданы посторонним. Тогда Алиса сможет подтвердить свое членство постороннему (возможно, для членской скидки в буфете местной контрразведки ), не показывая ему весь список членов.
Новых членов можно добавить просто послав по кругу новые имена. К несчастью, удалить члена можно только единственным путем: всем членам рассылается новый список и они пересчитывают свои значения . Но "заговорщикам" придется выполнять это действие только при отставке кого-то из членов, мертвые члены могут остаться в списке. (Странно, но это не создает проблемы.)
Это разумная идея применяется в ряде приложений, когда вы хотите достичь эффекта цифровой подписи без использования централизованной системы подписей .
4.13 Раскрытие секретов "все или ничего"
Представьте себе, что Алиса - бывший агент бывшего Советского Союза, а теперь безработная . Чтобы зара- ботать, она продает секреты. Каждый, готовый заплатить названную цену, может купить секрет . У нее даже есть каталог. Все ее секреты с аппетитными названиями упорядочены по номерам : "Где Джимми Хоффа?", "Кто тайно контролирует Трехстороннюю комиссию ?", "Почему Борис Ельцин всегда выглядит, как будто он прогл о- тил живую лягушку?", и т.д.
Алиса не хочет отдавать два секрета по цене одного и не показывает даже части информации, касающейся любого из секретов. Боб, потенциальный покупатель, не хочет платить за кота в мешке . Он также не хочет со- общать Алисе, какие из секретов ему нужны . Это не ее дело, и, кроме того, тогда Алиса сможет добавить в свой каталог пункт "Секреты, которыми интересуется Боб" .
Протокол покера не работает в этом случае, так как в конце этого протокола Алиса и Боб должны раскрыть свои карты друг другу. К тому же, существуют трюки, с помощью которых Боб может узнать сразу несколько секретов.
Решение называется раскрытием секретов "все или ничего" (all-or-nothing disclosure of secrets, ANDOS)
[246], потому что если Боб получил любую информацию о любом из секретов Алисы, то он потерял возмож- ность узнать что-либо еще о других ее секретах .
В криптографической литературе можно найти различные протоколы ANDOS. Некоторые из них обсужда- ются в разделе 23.9.
4.14 Условное вручение ключей
Вот отрывок из введения в тему Сильвио Микали [1084]:
Сегодня подслушивание с разрешения суда является эффективным методом отдавать преступников в руки правосудия .
По нашему мнению еще более важно, что это также предотвращает дальнейшее распространение преступления, удерживая от использования обычных сетей связи с незаконными целями . Следовательно, существует обоснованное беспокойство, что ра с- пространение криптографии с открытыми ключами может быть на руку преступным и террористическим организациям . Дей- ствительно, во многих законах предполагается, что соответствующие правительственные ведомства при определенных усл о- виях, оговоренных законом, должны иметь возможность получить открытый текст любого обмена информацией по общедо с- тупным сетям. В настоящее время many это может быть трактоваться, как требование к законопослушным гражданам либо
(1) использовать слабые криптосистемы - т.е., криптосистемы, которые соответствующие власти (а также кто угодно!) см о- гут вскрыть с помощью умеренных усилий, или (2) заранее сообщать свои секреты властям. Не удивительно, что такая аль- тернатива законно встревожила многих заинтересованных граждан, создавая в результате мнение, что тайна личности дол ж- на стоять над национальной безопасностью и отправлением закона .
Условное вручение ключей является сутью продвигаемых правительством США программы Clipper и Стан- дарта условного шифрования (Escrowed Encryption Standard). Проблема в том, чтобы и обеспечить тайну личн о- сти, и в то же время позволить разрешенное судом подслушивание .
Escrowed Encryption Standard обеспечивает безопасность с помощью защищенного оборудования . У каждой микросхемы шифрования уникальный идентификационный номер ( ID) и секретный ключ. Этот ключ делится на

две части и хранится, вместе с ID, двумя различными организациями условного вручения . Всякий раз, когда микросхема шифрует файл данных, она сначала шифрует сеансовый ключ уникальным секретным ключом. З а- тем она передает зашифрованный сеансовый ключ и свой ID по каналу связи. Когда правоохранительные орга- ны хотят расшифровать поток информации, зашифрованной одной из этих микросхем, они извлекают из потока
ID, получают соответствующие ключи из организаций условного вручения, объединяют их с помощью операции
XOR, расшифровывают сеансовый ключ и затем используют его для дешифрирования потока сообщений . Для защиты от мошенников в эту схему введены дополнительные усложнения, подробно описанные в разделе 24.16.
Аналогичная схема может быть реализована и программно с использованием криптографии с открытыми кл ю- чами [77, 1579, 1580, 1581].
Микали называет свою идею честной криптосистемой [1084,10851. (Говорят, что правительство США за- платило Микали $1000000 за использование его патентов [1086, 1087] в своем стандарте Escrowed Encryption
Standard, затем патент Микали купил Банковский трест.) В таких криптосистемах закрытый ключ делится на части и распределяется среди различных организаций . Как и схема с совместным использованием секрета, эти организации могут объединиться и восстановить закрытый ключ. Однако, части ключа обладают дополнител ь- ным свойством - их правильность может быть проверена независимо без восстановления закрытого ключа .
Алиса может создать свой собственный закрытый ключ и распределить его части среди n доверительных собственников. Ни один из них не может восстановить закрытый ключ Алисы. Однако каждый может пров е- рить, что его часть - это правильная часть закрытого ключа. Алиса не может послать кому-то из доверительных собственников строку случайных битов и надеяться улизнуть. Если судебные власти разрешат подслушивание,
соответствующие правоохранительные органы смогут воспользоваться постановлением суда для того, чтобы n доверительных собственников выдали свои части . Собрав все n частей, власти восстановят закрытый ключ и смогут подслушивать линии связи Алисы . С другой стороны, чтобы получить возможность восстановить ключ
Алисы и нарушить ее тайну личности, Мэллори придется купить всех n доверительных собственников.
Вот как работает этот протокол:
(1) Алиса создает пару закрытый ключ/открытый ключ. Она разбивает закрытый ключ на несколько откр ы- тых и закрытых частей.
(2) Алиса посылает открытую часть и соответствующую закрытую часть каждому из доверительных собс т- венников. Эти сообщения должны быть зашифрованы. Она также посылает открытый ключ в KDC.
(3) Каждый из доверительных собственников независимо выполняет вычисления над своими закрытой и о т- крытой частями, чтобы убедиться в их правильности. Каждый доверительный собственник хранит закр ы- тую часть в каком-нибудь надежном месте и отправляет открытую часть в KDC.
(4) KDC выполняет иное вычисление для открытых частей и открытого ключа. Убедившись, что все правил ь- но, он подписывает публичный ключ и отправляет его обратно Алисе или помещает в какую-нибудь базу данных.
При наличии постановления суда о подслушивании каждый из доверительных собственников передает свою часть в KDC, и KDC получает возможность восстановить закрытый ключ . До этой передачи ни KDC, ни кто- либо из доверительных собственников не может самостоятельно восстановить закрытый ключ, для восстано в- ления ключа нужны все доверительные собственники .
Любой алгоритм с открытыми ключами можно сделать "честным" подобным образом . Ряд конкретных алго- ритмов рассматривается в разделе 23.10. В работах Микали [1084, 1085] обсуждаются пути объединения опи- санного с пороговой схемой, чтобы для восстановления закрытого ключа требовалось некоторое подмножество доверительных собственников (например, трое из пяти). Он также показывает, как объединить это с рассеянной передачей (см. раздел 5.5) так, чтобы доверительные собственники не знали, чей закрытый ключ восстанавл и- вается.
"Честные" криптосистемы несовершенны . Преступник может использовать такую систему, применяя подсо з- нательный канал (см. раздел 4.2.), чтобы вставить другой секретный ключ в свою информацию. Таким образом он может безопасно обмениваться информацией с кем-нибудь еще, используя подсознательный ключ и сове р- шенно не волнуясь по поводу разрешенного судом подслушивания . Данная проблема решается другим проток о- лом, который называется отказоустойчивым условным вручением ключей [946, 833]. Этот алгоритм и про- токол описывается в разделе 23.10.
Политика условного вручения ключей
Помимо правительственных планов относительно условного вручения ключей распространяются и комме р- ческие системы с условным вручением ключей. Возникает очевидный вопрос: какое преимущество от условного вручения ключей получает пользователь?
Ну, на самом деле никакого. Пользователь не получает от условного вручения ключей ничего такого, чего он

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