我们常常在电视上看到这样的一幕：一位老太太兴冲冲地走上台去，翻过三个商标牌，发现上面尽是5块钱、10块钱的小奖，垂头丧气地回到观众席；然后马脸李咏会跑出来，边翻着另外几个牌子边说，1000块的大奖在这个后面，800块的在这里，之类的。或许有人会纳闷了，为什么主持人要演出“事后揭大奖”这一幕呢？道理很简单，节目组想通过这一个“验证过程”告诉观众，这个环节不是骗人的，大奖真的就在这后面，只是刚才那家伙运气背了没摸到而已。摸奖前宣称有大奖，摸完奖之后还能证实大奖真的存在，这就是带有防欺骗的承诺。
但是，同样的事情在网络上似乎是办不到的。一个典型的例子就是QQ原来弄的那个恶心的砸金蛋砸银蛋。屏幕左边那个是银蛋，屏幕右边那个是金蛋，你鼠标选一个敲下去，看能否砸出QQ宠物来。大量测试表明砸出宠物的概率远远低于50%，让人质疑游戏的真实性。鬼知道它那个程序是不是真的预先指定了一个有宠物的蛋蛋，很可能不管你点了哪个蛋蛋结果都一样，系统按照概率直接显示出抽奖结果来。当然，怀疑游戏的公平性也没办法，要想在网络上实现带防欺骗的承诺是比较困难的，毕竟让你看一段从另一个蛋蛋里跳出一个宠物的Flash动画不能让你相信刚才你是真的“选错”了吧。
我们的问题就是：如何设计一个协议，用以保证一个二选一的网络互动抽奖游戏的真实性？换句话说，假如你选择了金蛋，结果没有中奖，那么系统如何能够令你相信奖品刚才真的在银蛋里？
算法
趣题：理想模型下的排序算法（上）
当我们研究复杂度时，我们往往会将现实机器进行理想化。例如，我们说冒泡排序是O(n^2)的，这其实是不准确的。这个论断假设整数之间的比较运算是O(1)的，而事实上它们是O(log(min(|a|,|b|)))的。多数时候我们都认为这种机器模型的理想化是合理的，毕竟这让问题简化了不少，并且也能反映出算法的本质。但大家有想过吗，这个“大整数随便算”的假设其实是一个超级大漏洞，我们可以利用理想模型中的这一漏洞来作弊，获得时间复杂度更低的算法。上个月，Michael Brand在他的UyHiP里就提出了这样一个问题：假设计算机对任意大整数的赋值、四则运算、取余运算、比较运算、位运算（包括左移右移）的复杂度都是常数级别，你能否设计出一个O(n)的排序算法来？
我非常喜欢这个题目。月初的时候我就提交了一个正确的算法。我们将用左移和加法运算把整数序列编码成一个超大整数，然后利用排序网络进行并行排序。这个算法比较复杂，你可以按照下面的思路一步一步得到这个算法。
1. 如何用位运算来取绝对值？
2. 给出两个正整数a, b，不用比较运算和判断语句如何把小数赋给a，大数赋给b？
提示：和加差除以2等于大数，和减差除以2等于小数3. 如何利用位运算把整数序列编码成一个超大整数？
例如把（二进制数）11, 1011, 1110, 1编码为一个数00011 01011 01110 000014. 如何用位运算给超大整数中的所有数同时取绝对值？
5. 给出两个超大整数a, b，不用比较运算和判断语句如何把对应位置上的小数赋给a的对应位置，大数赋给b的对应位置？ 例如把
a = 000010 000111 000100 001001
b = 000001 001011 000011 011111
变成
a = 000001 000111 000011 001001
b = 000010 001011 000100 0111116. 如何实现奇偶移项排序？
最后，由于奇偶移项排序只有O(n)层，因此整个算法是O(n)的。
但是，这个算法太繁琐了，不具有美观性。虽然这个算法是我自己想出来的，但我仍然很不满意。待我看了这个月Michael Brand发布的答案后，我一拍大腿，哎呀，还有一个如此简单巧妙的算法我没想到！相比之下，我的算法太复杂了，原因就在于我还没有充分挖掘到“大整数的常数级运算”的潜力。这个理想模型的假设太强大了。打开思路，放宽思维，大胆想象，从更大的尺度上来思考，我们可以得到一个简单得出奇的线性排序算法来。
身份验证、中间人攻击和数字签名：浅谈密码学（下）
前面我们看到，签名具有不可伪造性，因此签名者可以很好的证明自己的身份。事实上，由于签名是不可伪造的，因此签名还有一个重要的功用。当一个人对某份文件进行签名后，这份文件便具有了法律效应：你今后无法再否认你签过这份文件，因为别人是不能伪造签名文件的。签名的这种性质叫做“抗抵赖性”。
在实际生活中，签名的抗抵赖性用的最多的场合就是签合同了。为了防止一方今后毁约，双方可以要求对方在合同上签名。此后，合同签署人的行为将受到这个签名文件的限制。一旦签名者想毁约，利益受到侵害的人便可以拿着这份合同大闹法庭，高举这份文件大叫“当初他签过名的”。
当签名用于抗抵赖时，新的问题产生了。签名的法律效应是如此之高，以至于人们往往不敢随意签名。一份合同往往同时规定了双方的权利和义务，并需要双方都在上面签名。第一个在上面签字的人就会觉得很亏：万一我签了字后对方突然翻脸耍赖不签了咋办？即使合同上规定“合同仅在双方均签署之后才有效”，这个问题仍然存在，因为后签名者将具有绝对的主动权，他想什么时候签就什么时候签，而只有他的签名才具有决定意义。因此很多时候，双方都希望能够在对方签名之后自己再签名，从而获得一些安全感。这里我们来探讨一个有趣的问题：有没有什么办法能够让双方同时签约，使得双方签名时都能确保自己的利益安全？
如果我们谈论的是传统意义上的签名，同时签名当然是有可能办到的：双方只需要拿起各自的笔，同时在文件上写下自己的名字即可。当然，事实上肯定不会有人这么做。试想这样一个荒唐的画面：两个西装笔挺的人挤在一起，两只手臂磕磕碰碰地交错在一起，然后双方同时喊“三、二、一”并一起开始写字……比起自己丢掉的脸面，自己先签名所带来的忧虑还算个屁啊。
有没有体面一些的，不那么荒唐的同时签字法呢？这里有一个很有启发性的办法。合同双方面对面地坐在桌子的两端。其中一个人在合同上写下自己姓名的第一个字母，然后传给坐在对面的第二个人；第二个人写下他自己名字的第一个字母，然后又回递给第一个人；第一个人签下自己名字的第二个字母，又交给对方要求对方写下自己的第二个字母……以此类推，直到双方都签署完自己的名字为止。为了让双方能够“同时”签完，名字较长的人偶尔可能需要连续写下两三个字母。
双方都愿意履行这一协议，因为在这个协议下双方是一点一点地签完整个文件的。第一个写字的人不会觉得自己很亏，因为写下一个字母是远不具备法律效应的；如果对方拒绝签他的第一个字母，我可以当即撕毁合同。虽然他们都不知道，究竟要写多少个字母才算签字，但大家都保持自己签下的名字长度与对方基本相当，因此不会担心对方突然放弃协议。就在这种互动的心理过程中，签名的法律效应一点一点地增强，直到最后双方写完自己的名字。
趣题：匿名的消息广播
三个好朋友到一家餐厅吃饭。饭快吃完的时候，一个服务员过来告诉他们说，他们的账单已被匿名支付了。三个人都尊重他人匿名付款的权利，但同时他们也想知道，这个匿名支付者是他们三位中的一个，还是他们三人之外的一个第四者。有没有什么办法能够让他们知道在他们之间是否有人付账，但又保证任何人都推测不出究竟是谁付的账？利用三枚硬币可以轻易做到这一点。你能想到这个办法吗？
身份验证、中间人攻击和数字签名：浅谈密码学（中）
事情还没有结束呢！我们前面假设，大家公开公钥的方式是“发布在一个众人可信的网站上”，这种假设是有原因的。需要临时交换双方公钥的通话协议是不安全的，这里面存在一个戏剧性的漏洞。举个例子，假如A和B认为，任何网站都是不可靠的，他们从未并且今后也不会在网上公布自己的公钥。为了加密通信，A需要亲自告诉B他的公钥，B也需要亲自告诉A自己的公钥。收到公钥后，双方便用对方的公钥加密进行数据传输。因为用这个公钥加密后，只有对方才能解开密码，因此双方都认为这条通信线路是安全的。其实，他俩的麻烦大了。这条线路并不是安全的，第三者可以用一种很搞笑的方式来窃听消息。假设有一个人C知道A和B之间将有一次加密通话。C劫持了A和B之间的通讯线路。现在，A把他的公钥发给B，这个公钥传到一半时被C拦截下来，于是C获得了A的公钥；C再把他自己的公钥发给B，让B把C的公钥错当成A的公钥。同样地，B把他自己的公钥发给A，被C拦截下来。C把自己的公钥发给A，让A以为那是B的公钥。以后，每当A给B发加密消息时，A其实是用C的公钥在加密；C把A的消息解密后，再用B的公钥加密后传给B。类似地，一旦B给A发送消息，C都可以将消息解密，并用A的公钥进行加密后传过去。此时，A和B都以为自己在用对方的公钥加密，并都能用自己的私有钥匙解开对方传来的密文；殊不知，这中间有人仅仅用了一点雕虫小技，无声无息地窃走了所有的信息。C正是利用了公钥加密术“谁都可以加密”的性质，结结实实地玩弄了A和B。这种攻击方法叫做“中间人攻击”。
这让我想起了经典的国际象棋骗术。一个象棋白痴宣称自己是个大牛。为了证实这一点，他将要与两位大师同时对弈。他说，我先下后下都能赢。于是，在与大师A的对弈中他为白方，与大师B对战则执黑。结果呢，两盘比赛下来居然都打成了平手。怎么回事呢？其实那个象棋白痴耍了个小伎俩，他把大师A走的棋记了下来，跑到另一边去下给B看，又把B的应着原封不动地搬到了和A的棋局上。来来回回搞了半天，他自己只起了个传递信息的作用，真正在对弈的是两个大师。