去年5月5日，芝加哥附近的一个全球知名的物理实验室——Fermi国立加速器实验室——收到了一封神秘的来信。收信人只是简单的一个Fermilab，信件上没有留下寄信人地址。信纸上是一些短竖线、数字和怪异的符号。实验室里的所有人都不知道这封信是怎么回事。这究竟是一个玩笑，还是一个恐吓，或者暗示着一个革命性的物理理论？
    不管他是什么玩意儿，第一个读到信件的人Judy Jackson对它产生了极大的兴趣。为了更快地破解密码，今年五月，Jackson的同事把这封信发到了他们的Blog上。他们得到了全球各地好几百人的回复，其中一些人甚至已经解开了密码的一部分。

    信件内容公布不久，很快就有人注意到，最上面的那部分密码实质上是一个三进制编码，最底下那部分实质上是一个二进制编码。有人甚至把两部分的编码都录入了下来：

323233331112132
33323132212331
2111331132312233
333212123213113
311333313331111
211333323232211
232313331121231
33231312

111212112121212121121212121112121121
1121121121211121211211121211211121111
1111212121121121211121212121112111211
2111212112112111211121112111211121112
111211211121112121121112122211121211
1212112111211121112112111212121112111
211211211121121112112111212112111212
112121211

    破译这样的密码并不容易，前段时间某MM写给我的一段密码我至今仍未破译。你需要从有限的密文中寻找各种形式的特征，从密码本身的规律中寻找提示。人们注意到，在后面的二进制编码中，连续的2仅仅出现了一次。这是为什么？人们更倾向于认为，连续的三个2是不应该出现的，这打破了这段编码的模式；很可能中间那个2仅仅是两个画得比较近的1罢了。后来，这一点得到了证实：人们渐渐意识到，数字2起到一个分隔符的作用。连续的1的个数最多不超过3个，这绝对不是一种巧合；如果把二进制编码中的2看成分隔符的话，下面一部分也是一个三进制编码。这样的话，后一部分的密码可以重新编码为：

312111121113123221312312333112213111332312233333332331231231312333231133223232312312112

查看更多 »

    昨天，一帮密码学家在网上宣称，他们通过一台PS3成功预测出了2008年大选的结果。但为了不干预事件的进程，他们将放出描述大选结果的文档的md5值。大选结束后，密码学家们会放出该文档，证实他们之前确实成功预测到了这个结果。这份电子文档的md5值为：

3D515DEAD7AA16560ABA3E9DF05CBC80

    你能猜出这背后有什么阴谋诡计吗？




    在字谜界有一个非常有趣的故事。美国大选结果出炉的前一天，某报纸上刊登了一则纵横字谜，正中间的那个最长的单词的提示是：美国新一任总统的名字。字谜爱好者纷纷给报社打电话，说大选结果还没出来，我他妈的咋知道新总统是谁，这背后到底隐藏了什么秘密。第二天，报纸上刊登了字谜的答案，中间那个单词果然就是新总统的名字。这家报社“预测”出了大选的结果。你可能已经想到了，这是一个设计得非常巧妙的字谜。这则纵横字谜有两个答案，每个答案都完全符合所有的提示，只是中间的那个人名字不同。纵横字谜中任一个字母的改变都会引起连锁反应导致很大一片字母的改变，因此要想设计出这样一个字谜是非常困难的。但是，就有这么牛的人设计出来了。
    你相信吗？就有那么牛的人，他居然可以构造出两篇文档，hash出来的md5是完全一样的！比起纵横字谜来，这似乎变得更不可思议，因为一篇文档中任何一处微小的改变都会使原来的md5值面目全非。但是，就有这样一种算法，它可以在短时间内构造出md5发生“碰撞”的情况。这就是前几年炒得沸沸扬扬的“山东大学王小云教授成功破解md5”一事。
    当时的新闻很不负责任，没有几个是说清楚了的。和大多数人想的不同，md5被破解并不是真的md5被破解了，你无法把md5还原为原来的信息（因为md5是多对一、不可逆的），也几乎不可能构造一个字符串具有指定的md5值。但是，王小云教授发现，作为一种验证码，md5已经不再可靠了，因为利用他的发现可以很轻易地构造出md5发生冲突的情况。考虑这样一种情况，你需要在未来的某个时间公开一份秘密文档，但到时候你必须证明这份文档确实就是之前说要公开的那一份。比如，你参加CCTV的垃圾娱乐节目，主持人叫你猜一个充气娃娃的价格，你猜是1000元，然后被干冰吓跑，主持人阴笑着宣布这个充气娃娃的真实价格是998。但制作单位如何证明这个价格确实就是998呢？即使是把真实价格藏在一块遮板后面，也有作假的可能。一种不错的方式就是，预先算出998的md5值，由于md5值是不可逆转的，因此即使公开md5别人也拿它没办法；但这个md5可以起一个验证作用，我在报出998的同时你可以验证998的md5值和刚才给的是不是一样，这样才能确保制作单位没有作假。这就需要md5算法具有很低的碰撞概率。现在看来，这种验证方法也不能相信了，因为人为构造md5冲突的两个原始信息变得越来越容易，你猜价格是A我就说是B，你说是B我就说是A，而A和B的md5是一样的。这样的话，我可以做很多坏事，比如说些什么我能预测股票的走向，我五年前就知道我会和你在一起之类的屁话。从这个意义上说，md5不再安全，它已经被破解了。

消息来源：http://blog.wired.com/27bstroke6/2007/11/cryptographers.html
查看更多：http://www.win.tue.nl/hashclash/Nostradamus/
做人要厚道，转贴请注明出处

    69年7月31日，三家报社各自收到了连环杀手Zodiac写的一封密文的三分之一。Zodiac要求这三家报社把密文发表在报纸上，否则他将在这周末再次杀人。Vallejo Times-Herald得到的是整个密文的头三分之一(图1)，另外两家报社则是San Francisco Chronicle和San Francisco Examiner。这个密文共有408个符号，以后大家都习惯称它为408-密文(408-cipher)。408-密文是Zodiac的第一封密信，是Zodiac事件中极其重要的一环，David Fincher的电影Zodiac就完整地记述了这一事件。
    一个星期后，一位教师和他的妻子破解了这篇密文。他们发现，这篇密文用的是最简单的字母替换法，所不同的是一个字母可能对应多个符号。通常这种一对多的替换加密叫做同音替换法(Homophonic Substitution Cipher)。同音替换密码可以很好地防止字频破解法，因为你可以让常用的字母对应更多的符号，保证每个符号出现的次数大致相等。破解同音密码的常见方法是利用“字母Q后面一定是U”这一类的英文特性，因此你可以特别注意一个符号后面总是跟着那几个符号的情况（Q是不常用的字母，一般只对应一个符号）。但这篇密文太短，可以获取的信息有限，因此可能的破解方法只有一个：不断尝试，不断猜测，不断改进。不管怎样，那位教师和他的妻子解开了Zodiac的密码：

I LIKE KILLING PEOPLE BECAUSE IT IS SO MUCH FUN

IT IS MORE FUN THAN KILLING WILD GAME IN THE FORREST BECAUSE MAN IS THE MOST DANGEROUE ANIMAL OF ALL TO KILL SOMETHING GIVES ME THE MOST THRILLING EXPERENCE

IT IS EVEN BETTER THAN GETTING YOUR ROCKS OFF WITH A GIRL

THE BEST PART IS THAE WHEN I DIE I WILL BE REBORN IN PARADICE AND ALL THE I HAVE KILLED WILL BECOME MY SLAVES

I WILL NOT GIVE YOU MY NAME BECAUSE YOU WILL TRY TO SLOI DOWN or STOP MY COLLECTING OF SLAVES FOR MY AFTERLIFE EBEORIETEMETHHPITI

    最后这个EBEORIETEMETHHPITI是什么意思现在还没搞清楚。

    11月8日，Zodiac又寄出了一篇密文。这篇密文有340个字符，被称作340-密文。与408-密文不同的是，虽然大家都相信340-密文同样使用的是同音替换加密，但直到现在340-密文也没有解开。
    时至今日，David Fincher电影Zodiac又掀起了一次破解未解之谜的热潮，很多人都开始尝试破解340-密文并在网络上分享他们的新发现。最近，网络上出现了一个专门用于破解340-密文的网页。这个网页假设340-密文和408-密文一样也是用的同音替换法，你可以方便地对符号进行替换，同时程序可以告诉你替换后可以得到哪些单词。你也可以随机建立替换表，或者查看一些有趣的替换结果。目前最好的替换表可以产生halloween, killing, you, next, die, zodiac等单词。看过很多侦探小说和电影？对密码破译很有兴趣？340-密文是货真价实的“侦探小说式”密码，有兴趣的话不妨试一试。

We all use math everyday: to forecast weather, to tell time, to handle money; we also use math to analyze crime, reveal patterns, predict behavior. Using numbers we can solve the biggest mysteries we know.

    上面这个图片我非常喜欢，是美剧Numb3rs的一个经典画面，展示出一个数学家眼前的世界。上面这段话也非常经典，它告诉我们数学无处不在。这部单元剧讲述一个数学家帮助FBI破案的故事，开篇第一集（下文有些许改动）给我印象最深。

    一个城市里发生了连环杀人事件，FBI探员Don Eppes负责调查此案。Eppes工作非常忙，为了充分利用时间，他把案件的资料带回了家。他的天才弟弟Charlie看到了其中一份案件资料——一张标有13个受害人被害地点的地图。Charlie是一个应用数学家，他告诉他哥，我可以帮助你。Don回答，虽然你曾帮助我破过几次经济案件，但这次的案件与数字无关，你帮不上忙。Charlie说你错了，数学无处不在，Everything is numbers。他把他哥带到屋外灌溉草坪用的喷水器旁边说，我们知道喷水器的位置，并且测量出水压、气压、风力等一切参数，那么我们完全可以计算出每个水滴精确的落点；反过来，如果我们已经知道每个水滴落地的时间和位置，我们可以用数学方法推算出喷水器的位置，并预测下一个水滴将出现在什么地方。同样地，连环杀手犯案的时间和地点也受到地形、街道、人口、警力部署和他自身心理等等的影响。这些参数可以从FBI的资料中得到，比如我们可以从被害者的伤口形状和深浅看出凶手当时的心理状态。建立适当的数学模型，我可以推算出他的居住地和下一次凶案发生的地点。

    应用数学家Charlie就这样开始了案件分析。Charlie从以往的资料中找到了一般连环杀手选择凶案地点的模式：凶案现场不会离他家太近以免遭到警方嫌疑，同时凶手也不会走得太远；凶手会潜意识地避免在大致相同的地点犯案，以免产生固定的模式。根据这些假设，Charlie推算出了凶手所住的地方。故事总是一波三折，FBI的调查表明Charlie算出的地点是错误的。这个模型哪里有问题？

    几天的思考后，Charlie带着他的新发现来到FBI办公室。他说，我的模型是正确的，但数据错了。假设凶手确实住在那里，我构造的一个新算法可以返回去算出某时某地发生凶案的概率。对于已经发生的这十几起凶杀案，算法得到的概率几乎都大于70%；而其中一个案件却不符合这个模式，被害者在那里遇害只有2%的可能。看来你们需要重新调查这个案件，目击者很可能隐瞒了什么。
    FBI再次拜访目击证人，证实了Charlie的猜想。目击者确实撒了慌，因为她不想让她的未婚夫知道她去哪里了。她说出了案件发生的真实地点，这个地点完全符合凶手的模式。这是Charlie的数学模型第一次发挥了作用。重新应用Charlie的模型，FBI得到了一个新的“可疑区域”，这个区域里的人数比较多，需要一个一个调查。

    但很快，区域中的所有人都排除了嫌疑，FBI决定在更大的范围内搜寻目标。这预示着Charlie的模型还有问题。是哪里有问题？算法错了？计算错了？直到他走进了他的办公室才恍然大悟，骂自己笨得居然没有想到这个：普通人的活动范围并不只是以居住地为中心，大多数人都过着两点一线的生活。凶手很可能在工作和家之间来往。模型和算法都没错，只是最初的假设错了——喷水器不是一个，而是两个。被害者遇害地点的模式并不只是由一个中心点决定的，而是由一个“工业区—居住区”的哑铃形区域确定。

    新的结果很快打印了出来。根据新的可疑区域，FBI找到了凶手的住处和新的作案地点，并及时救出受害者，证实了Charlie的这一想法。Charlie再一次感叹，Everything is numbers。 Numbers, numbers, numbers... 屏幕上的画面随着似有似无的回声淡出。


Matrix67原创
转贴请注明出处

    2007.03.11注：考虑到现在这个Blog的阅读者逐渐改变，有必要说明一下。这篇日志是早以前（还在MSN Space时代的时候）写的，涉及到诸多内部笑话，广大网友没法看懂。本来我想把它删除了或者隐藏了，但考虑到网志的完整性，仍然保留了下来。
    我参加省选前，Zroge曾经来给我们讲过课。他讲完SPFA后，我们老师（Zlaner，女，即照片中的人）叫一个同学去编程实现这个算法，她把SPFA读作es pee far，我们笑了一晚上。有一天我们老师上厕所出来时发现大门锁了，丢死人了，给我打了个电话叫我帮她。我拿我的Nokia 6020咔嚓咔嚓照了几张像后说要把这个发到Space上。回家后突发奇想，编了这个故事。

    一次星期天晚上下了晚自习，我走在回家的路上，才考了语文，没考好，心里很郁闷。路过小龙坎车站那里，突然从天上掉下来一个女的，不大，十六七岁的样子，穿得很少，看起很乖。如此美丽的她就这样突然出现在我面前。当时已经很晚了，看看周围没有人，我就偷偷地把她带回了家。
    跟她住一起住久了，我发现她有一些奇怪。后来，她告诉我，她是从别的星球来的。因为我们星球质量比他们那里大，她不习惯这里的重力，因此来的时候才从天上摔下来。我问她叫什么名字。她说她虽然有名字，但在那个星球上，他们的名字都很长。就这样，我算认识了一个外星人MM。
    再后来我停课了。我有更多的时间陪她在一起玩。我经常带她去三峡广场，逛商店，吃东西，看电影。
    今天早上起来时，她告诉我，她想看一看地球上的生物。她说，她听说地球上有各种各样的动物。想到这几天我都到学校去做Zlan的题，很久没出去玩了，我就答应带她去一趟动物园。我给Zlan发了个短信，说我今天有点事，上午暂时不来了。
    然后我把她带到杨家坪的那个动物园去玩，就是小学春游常去的那个动物园。她逛了一会儿就不想玩了，说没意思。我看看时间，才十点过，于是问她还想去哪儿。她想了一下，突然来了兴趣，告诉我说她不是一个人来地球的，其实他们星球一共来了四个人。另外三个从事着更复杂的一些研究。她想带我去看看他们到地球的一些研究成果。我答应了。
    路上，她告诉我了他们来地球的真正目的。他们星球的科技发展到需要相当精度的电容器，其电容值的允许误差范围甚至难以测量出来的。他们称高度精确的一皮法电容叫做一个超级皮法，也就是他们所说的Super皮法，简称S皮法。为了得到一个S皮法，他们花了几个世纪的时间。偶然的一次机遇，他们星球上的人监听到了在一个遥远的蓝色星球上已经有人做出了S皮法。于是，他们星球派出了包括我的外星MM在内的四个人试图带回这一项技术。
    我学文，不知道什么叫电容，什么叫皮法。依稀记得教我们年级16班的物理老头在我们班上课时说过什么“皮法”、“微法”。
    我问MM，难道你们已经找到了掌握这项技术的人了吗？
    她说，当然，是一个重庆八中的教师。
    我一惊——难道物理老头在我们班平静地叙述着“皮法”、“微法”时背后竟然藏着一个令外星文明如此感兴趣的科研成果？不愧是八中教师啊。
    MM告诉我，这是他们难得的机遇。他们把这个人锁在了一个玻璃门内，千万不能让这人给跑了。
    我看看表，十一点。我赶紧催促，快，带我去看看。
    她拉着我的手走进八中校园，经过草场边和林阴道，径直走向逸夫楼。
    当走到逸夫楼三楼楼梯拐口时，我突然觉得什么地方不对。我问MM，你们星球的人是怎么知道那个人掌握了S皮法技术的？
    她说，他们监听到在一个满是计算机的房间里，这个人竟然随口指使另一个人说，“NK，嘛哈儿去按照Zroge说的把S皮法做出来”。
    正说着，我们来到了逸夫楼四楼。
    于是，我看到了如下的画面。

  

    

幸兄说的果然没错，“6020成像不好”，不愧是行家啊。
今天看了一下大家的MSN Cartoon头像，还是幸兄的那个最像。

    刚看完。看到过的最好看的一集House了。
    先告诉不知道House的，这是一个我喜欢的美剧，讲一个名字叫House的医生和他的团队专门负责送来的疑难杂症，那种最奇怪的病历。House这人很幽默；情节结尾往往很有戏剧性。
    通常这种系列剧的最后一集总会发生一件大事。这一集开头时，House团队正在讨论一个很怪的病例，突然冲进来一个人给了House两枪。片头曲过后， House从病床上醒过来，显然已经脱离生命危险了。他继续和他的队伍研究那个病例。House队伍里的那些人很聪明，House打了一些形象的比喻，那些人立刻就明白了他的意思，进行相应的检查。House自己也知道，头几次设想就猜对的可能性极小。在他的人向他汇报结果之前House就猜到每次测试结果都显阴性。不久，所有设想都被否定。这个病人的病前所未有的不可思议，没有任何理论支持他的症状。House觉得他们肯定漏掉了什么，他一定是默认了某个很基础的东西。他叫他的人想想一些最基本、最底层的东西，比如，检查一下这个病人究竟是不是个“人”。
    与此同时，House自己的精神状况出了一些问题。他估计，他在中枪后的手术中一定有什么东西被碰到了，导致他现在常常出现幻觉。他甚至有时候忘记了自己“是怎么来到这里的”。
    最后，House完全明白了。他明白了为什么他的团队没有把有精神毛病的他踢出队伍，为什么他的每次比喻都能被正确的理解，为什么他每次提出设想都没有遭到反驳，为什么在他的人还没来汇报时他事先就知道结果，以及为什么他精神恍惚记不起东西。因为他忽略了一个最最基本的东西：这些东西不一定是真的。他默认了一切都是真实的。片头曲过后的一切都是在他意识中的东西，都是他的幻觉，都是他自己想出来的。一个人在梦中当然知道别人想说什么，因为别人要说的话也是他自己想出来的。同时，梦也常常不是完整的、清晰的，而是模糊的、断断续续的。
    他必须做出一些不能被他自己的大脑接受的事情来摆脱幻觉。于是，他跑到病人那里去，当着他的队伍用机械手术刀把病人的腹部剖成两半。
    最后一个镜头——House在一个担架上睁开眼睛，一群人跟着他跑。时间不过是中枪后的几分钟，他还在推往手术室，旁边的人告诉他You'll be OK。之前的他全活在昏迷后的幻想中。

做人要厚道 转帖请注明出处

    这几天看Lost，第一季一共25集，讲一个飞机上的48个人遇空难后困在一个孤岛上，他们为了生存、求救和探索岛上的一些秘密（看到12集还不知道岛上的怪事究竟来源于什么玩意儿）进行的奋斗和人物之间的冲突。
    想讲一个Lost里的一个小故事，关于48人中的一个怀孕的女人在空难前的事。
    几个月前，女人（长得很乖）知道自己怀孕了。男友不能负起这个责任，和女的分了。同时女的也知道即使把孩子生出来也不能抚养他，毕竟这个女的还太小了，担负不起这个重担。于是女人前去请教一个算命的。算命的准确地算出她关于身孕和男友离开的事，并坚决告诉她这个孩子必须由她亲自抚养，还把女人给他的算命的钱还给了她。女人知道自己还没有能力带大一个孩子，于是她决定孩子出生后把他给一对夫妇。算命的人连续几个月给她打电话警告她，并告诉她他有一个更好的办法。她没听。最后，当她被要求在文件上签字证明她自愿把孩子给那对夫妇时她放弃了她的决定，奔向算命的人的家里，问那个更好的办法是什么。算命的告诉她，他找到了洛杉矶的一对夫妇，她的孩子可以安全地寄养在那里。算命的给了她到洛杉矶的机票，告诉她只能做这班飞机，洛杉矶的那对夫妇会准时到机场接她。她上了飞机，结果这班飞机遇到空难（就是剧里的这次空难），她和另外47个人活了下来。她的孩子必须由她抚养了。她明白了洛杉矶机场根本就没有等她的夫妇，因为算命的已经事先预知了这次空难；他为了让她能把这孩子带大，骗她上了这班飞机。

做人要厚道，转帖请注明出处