從「教科書式RSA」到「RSA-OAEP」

1 人贊了文章

密碼學可謂是一個古老的學科，但在區塊鏈誕生之前，密碼學更多停留在公眾的視野之外：無論是學術論文、原型驗證還是已經實用化的工程實現，都更像是小範圍的自娛自樂。區塊鏈行業的發展無形中提高了工業界對密碼學的重視程度，橢圓曲線簽

名演算法ECDSA以及密碼學哈希演算法已經是我們耳熟能詳的了。除此之外，環簽名和零知識證明等經典協議也得以重獲新生，在一些項目中發光發熱。但與此同時，一些項目宣稱使用了一些前沿的密碼學演算法，筆者作為一名學渣，不禁擔心這些演算法的使用是否經過了深思熟慮。本文以RSA演算法的實用化為例，介紹一下密碼學協議在工程實踐中需要考慮的問題以及解決思路，希望對大家有所幫助。

對於教科書式的RSA演算法，阮一峯老師的兩篇文章（RSA演算法原理（一） - 阮一峯的網路日誌,RSA演算法原理（二） - 阮一峯的網路日誌）絕對可以讓一個門外漢短時間內對演算法的原理清楚明白。

圖片來自這裡

藉助阮老師的博文，簡單描述一下RSA演算法。公鑰密碼學演算法一般由三部分組成，即密鑰生成、加密和解密。

RSA演算法的密鑰生成過程如下，其中 \% 為取模運算， gcd ?為最大公約數：

  1. 隨機選擇兩個不相等的質數 p ?和? q
  2. 計算? n=p imes q
  3. 計算 n ?的歐拉函數? varphi(n)=(p-1)(q-1)
  4. 隨機選擇 ein (1, varphi(n)) ?，並滿足 ? gcd(e,varphi(n))=1
  5. 計算? e 對於 varphi(n) ?的模反元素?， ecdot dequiv 1 (mod varphi(n))
  6. 公鑰 pk=(n,e) ?，私鑰? sk=(n,d)

假設消息明文為? m ，加密過程使用公鑰? pk ：

  1. 計算 c ?使得? m^eequiv c (mod n)

解密過程使用私鑰 sk ?：

  1. 計算? c^d equiv m (mod n)

順便提一句，RSA是一個具有「買一送一」性質的演算法，就是說我們不需要做什麼大的修改，就可以構造出來一個簽名演算法。從上文中我們可以看到，RSA演算法的加密和解密過程可以合併起來，即 {(m^e)}^d=m^{ed}=m ?，對於一個加密演算法，我們希望只有私鑰持有者可以解密，而對於簽名演算法，我們則希望公鑰持有者可以解密。於是我們只交換? d 和 e ?的順序（上面的式子顯然成立），就又得到了一個簽名演算法。

那我們如何去衡量這個演算法的安全性呢？這就引出了安全模型這個概念。

我們首先假設這麼一種場景：李雷使用RSA演算法，用公鑰 (n,e) ?加密了一段明文；Jim擁有這個公鑰，也知道密文，但卻沒有私鑰；Jim想要知道明文是什麼。參考前面對演算法的描述，上面的場景可以描述為，Jim已知? (n,e) 和? c ，想要知道 m ?。

根據加密過程，我們可以推導出? m=c^{e^{-1} mod varphi(n)} mod n ?，於是問題轉化為瞭如何解出? varphi(n) 。由密鑰的生成過程我們可知，計算 n ?的歐拉函數 varphi(n) ?，最快的方式就是將? n 分解為兩個大質數 p ?和? q ：這個問題也被稱為RSA問題。在?足夠大的前提下，RSA問題被證明是一個難題，也就是不存在一個多項式複雜度的演算法可以解決該問題，參考這裡。

那麼，當我選擇一個足夠大的 n ?，比如長度為2048個比特位（這也是目前推薦的長度），演算法是不是就足夠安全了呢？

首先不得不提的一點，RSA是一個確定性的演算法，也就是說，給定密鑰，同樣的明文總是會計算出同樣的密文。假如Jim知道明文大概會是什麼樣的，比如11位的電話號碼，他就可以用少得多的代價，嘗試出所有的明文-密文組合，也就可以在下一次拿到密文的時候，對比出相應的明文。

上面的場景，在Jim可以選擇明文分佈的前提下，如何保證密文不被破解，就構成了密碼學中的「選擇明文攻擊下的語義安全性（semantic security under chosen plain-text attack）」。對上述問題的形式化定義也是前些日子蒞臨浙大的Micali教授早年最重要的貢獻之一。

不僅如此，教科書式的RSA演算法還存在密文可構造的問題。我們假設另一種場景：Jim很狡猾，他不僅可以獲得前面場景提到的信息，還可以發給李雷密文並哄騙李雷幫他解密；當然，李雷也還不算太傻，如果發現Jim發送的密文是自己之前發過的，他就會直接拒絕掉解密的請求。

RSA演算法再一次表示壓力山大，因為這個演算法下的密文是可構造的（malleable）：Jim計算? cequiv c cdot 2^e mod n ，並發送給李雷；參考上面的式子，李雷解密之後，Jim就得到了 2m ?，演算法的安全性可謂是蕩然無存。密文的可構造性容易造成很糟糕的後果，例如對AES-CBC的攻擊。

上面的場景構成了一個更強的安全性假設，即選擇密文攻擊下（chosen cipher-text attack）的安全性。這個場景聽起來似乎有點不切實際，怎麼會有李雷這麼傻的存在？確實，對於客戶端-服務端方式的應用，我們通常會認為攻擊者只能通過監聽雙方的通信，然後試圖獲取通信的內容。但是，如果客戶端也掌握在攻擊者手中呢？即便客戶端是正常工作的，攻擊者也可以通過某些手段來獲取客戶端解密之後的明文，這樣就給攻擊者提供了一種實施上述攻擊的思路，例如對蘋果iMessage的攻擊。

在真實環境中，對密碼學協議實施任何一種攻擊相對來說都是困難的，攻擊者更傾向於去關注代碼層面的漏洞。即便如此，協議的設計者依然有必要去考慮上述問題。類比模塊化地去開發一個軟體時，我們需要考慮自己的模塊應當怎麼處理錯誤，而不是寄希望於使用者只會正確地使用自己的模塊。因此，一個演算法或者協議至少需要滿足上述的語義安全性時，纔可以被認為是實用的。

回到正題，如果要使用RSA演算法，我們首先要將演算法改造為非確定性，具體的做法就是通過「Padding」，就是將明文與某個隨機數組合起來，這樣，明文就被轉移到了一個更大的明文空間上，一定程度上防止了選擇明文攻擊。但這樣還是不夠，隨著選擇密文攻擊被提出，兩千年前後，密碼學界提出了更安全的Padding模式，即RSA-PSS和PSA-OAEP，後者正是PKCS#1 v2中使用RSA的標準方式。感興趣的讀者可以自行去了解一下。

時至今日，RSA依然是應用最為廣泛的一種密碼學演算法，尤其是在互聯網應用中。我們點開Chrome瀏覽器左上角的鎖形圖標，查看網站的證書信息，會發現絕大多數網站依然在使用PKCS#1標準的RSA演算法。RSA作為公鑰密碼學的經典演算法，其實用化過程中的設計思想，是值得我們借鑒並落實在工作中的。


推薦閱讀：
查看原文 >>
相關文章