密碼分析（英語：cryptanalysis，來源於希臘語kryptós，即“隱藏”，以及analýein，即“解開”），是一門研究在不知道通常解密所需要的秘密信息的情況下對信息進行解密的學問。通常，這需要尋找一個秘密的鑰匙。用不是很正規的話來說，這就是所謂的破解密碼。
基本介紹
- 中文名：密碼分析
- 外文名：cryptanalysis
- 提出者：William Friedman
- 提出時間：1920年
- 學科：密碼學
- 希臘語：kryptós
概述,經典密碼分析,現代密碼分析,密碼分析的後果,成功密碼分析的類別,
概述
密碼分析這個詞有時也被用來指廣義上的繞開某個密碼學算法或密碼協定的嘗試，而不僅僅是針對加密算法。但是，密碼分析通常不包括並非主要針對密碼算法或協定的攻擊。
雖然密碼分析的目標在密碼學的歷史上從古至今都一樣，但是實際使用的方法和技巧則隨著密碼學變得越來越複雜而日新月異。密碼學算法和協定從古代只利用紙筆等工具，發展到第二次世界大戰時的恩尼格瑪密碼機（又稱“謎”，德語：Enigma），直到目前的基於電子計算機的方案。而密碼分析也隨之改變了，無限制地成功破解密碼已經不再可能。事實上，只有很少的攻擊是實際可行的。在上個世紀70年代中期，公鑰密碼學作為一個新興的密碼學分支發展起來了，而用來破解這些公鑰系統的方法則和以住完全不同，通常需要解決精心構造出來的純數學問題，其中最著名的就是大數的質因數分解。
經典密碼分析
儘管密碼分析這個詞是晚近出現的（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），其後果從使歐洲戰場早幾個月結束，到對整個戰爭起決定性作用，各種說法都有。美國也從對日本的PURPLE密碼的密碼分析中受益。
一些國家的政府很早就已經意識到了密碼分析對於情報收集的重要性，不管是對於軍事還是外交都一樣。這些國家還建立了專門破解密碼的機構，如英國政府通訊總部（GCHQ），以及美國國家安全局（NSA），這些機構在當今都非常活躍。2004年，有報導說美國成功破解了伊朗的密碼，但這是純粹的密碼分析還是有其它因素，還不清楚。
成功密碼分析的類別
對於密碼分析的結果來說，其有用的程度也各有不同。密碼學家Lars Knudsen於1998年將對於分組密碼的攻擊按照獲得的秘密信息的不同分為以下幾類：
完全破解 -- 攻擊者獲得秘密鑰匙。 全局演繹 -- 攻擊者獲得一個和加密和解密相當的算法，儘管可能並不知道鑰匙。 實例（局部）演繹 -- 攻擊者獲得了一些攻擊之前並不知道的明文（或密文）。 信息演繹 -- 攻擊者獲得了一些以前不知道的關於明文或密文的香農信息。 分辨算法 -- 攻擊者能夠區別加密算法和隨機排列。 對於其它類型的密碼學算法，也可以做出類似的分類。
可將密碼分析分為以下五種情形。
（1）惟密文攻擊（Ciphertext only）
對於這種形式的密碼分析，破譯者已知的東西只有兩樣：加密算法、待破譯的密文。
（2）已知明文攻擊（Known plaintext）
在已知明文攻擊中，破譯者已知的東西包括：加密算法和經密鑰加密形成的一個或多個明文—密文對，即知道一定數量的密文和對應的明文。
（3）選擇明文攻擊（Chosen plaintext）
選擇明文攻擊的破譯者除了知道加密算法外，他還可以選定明文訊息，並可以知道對應的加密得到的密文，即知道選擇的明文和對應的密文。例如，公鑰密碼體制中，攻擊者可以利用公鑰加密他任意選定的明文，這種攻擊就是選擇明文攻擊。
（4） 選擇密文攻擊(Chosen ciphertext)
