密码学协议举例[6]–两个人能够在电话上打牌吗？|文艺数学君

两个人能够在电话上打牌吗？

这是关于密码学协议的第6篇文章, 前面5篇文章在加上这一篇文章的链接是:

• 密码学协议举例[1]–秘密共享的门限方案
• 密码学协议举例[2]–带有防欺骗的承诺
• 密码学协议举例[3]–另类的密钥交换协议
• 密码学协议举例[4]–秘密数字的比较（百万富翁问题）|文艺数学君
• 密码学协议举例[5]–平均薪水问题|文艺数学君
• 密码学协议举例[6]–两个人能够在电话上打牌吗？|文艺数学君

问题来源

考虑这样一个问题，两个人想通过一部电话打牌，但他们都不信任对方。有没有可能仅通过一部电话实现扑克牌协议，并且保证游戏的公正性呢？

我们可能会遇到已下的问题：

• 比如你说你出方片7，我怎么知道你有一个方片7？
• 事先发牌？那谁来负责发牌呢？怎样发牌呢？难道我告诉你"发到你手中的是两张3一张5一张8一张9"?

这样一看，两个人"盲打扑克牌"似乎是不可能的了，要么需要借助道具，要么需要第三者的帮助。不过，运用密码学知识，我们可以设计一套扑克牌协议，该协议能够实现随机的、隐蔽的、公平的发牌，并且不需要其它东西的帮助。我们以一手五张牌为例，说明如何实现“两人各摸五张牌”的程序。

解决办法--想法来源

我们先来看另外一个问题，然户将这两个问题进行类比：

问题: 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张牌最后是B的牌，B不能让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)，容易想到(e1e2)(d1d2)=(e1d1)(e2d2)，它仍然同余于1。因此，计算密文c=m^(e1e2)之后，再计算c^(d1d2)一定能恢复明文m，不管你是先算c的d1次方还是d2次方。

最终的协议

有了RSA算法，我们的协议也就出来了。

A、B两人各生成一对RSA公私匙（公钥不必也不能公开，我们这里只用到了RSA的可交换性，没用到RSA的加密钥匙可公开性）。A把54个加了随机字符串前缀的扑克牌分别用公钥加密并发给B，B从中选5张牌并再用自己的公钥加密，然后A用私钥解开B的这5张牌中里面一层的密码，B再用自己的私钥解密以得到自己的一手牌。

同时，B在剩余的49张牌中挑选5张发给A，A用自己的私钥解密以获得自己的一手牌。这样下来，每个人都得到了自己的一手牌，而都不知道对方手里捏的是啥牌。以后如果还需要摸牌的话，则可以重复刚才的协议。游戏结束后，双方公开自己的钥匙，你可以验证看对方的钥匙与游戏中的数据是否吻合，以确定对方在游戏过程中没有作弊。这个协议可以轻易扩展到多个人的情况，也可以适用于更复杂的扑克牌游戏。