密碼分析（英語：cryptanalysis，來源于希臘語kryptós，即隱藏，以及analýein，即解開），是一門研究在不知道通常解密所需要的秘密信息的情況下對加密的信息進(jìn)行解密的學(xué)問。通常，這需要尋找一個(gè)秘密的鑰匙。用不是很正規(guī)的話來說，這就是所謂的破解密碼。
密碼分析這個(gè)詞有時(shí)也被用來指廣義上的繞開某個(gè)密碼學(xué)算法或密碼協(xié)議的嘗試，而不僅僅是針對加密算法。但是，密碼分析通常不包括并非主要針對密碼算法或協(xié)議的攻擊，如賄賂、拷打、入室搶劫、鍵盤記錄器，等等。盡管這些攻擊方式是計(jì)算機(jī)安全領(lǐng)域里的重要考慮因素，而且通常比傳統(tǒng)的密碼分析更加有效。
雖然密碼分析的目標(biāo)在密碼學(xué)的歷史上從古至今都一樣，實(shí)際使用的方法和技巧則隨著密碼學(xué)變得越來越復(fù)雜而日新月異。密碼學(xué)算法和協(xié)議從古代只利用紙筆等工具，發(fā)展到第二次世界大戰(zhàn)時(shí)的恩尼格瑪密碼機(jī)（又稱謎，德語：Enigma），直到目前的基于電子計(jì)算機(jī)的方案。而密碼分析也隨之改變了。無限制地成功破解密碼已經(jīng)不再可能。事實(shí)上，只有很少的攻擊是實(shí)際可行的。在上個(gè)世紀(jì)70年代中期，公鈅密碼學(xué)作為一個(gè)新興的密碼學(xué)分支發(fā)展起來了。而用來破解這些公鈅系統(tǒng)的方法則和以住完全不同，通常需要解決精心構(gòu)造出來的純數(shù)學(xué)問題。其中最著名的就是大數(shù)的質(zhì)因數(shù)分解。
密碼分析的歷史
密碼分析和密碼學(xué)是共同演化的。這從密碼學(xué)史中可以看得很明顯。總是有新的密碼機(jī)被設(shè)計(jì)出來并取代已經(jīng)被破解的設(shè)計(jì)，同時(shí)也總是有新的密碼分析方法被發(fā)明出來以破解那些改進(jìn)了的方案。事實(shí)上，密碼和密碼分析是同一枚硬幣的正反兩面：為了創(chuàng)建安全的密碼，就必須考慮到可能的密碼分析。
經(jīng)典密碼分析
盡管密碼分析這個(gè)詞是晚近出現(xiàn)的（1920年由William Friedman確立），但破解密碼和密碼機(jī)的方法卻已經(jīng)存在很久了。世界上最早的破解密碼方法的文字記錄可以追溯到九世紀(jì)阿拉伯通才Al Kindi所著《破解密碼信息》（A Manuscript on Deciphering Cryptographic Messages），這篇文章論述了一個(gè)頻率分析的方法。
頻率分析是破解經(jīng)典密碼的一個(gè)基本方法。在自然語言里，字母表里的有些字母比其它的字母出現(xiàn)得更頻繁。例如，在英語里，字母E很有可能是在任何文字樣本里出現(xiàn)頻率都最高的字母。同樣的，TH這兩個(gè)字母連起來是最有可能出現(xiàn)的字母對。頻率分析法假設(shè)密碼沒有隱藏這樣的統(tǒng)計(jì)信息。例如，在簡單的替換密碼中，每個(gè)字母只是簡單地被替換成另一個(gè)字母，那么在密文中出現(xiàn)頻率最高的字母就最有可能是E。
頻率分析法除了需要用到統(tǒng)計(jì)學(xué)外，也需要用到語言學(xué)。但隨著密碼算法的日漸復(fù)雜，密碼分析也漸漸變得主要依賴數(shù)學(xué)方法。這個(gè)改變在第二次世界大戰(zhàn)時(shí)最為明顯。那時(shí)，為了破解軸心國的密碼，需要發(fā)展更加復(fù)雜的數(shù)學(xué)方法。而且，自動計(jì)算也頭一次被應(yīng)用到密碼分析中，如密碼炸彈（Bomba）以及最早的計(jì)算機(jī)之一，巨人計(jì)算機(jī)（Colossus）。
現(xiàn)代密碼分析
盡管第二次世界大戰(zhàn)時(shí)計(jì)算機(jī)的運(yùn)用使得密碼分析更加容易，這同時(shí)也使得新的密碼學(xué)方案的復(fù)雜程度上升了好幾個(gè)數(shù)量級。總體來說，破解密碼在現(xiàn)代比起只用紙和筆的年代來說要困難得多了?，F(xiàn)在看來，似乎密碼學(xué)對純密碼分析來說已經(jīng)占了上風(fēng)。美國歷史學(xué)家卡恩（David Kahn）這樣說道：“今天，由數(shù)百個(gè)商家提供的很多密碼系統(tǒng)都不能被已知的密碼分析方法來破解。確實(shí)，在這樣的密碼系統(tǒng)中，即使用選擇明文攻擊，也就是攻擊者可以選擇明文并比對相應(yīng)的密文，也不能找出可以用來解開其它加密信息的鑰匙。從某種意義上來說，密碼分析已經(jīng)死了。但是，故事還沒有結(jié)束。密碼分析也許是死了，但是，打個(gè)不恰當(dāng)?shù)谋确剑鋵?shí)條條大道通羅馬。”（2002年11月1日在美國國家安全局50周年紀(jì)念會上的講話）。卡恩接著又提到，其它的攻擊方式的可能性增加了。例如攔截攻擊，竊聽，邊信道攻擊，以及用量子計(jì)算機(jī)來代替?zhèn)鹘y(tǒng)計(jì)算機(jī)做密碼分析[1]。
卡恩對于密碼分析所作的論斷也許還為時(shí)過早。不安全的密碼并沒有絕跡，美國國家情報(bào)機(jī)構(gòu)的密碼分析方法也沒有公開過。在學(xué)術(shù)界，新的密碼在不斷地被設(shè)計(jì)出來，也經(jīng)常地被破解。1984年，Madryga分組密碼被一種唯密文攻擊破解。1998年，原本提出來要取代DES標(biāo)準(zhǔn)加密算法的分組密碼FEAL-4，也因?yàn)楸粚W(xué)術(shù)界發(fā)現(xiàn)了很多類似而且實(shí)際可行的攻擊而消亡。在工業(yè)界，很多密碼也被發(fā)現(xiàn)有漏洞。例如，在手機(jī)中使用的A5/1，A5/2以及CMEA算法，用一般的計(jì)算工具可以在幾小時(shí)，幾分鐘內(nèi)，甚至是實(shí)時(shí)地被破解。2001年，用來保護(hù)無線Wi-Fi網(wǎng)絡(luò)的有線等效加密協(xié)議（或稱無線加密協(xié)議，即WEP）也可以用相關(guān)鑰匙攻擊來破解。
密碼分析的后果
無疑，成功的密碼分析影響了歷史的進(jìn)程。能夠看懂別人本以為是秘密的想法或計(jì)劃，這種能力可以成為決定性的優(yōu)勢。在戰(zhàn)爭期間尤其如此。例如，在第一次世界大戰(zhàn)中，成功地破解齊默爾曼電報(bào)是促使美國參戰(zhàn)的直接原因。在第二次世界大戰(zhàn)中，對德國密碼的成功破解，包括恩尼格瑪密碼機(jī)（Enigma）和洛侖茲密碼機(jī)（Lorenz Cipher），其后果從使歐洲戰(zhàn)場早幾個(gè)月結(jié)束，到對整個(gè)戰(zhàn)爭起決定性作用，各種說法都有（參見ULTRA）。美國也從對日本的PURPLE密碼的密碼分析中受益（參見MAGIC）。
一些國家的政府很早就已經(jīng)意識到了密碼分析對于情報(bào)收集的重要性，不管是對于軍事還是外交都一樣。這些國家還建立了專門破解密碼的機(jī)構(gòu)，如英國政府通訊總部（GCHQ），以及美國國家安全局（NSA）。這些機(jī)構(gòu)在當(dāng)今都非?；钴S。2004年，有報(bào)道說美國成功破解了伊朗的密碼。但這是純粹的密碼分析還是有其它因素，目前還不清楚[2]。
攻擊類型
不同的密碼分析攻擊有不同的效力，對于實(shí)際的密碼系統(tǒng)的威脅也不盡相同。有的時(shí)候，對于某個(gè)密碼系統(tǒng)的攻擊只是停留在理論上，對于任何實(shí)際的密碼系統(tǒng)可能并不適用。這就是所謂的“證書式弱點(diǎn)”（certificational weakness）。現(xiàn)代密碼分析的學(xué)術(shù)研究結(jié)果大部分都屬于這一類。從根本上說，某種攻擊方式在實(shí)際中的有效性取決于它對于以下幾個(gè)問題給出的答案：
這個(gè)攻擊需要何種知識及能力？
通過攻擊可獲得多少新的秘密信息？
這個(gè)攻擊需要花多少工夫？（它的計(jì)算復(fù)雜度為何？）
密碼分析中的情形
在攻擊中，通過觀察或研究目標(biāo)系統(tǒng)，多少會獲得關(guān)于這個(gè)系統(tǒng)的信息。隨著能夠獲得信息多少的假設(shè)不同，密碼分析的方法也不盡相同。在密碼分析中最基本的一點(diǎn)，就是假設(shè)攻擊者能夠知道系統(tǒng)所用的算法。這也就是“敵人了解系統(tǒng)”的所謂柯克霍夫原則。這個(gè)假設(shè)在實(shí)際中是合理的。從古至今，有無數(shù)的秘密算法最后終為人所知，而其途徑多種多樣，包括間諜，叛變，以及逆向工程。在一些不多見的情況下，密碼機(jī)也能夠通過純粹的推演而被重建。例如德國的洛侖茲密碼機(jī)（Lorenz Cipher）和日本的PURPLE密碼機(jī)，以及其它很多經(jīng)典密碼。
另外，我們通常用攻擊模式來描述攻擊者可以獲得關(guān)于系統(tǒng)信息的方式。攻擊模式包括以下幾種：
唯密文攻擊：攻擊者僅能獲得一些加密過的密文。
已知明文攻擊：攻擊者有一些密文并且知道相對應(yīng)的明文。
選擇明文攻擊：攻擊者在開始攻擊之前可以選擇一些明文并從系統(tǒng)中獲得相對應(yīng)的密文。如果攻擊者在攻擊中途可以根據(jù)已經(jīng)獲得的信息選擇新的明文并獲得對應(yīng)的密文，則稱為適應(yīng)性選擇明文攻擊。
選擇密文攻擊：攻擊者在開始攻擊之前可以選擇一些密文并從系統(tǒng)中獲得相對應(yīng)的明文。如果攻擊者在攻擊中途可以根據(jù)已經(jīng)獲得的信息選擇新的密文并獲得對應(yīng)的明文，則稱為適應(yīng)性選擇密文攻擊。
相關(guān)鑰匙攻擊：與選擇明文（或密文）攻擊類似。不同的是，攻擊者可以得到被兩個(gè)不同的鑰匙所加密（或解密）得到的密文（或明文）。攻擊者不知道這兩個(gè)鑰匙的數(shù)值，但知道這兩個(gè)鑰匙之間的關(guān)系，比如兩個(gè)鑰匙之間相差一個(gè)比特。
顯然，這些不同種類的攻擊在實(shí)際中可能出現(xiàn)的機(jī)會也大不相同。盡管有些攻擊比其它的較為常見，密碼學(xué)家在設(shè)計(jì)算法時(shí)通常會采取保守的方式看待安全問題，總是假設(shè)最壞的情形。理由是，如果一個(gè)算法連不現(xiàn)實(shí)的攻擊都可以承受，那么它自然也可以抵抗實(shí)際可行的密碼分析。
事實(shí)上，這些假設(shè)雖然初看上去不切實(shí)際，但其實(shí)不然。例如在已知明文攻擊中，密碼分析者很有可能能夠知道或猜出明文的一部分。比方說，一封加密過的信有可能是以“敬啟者”開頭，而一個(gè)電腦會話則有可能以“用戶名：”開頭。選擇明文攻擊在密鈅密碼中較為少見，但也并非不可能。而在公鑰密碼中，選擇明文攻擊人人都可做到，因?yàn)榧用苡玫蔫€匙通常是公開或已知的。相關(guān)鑰匙攻擊通常只是在理論上的討論，但在實(shí)際中也會被用到，例如對WEP的攻擊。
成功密碼分析的類別
對于密碼分析的結(jié)果來說，其有用的程度也各有不同。密碼學(xué)家Lars Knudsen于1998年將對于分組密碼的攻擊按照獲得的秘密信息的不同分為以下幾類：
完全破解--攻擊者獲得秘密鑰匙。
全局演繹--攻擊者獲得一個(gè)和加密和解密相當(dāng)?shù)乃惴?，盡管可能并不知道鑰匙。
實(shí)例（局部）演繹--攻擊者獲得了一些攻擊之前并不知道的明文（或密文）。
信息演繹--攻擊者獲得了一些以前不知道的關(guān)于明文或密文的香農(nóng)信息。
分辨算法--攻擊者能夠區(qū)別加密算法和隨機(jī)排列。
對于其它類型的密碼學(xué)算法，也可以做出類似的分類。
