密码学协议举例(一):带有防欺骗的承诺

    我们常常在电视上看到这样的一幕:一位老太太兴冲冲地走上台去,翻过三个商标牌,发现上面尽是5块钱、10块钱的小奖,垂头丧气地回到观众席;然后马脸李咏会跑出来,边翻着另外几个牌子边说,1000块的大奖在这个后面,800块的在这里,之类的。或许有人会纳闷了,为什么主持人要演出“事后揭大奖”这一幕呢?道理很简单,节目组想通过这一个“验证过程”告诉观众,这个环节不是骗人的,大奖真的就在这后面,只是刚才那家伙运气背了没摸到而已。摸奖前宣称有大奖,摸完奖之后还能证实大奖真的存在,这就是带有防欺骗的承诺。
    但是,同样的事情在网络上似乎是办不到的。一个典型的例子就是QQ原来弄的那个恶心的砸金蛋砸银蛋。屏幕左边那个是银蛋,屏幕右边那个是金蛋,你鼠标选一个敲下去,看能否砸出QQ宠物来。大量测试表明砸出宠物的概率远远低于50%,让人质疑游戏的真实性。鬼知道它那个程序是不是真的预先指定了一个有宠物的蛋蛋,很可能不管你点了哪个蛋蛋结果都一样,系统按照概率直接显示出抽奖结果来。当然,怀疑游戏的公平性也没办法,要想在网络上实现带防欺骗的承诺是比较困难的,毕竟让你看一段从另一个蛋蛋里跳出一个宠物的Flash动画不能让你相信刚才你是真的“选错”了吧。
    我们的问题就是:如何设计一个协议,用以保证一个二选一的网络互动抽奖游戏的真实性?换句话说,假如你选择了金蛋,结果没有中奖,那么系统如何能够令你相信奖品刚才真的在银蛋里?


 
    md5一类的单向散列函数提供了一个不错的方案。系统首先随机选择一个蛋(比如银蛋),在蛋里面藏好奖品,然后把单词“silver”连同一个随机字符串(比如“jq548s”)进行md5。在你抽奖之前,把这个md5值先告诉你。然后你砸蛋,发现金蛋里没有奖品。此时,系统宣布字符串“silverjq548s”,你计算它的md5值,发现和之前系统告诉你的一模一样。此时,你便相信系统刚才是真的把奖品藏在银蛋里了。若你刚才真的砸了银蛋,那系统就没办法抵赖了,因为md5函数是一个单向的、不可逆的、不可预测的函数,想要构造一个“golden某某某”形式的,且md5值和刚才一样的字符串,那比登天还难。另外,注意到在单词后面添加随机字符串这一步骤是必须的,否则你可以尝试计算“silver”和“golden”各自的md5值,从而获知哪个蛋里面有奖品。
    不过,现在看来,这个协议也不可靠了。系统有一个办法可以耍赖:字符串“jq548s”有可能根本不是随机生成的,而是经过一系列精心构造的。我们不能排除这样一种情况,即我们可以通过某种算法构造出一对字符串xxx和yyy,使得“silverxxx”和“goldenyyy”的md5值是一样的。md5被破解后,造成这种“碰撞”更是轻松,并且同一对碰撞还可以反复用于欺骗不同的用户。其中一个解决办法是,你可以在协议最初时生成一个自己的随机字符串发给系统,并要求系统传回 “silver/golden” + 系统生成的随机串 + 你自己传过去的随机串 三者并在一起后的md5值。用户一旦参与了字符串的构造,系统作弊就变得真正棘手了。

    还有没有什么其它办法呢?我在《应用密码学》里看到了一个颇有意思的协议,它用伪随机序列来代替单向散列函数。不妨把银蛋标为数字“0”,金蛋标为“1”。在砸蛋之前,你给系统发一个足够长(比方说100位吧)的随机01串A。然后,系统把奖品藏在标号为X的蛋里。下面,系统选择一个随机种子,通过伪随机数列发生器生成100个随机数,并全部模2得到一个100位的随机01串B。然后系统计算01串C,其中

C[i] = B[i] 当A[i]为0
C[i] = B[i] xor X 当A[i]为1

    系统把C传给你,并宣布准备完毕,开始抽奖。事后,系统公开自己选取的随机种子的值,你便能还原序列B,验证序列C是否和系统之前所给的一样。
    如果系统想作弊的话,这要求系统能寻找两个不同的随机种子s1和s2,使得在由它们生成的随机01串(的前100位)中,A中等于“0”的位置上它们的值全部相等,A中等于“1”的位置上它们的值正好相反。但伪随机数列发生器的行为是不可预测,找到这样的s1和s2相当困难,目前看来该协议仍然是安全的。即使找出了这样的碰撞,这样的努力也是一次性的,因为当别的人来抽奖时,随机串A又不一样了,刚才的碰撞就完全没用了。

17 条评论

发表评论

  ×  8  =  64