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

每一样简单的社交活动里都有很大的学问。考虑这样一个问题,两个人想通过一部电话打牌,但他们都不信任对方。有没有可能仅通过一部电话实现扑克牌协议,并且保证游戏的公正性呢?
我们首先来看这里面的一个趣题。

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

4 days ago, this page was being read.


Subscribe to Comments