檢視密碼分析的原始碼

{| class="wikitable" style="float:right; margin: -10px 0px 10px 20px; text-align:left"
|<center>'''密碼分析'''<br><img src="https://pic1.xuehuaimg.com/proxy/csdn/https://img-blog.csdnimg.cn/2020010114264312.jpeg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hsc2oyMjg=,size_16,color_FFFFFF,t_70" width="280"></center><small>[https://www.twblogs.net/a/5e53de48bd9eee21168322d1 圖片來自twblogs]</small> 
|}

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

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

雖然密碼分析的目標在[[密碼學]]的歷史上從未改變，但是實際使用的方法和技巧則隨著密碼學變得越來越復雜而日新月異。密碼學算法和協議從古代只利用紙筆等工具，發展到[[第二次世界大戰]]時的[[恩尼格瑪密碼機]]（又稱「謎」，[[德語]]：Enigma），直到目前的基於[[電子計算機]]的方案。而密碼分析也隨之改變了。無限制地成功破解密碼已經不再可能。事實上，只有很少的攻擊是實際可行的。在上個世紀70年代中期，[[公鑰密碼學]]<ref>[https://medium.com/@RiverChan/%E5%9F%BA%E7%A4%8E%E5%AF%86%E7%A2%BC%E5%AD%B8-%E5%B0%8D%E7%A8%B1%E5%BC%8F%E8%88%87%E9%9D%9E%E5%B0%8D%E7%A8%B1%E5%BC%8F%E5%8A%A0%E5%AF%86%E6%8A%80%E8%A1%93-de25fd5fa537 公鑰密碼學]，medium</ref> 作為一個新興的密碼學分支發展起來了。而用來破解這些公鑰系統的方法則和以往完全不同，通常需要解決精心構造出來的[[純數學]]問題。其中最著名的就是大數的[[整數分解|質因數分解]]。

=== 經典密碼分析 ===

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

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

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

=== 現代密碼分析 ===

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

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

=== 密碼分析的後果 ===

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

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

== 攻擊類型 ==

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

# 這個攻擊需要何種[[知識]]及能力？
# 通過攻擊可獲得多少新的秘密信息？
# 這個攻擊需要花多少工夫？（它的[[計算復雜度]]為何？）

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

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

另外，我們通常用[[攻擊模式]]來描述攻擊者可以獲得關於系統信息的方式。[[攻擊模式]]包括以下幾種：
* [[唯密文攻擊]]：攻擊者僅能獲得一些加密過的[[密文]]。
* [[已知明文攻擊]]：攻擊者有一些[[密文]]並且知道相對應的[[明文]]。
* [[選擇明文攻擊]]：攻擊者在開始攻擊之前可以選擇一些明文並從系統中獲得相對應的密文。如果攻擊者在攻擊中途可以根據已經獲得的信息選擇新的明文並獲得對應的密文，則稱為'''適應性選擇明文攻擊'''。
* [[選擇密文攻擊]]：攻擊者在開始攻擊之前可以選擇一些密文並從系統中獲得相對應的明文。如果攻擊者在攻擊中途可以根據已經獲得的信息選擇新的密文並獲得對應的明文，則稱為'''適應性選擇密文攻擊'''。
* [[相關鑰匙攻擊]]：與選擇明文（或密文）攻擊類似。不同的是，攻擊者可以得到被兩個不同的[[鑰匙]]所加密（或解密）得到的密文（或明文）。攻擊者不知道這兩個鑰匙的數值，但知道這兩個鑰匙之間的關係，比如兩個鑰匙之間相差一個:比特:位元。

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

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

=== 成功密碼分析的類別 ===

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

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

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

== 參考文獻 == 
{{reflist}}
[[Category: 310 數學總論]]