密碼分析學

出自 MBA智库百科(https://wiki.mbalib.com/)

密碼分析學（Cryptanalysis）

　　密碼分析學是指研究密碼、密文或密碼系統（即秘密代碼系統），著眼於找到其弱點，在不知道密鑰和演算法的情況下，從密文中得到原文的學科。這也被稱作破解密碼、密文或密碼系統。破解有時可以與弱化膠體使用，它們通常指的是找到密碼設計或執行上的弱點，以減少密鑰的數量，以便進行暴力破解（簡單的說，就是嘗試每一個可能的密鑰知道找到正確的那個）。例如，假設一個均衡的密碼執行使用2^128位的密鑰長度（2的128次冪）：這意味著暴力破解需要嘗試2^128個可能的組合以確信找到正確的密鑰（或者，平均有2^127個可能的組合），將密文轉換成原委，這對於現在和未來的計算能力看起來都是不可能實現的。然而，密碼分析學揭示了密碼的加密技術，解出來原文只需要2^40次嘗試。這對於現有的電腦資源來說，是很容易的。

　　雖然密碼分析的目標在密碼學的歷史上從古至今都一樣，實際使用的方法和技巧則隨著密碼學變得越來越複雜而日新月異。密碼學演算法和協議從古代只利用紙筆等工具，發展到第二次世界大戰時的恩尼格瑪密碼機（又稱謎，德語：Enigma），直到目前的基於電子電腦的方案。而密碼分析也隨之改變了。在上個世紀70年代中期，公鑰密碼學作為一個新興的密碼學分支發展起來了。而用來破解這些公鑰系統的方法則和以住完全不同，通常需要解決精心構造出來的純數學問題。其中最著名的就是大數的質因數分解。

　　在不知道關於密鑰的任何信息這一情況下，利用各種技術手段，試圖通過密文來得到明文或密鑰的全部信息或部分信息。密碼分析也稱為對密碼體制的攻擊。

　　按照攻擊者是否對通信作干擾，密碼分析可分為被動攻擊和主動攻擊2類。所謂被動攻擊是指，攻擊者僅是利用截獲的密文及公開的演算法，分析明文或密鑰，不對通信作干擾。所謂主動攻擊是指，攻擊者通過對通信線路進行干擾，如引入新的密文，重覆傳播舊的密文，替換合法密文等，再對截獲的密文進行分析。

　　按照攻擊者掌握的知識條件，密碼分析可分為唯密文攻擊、己知明文攻擊、選擇明文攻擊和選擇密文攻擊4類。所謂唯密文攻擊是指，攻擊者只知道一個要攻擊的密文(通常包含消息的上下文)。所謂己知明文攻擊是指，攻擊者知道一些明文/密文對，若一個密碼系統能夠抵抗這種攻擊，合法的接收者就不需要銷毀己解密的明文。所謂選擇明文攻擊是指，攻擊者可以選擇一些明文及對應的密文(公鑰密碼體制必需能夠抵抗這種攻擊)。所謂選擇密文攻擊是指，攻擊者可以選擇一些密文並得到相應的明文。

　　密碼分析和密碼學是共同演化的。這從密碼學史中可以看得很明顯。總是有新的密碼機被設計出來並取代已經被破解的設計，同時也總是有新的密碼分析方法被髮明出來以破解那些改進了的方案。事實上，密碼和密碼分析是同一枚硬幣的正反兩面：為了創建安全的密碼，就必須考慮到可能的密碼分析。

　　經典密碼分析

　　儘管密碼分析這個詞是晚近出現的（1920年由William Friedman確立），但破解密碼和密碼機的方法卻已經存在很久了。世界上最早的破解密碼方法的文字記錄可以追溯到九世紀阿拉伯通才Al Kindi所著《破解密碼信息》（A Manuscript on Deciphering Cryptographic Messages），這篇文章論述了一個頻率分析的方法。

　　頻率分析是破解經典密碼的一個基本方法。在自然語言里，字母表裡的有些字母比其它的字母出現得更頻繁。例如，在英語里，字母E很有可能是在任何文字樣本里出現頻率都最高的字母。同樣的，TH這兩個字母連起來是最有可能出現的字母對。頻率分析法假設密碼沒有隱藏這樣的統計信息。例如，在簡單的替換密碼中，每個字母只是簡單地被替換成另一個字母，那麼在密文中出現頻率最高的字母就最有可能是E。

　　頻率分析法除了需要用到統計學外，也需要用到語言學。但隨著密碼演算法的日漸複雜，密碼分析也漸漸變得主要依賴數學方法。這個改變在第二次世界大戰時最為明顯。那時，為了破解軸心國的密碼，需要發展更加複雜的數學方法。而且，自動計算也頭一次被應用到密碼分析中，如密碼炸彈（Bomba）以及最早的電腦之一，巨人電腦（Colossus）。

　　現代密碼分析

　　儘管第二次世界大戰時電腦的運用使得密碼分析更加容易，這同時也使得新的密碼學方案的複雜程度上升了好幾個數量級。總體來說，破解密碼在現代比起只用紙和筆的年代來說要困難得多了。現在看來，似乎密碼學對純密碼分析來說已經占了上風。美國曆史學家卡恩（David Kahn）這樣說道：“今天，由數百個商家提供的很多密碼系統都不能被已知的密碼分析方法來破解。確實，在這樣的密碼系統中，即使用選擇明文攻擊，也就是攻擊者可以選擇明文並比對相應的密文，也不能找出可以用來解開其它加密信息的鑰匙。從某種意義上來說，密碼分析已經死了。但是，故事還沒有結束。密碼分析也許是死了，但是，打個不恰當的比方，其實條條大道通羅馬。”（2002年11月1日在美國國家安全局50周年紀念會上的講話）。卡恩接著又提到，其它的攻擊方式的可能性增加了。例如攔截攻擊，竊聽，邊通道攻擊，以及用量子電腦來代替傳統電腦做密碼分析。

　　卡恩對於密碼分析所作的論斷也許還為時過早。不安全的密碼並沒有絕跡，美國國家情報機構的密碼分析方法也沒有公開過。在學術界，新的密碼在不斷地被設計出來，也經常地被破解。1984年，Madryga 分組密碼被一種唯密文攻擊破解。1998年，原本提出來要取代DES標準加密演算法的分組密碼 FEAL-4，也因為被學術界發現了很多類似而且實際可行的攻擊而消亡。在工業界，很多密碼也被髮現有漏洞。例如，在手機中使用的A5/1，A5/2以及CMEA演算法，用一般的計算工具可以在幾小時，幾分鐘內，甚至是實時地被破解。2001年，用來保護無線Wi-Fi網路的有線等效加密協議（或稱無線加密協議，即WEP）也可以用相關鑰匙攻擊來破解。

　　密碼分析的後果

　　無疑，成功的密碼分析影響了歷史的進程。能夠看懂別人本以為是秘密的想法或計劃，這種能力可以成為決定性的優勢。在戰爭期間尤其如此。例如，在第一次世界大戰中，成功地破解齊默爾曼電報是促使美國參戰的直接原因。在第二次世界大戰中，對德國密碼的成功破解，包括恩尼格瑪密碼機（Enigma）和洛侖茲密碼機（Lorenz Cipher），其後果從使歐洲戰場早幾個月結束，到對整個戰爭起決定性作用，各種說法都有（參見ULTRA）。美國也從對日本的PURPLE密碼的密碼分析中受益（參見MAGIC）。

　　一些國家的政府很早就已經意識到了密碼分析對於情報收集的重要性，不管是對於軍事還是外交都一樣。這些國家還建立了專門破解密碼的機構，如英國政府通訊總部（GCHQ），以及美國國家安全局（NSA）。這些機構在當今都非常活躍。2004年，有報道說美國成功破解了伊朗的密碼。但這是純粹的密碼分析還是有其它因素，目前還不清楚。

　　1、強力攻擊

　　強力攻擊包括查表攻擊，時間-存儲權衡攻擊，字典攻擊以及窮舉搜索攻擊。對於任何一種分組密碼來說，強力攻擊都是適用的。特別地，這種攻擊方法的複雜度僅僅取決於密鑰和分組的長度。更嚴格地講，這種攻擊技術的時間複雜度只取決於分組密碼演算法的效率，如存儲大小，密鑰擴展速度，加密和解密的速度等。

　　2、線性密碼分析

　　作為一種己知明文攻擊方法，線性密碼分析方法叫的本質思想在於，通過將一個給定的密碼演算法有效且線性近似地表示出來以實現破譯。現有密碼分析技術也得到了一定的推廣。目前，利用己知明文，16輪DES系統己可以通過線性密碼分析進行破譯，在某些情況下甚至可以實現唯密文攻擊。針對數據加密標準DES系統的主要攻擊包括強力攻擊手段，差分密碼分析等。就16輪DES密碼系統而言，不管是差分密碼分析還是線性密碼分析方法，需要用到的明文太多，因此效率比較低。為了提高攻擊效率，可以結合差分密碼分析和線性密碼分析技術，即差分-線性密碼分析技術。

　　3、差分密碼分析

　　1990年，以色列密碼學家Biham和Shamir提出了差分密碼分析技術。差分密碼分析特別適用於迭代密碼。差分密碼分析的本質思想在於，通過分析相應明文對差值和密文對差值之間的相互影響關係，來得到密鑰的一些比特信息。對於差分密碼分析也有很多推廣，其中比較常見的包括高階差分密碼分析等。