從「教科書式RSA」到「RSA-OAEP」
從「教科書式RSA」到「RSA-OAEP」
密碼學可謂是一個古老的學科,但在區塊鏈誕生之前,密碼學更多停留在公眾的視野之外:無論是學術論文、原型驗證還是已經實用化的工程實現,都更像是小範圍的自娛自樂。區塊鏈行業的發展無形中提高了工業界對密碼學的重視程度,橢圓曲線簽
名演算法ECDSA以及密碼學哈希演算法已經是我們耳熟能詳的了。除此之外,環簽名和零知識證明等經典協議也得以重獲新生,在一些項目中發光發熱。但與此同時,一些項目宣稱使用了一些前沿的密碼學演算法,筆者作為一名學渣,不禁擔心這些演算法的使用是否經過了深思熟慮。本文以RSA演算法的實用化為例,介紹一下密碼學協議在工程實踐中需要考慮的問題以及解決思路,希望對大家有所幫助。
對於教科書式的RSA演算法,阮一峯老師的兩篇文章(RSA演算法原理(一) - 阮一峯的網路日誌,RSA演算法原理(二) - 阮一峯的網路日誌)絕對可以讓一個門外漢短時間內對演算法的原理清楚明白。
圖片來自這裡
藉助阮老師的博文,簡單描述一下RSA演算法。公鑰密碼學演算法一般由三部分組成,即密鑰生成、加密和解密。
RSA演算法的密鑰生成過程如下,其中
- 隨機選擇兩個不相等的質數
?和? - 計算?
- 計算
?的歐拉函數? - 隨機選擇
?,並滿足 ? - 計算?
對於 ?的模反元素?, - 公鑰
?,私鑰?
假設消息明文為?
- 計算
?使得?
解密過程使用私鑰
- 計算?
順便提一句,RSA是一個具有「買一送一」性質的演算法,就是說我們不需要做什麼大的修改,就可以構造出來一個簽名演算法。從上文中我們可以看到,RSA演算法的加密和解密過程可以合併起來,即
那我們如何去衡量這個演算法的安全性呢?這就引出了安全模型這個概念。
我們首先假設這麼一種場景:李雷使用RSA演算法,用公鑰
根據加密過程,我們可以推導出?
那麼,當我選擇一個足夠大的
首先不得不提的一點,RSA是一個確定性的演算法,也就是說,給定密鑰,同樣的明文總是會計算出同樣的密文。假如Jim知道明文大概會是什麼樣的,比如11位的電話號碼,他就可以用少得多的代價,嘗試出所有的明文-密文組合,也就可以在下一次拿到密文的時候,對比出相應的明文。
上面的場景,在Jim可以選擇明文分佈的前提下,如何保證密文不被破解,就構成了密碼學中的「選擇明文攻擊下的語義安全性(semantic security under chosen plain-text attack)」。對上述問題的形式化定義也是前些日子蒞臨浙大的Micali教授早年最重要的貢獻之一。
不僅如此,教科書式的RSA演算法還存在密文可構造的問題。我們假設另一種場景:Jim很狡猾,他不僅可以獲得前面場景提到的信息,還可以發給李雷密文並哄騙李雷幫他解密;當然,李雷也還不算太傻,如果發現Jim發送的密文是自己之前發過的,他就會直接拒絕掉解密的請求。
RSA演算法再一次表示壓力山大,因為這個演算法下的密文是可構造的(malleable):Jim計算?
上面的場景構成了一個更強的安全性假設,即選擇密文攻擊下(chosen cipher-text attack)的安全性。這個場景聽起來似乎有點不切實際,怎麼會有李雷這麼傻的存在?確實,對於客戶端-服務端方式的應用,我們通常會認為攻擊者只能通過監聽雙方的通信,然後試圖獲取通信的內容。但是,如果客戶端也掌握在攻擊者手中呢?即便客戶端是正常工作的,攻擊者也可以通過某些手段來獲取客戶端解密之後的明文,這樣就給攻擊者提供了一種實施上述攻擊的思路,例如對蘋果iMessage的攻擊。
在真實環境中,對密碼學協議實施任何一種攻擊相對來說都是困難的,攻擊者更傾向於去關注代碼層面的漏洞。即便如此,協議的設計者依然有必要去考慮上述問題。類比模塊化地去開發一個軟體時,我們需要考慮自己的模塊應當怎麼處理錯誤,而不是寄希望於使用者只會正確地使用自己的模塊。因此,一個演算法或者協議至少需要滿足上述的語義安全性時,纔可以被認為是實用的。
回到正題,如果要使用RSA演算法,我們首先要將演算法改造為非確定性,具體的做法就是通過「Padding」,就是將明文與某個隨機數組合起來,這樣,明文就被轉移到了一個更大的明文空間上,一定程度上防止了選擇明文攻擊。但這樣還是不夠,隨著選擇密文攻擊被提出,兩千年前後,密碼學界提出了更安全的Padding模式,即RSA-PSS和PSA-OAEP,後者正是PKCS#1 v2中使用RSA的標準方式。感興趣的讀者可以自行去了解一下。
時至今日,RSA依然是應用最為廣泛的一種密碼學演算法,尤其是在互聯網應用中。我們點開Chrome瀏覽器左上角的鎖形圖標,查看網站的證書信息,會發現絕大多數網站依然在使用PKCS#1標準的RSA演算法。RSA作為公鑰密碼學的經典演算法,其實用化過程中的設計思想,是值得我們借鑒並落實在工作中的。
推薦閱讀: