如何利用密碼學以及數論基礎攻擊一個「宣稱安全」的密碼系統

最近在對基於區塊鏈構建的信任社會（未來社會形態）非常感興趣，區塊技術去中心化的特性，讓沒有金融機構成為了可能（包括央行，以及各種商業銀行）。

除了在數字貨幣領域大放異彩外，在包括供應鏈，網路購物，公平合約等方面的應用也非常廣泛。其中智能合約的特性十分的吸引我。

不過我今天並不想討論區塊技術，因為區塊技術建立在密碼學的技術之上，今天我們討論如何利用密碼學以及數論基礎攻擊一個宣稱安全的密碼系統。

在密碼學中，演算法，秘鑰以及協議構成了一個完整的密碼系統。

演算法是密碼系統的基礎，它是將一組或多組輸入信息轉化成一組或多組輸出信息的數學方法，演算法的輸出會被秘鑰影響，秘鑰不同，輸出也不同。因此，加密同樣的信息，A用秘鑰Ka加密與B用秘鑰Kb加密輸出的信息是完全不同的。

秘鑰是密碼系統的核心，奧秘在於演算法存在一個最優解（最優解有很多種解釋，例如超遞增序列，因式分解兩素數之和等），這個秘密就是秘鑰。如果一個人想要解密別人的密文，在不知道秘鑰的情況下，他只能嘗試解數學難題，這對於普通人擁有的資源來說，直到宇宙毀滅也無法得出答案。

有了演算法和秘鑰，沒有協議就不是一個密碼系統。協議是指由多方參與的，確定要去完成一些事情。如果沒有多方參與，或者沒有去完成一些目標就不叫協議。協議有很多種，最明顯比如秘鑰交換協議（例如A和B要在一個加密的通道中傳遞信息，在這之前A和B要協商一個秘鑰並交換，使得A可以加密消息發送給B並確保B可以解密信息）。

密鑰交換協議

在一個安全的密碼系統中，必須是演算法，秘鑰，協議都安全，如果其中一個是不安全的，那麼整個系統就是不安全的。

大多數流行的公開演算法，已經被廣泛的證明是安全的，它們經歷過很多理論數學家的分析。秘鑰的安全性由秘鑰長度，以及你是否妥當的保管你的秘鑰來決定。如果你做的不錯，那麼秘鑰也是安全的。

協議卻不是如此了，協議很脆弱。舉個例子，A將重要的信息加密發送給B，只有B有秘鑰可以解密這些信息，C在網路上監聽到了A發送給B的秘密，但是C沒有秘鑰無法解密信息，怎麼辦。上面說過，秘鑰是這個數學難題的最優解，如果沒有秘鑰，C就只能嘗試解數學難題，恐怕C這一生都無法解開，但是C的老闆要求他必須在72小時內解密信息，不然C所在的公司就要遭受重大損失。於是C決定鋌而走險，他綁架了B，並對B進行嚴刑拷打，B扛不住，交出了他的秘鑰，C拿著B的秘鑰解密了秘密，並幹掉了B。

上面的例子說明了協議在整個密碼系統中是一個易攻擊的薄弱環節，這樣的攻擊類型很多（賄賂，美色誘惑，威脅等）。

我們來嘗試把這種攻擊帶入到軟體破解上來，同樣的結論也是攻擊協議，而非攻擊演算法和秘鑰。同樣來舉個例子，軟體D採用RSA公開秘鑰演算法來對用戶的信息以及軟體產品序列號摘要進行加密，併發送給軟體D公司的註冊伺服器，軟體公司D的計算機收到用戶A發送給它的加密信息，用自己的私鑰解密並把用戶信息與資料庫中的信息進行對比，如果序列號不在D公司的資料庫中說明這個產品的不是D公司銷售的產品，如果序列號在D公司的資料庫中，並且A用戶信息不在資料庫中，那麼A是第一次註冊，將A的信息與序列號綁定在一起保存在資料庫中，此序列號將不能再給其他人使用。如果序列號和A都在資料庫中，並且序列號與A綁定，那麼D公司用私鑰加密一段許可信息發送給A，A每次使用D軟體的時候驗證這段信息，如果是D公司發送的許可信息允許使用，如果不是不允許登陸。

看起來很不錯，RSA是安全的公開密鑰演算法，並且秘鑰被D公司保存起來，除非你能賄賂D公司的員工獲得秘鑰，或者攻破D公司的網路，否則秘鑰也是安全的。因此攻擊演算法和秘鑰是不現實的。那麼，我們可以從協議的角度入手，看看有沒有弱點。

先簡單說一下RSA演算法：

• 選擇兩個大素數 p 和 q，假設 p=3，q=11

• 計算 n = p × q = 3 × 11 = 33

• 計算 ∅(n) = (p – 1) × (q – 1) = 2 × 10 = 20

• 選擇 e 且 1 < e < ∅(n) , e 與 n 互為素數. 假設 e = 7

• 計算 d，使 (d × e) % ∅(n) = 1. 假設 d = 3，且 d = (3 × 7) % 20 = 1，滿足條件

• 公開 e, n => (7, 33)

• 保密 d => 3

• 加密公式 C = Me % n

• 解密公式 M = Cd % n

用上面的公式加密，假如消息是2，C = 27 % 33 = 29，密文就是29。解密的話就是M = 293 % 33 = 2。

回到剛才的軟體破解問題上，軟體產品中有e和n，如果能夠分解n我們就能夠構造d，也就知道了D公司的秘鑰，由於分解n是一個數學難題，我們不知道最優解很難解出答案。我們採用另一種方法，破壞協議，首先我們自己選擇2個大素數，構造另一個n，並分別求出對應的e和d。然後我們架設一個伺服器，用來模仿D公司的驗證伺服器。

我們侵入D公司的軟體，用我們自己的n和e替換D公司的n和e，這時軟體D會用我們的公開秘鑰加密用戶信息以及序列號，這段信息是無法送給D公司驗證的，因為D公司沒有我們的保密秘鑰，無法解密信息，因此這樣還無法完成軟體的驗證。

下一步，我們使軟體D將加密好的信息發送給我們剛才架設的模仿D公司的伺服器，這台機器擁有我們的保密秘鑰，它成功的解密信息，並直接構造一個驗證通過的數據塊，並用保密秘鑰加密發送給D軟體。D軟體用我們的公開秘鑰解密信息，驗證一切正常，並將這段信息保存到計算機中。每次D軟體啟動時，重新檢查是否存在驗證通過信息塊，並用我們設給它的公開秘鑰解密，解密成功后通過驗證，啟動D軟體。只要通過一次驗證，D軟體就無需再次與D公司伺服器進行交互，因此完成了破解。

再次說明，演算法，秘鑰，協議是一個密碼系統的組成部分，任何一個方面不安全，整個系統就是不安全的。當下，很多廠商對演算法和秘鑰很關注，在演算法的選擇與秘鑰的長度上下足了功夫。但他們的系統並不像他們想象的那麼安全，因為他們忽視了協議。

PS. 本文僅僅是基於理論方面的討論，真正的軟體破解過程比本文描述的要複雜的多，在real world中嘗試發現n和e可能要困難的多。至於Patch程序代碼，改變程序運行流程來達到破解目的與本文討論的主題無關。

*本文作者：TedZhang，轉載請註明FreeBuf.COM