理論上可以通過除窮舉法以外的方法破解不可逆的加密演算法嗎？

12-05

往往存在一個誤區，認為MD5、SHA1這樣的摘要演算法是加密演算法，其實是不對的，可以說是一種密碼演算法。加密演算法是要能把明文變成密文，密文再變回明文的，變不回來的不能算是加密。至於這個問題，則要從破解這個詞在各種不同語境中不同的含義來說了。

一、加密演算法的破解
加密演算法能在加密密鑰的作用下，把明文變成密文；在解密密鑰的作用下，把密文變成明文。針對加密演算法的破解，是在沒有密鑰的情況下，把明文給還原出來。不過更細的還分為只知道密文的唯密文攻擊，知道若干明文密文對的已知明文攻擊，能夠構造確定明文讓對方加密並得到對應密文的選擇明文攻擊等。另外值得說的是，密碼學中有柯克霍夫斯基原則，即加密演算法的安全性依賴的是密鑰的保密而不是演算法的保密，所以所有關於破解的討論中，都是假定攻擊者知道加密演算法的全部細節。所以尋找密鑰也是破解的途徑之一。

二、摘要演算法的破解
對於摘要演算法（也就是我們常說的Hash演算法），則不是這樣了。不是對於這個單向演算法求解一個反函數那麼簡單，因為我們都知道，hash函數是一個多對一的函數，多對一的函數沒有辦法得到一個反函數，所以對於摘要演算法的破解，也不是把所謂的「密文」變成「明文」，數學家都知道這個演算法是不存在的（該特性叫做原象穩固）。對於摘要演算法的破解，往往指的是製造碰撞。碰撞有兩種，一種是針對第二原象穩固的碰撞，就是在已知摘要值的情況下，求解另外一個消息使得該消息的摘要值等於已知摘要值，即已知d=H(m1)，求解m2使得H(m2)=d；另一種是針對碰撞穩固的碰撞，是生成一對摘要值相同的消息，即計算產生m1和m2，使得H(m1)=H(m2)。針對現有摘要演算法的攻擊往往是第二種。

三、更廣泛的破解
另外，破解還有另外一個含義，就是找到一種演算法完成上述的幾種破解，並且這種演算法比窮舉法（對於摘要演算法則是生日攻擊）要快，或者比已有的破解方法要快。這樣子也叫做破解，不過這樣的破解往往對於該演算法的安全性影響不大，比如從原來的複雜度10^80降低到10^72，計算上依然是不可行，但是我們依然稱作被破解了。

四、結論
不可逆演算法（上文所說的單向演算法）就是不可逆的，所以不可逆演算法的破解不是讓他可逆，而是製造碰撞，大家都混淆了破解這個詞在不同語境下的意義。

旗幟鮮明說觀點：沒有其它更好方法！

對稱加密、不對稱加密都是可逆的，唯獨單向哈希演算法是不可逆的，題主說到的不可逆加密演算法應該是專指單向哈希演算法。

為了更好說明問題，先會討論雙向加/解密可逆操作，再來談單向哈希演算法，這樣概念會清晰得多！

先從Cisco配置文件說起，一般配置文件（configure）存放在NVRAM里，當用戶配置用戶名密碼存在配置文件時，通常有三種方式：

A. 明文
B. 密文
C. 哈希

假設密碼的明文是：cisco123，假設此時password-encryption-service是關閉的，當你show memory將會顯示：
A. cisco123
B. 密文
C. 哈希

密文生成機制
B使用DES/3DES/AES對稱加密演算法，使用自己hardcoding的密鑰（key）來加密/解密
加密演算法如下：
Encryption( cisco123 + key) ---&> 密文

解密演算法如下：
Decryption( 密文 + key) ---&> cisco123

哈希生成機制
C使用MD5/SHA做單向不可逆哈希演算法（消息摘要演算法），哈希演算法如下：
MD5（cisco123) ---&> 哈希（128位）
SHA1（cisco123) ---&> 哈希（160位）
SHA256（cisco123) ---&> 哈希（256位）

所謂單向不可逆是指：可以通過明文cisco123得到哈希值，但是不可以通過哈希值來推導出cisco123。

假設此時用戶登錄此路由器，依據密碼的存放方式也有三種驗證方式：

1.1 密碼明文存放
直接將用戶輸入的密碼與存放的密碼cisco123比較，一致則驗證通過。

1.2 密碼加密存放
有兩種處理方式

1.2.1 將用戶輸入密碼加密處理
Encryption( 用戶輸入密碼 + key) ---&> 用戶密文，然後和存放的密文比較，一致則驗證通過。

1.2.2 將存放密碼解密處理
Decryption( 密文 + key) ---&> cisco123，然後比較用戶輸入的密碼與cisco123，一致則驗證通過。

1.3 密碼哈希處理
先將用戶輸入密碼做單向哈希，假設演算法為MD5，MD5（用戶輸入密碼) ---&> 用戶輸入哈希，然後和存放的哈希比較，一致則驗證通過。

對稱加/解密是可逆的
通過以上例子1.2可以看出，加密/解密是雙向可逆操作，設備可以根據自己的key將加密的密碼解密成明文cisco123，也可以將cisco123加密成密文，一旦這個key泄露，是可以破解密碼的，換句話說，Cisco是可以破解此密碼的。

單向哈希是不可逆的
而1.3是單向不可逆操作，如果配置文件只保存密碼的哈希值，是無法得到用戶的密碼的，為何？因為哈希演算法通過壓縮將原始信息截短了，信息丟失無法復原！cisco也無能為力。

可以用一個例子來形象比喻：大家看小電影，經常會有馬賽克，這個有馬賽克電影就是哈希，如果你想把馬賽克電影還原成原始電影，這是一個不可能完成的任務，因為打碼過程中丟失了很多關鍵信息，熟悉圖像信息處理的同學肯定知道打碼的部分灰度值被平滑了，信息丟失就無法復原。

一旦用戶密碼是以哈希HASH形式保存，連cisco設備都不知道你的原始密碼是什麼（假定只保存hash值），cisco也無法破解你的原始密碼（假定夠長、夠複雜）

如何破解單向哈希？
針對1.3 的破解，目前常用的做法是：先用密碼的組合，比如生日 + 字典 + 名字 + 數字運行哈希演算法，預先生成一張龐大的彩虹表，如果用戶密碼的哈希不幸置身於彩虹表中，很抱歉的通知你，你被破解了！

如何防範密碼被破解？
2.1不要使用字典辭彙做密碼
2.2 不要使用生日做密碼
2.3 要使用特殊字元
2.4 密碼要複雜，有大小寫、特殊字元、英文字母、數字
2.5 密碼要夠長，這是最最關鍵的，曾經聽說德國人輸入128位長的密碼，輸入時間為5分鐘

哈希演算法的特點
以MD5為例，

MD5（Message) ----&> Digest (128 bit)

消息可以是任意長度，這意味著輸入參數（message）是無限的，而輸出（Digest）是有限的，儘管是128bit，數量也很驚人，但以有限輸出對無限的輸入，這本身就不可逆。

根據message 可以得到特定的Digest，但根據Digest卻不可以得到特定的Message。所以理論上肯定會有海量的不同Message產生相同的Digest，此謂碰撞collision，也意味著演算法破解（Broken）。

哈希演算法的破解
針對MD5的破解，是預先用Message生成海量的Digest，然後拿需要破解的Digest來比對，比對上了就可以知道其message了。

你問的問題用不同的斷句可以得到兩個不同的問題。

第一個是：理論上來說，不可逆演算法能通過窮舉法之外的方法破解么？答案應該是：不知道。目前沒有確定性的方法驗證演算法是否可逆。一般認為久經考驗的加密演算法比較成熟，應該很難被破解。

第二個是：理論上不可逆的演算法，能通過窮舉法之外的方法破解么？答案自然是不能。能在理論上被證明不可逆的演算法是極少的，而據我所知，這些演算法能被證明理論上不可逆，是因為被證明即使使用窮舉法也不能攻破，比如最著名的一次一密演算法。

所謂不可逆演算法，就是一個不可逆運算的運算，一個演算法不可逆，那麼就不可能通過其結果得知輸入。譬如說f(x)=x*0|x是實數就是一個不可逆的運算，對於任何x而言，其結果都是0，你無法通過這唯一的結果0推斷x是什麼。

所以，不可逆演算法不存在破解的可能，也不能用於加密。

至於RSA什麼的，那是非對稱加密演算法，不是不可逆演算法。

針對 @王林的答案：

不可逆演算法的驗證也是單向的，所以只要有非蠻力的碰撞機制，即為破解。比如 @王林提出 f(x) = 0*x 的不可逆演算法在信息安全里沒有任何用途。普通的 hash 演算法，比如 Java String 的 hashcode 可以很容易找到碰撞，都視為破解。

另一方面，找到「有實質意義」的碰撞比單純的碰撞更難。所以不可逆演算法作為防篡改工具是比較安全的。但是作為驗證信息（比如 password），僅憑不可逆演算法是絕對不可以的。必須配合強 access control。甚至 AC 是主要方面。

http://en.wikipedia.org/wiki/Collision_resistance
Cryptographic hash functions are usually designed to be collision resistant. But many hash functions that were once thought to be collision resistant were later broken. MD5and SHA-1 in particular both have published techniques more efficient than brute force for finding collisions.

存在啊，MD5就被破解了。因為存在生日攻擊和不動點所以MD5的破解複雜度沒有設計的那麼高。
實際上密碼學就是設計一套代數結構，如果代數結構符合有一些特點就能用來加解密，也可以簽名。

問的不可逆的密碼更多的是只有加密沒有解密的演算法。這樣有很多。比如哈希。

我理解問的問題是：「是否存在一套安全性的證明能夠證明密碼系統只存在窮舉的解？」
也就是「這個密碼系統理論上是否是一個NP問題？」和「實際操作上也只有窮舉的解？」

在實際上就是NP問題我也能夠找到方法來解決。比如圖同構問題是一個NP問題，計算複雜度是o(n!)，通過排序就能降低裡面的複雜度，但是一定可以降低嗎？未必。

最安全的密碼演算法在香農博士的論文中已經有了，一次一密。這個只能通過窮舉攻擊。
密文程度l,隨機數長度l，對明文異或，只有隨機數是真隨機數那麼只有通過窮舉才能得到答案。

加密演算法不可逆，要它何用

我剛好是信息安全專業的。我只能簡單回答一下，因為我數學不是太好。
是有其他的方法的，但是破解能力是有限的。比如利用差分密碼攻擊可以破解DES，還有一些其他手段如線性密碼分析等等。這些方法都很精巧，而且數學成分很多，所以我只試過差分密碼攻擊，沒有嘗試過其他手段，太複雜。
建議找本密碼學的書來看，都有講。

補充：我不同意paradisor的觀點。
也許是我的知識量不夠，但是按照我目前學到的，我的反駁如下：

第一條，「目前沒有確定性的方法驗證演算法是否可逆」，不可逆的定義是：正向計算是簡單的，逆向計算是困難的。現代密碼學與以往不同，古代的密碼學更多的是藝術而非技術，而現在密碼學包含更多的數學成分。比如RSA演算法是建立在「大素數乘積」[註解1]這一數學問題上的，而大素數乘積這一數學問題，理論上就是不可逆的。再比如數字簽名方案，以Diffie-Hellman密鑰交換演算法為例，是建立在有限域的離散對數問題上[註解2]的，同樣是數學上不可逆的問題。而著名的DES，雖然不是建立在數學上難解問題之上，但是經過移位以及S盒擴散[註解3]等作用，在實際使用中證明也是可靠的。當然現代計算機速度越來越快，窮舉法已經威脅到了DES生存。另外，上述我所說的差分密碼攻擊，對DES也很有效，這就是為什麼，AES會成為取代DES的新標準。

第二條，「理論上不可逆的演算法，能通過窮舉法之外的方法破解么？答案自然是不能。」您低估了那些數學家的能力。理論上不可逆的問題，比如我第一條所說的「數字簽名方案」，以EIgamal協議為例，雖然數學上很精巧，但是仍然是有攻擊和偽造的方法的，詳細可見EIgamal的論文--「A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms ElGamal」。又如MD5哈希演算法，也已經被王小雲破解[註解4]。您說的「一次一密方案」[註解5]，這一個是唯一一個理論上絕對安全不可破解的演算法，但是現實中是不可用的，因為開銷太大。

總結一下，paradisor所說的理論上不可逆，定義過於狹隘，您認為的理論上不可逆，就是理論上絕對不可破解。理論上不可逆，僅僅是指在數學上或者是在實際中是一個難解的問題。正如我第一條中所說，不可逆是指「
正向計算是簡單的，逆向計算是困難的。」，僅僅是指困難的，而非絕不可能。所以，理論上不可逆的演算法，經過一段時間，也許就能用其他方法破解。而且，密碼學在實際應用中，並不追求理論上不可逆，僅僅要求實際中可用，當破解一個密碼所消耗的資源（包括時間，金錢，計算資源）超過破解密碼所得到的利益的時候，這個演算法就是好的，可用的。

註解1：大素數乘積問題。兩個很大的素數p,q, 計算n=p*q是容易的，但是知道n值，分解成p和q是困難的。
註解2：有限域的離散對數問題。簡單來說，y=a^x, 知道a, x計算y是容易的，但是知道a, y,通過公式x=loga(y)來計算x是困難的。有限域的定義不在這裡解釋，詳情google之。
註解3：移位以及S盒變換。是DES加密過程中重要的步驟，目的在於加強密文的混淆性和擴散性。詳細參見DES加密流程，太複雜，這裡說不清楚。
註解4：MD5哈希演算法。hash演算法是將一段大的文字映射成一段小的文字，比如500字的文字，用某種方法提出100字作為摘要，以後可以用這100字的摘要驗證這500字有沒有錯誤。但是500字映射成100字，根據「鴿巢原理」，500字的組合數目要大於100字的組合數目，必然有些「明文」（稱呼不準確）計算出的hash值是相同的，也就是會「碰撞」。王小雲已經找到了MD5的碰撞方法，能通過hash值快速得出明文，也就是找到碰撞。但是，她找到的明文，並不一定是原先的明文，但是仍然可以驗證通過。
註解5：一次一密方案。很容易理解，每次加密完，換一個密碼本，別人拿不到密碼本，而且每次都會變化，當然是絕對安全的。

問題不對，加密演算法不可逆要他何用？我的理解是：1.大整數分解，離散對數，橢圓曲線類，只能暴力破解；2.散列函數，只能暴力破解。如果有別的方法，那可是個大新聞。

理論上用窮舉法也沒法解決md5吧。如果我沒記錯，一個MD5字元串理論上對應無視個值。
(如果我記錯了，請指正，謝謝)

1. 舉個摘要演算法的例子，可能不太恰當。
f(x)=0
讓你破解x到底是多少，鬼才知道。
2. 再舉個加密演算法的例子
f(x)=x
讓你破解x到底是什麼。
大概就是這個意思，只是現實中f會複雜一些。

第一不可逆的是摘要，不是加密
第二摘要除了窮舉好像目前沒有方法能還原原文。。。。

不可逆就不算加密演算法，摘要演算法或許可以找到碰撞，但恢復原文不太現實。現在很多摘要演算法都經過高次迭代，窮舉在計算量上也是不可行的。

如果你指的是摘要生成演算法，那真的沒有絕對的安全不可破解的方案，就像md5在一段時間內也沒人能破解但是最後還是被王教授破解了，或者不是完全意義上的破解，她的破解是有條件的，說不定未來的某一天，sha1就被破解了。
密碼學本來就是一個不斷改進不斷破解的過程，從古至今都是，如果有人能夠證明某個密碼無法破解，密碼學的發展就，，呵呵了。
現在很多所謂的無法破解是基於數學難題的，但不能保證這些難題以後一直是難題。

還真不知道是否有除了窮舉以外的方法來破解。一般都是窮舉產生衝撞吧--鴿巢原理。可以諮詢一下王小雲教授