密碼分析

密碼分析和破解一直是密碼學中的一個重要內容，目前國內外非常熱衷於密碼分析研究，並且取得了一些令人矚目的成績。我國著名的密碼學專家、山東大學信息安全研究所所長王小雲教授帶領的密碼研究團隊在國家自然科學基金“網路與信息安全”重大研究計劃的資金支持下，經過一年多的研究，先後破譯了包含MD5與SHA-1在內的系列Hash函數演演算法。2005年2月15日，在美國召開的國際信息安全RSA研討會上，國際著名密碼學專家Adi Shamir宣布，他收到了來自中國山東大學王小雲、尹依群、於紅波等三人的論文，本論文描述了如何使得兩個不同的文件產生相同的SHA-1散列值，而計算複雜度比以前的方法更低。這是繼2004年8月王小雲教授破譯MD5之後，國際密碼學領域的又一突破性研究成果。

密碼分析技術的發展和密碼加密技術的發展是分不開的。目前，密碼加密技術的方向向量子密碼、生物密碼等新一代密碼加密技術發展，因此，密碼分析技術也會隨之進入一個新的領域。提高密碼分析的準確度、減少密碼分析消耗的資源也是研究的重點。

目前，由於黑客技術的發展和普及，網路安全受到很大挑戰，各種密碼演演算法和標準廣泛應用。在各類信息系統中獲取的機密信息很大部分都是經過加密處理的，因而密碼分析與破解成為網路信息獲取中的一個必須面對的問題。結合實際的密碼應用，通過對密碼分析的研究將會大大提高電子取證工作的成效。密碼破解技術將成為一個重要研究熱點，應用前景非常可觀。

什麼是美國早在1977年就制定了自己的數據加密標準:DES。隨著DES的出現，人們對分組密碼展開了深入的研究和討論。出現了各種各樣的分組密碼。用抽象的觀點來看，分組密碼就是一種滿足下列條件的映射E:Fm2×SK→Fm2對每個k∈SK,E(.,k是從Fm2到Fm2的一個置換。可見，設計分組密碼的問題在於找到一種演演算法，能在密鑰控制下從一個足夠大且足夠“好”地置換子集合中，簡單而迅速地選出一個置換。一個好的分組密碼應該是既難破譯又容易實現，即加密函數E（.,k）和解密函數D(.,k)都必須容易計算，但是至少要從方程y=E(x,k)或x=D(y,k)中求出密鑰k應該是一個困難問題。

在分組密碼設計技術發展的同時，分組密碼分析技術也得到了空前的發展。已有很多分組密碼分析技術，如強力攻擊(包括窮盡密鑰搜索攻擊、字典攻擊、查表攻擊、時間—存儲權衡攻擊)、差分密碼分析、差分密碼分析的推廣(包括截段差分密碼分析、高階差分密碼分析、不可能差分密碼分析)、線性密碼分析、線性密碼分析的推廣(包括多重線性密碼分析、非線性密碼分析、劃分密碼分析)、差分—線性密碼分析、插值攻擊、密鑰相關攻擊、能量分析、錯誤攻擊、定時攻擊等等。

密碼分析除了依靠數學、工程背景、語言學知識外，

還要靠經驗、統計、測試、眼力、直覺判斷力…..有時還要靠點運氣

? 密碼破譯的原則: 遵循觀察與經驗

? 方法：採用歸納與演繹

? 步驟：分析、假設、推測和證實

主條目：事實上，密碼和密碼分析是同一枚硬幣的正反兩面：為了創建安全的密碼，就必須考慮到可能的密碼分析。

儘管密碼分析這個詞是晚近出現的（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年，有報道說美國成功破解了伊朗的密碼。但這是純粹的密碼分析還是有其它因素，目前還不清楚。

對於密碼分析的結果來說，其有用的程度也各有不同。密碼學家Lars Knudsen於1998年將對於分組密碼的攻擊按照獲得的秘密信息的不同分為以下幾類：完全破解 -- 攻擊者獲得秘密鑰匙。全局演繹 -- 攻擊者獲得一個和加密和解密相當的演演算法，儘管可能並不知道鑰匙。實例（局部）演繹 -- 攻擊者獲得了一些攻擊之前並不知道的明文（或密文）。信息演繹 -- 攻擊者獲得了一些以前不知道的關於明文或密文的香農信息。分辨演演算法 -- 攻擊者能夠區別加密演演算法和隨機排列。對於其它類型的密碼學演演算法，也可以做出類似的分類。

可將密碼分析分為以下五種情形。

（1）惟密文攻擊（Ciphertext only）

對於這種形式的密碼分析，破譯者已知的東西只有兩樣：加密演演算法、待破譯的密文。

（2）已知明文攻擊（Known plaintext）

在已知明文攻擊中，破譯者已知的東西包括：加密演演算法和經密鑰加密形成的一個或多個明文—密文對，即知道一定數量的密文和對應的明文。

（3）選擇明文攻擊（Chosen plaintext）

選擇明文攻擊的破譯者除了知道加密演演算法外，他還可以選定明文消息，並可以知道對應的加密得到的密文，即知道選擇的明文和對應的密文。例如，公鑰密碼體制中，攻擊者可以利用公鑰加密他任意選定的明文，這種攻擊就是選擇明文攻擊。

（4）選擇密文攻擊(Chosen ciphertext)

與選擇明文攻擊相對應，破譯者除了知道加密演演算法外，還包括他自己選定的密文和對應的、已解密的原文，即知道選擇的密文和對應的明文。

（5）選擇文本攻擊（Chosen text）

選擇文本攻擊是選擇明文攻擊與選擇密文攻擊的結合。破譯者已知的東西包括：加密演演算法、由密碼破譯者選擇的明文消息和它對應的密文，以及由密碼破譯者選擇的猜測性密文和它對應的已破譯的明文。

很明顯，惟密文攻擊是最困難的，因為分析者可供利用的信息最少。上述攻擊的強度是遞增的。一個密碼體制是安全的，通常是指在前三種攻擊下的安全性，即攻擊者一般容易具備進行前三種攻擊的條件。

分析、推斷、假設、證實。