概率論：數(shù)學(xué)讓密碼學(xué)加速進(jìn)化 你想過一個(gè)問題沒有： 是什么因素決定了一個(gè)密碼能否被破譯呢？ 對(duì)比一下古典密碼和現(xiàn)代密碼，你就能發(fā)現(xiàn)答案了。 古典密碼學(xué)，加密和解密過程中，最小操作單位都是單個(gè)字符或者符號(hào)，所以古典密碼學(xué)的核心就是移位法和替代法。 現(xiàn)代密碼學(xué)，把研究對(duì)象用數(shù)來描述，再對(duì)數(shù)進(jìn)行運(yùn)算。不但突破了字母作為最小變化單位的限制，還可以使用更高等的數(shù)學(xué)工具做運(yùn)算，因此破譯就變得越來越難。 所以，加密時(shí)所用的數(shù)學(xué)工具，決定了一個(gè)密碼能否被破譯。 第二代的移位法和替換法的安全性很好，也比較好用，但到了16世紀(jì)，這個(gè)局面扭轉(zhuǎn)了。因?yàn)楦怕收摰某霈F(xiàn)，這兩種加密法可以破解了。 自此之后，加密與解密的對(duì)抗戰(zhàn)中，因?yàn)閿?shù)學(xué)的應(yīng)用，解密一方暫時(shí)占據(jù)優(yōu)勢。 兩個(gè)破解 第二代加密法 最經(jīng)典的案例。 一個(gè)發(fā)生在16世紀(jì)的蘇格蘭女王瑪麗一世身上，一個(gè)發(fā)生在17世紀(jì)中后期到18世紀(jì)初的法國國王路易十四身上。 瑪麗一世女王，她是我聽說過的最剛烈的女人。在這門課《密碼學(xué)人物列傳》的模塊中，我會(huì)專門用一講詳細(xì)講講她的故事。這節(jié)課，我們還是主要圍繞密碼展開。 27歲時(shí)，瑪麗一世被自己的姑姑英格蘭女王伊麗莎白一世關(guān)押了起來，一關(guān)18年。到44歲時(shí)，監(jiān)獄里的她和外界反叛軍密謀要?dú)⒑霉茫坏┲\殺成功，她自己就能坐上王位。當(dāng)時(shí)的信件都是通過特殊渠道傳入監(jiān)獄，最后由侍女在遞送紅酒時(shí)，藏在瓶塞中帶進(jìn)去。 瑪麗一世很聰明，包含暗殺計(jì)劃的并不是普通的信，而是加密過的。就算不慎落入伊麗莎白一世的手中，也沒人看得懂。 其中用到的加密方法，就是替代法。所有的英文字母被類似符文的東西替換，一些常用詞也用符號(hào)代替。具體的對(duì)應(yīng)方式，你可以參考下面這個(gè)圖表。 瑪麗此后就通過這個(gè)特殊渠道和反叛軍通信，幾個(gè)月后，她熟練掌握，寫信可以直接用密文，不用一個(gè)個(gè)字母查對(duì)照表了。 不幸的是，這個(gè)特殊消息傳遞的渠道里，竟然隱藏著一個(gè)雙面間諜，他把情況匯報(bào)給了伊麗莎白。在位的女王正愁抓不到把柄，這下終于有機(jī)會(huì)名正言順的處死瑪麗了。 不過現(xiàn)在還急不得，必須抓到足夠硬的證據(jù)，而且最好把整個(gè)陰謀背后所有的參與者一起除掉，所以伊麗莎白沒有打草驚蛇。 此后瑪麗和外界的通信，每一封都先經(jīng)過雙面間諜送到密碼學(xué)校，花1個(gè)小時(shí)謄寫好，然后再密封好，就像從沒有被截獲過那樣，遞出皇宮。密碼學(xué)校的人再拿著謄寫好的密文想法破解，最終他們成功了。 破解方法，就叫做“ 頻率分析法 ”。這種方法其實(shí)在9世紀(jì)的阿拉伯就出現(xiàn)了，只是到了16世紀(jì)才被歐洲數(shù)學(xué)家注意到。 下面咱們講講它的原理。很簡單，英文中字母出現(xiàn)的頻率，是不一樣的。比如字母e是出現(xiàn)頻率最高的，占；其次是t，；然后是a，o，i，n等，最少的是z，只占。 英語中字母頻率統(tǒng)計(jì) 除了英語，其他語言也有詳細(xì)統(tǒng)計(jì)。 瑪麗和外界用密文往來很多，字符總量足夠多，全部收集到一起，統(tǒng)計(jì)哪個(gè)符號(hào)出現(xiàn)的比例最高，那個(gè)字符大概就是字母e。 當(dāng)然，有些字母出現(xiàn)的頻率極為接近，比如h，r和s，分別是，和。但只要稍微留意字母前后的關(guān)聯(lián)，就可以區(qū)分出來。比如：t幾乎不可能出現(xiàn)在b，d，g，j，k，m，q這些字母的旁邊，h和e經(jīng)常連在一起，ee一起出現(xiàn)的頻率遠(yuǎn)比aa一起出現(xiàn)高得多等等。 頻率分析法的實(shí)質(zhì)，就是大幅降低字母排列組合的可能性。 從前我們假設(shè)每個(gè)符文都可以是26個(gè)字母的任意一個(gè)，有多少個(gè)替代符號(hào)出現(xiàn)，就有26的多少次方種可能。但頻率分析法把很多符號(hào)的可能性大大降低，有的降低為只有1種可能，有的降低為只有2-3種可能。 這樣一來，即便第一步統(tǒng)計(jì)各種符號(hào)出現(xiàn)的頻率時(shí)并不完全確定，但只要再根據(jù)拼寫規(guī)律篩選一下，替代符號(hào)對(duì)應(yīng)的真實(shí)字母就確定了。 在審訊的過程中，盡管瑪麗始終沒有承認(rèn)謀反，但證人和密碼學(xué)專家一起向公眾展示了密文和原文，講解了解密規(guī)則，最后瑪麗一世還是被砍了頭。 這是加密和解密在皇權(quán)斗爭中最著名的一次應(yīng)用，解密法大勝。 解密方法公布后，替代法就不再有效。起碼對(duì)歐洲王室來說，決心要破解的話，一定可以破。 加密一方當(dāng)然不甘落敗，怎么辦？ 很快就出現(xiàn)了另一種叫做“ 同音替代法 ”的方法。 比如說字母a可以用11，23，41三個(gè)數(shù)字替代，這三個(gè)數(shù)字翻譯過來都是a。越常用的字母，比如e，就用越多的符號(hào)代替它。這種想法的終極目標(biāo)，就是讓每個(gè)數(shù)字出現(xiàn)的頻率都大致相等。頻率特征沒有了，密碼就不容易破解了。 同音替代法 從上面這張同音替代法的表格中可以看到，最常使用的e，替代的字符最多。 不過這種方法的解密法馬上也出現(xiàn)了，就是通過字母前后順序關(guān)系來猜。 最典型的例子是，q后面出現(xiàn)的最大可能是u，而q又是一個(gè)不常用的字母，有很大概率猜出來。其他字母猜出來的難度大一些，但只要肯花時(shí)間，總能破解。 史上最有名的采用同音替代法的密碼，是法國國王路易十三、十四時(shí)期的“大密碼”（Grand Chiffre）。它使用了40多年后，隨著拿破侖倒臺(tái)突然失傳。直到1890年才被完整破解，破解方法就是從單詞拼讀規(guī)律入手的。 這套加密法用了587種數(shù)字，來表示不同的發(fā)音。其中陷阱還很多，比如有些數(shù)字只代表字母，不代表發(fā)音；很多數(shù)字是干擾字符，它們沒有意義；還有一些數(shù)字既不是發(fā)音也不是字符，而是代表刪掉前一個(gè)字符。 大密碼被破解后，很多200年前路易十四的宮廷秘聞才大白于天下。 其中有一段，是法國宮廷傳奇“鐵面人”的新發(fā)現(xiàn)。鐵面人的故事在歐洲，就像咱們關(guān)心康熙晚年雍正是怎么即位的故事那樣。無數(shù)小說都以這個(gè)為背景，大仲馬和伏爾泰都寫過。 故事說的是一個(gè)犯人從1669年被捕后，一直關(guān)押。而且負(fù)責(zé)關(guān)押他的監(jiān)獄長不論工作怎么調(diào)動(dòng)，總把這個(gè)犯人帶上，一關(guān)就是34年。按說這么重的罪，就讓他把牢底坐穿吧。不，給他吃的都是美味，穿的都是華服，還可以彈琴，有醫(yī)生定期探望，甚至轉(zhuǎn)移監(jiān)獄時(shí)都是高級(jí)馬車護(hù)送。什么都有，只是沒自由。 有獄卒看到過這個(gè)人在遠(yuǎn)離其他犯人的地方散步，臉上總帶著一個(gè)鐵面具，沒人知道他長什么樣。 鐵面人到底是誰，有N種猜測，在大密碼告破之前，有猜是路易十四同父異母哥哥的，有猜是路易十四親生父親的，有猜是英國國王私生子、法國財(cái)務(wù)大臣、意大利外交官的。之所以有爭議，是因?yàn)槊總€(gè)說法都有漏洞。 在大密碼告破后，又多了一種解釋，那就是當(dāng)時(shí)路易十四手下的德布隆德將軍（Vivien de Bulonde）。解密后，有一封信是戰(zhàn)爭部長寫給路易十四的，提到立即抓捕德布隆德將軍，晚上關(guān)進(jìn)牢房看管，白天可以允許他帶著面具在城垛上活動(dòng)。 這個(gè)說法雖然后來也發(fā)現(xiàn)了漏洞，但因大密碼破解而公布的文件和信件，讓法國宮廷內(nèi)部的歷史變得更有據(jù)可查。 你想過為什么替代法會(huì)被破解嗎？是宮廷天才對(duì)猜字游戲很擅長，還是雙面間諜的勇敢機(jī)智？ 這些因素當(dāng)然都有。但最重要的觀察視角是——那個(gè)年代的數(shù)學(xué)突飛猛進(jìn)，終于誕生了“ 概率 ”這種新概念。 今天的人聽到“某個(gè)字母在一篇文章里出現(xiàn)的概率”這樣的表述，當(dāng)然不會(huì)覺得難以理解。但400多年前的人雖然也知道，硬幣扔出去，女王頭像一面朝上的機(jī)率是一半，這樣粗淺的概率知識(shí)。但他們大都不會(huì)用這個(gè)視角衡量感興趣的對(duì)象。 其實(shí)直到現(xiàn)在，大多數(shù)人也沒什么機(jī)會(huì)用這個(gè)視角去思考，唯一涉及切身利益的就是買彩票。 而當(dāng)年概率論之所以誕生，正因?yàn)榈谝粋€(gè)研究概率論的那個(gè)數(shù)學(xué)家卡爾達(dá)諾（Girolamo Cardano）是個(gè)賭徒，他還是三次方程一般解法的發(fā)現(xiàn)者，也是最早使用復(fù)數(shù)概念的人。世界上第一本概率著作《論賭徒的游戲》，就是他寫的。正是這本書寫完5年后，瑪麗女王被姑姑囚禁了起來。 數(shù)學(xué)的發(fā)展，有兩個(gè)高峰。一次是公元前500年到公元前300年，那之后一直在下滑，大約在公元500年跌到谷底。另一次高峰是在這1000年之后，大約在瑪麗女王時(shí)代，才超越古希臘巔峰時(shí)期的水平，而且這個(gè)高峰現(xiàn)在還沒出現(xiàn)最高值。 隨著數(shù)學(xué)水平的提高，不只是密碼學(xué)，所有使用到數(shù)學(xué)的應(yīng)用學(xué)科也會(huì)跟著變。很多在1500年之前只是旁門左道的事情，逐漸成為獨(dú)立的行業(yè)，或者單獨(dú)的學(xué)科分支。 創(chuàng)文鏈接： ? 執(zhí)劍與破壁的永恒之光 ? 密碼為什么要從俚語加密開始Why do passwords start with slang encryption