可信的抽奖机制

我想起小时候常玩的一种游戏，潮州话叫”安仔”，不知怎用文字称呼。它很像一张邮票，一面有图案，一面空白。游戏规则是：两个人，每人拿一张，放在掌心，然后相互击掌，放开，使”安仔”自由落地，正面向上的一方赢。如果同为正面向上或正面向下，则算打平。有些小朋友爱作弊，把两张一模一样的”安仔”背靠背贴在一起，这样无论怎样它都是正面的。于是，有时一方赢得太多，输的一方总会检查”安仔”，以确定对方未作弊。

这是现实生活中很典型的验证真伪的方法。抓阄、抽牌等赌博方式都是可以去验证真伪的。比方说抓阄二选一，一个有字一个无字，如果一方抽到无字的，那他会看看另一张是否有字，以验证其参与了一场公平的赌博。

事情从现实到了计算机世界就大为不同。假设前面说到得”安仔”的双面是高科技的显示屏，作弊的人只要写个程序，让”安仔”在落地的瞬间，在其向上的一面显示出图案，背面不显示图案，那么这个”安仔”将是常胜将军。

计算机世界要实现这样的作弊就太简单了。看看这个例子，某公司举办一抽奖活动，每购买一件该公司商品可获得抽奖机会一次。奖金丰厚，中奖概率50%，由于抽奖人数过多，该公司决定用计算机抽奖。于是他们写了个程序：计算机随机地将0和1这两个值赋给变量a、b，也就是说a是0或1的概率相等，然后，由抽奖者选择a或b哪个的值是1，猜对者获奖。按照上面提到的验证真伪的方法，如果某人选到的变量是0，那么他会要求公开另一个变量，看看是否是1. 现实中可以的验证方法到了计算机就未必使人信服，作弊太简单了。

用伪代码写的作弊程序:

   If (rand() > 0.5) a=0,b=1; //rand()产生一个[0,1 )之间的数
   Else a=1,b=0;

   Print "请猜猜哪个是1，a或b"
 
   Cin >> char; //用户输入a或b

   if (用户输入的变量的值为1) a 、b交换值; //作弊了
   
   Print 你中的变量的值是0 //无论用户选哪个，都是0

由于计算机的运行速度极快且其内部运算不可见，所以这个程序可以让抽奖者无论如何抽不中，就算他抽后检查另一个变量的值也没用。当然该公司为了掩人耳目，可以将中奖概率修改为30%并捏造出20%虚假的中奖者，这样更难被发现。

事情似乎无法继续，难道计算机世界和真实世界存在着质的区别吗？它们验证证伪的特性如此不同。在继续之前，须介绍些密码学知识。

HASH函数：指将任意长度的字符串映射到另一段字符串的函数。实际应用中，另一段字符串一般为数字或是固定长度的字符串。密码学中，典型的HASH函数有MD5、SHA1等，它们有如下特点，假设f是HASH函数，x属于定义域，y是值域：

• 已知y，反求x是极其困难的。
• 找到两个不同的x1、x2，使得f(x1)=f(x2)是极其困难的。(碰撞困难)
• 已知x，求y=f(x)速度很快。

满足这样性质的HASH函数最适合用于密码学，所谓的极其困难一般指除了暴力破解外别无他法，暴力破解耗费的时间上万年。

MD5的碰撞性质已经被破解，不过它的第一个性质还没被破解，即已知y，反求x。为了安全起见，可以使用SHA1，甚至SHA-512，这些HASH函数目前要多少有多少。

利用这样的HASH函数，可以解决上面的验证真伪问题。机制是这样的：

   1) 程序产生随机地一串足够长的字符串STRING1

   2) 用户输入随机地一串足够长的字符串STRING2

   3) 计算机计算HASH(STRING1+a的值+STRING2)，发送给用户

   4) 计算机计算HASH(STRING1+b的值+STRING2)，发送给用户

   5) 用户选择这两个HASH值的一个，也即选择a或b

   6) 计算机公开a、b的值，用户知道是否中奖

   7) 用户可验算a、b值是否被篡改

利用密码学HASH函数的特征，可以推断上述机制是对双方是安全的：

1)用户得到这两串HASH值之后，不可能从此HASH值反求出原来的值，也即用户不可能反求出a、b的值。因为STRING1足够长，暴力破解出STRING1在短时间内不可能。这保证”奖券”在”刮开”之前是安全的。

2)由于STRING2是用户随机输入的，计算机就无法实时计算好作弊数据。具体用图表示，左边是正常过程，右边是作弊需要的手段：

Str1是计算机生成的，用户在步骤5)完成之前，不可能知道。当计算机把C1、C2这两个HASH值告诉用户之后，如果它要作弊，就必须找到新的Str1’，并且满足上图右边的情况。这在短时间内是不可能的，根据HASH函数特点，HASH碰撞是极其困难的，即使是已被破解的MD5，在上面机制下也无能为力，就算计算机找到Str1’，使得HASH (Str1’+b的值+Str2) = C1，那么要让这个Str’同时满足HASH (Str1’+a的值+Str2) = C2那真的是不可能的巧合。

用户验证真伪：问题回到现实中来，现在用户验证真伪很简单。计算机公开Str1及a、b的值，用户计算HASH (Str1+a的值+Str2)和HASH (Str1+b的值+Str2)是否等于C1和C2即可。

下面这个是可信抽奖程序的伪代码：

   If (rand()<0.5) a=0,b=1; //rand()产生一个[0,1 )之间的数
   Else a=1,b=0;

   Str1 = 随机生成的一串足够长字符串

   Print "请用户输入一串随机足够长的字符串"
   Cin >> Str2; 用户输入足够长的字符串Str2

   C1 = HASH(Str1+a+Str2);
   C2= HASH(Str1+b+Str2);

   Print "a的HASH值："+C1 +"b的HASH值："+C2

   Print "请选择一个："

   If(用户选择的变量是1) Print "中奖了"; Else "没中奖";

   Print "计算机生成的Str1是"+Str1+",请验证。"

按照上面的分析，如果计算机在用户输入a或b之后变换a、b的值，那么最后的验证将出错，作弊行为将被发现。现实中的问题在数学的辅助下得到更好的解决，我想大家现在更相信这种抽奖方式，因为现实中可能还存在魔术师，而要破解这个验证真伪的方法，比变魔术还难。