密碼分析

密碼分析（英語：cryptanalysis，來源於希臘語kryptós，即「隱藏」，以及analýein，即「解開」），是研究在不知道通常解密所需要的秘密資訊的情況下對已加密的資訊進行解密的一門學問。一般情況下，要成功解密需要尋找到一個秘密的鑰匙，俗稱破解密碼（破密）。

從廣義的角度看，密碼分析這個詞語有時也泛指繞開某個密碼學演算法或密碼協定的嘗試，而不僅僅是針對加密演算法。但是，密碼分析通常不包括並非主要針對密碼演算法或協定的攻擊。儘管這些攻擊方式是計算機安全領域裡的重要考慮因素，而且通常比傳統的密碼分析更加有效。

雖然密碼分析的目標在密碼學的歷史上從未改變，但是實際使用的方法和技巧則隨著密碼學變得越來越復雜而日新月異。密碼學演算法和協定從古代只利用紙筆等工具，發展到第二次世界大戰時的恩尼格瑪密碼機（又稱「謎」，德語：Enigma），直到目前的基於電子計算機的方案。而密碼分析也隨之改變了。無限制地成功破解密碼已經不再可能。事實上，只有很少的攻擊是實際可行的。在上個世紀70年代中期，公鑰密碼學作為一個新興的密碼學分支發展起來了。而用來破解這些公鑰系統的方法則和以往完全不同，通常需要解決精心構造出來的純數學問題。其中最著名的就是大數的質因數分解。

密碼分析的歷史

主條目：密碼學史

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

經典密碼分析

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

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

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

現代密碼分析

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

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

密碼分析的後果

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

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

攻擊類型

不同的密碼分析攻擊有不同的效力，對於實際的密碼系統的威脅也不盡相同。有的時候，對於某個密碼系統的攻擊只是停留在理論上，對於任何實際的密碼系統可能並不適用。這就是所謂的「憑證式弱點」（certificational weakness）。現代密碼分析的學術研究結果大部分都屬於這一類。從根本上說，某種攻擊方式在實際中的有效性取決於它對於以下幾個問題給出的答案：

1. 這個攻擊需要何種知識及能力？
2. 通過攻擊可獲得多少新的秘密資訊？
3. 這個攻擊需要花多少工夫？（它的計算復雜度為何？）

先驗知識：密碼分析中的情形

在攻擊中，通過觀察或研究目標系統，多少會獲得關於這個系統的資訊。隨著能夠獲得資訊多少的假設不同，密碼分析的方法也不盡相同。在密碼分析中最基本的一點，就是假設攻擊者能夠知道系統所用的演算法。這也就是「敵人了解系統」的所謂柯克霍夫原則。這個假設在實際中是合理的。從古至今，有無數的秘密演算法最後終為人所知，而其途徑多種多樣，包括間諜，叛變，以及逆向工程。在一些不多見的情況下，密碼機也能夠通過純粹的推演而被重建。例如德國的洛侖茲密碼機（Lorenz Cipher）和日本的PURPLE密碼機，以及其它很多經典密碼。

另外，通常用攻擊模式來描述攻擊者可以獲得關於系統資訊的方式。攻擊模式包括以下幾種：

• 唯密文攻擊：攻擊者僅能獲得一些加密過的密文。
• 已知明文攻擊：攻擊者有一些密文並且知道相對應的明文。
• 選擇明文攻擊：攻擊者在開始攻擊之前可以選擇一些明文並從系統中獲得相對應的密文。如果攻擊者在攻擊中途可以根據已經獲得的資訊選擇新的明文並獲得對應的密文，則稱為適應性選擇明文攻擊。
• 選擇密文攻擊：攻擊者在開始攻擊之前可以選擇一些密文並從系統中獲得相對應的明文。如果攻擊者在攻擊中途可以根據已經獲得的資訊選擇新的密文並獲得對應的明文，則稱為適應性選擇密文攻擊。
• 相關鑰匙攻擊：與選擇明文（或密文）攻擊類似。不同的是，攻擊者可以得到被兩個不同的鑰匙所加密（或解密）得到的密文（或明文）。攻擊者不知道這兩個鑰匙的數值，但知道這兩個鑰匙之間的關係，比如兩個鑰匙之間相差一個位元。

顯然，這些不同種類的攻擊在實際中可能出現的機會也大不相同。儘管有些攻擊比其它的較為常見，密碼學家在設計演算法時通常會採取保守的方式看待安全問題，總是假設最壞的情形。理由是，如果一個演算法連不現實的攻擊都可以承受，那麼它自然也可以抵抗實際可行的密碼分析。

事實上，這些假設雖然初看上去不切實際，但其實不然。例如在已知明文攻擊中，密碼分析者很有可能能夠知道或猜出明文的一部分。比方說，一封加密過的信有可能是以「敬啟者」開頭，而一個電腦會話則有可能以「使用者名稱：」開頭。選擇明文攻擊在金鑰密碼中較為少見，但也並非不可能。而在公鑰密碼中，選擇明文攻擊人人都可做到，因為加密用的鑰匙通常是公開或已知的。相關鑰匙攻擊通常只是在理論上的討論，但在實際中也會被用到，例如對WEP的攻擊。

成功密碼分析的類別

對於密碼分析的結果來說，其有用的程度也各有不同。密碼學家Lars Knudsen於1998年將對於分組密碼的攻擊按照獲得的秘密資訊的不同分為以下幾類：

• 完全破解 -- 攻擊者獲得秘密鑰匙。
• 全域演繹 -- 攻擊者獲得一個和加密和解密相當的演算法，儘管可能並不知道鑰匙。
• 實例（局部）演繹 -- 攻擊者獲得了一些攻擊之前並不知道的明文（或密文）。
• 資訊演繹 -- 攻擊者獲得了一些以前不知道的關於明文或密文的香農資訊。
• 分辨演算法 -- 攻擊者能夠區別加密演算法和隨機排列。

對於其它類型的密碼學演算法，也可以做出類似的分類。

非對稱密碼學的密碼分析

非對稱密碼學是一種使用不同金鑰（公開金鑰和私有金鑰）進行加密和解密的密碼學。這種方法的安全性基於數學難題，如大素數的因數分解或離散對數問題。密碼分析方法通常針對非對稱密碼學中的公開金鑰進行，以下是一些常見的分析方法：

1. 因數分解攻擊：基於大數的因數分解的困難性，通常使用一個大素數的乘積作為公開金鑰，從而使得破解加密訊息需要極其巨大的計算量。然而，隨著量子計算技術的進步，Shor演算法可能會在未來成為一種威脅，因為它可以有效地破解這種加密方法。
2. 密碼文攻擊：嘗試利用公開密文來推斷出明文或金鑰的攻擊。這可能包括使用已知的明文-密文對來推斷出金鑰，或者利用密文的統計特性來猜測明文。
3. 選擇明文攻擊：攻擊者能夠選擇自己感興趣的明文訊息，並根據相應的密文來觀察公開金鑰加密的過程，從而獲取有關金鑰或加密演算法的資訊。
4. 側信道攻擊：利用加密演算法實現的物理實現的特定資訊，如功耗、電磁輻射或時間，來推斷出金鑰的攻擊。這些攻擊不直接針對演算法本身，而是利用實際實現的特性來進行攻擊。
5. 離散對數攻擊：基於離散對數問題的困難性，如在橢圓曲線密碼學中使用的ElGamal加密演算法，攻擊者可能會嘗試利用數學技巧來破解密文。
6. 公開金鑰替換攻擊：當攻擊者能夠將合法的公開金鑰替換為自己的公開金鑰時，便可進行攻擊。這可能發生在中間人攻擊或者通過竊取合法使用者的公開金鑰來實現。

為了防止這些攻擊，密碼學家們致力於開發更強大的加密演算法和協定，並提供相應的安全性證明。此外，密碼學家們還研究和開發用於抵禦側信道攻擊和其他物理攻擊的硬體和軟體保護措施。

量子計算在密碼分析中的應用

量子計算在密碼分析中具有潛在的顯著影響，因為它利用了量子力學中的特性，如量子疊加和量子糾纏，可以在某些情況下實現比傳統計算更快速和更有效的運算。以下是量子計算在密碼分析中的應用：

1. Shor演算法：Shor演算法是一種著名的量子演算法，用於因數分解。這對於公鑰加密系統（如RSA）是一個潛在的威脅，因為這些系統的安全性基於大素數因子的難解性。Shor演算法可以在多項式時間內找到大數的因子，從而破解這些加密系統。
2. 量子搜尋演算法：Quantum Search Algorithms，如Grover演算法，可以在平方根的時間內搜尋未排序的資料庫。這意味著在破解基於密碼雜湊的加密時，攻擊者可以更快地找到碰撞（即具有相同雜湊值的不同輸入）。
3. 量子金鑰分發：Quantum Key Distribution（QKD）利用了量子力學中的原理來實現安全的金鑰傳輸。這可以用於在通訊過程中安全地交換金鑰，防止量子計算攻擊者監聽通訊。
4. 量子側信道攻擊：與傳統側信道攻擊相比，量子側信道攻擊可能更加強大。這些攻擊利用量子計算的特性，例如通過觀察量子位元的狀態來推斷密碼。

雖然量子計算在密碼分析中帶來了一些新的挑戰，但也促使密碼學家開發出新的加密技術，這些技術能夠抵禦量子計算的攻擊。這包括基於格的加密、量子安全的雜湊函式和量子安全的密碼協定等。因此，量子計算不僅是一個威脅，同時也是激勵加密技術進步的動力。

密碼分析的方法

密碼分析是一門涉及破解、評估和保護密碼的學科。這涉及多種技術和方法，以下是一些常見的密碼分析方法：

1. 暴力破解（Brute Force）：這是一種基本的方法，通過嘗試所有可能的組合來找到密碼。這可以是字典攻擊（使用預先準備的單詞列表）或是全盤搜尋。
2. 字典攻擊（Dictionary Attack）：使用預先準備好的單詞列表（字典）來嘗試可能的密碼。這種方法假設使用者使用常見的單詞或短語作為密碼。
3. 彩虹表攻擊（Rainbow Table Attack）：這是一種使用預先計算的密碼雜湊值和對應的明文密碼之間的對映表的攻擊方法。這可以節省計算時間，因為不需要每次都重新計算密碼的雜湊值。
4. 社會工程學（Social Engineering）：這種方法涉及通過欺騙、詢問或其他方式來獲取密碼。這可能包括偽裝成合法的使用者或系統管理員，以便使用者自己提供密碼。
5. 側通道攻擊（Side-Channel Attacks）：這種攻擊利用了密碼處理系統的實際實現漏洞，而不僅僅是依賴於破解密碼本身。這可能包括分析電源消耗、計算時間等來推斷密碼。
6. 網路監聽（Network Sniffing）：通過監聽網路流量，特別是在未加密的情況下，攻擊者可以截取帶有密碼的通訊。
7. 釣魚（Phishing）：這是一種通過偽造信任來詐騙使用者提供他們的密碼的方法，通常通過偽裝成合法的網站或服務來實現。
8. 側信道攻擊（Side-Channel Attacks）：這是一種利用實際裝置的特性（如功耗、電磁輻射等）來推斷密碼的攻擊方法。
9. 社交工程：攻擊者可能通過與目標交往、通過社群媒體收集資訊等方式來獲取關於目標的資訊，以便猜測或重設其密碼。

綜合利用這些方法可以提高對不同密碼的破解成功率，而針對性的密碼保護方法也應該考慮這些攻擊手段來提高安全性。

參見

• Ophcrack