難道不能直接根據公鑰逆運算嗎？

是否可以舉一個知道演算法和運算結果但無法推導出計算前的輸入數值的，且知道結果根據另一演算法可以直接計算出輸入值例子？

我發現對於缺少數學背景的讀者來說，RSA演算法「不能通過公鑰逆運算」這個結論真的很不直觀。所以這道問題我打算另闢蹊徑，不討論已經被說爛的RSA演算法了，而是換個切入點，先從一個異曲同工的，名叫Merkles Puzzles的協議開始講起。

0x01 Merkles Puzzles

與RSA演算法不同，Merkles Puzzles並不是一個公鑰加密演算法，其中並沒有公鑰私鑰這樣的東西存在。Merkles Puzzles是一個密鑰交換協議，可以讓通信雙方分享一小段時效很短的機密信息，這個機密信息可以是對稱式加密的密鑰，也可以是其他用途的數據。

那麼，我為什麼說這個東西和RSA演算法異曲同工呢？因為兩者的內核建立在相似的數學原理之上，最終實現的效果也非常相似。RSA演算法能夠做到「拿到公鑰也算不出私鑰或相應明文」，而Merkles Puzzles能夠做到「拿到所有通信內容也找不出雙方交換的密鑰」。

假定通信雙方分別名為Alice和Bob，兩者之間只有一條已認證(authenticated)但不保密(confidential)的信息通道——即是說，Alice和Bob可以確認信道兩端確實是彼此本人，但是中間可能存在一個竊聽者Eve，能夠竊聽到兩個人分享的一切數據。1974年，Ralph Merkle提出，即使在這種情況下，Alice仍然可以通過Merkles Puzzles協議，分享一枚Eve難以破譯的一次性會話密鑰（One-time Session Key）給Bob，其步驟如下：

  1. Alice生成 [公式] 個可用的會話密鑰， [公式] ，以及 [公式] 個隨機生成的序列號 [公式]，每個序列號與會話密鑰一一對應。
  2. Alice將每對會話密鑰和序列號打包成 [公式] 個謎題（puzzle），令每個謎題 [公式] 具有如下特徵：
    1. 解決謎題 [公式] 需要一定的計算量，比如每道謎題平均需要花1小時才能解決。
    2. 解決謎題 [公式] 後，可以得到兩個值：一個是會話密鑰 [公式] ，另一個是序列號 [公式]
  3. Alice將這些謎題發送給Bob，Bob隨機選擇一個謎題 [公式] 加以解決，並發回相應的序列號 [公式]
  4. Alice根據Bob傳回的序列號，確定通信雙方接下來將要使用的會話密鑰 [公式]

Ralph Merkle沒有限定過協議中的謎題到底應該以何種方式生成，一個比較簡單的方法是利用對稱式加密演算法。假定這個演算法有64位的加密強度，我們可以用一枚隨機生成的密鑰將 [公式] 與 [公式] 加密，然後當場銷毀這枚隨機密鑰。這樣一來，想要解密這道謎題，就需要進行 [公式] 次計算，滿足了Merkles Puzzles所需的條件。

在這個交換過程中，Bob只需要解決一個謎題，Alice只需要進行一次查表，兩名合法用戶可以非常高效的完成密鑰交換。而攻擊者Eve，雖然成功竊聽到所有的謎題，以及Bob傳回的序列號 [公式] ， 然而為了從謎題的汪洋大海當中找到對應的會話密鑰 [公式]，Eve仍然需要解決平均 [公式] 個謎題。

0x02 從 Merkles Puzzles 到 RSA

Merkles Puzzles協議雖然直觀，但是並不實用。因為攻擊者平均只需要解決一半的謎題就能拿到密鑰了，這讓每次密鑰交換的成本變得很高——要麼生成海量的謎題，要麼提高解決謎題所需的計算量。不管是哪種方案，實際操作起來都不太划算。

更加理想的情況是，每當合法用戶的運算量增加時，攻擊者的運算量就跟著指數上漲。這樣我們只需要付出很小的努力，就能打造堅不可摧的城牆了。

經過一段時間的探索之後，密碼學家們找到了一類非常有趣的數學工具——陷門單向函數（Trapdoor One-way Function）。我注意到有其他答主提到了這個概念，而且幾個關鍵點說得很對，但是不知道為什麼定義寫得很模糊，我在這裡給一組更為規範條理的定義：

假定 [公式] 為單向函數，則對於任何一個輸入 [公式] ，我們都可以快速地算出函數值 [公式] （在多項式時間內）；但對於任何一個函數值 [公式] ，我們卻難以快速計算出對應的輸入 [公式] 。

假定 [公式] 為陷門單向函數，則存在一段秘密信息 [公式] ，使得 [公式] 可以被快速地還原為 [公式]，這段秘密信息被稱為陷門（Trapdoor）。

如果要打個比較形象的比方的話，陷門單向函數生成的函數值就好比是一把鎖，而相應的陷門就是開鎖的鑰匙。合法用戶可以使用陷門輕鬆開鎖，而非法用戶就只能依據函數值去硬算。

在Merkles Puzzles協議當中，「會話密鑰和隨機序列號之間的對應關係」扮演的就是陷門的角色。掌握陷門的Alice可以查表直接拿到會話密鑰。而沒有陷門的Eve，只能從浩如煙海的謎題中猜出正確的謎題。唯一的遺憾在於Eve只需要解決一半左右的謎題就能找到答案了，沒有達到理想的防禦強度。

而在RSA演算法中，生成密鑰時所使用的兩個巨大的質數 [公式] 就是它的陷門。題主好奇為什麼不能通過公鑰逆運算出私鑰或者相應明文，其實是可以的，只要你手裡握有陷門你就能算出來。然而在沒有陷門的情況下，你就只能從浩如煙海的質數中猜出正確的那對質數，目前還不存在任何一個經典演算法能在多項式時間內完成這項任務。

當然，說到這裡我不得不強調一點：我們僅僅只是還沒發現能夠快速分解巨大質因數的經典演算法存在，沒有任何證據表明這樣的演算法真的不存在。這個問題目前仍然是學界一個懸而未決的百年難題。

覺得本文有價值的話，歡迎點個贊支持一下。對信息安全感興趣的同學，也歡迎閱讀我寫的其他信息安全科普類文章：

  • 指紋識別/指紋支付安全嗎？
  • CA 機構是如何保護自己私鑰的？
  • SSH是如何防禦重放攻擊的？
  • 如何設計安全且方便記憶的密碼？

在非對稱加密中，使用了「陷門單向函數」，這類函數特點如下：

(1)對 [公式] 的定義域中的每一個 [公式] ，均存在函數 [公式] ，使得 [公式] ；

(2) [公式] 和 [公式] 都容易計算；

(3)僅根據已知的計算 [公式] 的演算法，去找出計算 [公式] 的容易演算法是困難的。

舉個栗子，已知兩個1024 bit位的的大素數，計算他們的乘積相對比較容易；反之如果已知這兩個大素數的乘積，分解出這兩個大素數，就相對困難了，題主可以自己試試。

這類單向函數如果稍加改進，配上「陷門」，就可以拿來用於非對稱加密，沒有「陷門」逆向難以計算，有了「陷門」計算就很方便，典型例子就是RSA，以及離散對數，具體實現網上一查一大把。

如果我製作一把鎖，並大量量產，發到市場上，但不同時配發鑰匙。那麼誰都可以從市場上買到這把鎖，用它鎖東西交給我。我有鑰匙能打開，其他人不能。不算特別準確，但大概就是這樣一個比喻。

難道不能直接根據公鑰逆運算嗎？

可以。不論演算法具體的實現如何，你永遠都有根據加密密鑰推算解密密鑰的方法。最簡單的，如果你知道密文，加密密鑰和加密函數，那麼無論如何，你都可以通過枚舉所有可能明文的密文並進行對比來得到明文。

但是這裡有另外一個問題，時間。

比如說，你要解密的通信是敵軍明天的部署，而你計算出解密密鑰所需的時間是24小時零1秒，那麼解密之後信息就已經沒有用了，這樣的解密你是不會去做的。

所以說，解密密鑰的絕對安全是不重要的，重要的是在信息的時效結束之前，解密密鑰的安全。

比如，你通過某種非對稱加密向銀行伺服器傳輸憑據，攻擊者需要進行10天的運算才能解密出你通信的內容，那麼你只需要每7天修改一次憑據，就可以保證賬戶安全。

而對於目前的演算法來說，10天還是很容易做到的。

p.s.

但是，如果你有什麼信息是即使一萬年之後被看到都不可接受的話，那麼你唯一應該做的事情就是忘掉它。

看過武俠小說嗎？沒看過電視劇總看過吧。

一瓶毒藥，一瓶解藥。毒藥給別人，誰都可以下毒，毫無難度。

但是要解，則必須要有解藥的人才可以。

所謂對稱加密，是同一瓶葯，吃一次中毒，吃第二次解毒；

所謂非對稱加密，就是這樣，不同的葯。

至於為什麼不能從毒藥反推出解藥。。。

因為世界上很多事情，都是單向（或者反向問題難度大大增加）的。

比如殺一個人比救一個人容易，雖然貌似只要將殺的過程反向就可以了，但是容易嗎？

比如下坡比上坡容易，同樣是反向就可以了，但是大多數人估計都能從山頂滾下來但是不見得都爬得上去。

具體到數學：

比如求導數，比求積分容易吧。一個確定的多項式，求導之後只有一個解，而積分出來卻還有一個常數項C，取值範圍是所有實數，你說原來倒底是哪個？

比如給你一個1000位的整數，讓你驗證其是不是質數，這個挺難吧？但是如果讓你找出我手裡的那個一個1000位的質數是哪個，是不是更難？

這就是非對稱加密的原理。

推薦閱讀：
相关文章