密码学的应用范围非常广泛。每一样简单的社交活动里都有很大的学问。考虑这样一个问题，两个人想通过一部电话打牌，但他们都不信任对方。有没有可能仅通过一部电话实现扑克牌协议，并且保证游戏的公正性呢？
扑克牌的信息隐蔽性带来了很多与密码学协议相关的有趣问题。两个象棋大师可以在洗澡间一边冲澡一边大喊“炮八平五”、“马八进七”，一对围棋情侣可以在床上一边亲热一边呻吟“点三三”、“拆二”。等事情办完了，一盘精彩的棋局或许也就结束了。这些棋类游戏之所以可以“盲下”，就是因为在棋类游戏中，双方的局面信息都是完全公开的。不过，打牌就是另外一码事了。你说你出方片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用自己的私钥解密以获得自己的一手牌。这样下来，每个人都得到了自己的一手牌，而都不知道对方手里捏的是啥牌。以后如果还需要摸牌的话，则可以重复刚才的协议。游戏结束后，双方公开自己的钥匙，你可以验证看对方的钥匙与游戏中的数据是否吻合，以确定对方在游戏过程中没有作弊。这个协议可以轻易扩展到多个人的情况，也可以适用于更复杂的扑克牌游戏。
sofa
支持一下。
赞，这样的话matrix67可以发明一种方法，让一个人收到一堆加密的计算任务，然后计算的人自己都不知道自己在干什么，然后把结果传回去解开。。
就可以让p2p的某东西打败云计算了。
问一下，你们合租是用的独立ip？每个人一个ip？
这样有什么好处？
用共享ip被封的几率有多少？
这个协议应该有漏洞，A可以作弊，并且协议提供的验证手段对此无能无力。因为首次加密是由A完成的，A完全可以暗中记下明文和密文的一一对应关系，这样A随后就可以判断出B选了哪5张牌。
请大家指正。
DavidW说的不对，A并不知道剩下了哪些牌（除了属于A的五张牌），所以就不知道B选的5张牌与以前的哪五张对应。
不过我觉得为了满足打牌时自己摸牌的选择权，应该让B把54张牌全部加密，然后B告诉A他选了哪五张，A将那五张解密并发给B，同时告诉B他选了哪五张，这时B将自己的再解密，就获得明文，将A选的牌解密并发给A，A将其再解密获得明文。
这样似乎不能防止过程中作弊以达到某些目的。由于这样子摸牌和出牌（以直接声称拥有某牌的方式）之间没有稳定可靠的固定联系，如果A仅仅想破坏一个牌局，这种协议无法阻止。如果能达到每一次出牌都能验证而不是需要事后来验证则是更好的。
好像可以很简单的表达：由A、B分别对54张牌都加密，然后公开一人抽一张。最后两人把对方抽的牌解密后还给对方，再把对方解密后发过来的自己的牌解密。
楼层: 地壳 | 2009-02-20 22:07 | iceberg 说
———————–
为了避免过程中作弊，可以规定在出任何一张牌的时候，都必须将这张牌的双重密文解掉一层，告诉对方，对方就可以验证了。
原来是密码学。。。
su27，如果B只加密5张牌，那么A显然可以辨认出是哪5张被B操作过了。
凌晨海风关于发牌的想法很好。
为了防止任何一方作弊（谎报或伪造等），双方都记录下每一轮选牌过程的密文，当一方声称出某张牌的时候，则把此牌加密传给对方验明正身。然而代价不菲。
@DavidW: 你可能没注意到本例中公钥不是公开的，所以即使B只加密5张牌，A也不能得知是哪五张被B加密，因为他不能计算出密文与之对照。
即时验证的话，2个人的代价只是信息量增加一倍，即必须同时发明文和解过一层的密文，但是n个人的话就会变得太繁杂了。
@su27
似乎不需要发明文，只要要求A在收到代表B的牌的双重密文时留底并编号。而B在提供自己选择的A的牌时顺便把它们加密留底并编号（这里还要用手段防止编号作弊）。出牌时，A声称自己编号为n的牌为X并解一层双重密文发出，B就可以验证。
多人时则会发生每一次声称都要所有人解密一轮的问题，很复杂。
su27，事实上我注意到了公钥不公开。但是正如我一开始就指出的，A能够作弊是“因为首次加密是由A完成的，A完全可以暗中记下明文和密文的一一对应关系（即加密一张牌后随即记下其密文），这样A随后就可以判断出B选了哪5张牌。” ，而不是你说的“计算出密文与之对照”（这种方法的确不行）。
解决方案之一就是B对N（>5）张牌加密。
不知DavidW的意思是A知道了自己手中的5张牌还是说知道了B手中的5张牌？后者是不可能的。而前者……A不知道自己有什么牌那还得了！
在刚才的评论中补充一句话：
A在收到代表B的牌的双重密文时留底并编号。而B在提供自己选择的A的牌时顺便把它们加密留底并编号（这里还要用手段防止编号作弊）并把这个双重密文传送给A。出牌时，A声称自己编号为n的牌为X并解一层双重密文发出，B就可以验证。
于是在n人游戏中，这导致所有人都需要交流一次n重密文，确保一次编号无作弊，并每一次出牌时都要过一轮n次解密。有个可靠的不会篡改数据的中立服务器，事情可能会简单一点。
在n人互动中，用这种出牌方式，似乎还会出现一个问题：中间人作弊问题。即一个中间人，需要轮到他解密时，他不提供本次提供的密文的解密文，而提供一个，例如，随机字符串。结果全部解密后的结果与明文不符。如果不公开公钥，如何消除这种作弊方式？
作弊方式貌似还有很多：如果A在发牌时，在B发送双重密文给他时，不提供解密文，而提供随机字符串，就会造成B解密后得到的明文与A拥有的明文不符。B就会错误判断自己的持牌。如何消除这种作弊呢？
当然，如果有一个可靠的不会篡改数据的中立服务器，只需要由它来发牌和判断就行了，根本用不着这么多事情。所以还是必须在这个限制下讨论。讨论那些不依赖于任何人的诚实的实现方法。
To 楼层: 19楼 | 2009-02-21 21:27 | iceberg
这种方法可以很快被B识别出来，因为A发过去的是随机字符串，那么B解密后得到正确牌型的概率很低，譬如最初用1～54数字当作扑克牌，那么如果B解密后的数字并不在这个范围内，当然可以判断是A在作弊。
但是既然这个协议中牌只用最后一个字符，那么就要加长字长，用例如说32位表示字符，那么这样的作弊者只有54/2^32的期望作弊不被发现，但不是零的都不能让完美主义者满意。另外多人过程仍然有问题，中途有人作弊，这方法判断不出作弊者。
好吧,从楼上的讨论我得出这样一个问题:当有N(N>=1)个人想破坏协议的时候,有什么协议能阻止人破坏这个协议?
乱了
我是从同学的博客里看到这文章然后摸过来的，有点问题：
今天嘎嘎吱吱想了好一会儿，发现漏洞了：假设把54张牌按照24点的方式编号（A为1，J为11，大王为15），玩家甲的密钥为4和0.25，那如果他用4加密这54张牌，则加密后的54张牌也是有大小顺序的，另一个往家只要排一下，那么数字最大的就是大王了，数字最小（有四个）的就是A，以此可以推算出所有的牌甚至解出对方的密钥。如果玩家甲用小于1的密钥（比如0.25）加密，那也只要把刚才的反一下就可以了。总之，猜对所有牌的可能性是50%。
（手机发表）
能不能证明一下这类算法的安全性？
比如一方能不能通过合数生成假的密钥来破解掉？
cosechy@gmail.com
这猜测有意思，有结果后告诉我一下，OK?
如果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来说也是可以偷窥的.
怎么总是感觉发牌的顺序不对呢？
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张牌。
这样才平等吧，而且也最符合前面的那个引例
实在不忍再看评论了。。。。
B拿到A解密后的5张卡片，通过明文与被A加密后的密文对照，搞出来A的加密方式，A不就惨了吗。。。。。^_^
To engine:
要是RSA加密用几组明文-密文就能破解出密钥，人家就不用混了。
学习了下，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这样的算法，位移的方向和量每次出牌都可以不一样。
如同磁铁吸引四周的铁粉，热情也能吸引周围的人，改变周围的情况。
test
还是有问题啊。。。模数相同才行，必须要有一个公共的机构发布模数与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的同态性（交换性）了。暗暗赞一句（偷偷乐）