Everything Bright and Beautiful

罪恶的校内时不时会滋生些 恶心的人物，前几天让我深深见识到人心的险恶，虽然在网络上混迹了数十载，这回算是第一次感受到网络的可怕，今早在进行五谷循环过程的时候突然想起了上次 与Sunny，LW逛校园时谈到的密码问题，这回着重谈谈Zero Knowledge Protocol的知识~

当然，一切还是要从头讲起（因为是科普嘛），破密在我心中分High Class与Low Class的方法，Low Class自然就是很鬼低级的那种破密，我赋予其一个名称叫暴力流~

比 如小时候，如果爸爸在电脑上设置了密码，可能小朋友们都用过这招，就是在键盘上撒上一层小灰，然后屁颠去老爸跟前说，“爸，您一日幸苦了，帮我打开电脑让 我用乌龟画图帮您画副画吧”~然后当老爸无知无畏地帮你输入了密码后，你开始琢磨那几个被抹掉灰尘的键能产生的排列组合，最后破解掉密码~显然，无比的暴 力，非我辈所为~

又或者，在闹市区租个小阁楼，正对着银行的柜员机，每天猥琐地架个小DV瞄着ATM的密码区，然后再更加猥琐地跑去捡别人办完手续后丢下来的操作凭条，最后利用所谓的高科技去仿造一张银行卡把人家的小钱放到自己口袋里~看，都是体力运动，依旧非常地暴力~

但我们不应该鄙视他们，怎么可以拿衡量自己的标准衡量他人呢？谢谢~

我们把密码界刨开看，应该分为encipher和decipher的，很明显，出于我本人强烈的正义感，我应该站在encipher的角度探讨接下来的问题，嗯，没错~

由于我也没研究过这个，所以只能从我所经历过的素材探讨（大部分内容出自电影，小说，传记，还有非常重要的YY）

不 知道大家有没有看过十二宫杀手（没看的话千万别看，boring），里面讲到了一段有关密码破译的过程，这是属于比较简单的字母类型的转换，不太涉及到数 学（因为英文字母很肤浅地只有26个，没什么必要弄个函数出来），故事里讲到十二宫杀手寄来的一封信，信里面是一些打乱了的字母，而怎么进行破译呢？首先 是通过第一步非常重要的推理，就是这是一封杀手写来的信，很有可能会出现Kill这个词，那么接下来就是找信中有没有出现既是四个字母，而最后两个字母又 是相同的单词，如果有，不妨假设看到的这个单词叫Uass，那么我们就初步猜测s=l，但最重要的是我们还知道了U=K, a=i~依次类推，知道把所有字母的一一对应关系弄出来~这是一种加密的方式，比较简单~

话说这也是古时候战争时期常用的手段，举个例子~

（杜撰）比如三国时期蜀国要发兵打魏国，这时诸葛亮就把关羽叫到帐前，从裤子的夹层翻出一张发黄的手绢，含泪交给关羽，说，二将军，这是这次的军事密码，请您务必妥善保管~关羽打开手绢一看，上面赫然写着：

床前明月光，

疑是地上霜，

举头望明月，

低头挠痔疮。

（这是唐朝的产物...）

好 啦，现在来解释一下这首诗的目的，事实上古时候是有一整套军事命令表的，这份表一般来说是固定的，何谓固定呢？就是说虽然对应的诗歌可能会变化，但是诗歌 的第一个字总是代表同一个意思，比如说“攻”，对应到这首诗呢就是说如果关羽到时候收到了来自诸葛亮的密信，上写“床”，那么关羽就知道要对敌人发动进攻 了！换句话说，如果看到是“前”，那对应的可能是“守”；看到是“明”，可能是“逃”；依次类推~

这也是很简单的密码设置过程，核心的观念就是设置一套一一对应的法则，只有自己人知道，而对于别人，就很难猜到是什么意思，因为可以是“床前明月光”，也可以是“前列腺炎”，一个对应“守”，一个对应“攻”，是来不得错误的~李连杰告诉我们“兵不厌诈，这是战争！”

但 是道高一尺，魔高一丈；有一法，自有一破；二战时也会有类似的加密方式，而且由于通信设备发达很多，所以加密的对应法则可以经常变换，一定程度上增加了破 译的难度~（因为过去一场战争一不小心可能打个几年，那么长期下来截获的密报多了，还是可以猜出来每个字对应什么意思的）~但是破译的也不是喝白粥长大 的，他们会巧妙地自己创造重复字段的机会，举个例子~

比如说，德国小兵Sunny一大清早截获了英国小兵LW给美国将军 Cobe发的一封电报，上面写的东西完全看不懂，这时候以Sunny天然的奸诈，他很坏地模拟了LW的信号，给Cobe发了一封杂乱无章的电报，那么 Cobe由于本性淳朴，很有可能会发一封电报给LW进行确认，这无形中就给Sunny多了一次找关系的机会，而且这次他具备了更有优势的条件，因为他知道 这封信里面很有可能会出现What啊，Why啊之类的词，所以就更容易破解两方的内容~

基本上上面讲的都是同一种方式，比 较简单，但是人们也深深感到这种密码传输的不可靠性，于是就开始引入比较数学的加密方法了，也就是High Class的那一种~大家了解的比较多的一个例子是比如我知道n是一个200 digit 的质数（知道质数是什么吧？靠，不知道别说认识陈曦），然后我还知道m也是一个200 digit的质数，那么我可以得出z=m*n，这时z是一个合数。我事先可以把m和n都告诉我想要进行沟通的那个人，但是在进行信息传输的过程中时始终只 使用z，那么对于一个事先不知道m和n是什么的外人，想通过z把m和n找出来其实是非常困难的，因此他也就无能为力（当然，暴力流依靠枚举加坚强的毅力及 上好的RP还是可能弄出来的，虽然很难）还原这套密码原本的信息~

我们把m和n两个质数对应成一种函数，就成为一种方法 了~这里举个例子，比如说，m代表穿上一条长袜，n代表穿上一条裤子，而Cobe正在用这种方法给LW传一张相片，此时又被Sunny截获了，但他看到的 实际是z图，而缺失了m和n的步骤，而z图是什么呢？或许是Sunny笔挺西装很鬼有型的一张相片，Sunny此时一定以为Cobe在赞他帅，但其实如果 依次用n , m两个函数还原的话，大家知道，其实Cobe正在和LW谈论Sunny茂密的脚毛，看，加密实现了~

上面这 种加密方式网上也多的去了，没必要谈太多~事实上利用数论的知识可以得到远比这个复杂千万倍的应用，有兴趣的朋友可以读读一本叫A course in number theory and cryptography的书，前段时间翻了翻，强~但由于涉及一些算法的东西，这里不好表达，作罢~

我 觉得真正有意义多加探讨的其实是我们日常生活中接触得最多的一种密码，这种密码和之前所说的信息加密是不同的，我们的密码诸如手机pin码，银行密码，论 坛账号密码等等其实是一种用来access的手段，判断的标准是如果和库里面存的账户对应密码相符，就算通过，不然就算密码错误~这种密码我们叫做 password，用来pass的~

而这种password存在很大的危险，因为不管以何种方式进行核对，密码本身总是需要暴露出来（哪怕你在输入密码时拿手遮着），因为你需要“完整展示”（请注意“完整”这个词，因为这是用来区分之后的部分展示概念的关键词）这个密码以证明你知道这个密码~

这里就引出了我们胡侃了这么久之后最核心的本日课题——Zero Knowledge Protocol~

其本质就是如何不把密码展现出来而让进行密码验证的人或机器知道你确实是知道密码的！很玄乎吧？

一 个经典的例子是我们都知道四色问题，就是一个地图，无论什么形状，我们总可以使用四种颜色填充完整个地图而不使任何两块相邻的区域拥有相同的颜色~但是如 果只使用三种颜色，那刚才说的结果就并不可以总是保证，对于特定的地图，那就存在有些人知道如何上色，有些人不知道~而对于知道如何上色的人，我们不妨称 他们作“色郎”（意为知道如何上色的人）~

那么如何简历在Zero Knowledge Protocol的基础上检验这些人究竟知不知道如何上色呢？假设“色郎”和“检验者”面前各有一个屏幕（假设色郎可以在），屏幕上现实的就是那副地图， 这时候色郎在自己的屏幕上把地图用三种色填好色，然后按summit，这时候检验者要怎么检验呢？相比较之前的所谓“完整展示”（也就是检验者拿着色郎提 交的这个“密码”与自己手上有的资料进行对照），此时检验者则需要采用另一种方式了~

检验者现在要做的实际上是分别检验地 图的每一条邻边，看这条邻边所对应的两个区域是否是不同色的，而关键点就在这里了，每当检验者点某条边的的时候，系统会自动ramdon地改变这条边两边 的颜色！比如说假设色郎一开始用的是红色和黄色来标记这两块地图的（色郎使用的所有颜色是红，黄，蓝），当检验者点击邻边时，红色可能会变成蓝色，黄色可 能变成红色，并且只有这两块区域的颜色会现实出来，并且如果检验者再点击一次同样的边，颜色也会再次random,所以不能通过重复检验来缩小范围~那么 一，当检验者验证了所有的边之后发现每次两块区域都不同颜色的话他可以断定色郎是真的很色；二，由于每次颜色都会随机变化，那么检验者虽然检验了每个区 域，但是却无法知道整个original picture究竟是怎样的！！Zero Knowledge Protocol实现！！

Martin Gardner曾经发明过一种叫Eleusis的小游戏，下面给上Wiki的链接，

http://en.wikipedia.org/wiki/Eleusis_(game)，

大概也体现了Zero Knowledge Protocol的思想~

我 当初就深深地觉得Zero Knowledge Protocol提出了一个非常好的思路，那就是建立在一种将原始的密码随机打乱却又可以进行验证的思想~虽然在实现上我也发现存在许多各种各样的问题， 主要是效率上的，因为如果要验证，那么为了不把整体密码表现出来，只能分拆成许多小部分进行分块验证~在刚才说到的A course in number theory and cryptography这本书中就介绍了一种数论中的方法，每次给2个signal随机选一个进行认证，如果验证T次，那么可信概率是 1-（1/2）^T，而至于这个概率要到99%才算高还是99.999才算高则又是很主观的一件事情了，毕竟我们追求的是100%的确定~~

以后我不搞这个，兄弟们加油吧~~~~

陈曦 2009年2月16日 LA Burgerking饭后