Бросание монеты
Для разрешения неожиданно возникшего спорного вопроса Антон и Борис решают бросить монету. Однако и у того, и у другого при себе не оказалось ни одной. Тогда они решают "бросить" монету в уме: сначала Антон загадает, что выпадет — "орел" или "решка", а потом Борис подумает и объявит. какой стороной упала "брошенная" им монета. Спрашивается: могут ли Антон и Борис сделать это так, чтобы полностью быть уверенными в том. что никто из них не смошенничал?
Могут, если воспользуются криптографическим протоколом, который заставит их действовать таким образом, что:
Антону придется бросить монету прежде, чем Борис попытается предсказать, какой стороной она упадет;
Антон не сможет изменить результат бросания монеты после того, как услышит, на какую сторону монеты сделал свою ставку Борис;
Борис не узнает, что выпало — "орел" или "решка", до тех пор. пока не примет окончательное решение и не сообщит о нем Антону.
Бросание монеты с помощью предсказания бита
В этом случае криптографический протокол, которою должны придерживаться Антон и Борис при бросании монеты, выглядит следующим образом:
1. Антон делает предсказание битового значения в соответствии с одной из схем, описанных в разделе "Предсказание бита",
2. Борис пытается догадаться, какое значение предсказал Антон, и информирует о своей догадке Антона.
3. Антон сообщает Борису предсказанное значение. Борис выигрывает, если его догадка была правильной.
Бросание монеты с помощью однонаправленной функции
Если Антон и Борис сумеют заранее договориться об использовании конкретной однонаправленной функции f(x), криптографический протокол бросания монеты будет выглядеть так:
1. Антон выбирает случайное число х и вычисляет значение y = f(x).
2. Антон посылает у Борису.
3. Борис пытается догадаться, является ли х четным или нечетным числом. и сообщает о своей догадке Антону.
4. Антон информирует Бориса о том, какое число х он выбрал.
5. Борис проверяет, действительно ли f(x) = y, а также узнает, была ли верна его догадка.
Здесь все зависит от свойств однонаправленной функции f. Если Антон вдруг сможет найти два числа х и х' такие, что х является четным, а х' — нечетным, и при этом y = f(x) = f(x'), то Борис всегда будет в проигрыше. Необходимо также, чтобы наименее значимый бит f(x) не зависел от х. Например, если f(x) будет четным в 90 процентах всех случаев, когда х является четным, Антон будет брать верх над Борисом почти всегда.
Бросание монеты с помощью криптосистемы с открытым ключом
В этом случае от алгоритмов шифрования (Е) и расшифрования (D) требуется, чтобы они были коммутативны, т. е.:
D K1 (E K2 (E K1 (M) ) ) ) = Е К2 (М),
где К 1 и К 2 — криптографические ключи, Р — открытый текст сообщения. Для симметричных криптоалгоритмов в общем случае это условие не выполняется, однако существуют алгоритмы шифрования с открытым ключом, для которых оно верно. Последние могут быть использованы в протоколе бросания монеты:
1. Антон и Борис генерируют каждый для себя по паре ключей, состоящей из открытого и тайного ключа.
2. Антон генерирует две случайные битовые строки Р 1 и Р 2, одна из которых означает, что при бросании монеты выпал "орел", а другая — что получилась "решка".
3. При помощи своего открытого ключа Антон шифрует сначала Р 1 , а потом Р 2 , и отсылает оба полученных в результате шифрсообщения (E A (P 1 ) и E A (P 2 )) Борису.
4. Борис выбирает одно из присланных ему Антоном шифрсообшений (для этой цели Борис может воспользоваться, например, известной считалкой "Эне, бене, раба, квинтер, минтер, жаба" или сходить за советом к астрологу). Борис шифрует выбранное шифрсообщение с помощью своего открытого ключа и отсылает результат (E Б (E A (P)) , где Р — это либо Р 1 , либо Р 2 ) Антону.
5. Антон расшифровывает пришедшее от Бориса сообщение на своем тайном ключе и посылает то, что у него получилось ( D Б (E Б (P)) = E Б (P) обратно Борису.
6. Борис расшифровывает это сообщение Антона ( D Б (E Б (P)) = P) и узнает, какой стороной упала монета. Затем Борис шлет Р Антону.
7. Антон проверяет, действительно ли Р — это одна из тех двух случайных битовых строк, которые он сгенерирована на шаге 2.
8. Чтобы окончательно убедиться в честности друг друга, Антон и Борис обмениваются парами ключей, которые они сгенерировали на шаге 1.
Читателю предоставляется возможность самому доказать, что каждый из участников этого протокола немедленно обнаружит, если другой участник попытается смошенничать.
Интересно отметить, что участники протокола узнают результат подбрасывания монеты не одновременно, а по очереди. Поэтому в некоторый момент времени один из участников знает, как "легла" подброшенная монета, а другой — еще нет. А следовательно, в случае неблагоприятного исхода, тот. кто уже знает результат, может повести себя неспортивно, отказавшись от дальнейшего выполнения шагов протокола.
На практике протоколы бросания монеты часто используются для генерации сеансовых ключей. В этом случае Антон и Борис могут сгенерировать случайную битовую последовательность таким образом, что посторонние окажутся не в состоянии повлиять на ее выбор. Тем не менее при генерации сеансовых ключей с помощью протокола бросания монеты Антону и Борису все равно придется шифровать все свои сообщения, чтобы защититься от возможного подслушивания.
Игра в покер
Подобно тому, как Антон и Борис бросали монету, не имея при себе самом монеты, они могут сыграть в покер без колоды карт. Соответствующий криптографический протокол аналогичен протоколу, который помог Антону и Борису организовать бросание монеты — в обоих необходимо обеспечить, чтобы используемые алгоритмы шифрования к расшифрования были коммутативны.
Отличие между этими протоколами состоит в том, что теперь Антону требуется сгенерировать, зашифровать и отослать Борису не 2 битовых последовательности, а 52 — по числу карт в воображаемой колоде. Среди них Борис случайным образом выбирает 5 битовых последовательностей, шифрует их при помощи своего открытого ключа и посылает Антону. Антон расшифровывает полученные последовательности и шлет обратно Борису, который тоже расшифровывает их. Затем Борис выбирает еще 5 битовых последовательностей и посылает Антону, который опять их расшифровывает. В результате и у Антона, и у Бориса на руках окажется по 5 карт, которыми они и будут играть друг против друга. Если потребуется, дополнительные карты могут быть розданы обоим игрокам по той же схеме.
По окончании игры Антон и Борис открывают свои карты и обмениваются ключами, чтобы иметь возможность проверить, насколько честно они следовали правилам карточной игры. К сожалению, криптографические протоколы, предназначенные для игры в покер, устроены таким образом, что в ходе нее игроки могут слегка мошенничать. Характер этого мошенничества зависит от используемого криптоалгоритма. Например, при шифровании при помощи квадратичных вычетов играющие имеют возможность пометить несколько карт. Не бог весть что, но ведь покер — это такая игра, в которой даже небольшая порция дополнительной информации о сопернике может в конечном счете решить исход игры.