密码学协议举例(五):两个人能够在电话上打牌吗?

    密码学的应用范围非常广泛。每一样简单的社交活动里都有很大的学问。考虑这样一个问题,两个人想通过一部电话打牌,但他们都不信任对方。有没有可能仅通过一部电话实现扑克牌协议,并且保证游戏的公正性呢?
    扑克牌的信息隐蔽性带来了很多与密码学协议相关的有趣问题。两个象棋大师可以在洗澡间一边冲澡一边大喊“炮八平五”、“马八进七”,一对围棋情侣可以在床上一边亲热一边呻吟“点三三”、“拆二”。等事情办完了,一盘精彩的棋局或许也就结束了。这些棋类游戏之所以可以“盲下”,就是因为在棋类游戏中,双方的局面信息都是完全公开的。不过,打牌就是另外一码事了。你说你出方片7,我怎么知道你有一个方片7?事先发牌?那谁来负责发牌呢?怎样发牌呢?难道我告诉你“发到你手中的是两张3一张5一张8一张9”?这样一看,两个人“盲打扑克牌”似乎是不可能的了,要么需要借助道具,要么需要第三者的帮助。不过,运用密码学知识,我们可以设计一套扑克牌协议,该协议能够实现随机的、隐蔽的、公平的发牌,并且不需要其它东西的帮助。我们以一手五张牌为例,说明如何实现“两人各摸五张牌”的程序。


    我们首先来看这里面的一个趣题。

    10. A、B两人分别在两座岛上。B生病了,A有B所需要的药。C有一艘小船和一个可以上锁的箱子。C愿意在A和B之间运东西,但东西只能放在箱子里。只要箱子没被上锁,C都会偷走箱子里的东西,不管箱子里有什么。如果A和B各自有一把锁和只能开自己那把锁的钥匙,A应该如何把东西安全递交给B?
    答案:A把药放进箱子,用自己的锁把箱子锁上。B拿到箱子后,再在箱子上加一把自己的锁。箱子运回A后,A取下自己的锁。箱子再运到B手中时,B取下自己的锁,获得药物。

    我们的基本思路就是这样。不妨用数字1到54来表示54张牌。发牌前,A在每个数字前附着一个随机字符串前缀,然后给每个字符串都加上一把锁,把54张加密的扑克牌传给B。B收到了扑克牌一看,傻了,这些牌他一张也不认识,每张牌上面都有A的锁。B从里面挑选5张牌出来。他自己不知道这5张牌是什么,但是他也不能让A知道,于是他在这5张牌上再各加一把锁,传给A。A可以解开自己当初上的那把锁,但牌上还有一把锁,A拿它没办法,只能原封不动地传回去。B把剩下的锁解开,得到自己的5张牌。然后呢,B手上不是还剩了49张牌吗?B从中随便挑5张出来给A,由A解开上面的锁,得到A的5张牌。
    听起来很完美,但实现起来并不简单。上锁开锁和加密解密并不完全相同:两把锁的地位是相同的,但两次加密则有先后的问题。要想把上述协议转换为密码学协议的话,我们需要采用这样一种加密方式:明文首先由A加密,B在这个密文的基础上再进行加密,此时A还能够把里面那一层密码解开,而保持B的那一层密码不动。如果用Ea(x)表示A的加密函数,用Da(x)表示A的解密函数的话,我们需要一种加密系统使得Db(Da(Eb(Ea(x))))=x。有这样的加密系统吗?有!模数相同的RSA算法就满足这样的“交换律”。
    RSA算法之所以起作用,原因就在于你能找到这么一对e和d,使得ed≡1 (mod φ(n))。假如存在两对钥匙(e1, d1)和(e2, d2),容易想到(e1*e2)(d1*d2)=(e1*d1)(e2*d2),它仍然同余于1。因此,计算密文c=m^(e1*e2)之后,再计算c^(d1*d2)一定能恢复明文m,不管你是先算c的d1次方还是d2次方。
    有了RSA算法,我们的协议也就出来了。A、B两人各生成一对RSA公私匙(公钥不必也不能公开,我们这里只用到了RSA的可交换性,没用到RSA的加密钥匙可公开性)。A把54个加了随机字符串前缀的扑克牌分别用公钥加密并发给B,B从中选5张牌并再用自己的公钥加密,然后A用私钥解开B的这5张牌中里面一层的密码,B再用自己的私钥解密以得到自己的一手牌。同时,B在剩余的49张牌中挑选5张发给A,A用自己的私钥解密以获得自己的一手牌。这样下来,每个人都得到了自己的一手牌,而都不知道对方手里捏的是啥牌。以后如果还需要摸牌的话,则可以重复刚才的协议。游戏结束后,双方公开自己的钥匙,你可以验证看对方的钥匙与游戏中的数据是否吻合,以确定对方在游戏过程中没有作弊。这个协议可以轻易扩展到多个人的情况,也可以适用于更复杂的扑克牌游戏。

47 条评论

  • yh

    赞,这样的话matrix67可以发明一种方法,让一个人收到一堆加密的计算任务,然后计算的人自己都不知道自己在干什么,然后把结果传回去解开。。
    就可以让p2p的某东西打败云计算了。

  • yh

    问一下,你们合租是用的独立ip?每个人一个ip?
    这样有什么好处?
    用共享ip被封的几率有多少?

  • DavidW

    这个协议应该有漏洞,A可以作弊,并且协议提供的验证手段对此无能无力。因为首次加密是由A完成的,A完全可以暗中记下明文和密文的一一对应关系,这样A随后就可以判断出B选了哪5张牌。
    请大家指正。

  • su27

    DavidW说的不对,A并不知道剩下了哪些牌(除了属于A的五张牌),所以就不知道B选的5张牌与以前的哪五张对应。
    不过我觉得为了满足打牌时自己摸牌的选择权,应该让B把54张牌全部加密,然后B告诉A他选了哪五张,A将那五张解密并发给B,同时告诉B他选了哪五张,这时B将自己的再解密,就获得明文,将A选的牌解密并发给A,A将其再解密获得明文。

  • iceberg

    这样似乎不能防止过程中作弊以达到某些目的。由于这样子摸牌和出牌(以直接声称拥有某牌的方式)之间没有稳定可靠的固定联系,如果A仅仅想破坏一个牌局,这种协议无法阻止。如果能达到每一次出牌都能验证而不是需要事后来验证则是更好的。

  • 凌晨海风

    好像可以很简单的表达:由A、B分别对54张牌都加密,然后公开一人抽一张。最后两人把对方抽的牌解密后还给对方,再把对方解密后发过来的自己的牌解密。

  • 凌晨海风

    楼层: 地壳 | 2009-02-20 22:07 | iceberg 说
    ———————–
    为了避免过程中作弊,可以规定在出任何一张牌的时候,都必须将这张牌的双重密文解掉一层,告诉对方,对方就可以验证了。

  • 1moJim

    原来是密码学。。。

  • DavidW

    su27,如果B只加密5张牌,那么A显然可以辨认出是哪5张被B操作过了。
    凌晨海风关于发牌的想法很好。
    为了防止任何一方作弊(谎报或伪造等),双方都记录下每一轮选牌过程的密文,当一方声称出某张牌的时候,则把此牌加密传给对方验明正身。然而代价不菲。

  • su27

    @DavidW: 你可能没注意到本例中公钥不是公开的,所以即使B只加密5张牌,A也不能得知是哪五张被B加密,因为他不能计算出密文与之对照。

    即时验证的话,2个人的代价只是信息量增加一倍,即必须同时发明文和解过一层的密文,但是n个人的话就会变得太繁杂了。

  • iceberg

    @su27
    似乎不需要发明文,只要要求A在收到代表B的牌的双重密文时留底并编号。而B在提供自己选择的A的牌时顺便把它们加密留底并编号(这里还要用手段防止编号作弊)。出牌时,A声称自己编号为n的牌为X并解一层双重密文发出,B就可以验证。

  • iceberg

    多人时则会发生每一次声称都要所有人解密一轮的问题,很复杂。

  • DavidW

    su27,事实上我注意到了公钥不公开。但是正如我一开始就指出的,A能够作弊是“因为首次加密是由A完成的,A完全可以暗中记下明文和密文的一一对应关系(即加密一张牌后随即记下其密文),这样A随后就可以判断出B选了哪5张牌。” ,而不是你说的“计算出密文与之对照”(这种方法的确不行)。
    解决方案之一就是B对N(>5)张牌加密。

  • iceberg

    不知DavidW的意思是A知道了自己手中的5张牌还是说知道了B手中的5张牌?后者是不可能的。而前者……A不知道自己有什么牌那还得了!

  • iceberg

    在刚才的评论中补充一句话:
    A在收到代表B的牌的双重密文时留底并编号。而B在提供自己选择的A的牌时顺便把它们加密留底并编号(这里还要用手段防止编号作弊)并把这个双重密文传送给A。出牌时,A声称自己编号为n的牌为X并解一层双重密文发出,B就可以验证。

    于是在n人游戏中,这导致所有人都需要交流一次n重密文,确保一次编号无作弊,并每一次出牌时都要过一轮n次解密。有个可靠的不会篡改数据的中立服务器,事情可能会简单一点。

  • iceberg

    在n人互动中,用这种出牌方式,似乎还会出现一个问题:中间人作弊问题。即一个中间人,需要轮到他解密时,他不提供本次提供的密文的解密文,而提供一个,例如,随机字符串。结果全部解密后的结果与明文不符。如果不公开公钥,如何消除这种作弊方式?

  • iceberg

    作弊方式貌似还有很多:如果A在发牌时,在B发送双重密文给他时,不提供解密文,而提供随机字符串,就会造成B解密后得到的明文与A拥有的明文不符。B就会错误判断自己的持牌。如何消除这种作弊呢?

  • iceberg

    当然,如果有一个可靠的不会篡改数据的中立服务器,只需要由它来发牌和判断就行了,根本用不着这么多事情。所以还是必须在这个限制下讨论。讨论那些不依赖于任何人的诚实的实现方法。

  • 凌晨海风

    To 楼层: 19楼 | 2009-02-21 21:27 | iceberg

    这种方法可以很快被B识别出来,因为A发过去的是随机字符串,那么B解密后得到正确牌型的概率很低,譬如最初用1~54数字当作扑克牌,那么如果B解密后的数字并不在这个范围内,当然可以判断是A在作弊。

  • iceberg

    但是既然这个协议中牌只用最后一个字符,那么就要加长字长,用例如说32位表示字符,那么这样的作弊者只有54/2^32的期望作弊不被发现,但不是零的都不能让完美主义者满意。另外多人过程仍然有问题,中途有人作弊,这方法判断不出作弊者。

  • ted

    好吧,从楼上的讨论我得出这样一个问题:当有N(N>=1)个人想破坏协议的时候,有什么协议能阻止人破坏这个协议?

  • wzyboy

    我是从同学的博客里看到这文章然后摸过来的,有点问题:
    今天嘎嘎吱吱想了好一会儿,发现漏洞了:假设把54张牌按照24点的方式编号(A为1,J为11,大王为15),玩家甲的密钥为4和0.25,那如果他用4加密这54张牌,则加密后的54张牌也是有大小顺序的,另一个往家只要排一下,那么数字最大的就是大王了,数字最小(有四个)的就是A,以此可以推算出所有的牌甚至解出对方的密钥。如果玩家甲用小于1的密钥(比如0.25)加密,那也只要把刚才的反一下就可以了。总之,猜对所有牌的可能性是50%。
    (手机发表)

  • yh

    能不能证明一下这类算法的安全性?
    比如一方能不能通过合数生成假的密钥来破解掉?
    cosechy@gmail.com

  • 蜡烛在线

    这猜测有意思,有结果后告诉我一下,OK?

  • phi

    如果B在传回自己的5张加密选择和其他牌之後, A把所有的牌都解密一遍, 这样就可以看到凡是已经解密的牌里头被B加密的都是密文, 剩下的都是明文, 通过找到明文缺少的牌, A就可以直接看出B的所有牌, 然後A再保持明文原来附加的随机字符不变加密传回去, B不会发现任何作弊现象.

  • 西木

    没明白,本来是想实现如何不用实体牌来三国杀,如果这一套密码加上,和实体牌的意义不是一样吗?

  • 数学家


    M67您能否想出一种多方通话玩杀人游戏的方法?

  • 聂锡宁

    没看完全文,那个趣题,漏洞的有

  • 聂锡宁

    c中途获得a(message), 直接回传给a; a以为回传的信息是经过b加密的b(a(message)), 于是a打开自己的那把锁, 再传出去; 这次的信息就是裸露的.

    或者,如果a能够判别message被加密的次数, 但不能判别是加密者是谁, c可以把c(a(message))回传给a, 然后经a解密后的c(message)对c来说也是可以偷窥的.

  • wuk

    怎么总是感觉发牌的顺序不对呢?
    1. A、B两人各生成一对RSA公私匙
    2. A把54个加了随机字符串前缀的扑克牌分别用公钥加密并发给B
    3. B也对54张牌加密发回给A
    4. A从中随机选5张牌解密,然后A将所有牌发回给B
    5. B对所有牌解密能得到明文的5张牌(自己的手牌),和49张A加密的牌,从49张中随机找5个发给A
    6. A自己解密后得到自己的5张牌。

    这样才平等吧,而且也最符合前面的那个引例

  • engine

    实在不忍再看评论了。。。。
    B拿到A解密后的5张卡片,通过明文与被A加密后的密文对照,搞出来A的加密方式,A不就惨了吗。。。。。^_^

  • youyanruyu

    To engine:
    要是RSA加密用几组明文-密文就能破解出密钥,人家就不用混了。

  • cervelo

    学习了下,2个人在电话里打牌

  • 路人甲

    1、A先加密所有54张
    2、然后B仅仅只加密其中5张牌
    3、那么A再对所有54张解密,不能解密的那5张,不就是B手上的牌?

  • 梁兵兵

    【今天嘎嘎吱吱想了好一会儿,发现漏洞了:假设把54张牌按照24点的方式编号(A为1,J为11,大王为15),玩家甲的密钥为4和0.25……猜对所有牌的可能性是50%。】
    每一次加密方法都可以略有改变,只要你下次能用同样的密匙把它解回来,比如y=(x+n) mod 54这样的算法,位移的方向和量每次出牌都可以不一样。

  • 环亚娱乐

    如同磁铁吸引四周的铁粉,热情也能吸引周围的人,改变周围的情况。

  • Sunday

    还是有问题啊。。。模数相同才行,必须要有一个公共的机构发布模数与p、q;

  • 哎呀

    作者描述的是A授权B发牌, A.第一次加密所有的牌后就再也没有机会接触到所有牌了, B等于瞎子一样拿到了所有的牌, 给自己分5张, 给A分5张, 给A分的牌直接丢该A去解密, 给自己分的牌先加密在丢给A,A解密到这5张牌后仍包含B的加密,丢回给B后B自行解密得到自己的5张牌

  • 哎呀

    多人情况: 玩家A(加密人) 玩家B(发牌) 玩家C(普通玩家) D(普通玩家)
    玩家A 加密54张牌 发给玩家B
    玩家B 随机选4张牌(带A秘文),将3张牌分别发给A,C,D
    玩家A收到自己的牌(带秘文A),解密得到自己的牌
    B,C,D 分别将手里的牌加密(带AB,AC,和AD)发送给A
    A对收到的牌进行解密AB->B , AC->C, AD->D, 发回给B,C, D
    BCD收到牌以后用各自的密文解密成明文牌
    自此一轮发牌结束

  • 八里土人

    看了锁,看了一开始的协议,就想到RSA的同态性(交换性)了。暗暗赞一句(偷偷乐)

发表评论

48  +    =  52