8.5　玩游戏

鲍勃和艾莉丝正在商量晚餐去哪里吃。鲍勃想吃牛排，而艾莉丝想吃鱼。他们决定抛硬币来选择餐馆。鲍勃抛起硬币，然后把它扣在胳膊上。艾莉丝猜正面。鲍勃拿开盖在硬币上的手，是反面，于是两人去吃牛排。

听起来挺公平，不过要是艾莉丝和鲍勃是通过电话或互联网联络怎么办？鲍勃可能会对硬币结果撒谎，甚至根本不抛硬币。艾莉丝如何才能确认过程是公平的？

一个办法是用公开的随机信息。鲍勃和艾莉丝可以商定如果当天道琼斯工业指数的收盘价最后一位是奇数，那么由鲍勃来选餐厅，如果是偶数则由艾莉丝说了算。但这个方法在星期六就失效了，股市不开盘。

这里介绍一种使用密码学的方法，用到了我们在本章前面讲到的公钥加密。首先由鲍勃生成公钥和私钥，然后随机选一个数，如69 441 251 920 931 124，把它用公钥加密。鲍勃把公钥和加密过的消息发给艾莉丝。

然后轮到艾莉丝来猜鲍勃的数字是奇数还是偶数，并把结果发给鲍勃。之后鲍勃把私钥发送给艾莉丝，后者用它解密信息，发现鲍勃选定的数字是69 441 251 920 931 124。若艾莉丝猜的是偶数，那她就赢了；如果她猜的是奇数，那鲍勃就赢了。

为什么这个方案能奏效呢？在艾莉丝选择猜奇数或偶数之前，鲍勃选好了一个数69 441 251 920 931 124。艾莉丝在猜的时候不知道鲍勃选的是什么数。艾莉丝只能看见加密过的消息，除非能破解密码，否则她对鲍勃选择的数一无所知。所以艾莉丝只能随便猜。另一方面，鲍勃无法改变选定的数，因为之前已经把它的加密版本发给艾莉丝了。艾莉丝猜完后鲍勃通过发送私钥来公布答案。如果双方都随机地进行游戏，那么胜率应该是五五平分的。只要公钥加密系统是安全的，就没有人能作弊。

抛硬币这个游戏太简单了，那么对于复杂点的游戏情况又如何呢？

鲍勃和艾莉丝能通过电话下国际象棋吗？可以，而且很容易——每个人轮流用标准国际象棋记谱法告诉对方自己的行动即可。

他们能下西洋双陆棋（backgammon）或强手棋（Monopoly）吗？鲍勃如何掷骰子才能让艾莉丝信服？他们可以采用一套掷骰子的协议，原理类似于上面的抛硬币协议。

他们可以玩扑克牌或其他牌类游戏吗？这回情况就变得复杂得多了。艾莉丝需要得到一些随机选择的牌，只有她能看见，鲍勃看不见；鲍勃也要有艾莉丝看不到的一些牌。还要有一些两个玩家都能看到的牌，以及一些两人现在看不到，但之后会让一个或两个玩家看到的牌。

好多网站都能让你玩扑克牌，但这些网站本身充当了受信任的第三方，由他们来发牌或将牌展示给各个玩家的浏览器。

在没有受信任的第三方的情况下，鲍勃和艾莉丝还能玩扑克牌吗？在20世纪70年代和80年代，密码学家设计了许多种通过电话或网络进行双人或多人牌类游戏的方案，每个玩家都有自己的私钥和公钥，并需要对加密的信息再进行一次加密。

20世纪80年代和90年代，密码学家研发出了非常通用的技术，让任意需要跟受信任对手玩的游戏都能通过互联网进行，即使没有受信任的对手也可以。这些方法既用到了加密技术，又使用了零知识证明。这些通信协议相当复杂，而且很少被实际应用。现实中人们要么依靠受信任的网站，要么会采用一些针对某个特定目的而设计的通信协议。