4.11 智力扑克

    这是一个类似于公平硬币抛掷协议的协议,它允许Alice和Bob通过电子邮件打扑克。Alice在这里不是地生成和加密两个消息,一个 “正面”和一个“反面”,她要生成52个消息M1,M2,LL,M52,每个代表一副牌中的一张牌。Bob随机选取5张牌,用他的公开密钥加密,然后回送给Alice。Alice解密消息并回送给Bob,Bob解密它们以确定他的一手牌。然后,当Bob接收到Alice发送的消息,他随机地选择另外5个消息,并发给Alice,Alice解密它们,并且它们变成她的一手牌。在游戏期间,可通过重复这些过程来为任意一方发其它的牌。在游戏结束时,Alice和Bob双方出示他们的牌和密钥对使得任意一方确信另一方没有作弊。

三方智力扑克

    人较多时玩牌会更有趣。基本的智力扑克协议可以很容易地扩展到三个或更多个玩牌者。在这种情况下,密码算法也必须是可交换的。

    (1)Alice、Bob和Carol都产生一个公钥/私钥密钥对。

    (1)Alice产生52个消息,每个代表一副牌中的一张牌。这些消息应包含一些唯一的随机串,以便她能在以后验证它们在协议中的真实性。Alice用她的公钥加密所有这些消息,并将它们发送给Bob。

EA(Mn)。

    (2)Bob,由于不能阅读任何消息,他随机地选择5张牌。他用他的公钥加密,并把它们回送给Alice。

EB(EA(Mn))。

    (3)Bob将余下的47张牌送给Carol。

EA(Mn)。

    (4)Carol,由于不能阅读任何消息,也随机选5个消息。她用她的公钥加密,并把它们送给Alice。

EC(EA(Mn))。

    (5)Alice也不能阅读回送给她的消息,她用她的私钥对它们解密,然后送给Bob或Carol(依据来自谁而定)。

DA(EB(EA(Mn)))= EB(Mn

DA(EC(EA(Mn)))= EC(Mn

    (7)Bob和Carol用他们的密钥解密并获得他们的牌。

DB(EB(Mn))= Mn

DC(EC(Mn))= Mn

    (8)Carol从余下的42张牌中随机取5张,把它们发送给Alice。

EA(Mn)。

    (9)Alice用她的私钥解密消息获得她的牌。

DA(EA(Mn))=Mn

    (10)在游戏结束时,Alice,Bob和Carol都出示他们的牌以及他们的密钥,以便每人都确信没有人作弊。

    其它的牌可以用同样的方式处理。如果Bob或Carol想要牌,任何一个人能够取被加密的牌,并和Alice一起履行该协议。如果Alice想要一张牌,当前得到牌的任何人都随机地发给她一张牌。

    在理想情况下第(10)步是不必要的。协议结束后,不应该要求所有选手都出示他们的牌;只有那些没有出完牌的人被要求。由于第(10)步是只设计来抓住骗子的部分,因而也可能有改进。

    在扑克中,人们只对赢家是否欺骗感兴趣。只要他们仍然失败,其它每个人也能进行他们想要的欺骗。(事实上,这确实是不对的。当失败时,可以收集其它牌手的玩牌风格的数据)。让我们看看不同选手赢牌的情况。

    如果Alice赢了,她出示她的牌和她的密钥。Bob能够用Alice的私钥确认Alice是合法地进行了第(2)步——52个消息的每个都对应一张不同的牌。Carol通过用Alice的公钥加密牌,并验证是与她在第(8)步中送给Alice的加密消息相同,从而确认Alice没有对出的牌撒谎。

    如果Bob或Carol赢了,赢牌者将出示他们的牌以及密钥。Alice可以通过检查她的随机串来确信这些牌是合法的。她也能确信通过用赢家的公钥对牌加密的牌是发的牌,并验证是与她在第(3)步或第(5)步中收到的加密消息相同。

    当防止恶意的牌手间串通时,这个协议便不安全了。Alice和别的牌手可以有效地联合对付第三方,可以在不引起怀疑的情况下骗取其所有东西。因此,每次检查牌手出的牌中的随机串以及所有的密钥是重要的。如果你与两个从未出示他们牌的人坐在虚拟桌子上,且其中一个为发牌者(上述协议中的Alice)时,你就应该停止玩了。

对扑克协议的攻击

    密码学家已经证明,如果使用RSA算法,那么这些扑克协议会泄漏少量的信息 [453,573]。具体地,如果牌的二进制表示是二次方程的残数(见11.3节),那么牌的加密亦为二次方程的残数。这个特性可被用来标记某些牌——比如,所有的“A”。虽然不能泄露许多牌,但在诸如扑克游戏中,在最后即便是一个微小的比特信息也会有用。

    Shafi Goldwasser和Silvio Micali[624]设计了一个两人玩的智力扑克游戏协议,它解决了这个问题,但由于其复杂性,使其太理论化而不能实用。在[389]中设计了消除信息泄漏问题的通用n方扑克协议。

    别的对扑克协议的研究可在[573,1634,389]中找到。一个允许牌手不出示他们的牌的复杂协议可在[390]中找到。Don Coppersmith讨论了在利用RSA算法的智力扑克游戏中两种作弊的方法。

匿名密钥分配

    在人们利用这个协议通过调制解调器玩扑克是不太可能的时候,Clarles Pfleeger讨论了这样一种情况,使得这类协议迟早有用。

    考虑密钥分配问题。如果我们假定人们不能生成他们自己的密钥(它们必须为某种形式,或必须被某组织签名,或类似的要求)。我们必须设置密钥分配中心(KDC),用来生成和分配密钥。问题是我们必须找出一些密钥分配方法使得(包括服务器)没有人知道谁得到了什么密钥。

    下面的协议解决了这个问题:

        (1)Alice生成一个公钥/私钥密钥对。对这个协议,她保持这两个密钥秘密。

        (2)KDC产生连续的密钥流。

        (3)KDC用它自己的公钥,逐个地将这些密钥加密。

        (4)KDC逐个地将这些加密后的密钥传送到网上。

        (5)Alice随机选择一个密钥。

        (6)Alice用她的公钥加密所选的密钥。

        (7)Alice等一段时间(要足够长使得服务器不知道她选择了哪个密钥),将这个双重加密的密钥送回KDC。

        (8)KDC用它的私钥解密双重加密的密钥,得到一个用Alice的公开密钥加密的密钥。

        (9)服务器将此加密密钥送给Alice。

        (10)Alice用她的私钥解密这个密钥。

    Eve在这个协议过程中也不知道Alice选择了什么密钥。她在第(4)步看到了连续密钥流通过。当Alice在第(7)步将密钥送回给服务器时,是用她的公开密钥加密的,而公开密钥在协议期间也是秘密的。Eve没法将它与密钥流关联起来。当服务器在第(9)步将密钥送回给Alice时,也是用Alice的公开密钥加了密的。仅当Alice在第(10)步解密密钥时,才知道密钥。

    如果你用RSA,这个协议以每个1比特的速度泄漏信息。它又是二次方程的残数。如果你准备用这种方式分配密钥,必须确保泄露是无关紧要的。来自KDC的密钥流也必须足够长,以阻止穷举攻击。当然,如果Alice不信任KDC,那么她就不应该从KDC得到密钥。恶意的KDC可以预先记录它所生成的所有密钥。然后,它能搜索所有的密钥,决定哪一个是Alice的。

    这个协议也假定Alice行为正当。利用RSA算法,她能够做其它事情来得到更多的信息。在我们的这个方案中,这不成其为问题,但在其它环境可能存在问题。