Читать книгу - "Золотой билет. P, NP и границы возможного - Лэнс Фортноу"

Боб и Элис спорят, куда пойти ужинать. Бобу хочется в стейк-хаус, Элис – в рыбный ресторан. В конце концов на помощь призывают орла и решку. Боб подбрасывает монетку и накрывает ее ладонью. Элис ставит на орла. Боб открывает монетку… решка. Этим вечером Боб будет наслаждаться сочным стейком.

Все бы хорошо, но что, если Боб и Элис говорят по телефону или переписываются по почте? Боб может соврать и сказать, что выпала решка, когда на самом деле выпал орел. А может и вообще монетку не бросать. Как убедиться, что он говорит правду?

Простейший способ – положиться на случайное событие, исход которого станет известен всем. Например, договориться, что если последняя цифра промышленного индекса Доу-Джонса на закрытие дня окажется нечетной, то выбирать ресторан будет Боб, а если четной – то Элис. Правда, в субботу торги не ведутся, так что на выходные придется придумывать что-то другое.

В этом случае подойдет рассмотренная ранее схема шифрования с открытым ключом. Боб создает пару ключей, открытый и закрытый. Затем выбирает случайное число, к примеру – 69441251920931124, и шифрует его своим открытым ключом, который отсылает Элис вместе с шифровкой.

Элис выбирает «чет» или «нечет» и сообщает об этом Бобу. В ответ он отправляет ей секретный ключ. Расшифровав криптограмму, Элис узнает, что Боб загадал 69441251920931124. Если она выбрала «чет», то выиграла, а если «нечет» – выиграл Боб.

Давайте разберемся, почему эта схема работает. Боб выбирает число еще до того, как Элис делает ставку. Но когда она загадывает «чет» или «нечет», то не знает, что он выбрал 69441251920931124. У нее есть лишь криптограмма, и если она не умеет взламывать шифры, то не получит никакой информации об этом числе. Все, что она может сделать, – это положиться на интуицию. Боб не станет менять свое число, поскольку уже отправил Элис криптограмму. Теперь ему остается лишь сообщить ей секретный ключ, чтобы она увидела, какое число он выбрал. Когда ставки делаются без всякой системы, каждый игрок выигрывает в половине случаев. Надежность шифров с открытым ключом исключает возможность обмана.

Бросать монетку – это как-то слишком просто. Что, если взять какую-нибудь более сложную игру?

Можно ли, к примеру, провести по телефону шахматную партию? Без проблем: игроки по очереди будут сообщать друг другу свой следующий ход, пользуясь принятыми в шахматах обозначениями.

Как насчет игры в кости, нарды или «Монополию»? Поверит ли Элис, что Боб не врет насчет выпавших очков? Безусловно – для этого лишь нужно будет утвердить протокол бросания костей, во многом совпадающий с протоколом бросания монетки.

А вот в случае с покером и другими карточными играми все обстоит несколько сложнее. Карты игроков выбираются случайным образом. Каждый видит свои карты и не знает о картах противника. Некоторые карты доступны обоим; какую-то часть не видят ни тот, ни другой. По ходу игры закрытые карты открываются и становятся доступны либо всем, либо лишь одному игроку.

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

Можно ли провести игру в покер без сайта-посредника? Можно, конечно, – вот только протоколом бросания монетки тут уже не обойдешься. В семидесятых и восьмидесятых годах прошлого века для карточных игр с двумя и более игроками появилось множество хитрых криптографических схем, в которых были и открытые ключи, и закрытые, и даже двойное шифрование. Применялись эти схемы как по телефону, так и по сети.

К началу девяностых криптографам удалось разработать универсальные схемы. С их помощью по интернету можно было играть в любую игру, в которой требовался честный противник. Эти схемы исключали всякую возможность мошенничества; в протоколах помимо шифрования применялось также доказательство с нулевым разглашением. И все же на практике удобнее было работать с сайтами-посредниками или пользоваться узкоспециализированными протоколами, поэтому широкого распространения универсальные схемы так и не получили.