信息攻防戰(zhàn)：破解與加密

antares

所謂密碼，是為了讓人解開而存在的。

這話聽起來或許有點哲學(xué)內(nèi)涵，不過仔細(xì)想想，無論是《福爾摩斯探案》里面的跳舞小人，海盜船長的藏寶日記，還是諜戰(zhàn)故事里雙方爭奪的密信，其實都預(yù)設(shè)了一個收信人或者受眾。這位受眾知道該怎么正確地解開密碼并讀出隱藏的信息，而其他人即使拿到密碼也讀不出來。

在密碼學(xué)里，把需要傳達(dá)的真實消息稱為“明文”，加密之后的消息叫作“密文”。從明文轉(zhuǎn)化成密文的流程稱為“加密算法”，而算法的核心參數(shù)就是“密鑰”。收信人知道密鑰，就可以通過反算加密算法從密文獲得明文，而竊聽者拿不到密鑰，就很難破解密碼。舉個例子，你寫的日記不希望爸爸媽媽看懂，于是就用一個字母代替同學(xué)的名字。那么，“用字母代替名字”就是日記的加密算法，而同學(xué)名字對應(yīng)字母的這張列表就是密鑰了。

因此，破譯密碼的第一步是猜出加密算法是什么。

歷史上的經(jīng)典加密法

總體說來，經(jīng)典密碼可以歸類為移位式密碼和替換式密碼兩類。移位式密碼，保留原文字母，只改變它們的排列方式。替換式密碼，將原文的字母或字母組按規(guī)律變成其他的符號。實際上，這兩類密碼可以交替組合使用，制造出更復(fù)雜的加密方式。

“亂碼”背后的博弈

隨著加密技術(shù)的復(fù)雜化，破解技術(shù)也在進(jìn)步。圍繞著一串意義不明的字符，加密者與破解者多年來一直進(jìn)行著持續(xù)的博弈。

頻率分析

頻率分析是根據(jù)密碼中符號出現(xiàn)的頻率來猜測明文，找到突破口的破解手法。在英語里，字母“e”出現(xiàn)的頻率最高，大約有12%之多，其次是“a”和“t”，分別在8%左右。因此，如果密文足夠長，那么出現(xiàn)頻率最高的字母很可能代表e。有時還可以根據(jù)雙字母或多字母組合的出現(xiàn)頻率來判斷。

在愛倫坡的小說《金甲蟲》里就有一段根據(jù)這種方法解碼的例子。小說里有一段指示海盜寶藏的密碼：

LINK

愷撒密碼&共濟(jì)會密碼

早在古羅馬時代，皇帝愷撒就發(fā)明了一種愷撒密碼。這種密碼會按照字母表把明文的字母往前或往后移若干位。如果往前移3位的話，D會變成A，E會變成B，以此類推。這樣，“Et tu，Bruno？”就會被加密成“Hw wx，Euxar？”。聰明的同學(xué)立刻可以想到，這種愷撒密碼非常容易破解。因為英語可能的字母共有26個，所以密鑰也就是移動的位數(shù)最多只有25種，即使把所有的可能性都試一遍也不會花太多時間。

更聰明的同學(xué)則會想到，我們其實可以讓密碼破解變得更難一點——如果不是單純的移位替換，而是把26個字母隨機(jī)對應(yīng)到一個新的字母上不就行了嗎？這就是最基本的簡易替換式密碼。很多古老的密碼都沒有逃出這一體系，例如，其濟(jì)會密碼會把26個字母按照規(guī)律改成26個符號。對密碼分析而言，使用符號還是使用字母并沒有本質(zhì)區(qū)別。但對于破解者來說，當(dāng)把符號納入加密替換范疇，這種簡易替換式密碼就不好使用暴力破解了，因為可能出現(xiàn)的密鑰有26！（26的階乘數(shù)，計算得26×25×…×2×1=4.033×1026）個之多。

偵探根據(jù)其中出現(xiàn)頻率最多的符號是“8”，以及“;48”的組合出現(xiàn)了高達(dá)5次為突破口，認(rèn)為“8”代表字母“e”，而“;48”是單詞“the”。幸運的是，這個猜測是對的，因此他就可以繼續(xù)根據(jù)英語語法猜測破解出其他的字母了。

互動問答

感興趣的同學(xué)，可以根據(jù)上面的密碼與提示，試著自己解讀出這段密文所對應(yīng)的正確明文。

明文為：“A good glass in the bishops hostel in the devils seat twenty-one degrees and thirteen minutes northeast and by north main branch seventh limb east side shoot from the left eye of the deaths head a beeline from the tree through the shot fifty feet out.”

為了防止密碼被破解，密碼學(xué)家們想出了許多強化密碼的方法，來增大破解難度。

多表替換加密

使用多組替換表，然后根據(jù)位置或前一個字母對每個字母使用不同的替換方式。例如，維熱納爾密碼可以視為根據(jù)字母位置采用不同密鑰加密的愷撒密碼。這種密碼采用了一張26×26的表格，代表了每個字母在不同密鑰行下的加密方式。它的密鑰是一個單詞，例如KEY。那么明文的第一個字母會用K行密鑰加密，第二個字母會用E行密鑰加密，第三個使用Y行密鑰加密，第四個又回到了K行，以此類推。

要破解多表替換加密也是有可能的。如果我們知道密鑰的周期是3（例如前文的KEY），那么就可以通過對密碼的第1、4、7、…、（3n+1）位的字母進(jìn)行頻率分析，以確定密鑰的第一位。以此類推，最終確定出整個密鑰。而有時相同的明文片段會被相同的密鑰加密，產(chǎn)生相同的密文片段。這使判斷密鑰的周期變得可能。

盡管存在破解可能性，但破解這種加密法的難度比簡易替換式密碼高，其難度隨著密鑰長度變長而提高。多表替換法的極致是多表非周期加密，這個加密方式使用隨機(jī)生成的一次性密碼本作為密鑰。它要求收發(fā)雙方都擁有相同的密碼本，且密碼本的長度要多于明文長度。在這種情況下，只要敵人拿不到密鑰，密碼在數(shù)學(xué)層面便無法被破解。

多字母加密法

這種加密法把兩個或多個字母作為一組進(jìn)行替換加密。例如，波雷費密碼把兩個字母作為一組，密鑰是一個5×5的字母表。然后根據(jù)兩個字母在表中的位置決定對應(yīng)的雙字母密文。由于加密單元從26個增加到了26²=676個，頻率分析也會變得困難許多。也存在使用更多字母組合的加密法，多字母組合加密和解密的復(fù)雜度過高，導(dǎo)致這些加密體系并不實用。

移位式密碼

前文中介紹過，這種加密方式不會替換原文中字母，而是改變其排列順序。最經(jīng)典的列移位法會把明文排成若干列，然后根據(jù)順序依次讀指定的列。例如，密鑰是3-4-2-1，而明文是I LOVE CRYPTOGRAPHY的話，就會首先把明文寫成：

然后按照列順序?qū)懗蒞GHOROPIEPRYLCTA。破解時則需要猜測密鑰長度，并觀察哪些長度下會出現(xiàn)和英語近似的結(jié)構(gòu)?！岸?zhàn)”時期德國使用了雙重移位的密碼，將移位式密碼加密后的密文用另一個密鑰再加密一次。法國人設(shè)計出了一種方法，可以在截獲多條長度相同的密文之后快速破解，因此德軍舍棄了這種加密算法。

不僅是數(shù)學(xué)那么簡單

我們前面介紹的各種加密與破解算法，都是數(shù)學(xué)層面的交鋒。但實際上，當(dāng)破解專家們拿到一段密文后，要想破解出明文，可不僅僅是做數(shù)學(xué)題那么簡單（其實數(shù)學(xué)題也挺難的）。

1.獲得盡可能多的密文信息。

拿到密文后，先問“十萬個為什么”。這到底是一段密文，還是單純的涂鴉？它的明文是哪種語言？可能代表什么內(nèi)容？這段密文可能是用哪種密碼體系加密的？有沒有可能通過其他方式拿到密鑰？

這些問題對于破解密碼是至關(guān)重要的，它們代表這些密文所包含的信息。要獲得這些信息，所依賴的更多是細(xì)致的調(diào)查分析、社會工程相關(guān)知識，甚至是破解者突然閃現(xiàn)的靈感。

現(xiàn)代的密碼分析一般假定密碼系統(tǒng)是滿足嚴(yán)格的數(shù)學(xué)邏輯的，但在解讀伏尼契手稿或是羅塞塔石碑這類的古文書時，這些條件都不一定滿足。例如，18世紀(jì)的一份叫作Copiale cipher的文書中包含了羅馬字母、希臘字母和雜亂的抽象符號，人們將羅馬字母和希臘字母提取出來，但一直無法成功破解，最后他們發(fā)現(xiàn)只有那些抽象符號有實際意義，而所有字母只是代表空格，這才最終破解了這份文書。

①香農(nóng)的信息論

克勞德·艾爾伍德·香農(nóng)，美國數(shù)學(xué)家。香農(nóng)信息論是以概率論、隨機(jī)過程為基本研究工具，研究廣義通信系統(tǒng)的整個過程，而不是整個環(huán)節(jié)，并以編、譯碼器為重點，其關(guān)心的是在不涉及具體環(huán)節(jié)的情況下研究最優(yōu)系統(tǒng)的性能及如何達(dá)到該性能。信息論將信息的傳遞作為一種統(tǒng)計現(xiàn)象來考慮，給出了估算通信信道容量的方法。信息傳輸和信息壓縮是信息論研究中的兩大領(lǐng)域。這兩個方面又由信息傳輸定理、信源-信道隔離定理相互聯(lián)系。

2.獲取盡可能多的樣本。

這包括使用同一密鑰加密的密文和對應(yīng)某些已知密文的明文片段，通過分析大量明文與相應(yīng)密文的關(guān)系，就有可能反推出密鑰。能獲取的密文越多，破解密碼也就越容易。實際上，破解密碼所需要的密文樣本數(shù)是有下限的，這取決于可能的密鑰種類數(shù)和明文的信息密度。如果低于下限的話，很可能有多種不同的密鑰都能破解出合理的明文。而實際可以破譯的密碼通常要求密文量至少是下限的4倍。

英語的簡易替換密碼所需要的破譯下限是大約28個字母，所以實際可以破譯的密碼通常需要有100個字母以上。對這方面感興趣的同學(xué)可以去了解一下香農(nóng)的信息論①。有些密碼體系在只有密文的情況下弱點較小，但是一旦知道一小部分明文片段就非常容易破解，例如上文介紹的列移位法，只要知道一段明文，密鑰就顯而易見了。

3.根據(jù)密碼體系的特點和文本的語言特征尋找規(guī)律。

到這一步我們才進(jìn)入了數(shù)學(xué)的領(lǐng)域。一方面，文本規(guī)律可以幫助我們判斷加密算法是什么。另一方面，知道加密算法之后也有助于我們猜測或排除密鑰。例如，簡易替換式密碼的頻率分析法用到了英語的字母頻率和簡易替換不改變字母頻率的特點。“二戰(zhàn)”時期破解德軍最強密碼機(jī)“Enigma”的時候，則利用了該密碼機(jī)不可能將字母加密成同樣的字母的特點，使得盟軍可以利用獲得的明文片段排除大量可能的密鑰。

4.暴力求解。

通常是使用大型計算機(jī)遍歷所有可能的密鑰，并找出唯一正確的一個。上面的所有步驟，都是為了讓這一步變得可行。只要密碼系統(tǒng)公開，且樣本量足夠多，就只有唯一的一個密鑰能讓反解出的明文看起來合理。這時，破解密碼就只取決于時間和計算量——那些所謂強的加密法，只表示以目前的計算力水平難以在有效時間內(nèi)破解而已。從圖靈破譯“Enigma”開始，破譯密碼就不再是手動的工作，而是大型計算機(jī)的領(lǐng)域。1976年推出的DES加密法所使用的56位密鑰長度在當(dāng)時被認(rèn)為是安全的，但隨著計算力和破解算法的發(fā)展，到了2008年，用DES加密法所加密的密碼已經(jīng)可以在一天之內(nèi)被破解了。

互動問答

聽完這些，我們可以回頭來看一下怪盜的留言，并試著根據(jù)下面的提示思考一下怪盜采用了什么加密手段，明文和密鑰分別是什么。

1.這段密碼留言并不是通常意義上的密碼。雖然是發(fā)給我們的，但怪盜并沒有留下明確的加密算法和密鑰。

2.這段留言是為了讓我們解開而存在的。密文不長，但是又能破解，那么加密算法的選項就不太多了。

解析 因為表演欲過剩的怪盜目的是將信息傳達(dá)出去，而不是用密碼難倒館長一行， 所以采用了比較簡單的愷撒密碼，明文為：“bishangming”，是將密碼“l(fā)scrkxqwsxq”中每個字母在字母表里右移10位后生成，密鑰為10。