當消息是模數時,如何在 RSA 選擇的密文攻擊中解密消息?
在選定密文攻擊的解密的最後階段,我們沒有使用這個等式
$$ c = m \cdot t \pmod n $$
刪除所有指數,如 $ d $ 和 $ e $ 在哪裡 $ c $ 是解密的消息(沒有任何意義), $ t $ 是我們與原始密文相乘的消息, $ m $ 是我們想要的資訊。
如果我們在解密後用這些值替換 $ c=2 $ , $ t=2 $ , $ n=5 $ 例如,我們得到:
$$ 2 = (m \cdot 2) \pmod 5 $$
但在這兒 $ m $ 可以是許多不同的值。可以是 6 也可以是 11: $ (6*2) \bmod 5 = 2 $ . 我的意思是這是一個時鐘,有很多選擇 $ m $ 將給出相同的解密密文輸出。
在選擇密文攻擊中,假設對手可以獲得對手選擇的密碼的解密,而不是目標密碼,此外還可以獲得對手選擇的任何消息的加密(非對稱免費加密)。
最一般的CCA實驗是:
密鑰生成:挑戰者秘密提取密鑰,如果有公鑰,則公開(即用於非對稱加密)
消息選擇和加密:
- 對手選擇消息 $ m_0 $ 和 $ m_1 $ 並將兩者都送出給挑戰者
- 挑戰者隨機抽取 $ b\in{0,1} $
- 挑戰者驗證兩者 $ m_0 $ 和 $ m_1 $ 是有效的(可以被加密),如果它持有加密 $ m_b $ 屈服 $ c_b $ , 套 $ c=c_b $ , 並揭示 $ c $ (與問題無關 $ c, $ ).
互動:挑戰者接受並回答加密和解密查詢,但密文匹配的解密查詢除外 $ c $ .
檢查:對手猜測 $ b $ . 當猜測正確的機率非消失優於選擇密文攻擊時,密碼系統被破壞 $ 1/2 $ .
對於非對稱加密,挑戰者不需要回答加密查詢,因為攻擊者可以使用公鑰輕鬆處理這些查詢。
根據這個定義,沒有確定性加密是 CCA 安全的(論點:對手可以獲得 $ c_0 $ 和 $ c_1 $ 並確定哪些匹配 $ c $ )。對於適用於確定性加密的較弱 CCA 安全概念,必須進行另一項更改。那可以是:
- 挑戰者不回答送出的密文匹配匹配之一的解密查詢 $ c_0 $ 或者 $ c_1 $ (挑戰者需要計算兩者)。
- 或者,只有挑戰者參與消息選擇,變成選擇 $ m $ 這樣加密成 $ c $ 成功。在檢查中,對手猜測 $ m $ , 不是 $ b $ . 並且必須以非零機率正確猜測。
問題是針對非對稱和確定性的教科書 RSA。使用上述第二個選項和一個解密查詢,實驗進行:
密鑰生成:挑戰者
- 繪製一個密鑰對
- 揭示公鑰 $ (n,e) $
- 保密私人指數 $ d $
筆記: $ (n,e,d) $ 是這樣的消息 $ m $ 可以加密的是那些整數 $ 0\le m<n $ ; 他們相應的加密是每 $ c\gets m^e\bmod n $ , 和解密 $ c $ 和 $ 0\le c<n $ 是每 $ m\gets c^d\bmod n $ 或同等學歷。
消息選擇和加密:挑戰者
- 隨機抽取一個整數 $ m\in[0,n) $
- 計算 $ c\gets m^e\bmod n $
- 揭示 $ c $ (與問題無關 $ c, $ ).
互動:挑戰者接受選擇的密文查詢
- 收到 $ \tilde c $ (選擇的密文)由對手送出
- 支票 $ 0\le \tilde c<n $ 和 $ \tilde c\ne c $
- 檢查和破譯 $ \tilde c $ ,即檢查 $ 0\le \tilde c<n $ 然後在肯定的計算和揭示 $ \tilde m={\tilde c}^d\bmod n $ (這個 $ \tilde m $ 是問題的 $ c, $ ).
檢查:對手猜測 $ m $ . 當猜測對非消失機率正確時,密碼系統在選擇密文攻擊下被破壞。
在教科書 RSA 中進行這種攻擊的標準方法是攻擊者
- 選擇一些 $ t $ 在 $ [2,n) $ 和 $ \gcd(t,n)=1 $ ,例如 $ t=2 $ 或者 $ t=n-1 $
- 計算 $ s=t^e\bmod n $
- 計算並送出 $ \tilde c=c\cdot s\bmod n $
- 獲得 $ \tilde m $ 來自挑戰者
註:來自 $ \tilde c=c\cdot s\bmod n $ 它遵循 $ {\tilde c}^d\equiv(c\cdot s)^d\pmod n $ (通過提高指數獲得 $ d $ ), 因此 $ {\tilde c}^d\equiv c^d\cdot s^d\pmod n $ , 因此 $ \tilde m\equiv m\cdot(t^e)^d\pmod n $ (因為解密適用於 $ m $ 和 $ \tilde m $ ), 因此 $ \tilde m\equiv m\cdot t\pmod n $ (因為解密適用於 $ t $ ).
- 解決了 $ m $ 和 $ 0\le m<n $ 方程 $ \tilde m\equiv m\cdot t\pmod n $ (在問題中是等式 $ c = m \cdot t \pmod n, $ ),並將結果作為恢復送出 $ m $ .
在後面的步驟中,對手計算乘法逆 $ t $ 模組 $ n $ , 那是一些整數 $ t’ $ 這樣 $ t\cdot t’\equiv1\pmod n $ . 這是可能的,因為 $ \gcd(t,n)=1 $ . 一種方法使用擴展歐幾里得算法。什麼時候 $ t=2 $ (分別。 $ t=n-1, $ ), 我們可以用 $ t’=(n+1)/2 $ (分別。 $ t’=n-1, $ ).
然後 $ \tilde m\equiv m\cdot t\pmod n $ 變成 $ \tilde m\cdot t’\equiv(m\cdot t)\cdot t’\pmod n $ , 因此 $ \tilde m\cdot t’\equiv m\cdot(t\cdot t’)\pmod n $ , 因此 $ \tilde m\cdot t’\equiv m\cdot1\pmod n $ , 因此 $ \tilde m\cdot t’\equiv m\pmod n $ .
因此,對手總是發現 $ m $ 通過計算唯一定義的 $ m=\tilde m\cdot t’\bmod n $ (見最後的符號)。
批判性地回答這個問題,幾個之間沒有猶豫 $ m $ 因為
- 已知挑戰者選擇了有效消息 $ m $ ,因此 $ 0\le m<n $
- 一個解法 $ m $ 至 $ \tilde m\equiv m\cdot t\pmod n $ 存在並且都是全等模 $ n $ ,因為一個解決方案 $ t’ $ 至 $ t\cdot t’\equiv1\pmod n $ 存在並且都是全等模 $ n $ ,因為對手選擇了 $ t $ 和 $ \gcd(t,n)=1 $ , 因此 $ t\bmod n $ 屬於模數乘法群 $ n $
- 什麼時候 $ y $ 是一致的 $ x $ 模組 $ n $ ,也就是當 $ y\equiv x\pmod n $ , 附加條件 $ 0\le y<n $ 使 $ y $ 由唯一定義 $ (n,x) $ .
表示法:對於整數 $ n>0 $ 和整數 $ x $
- $ y\equiv x\pmod n $ 意思是 $ n $ 劃分 $ x-y $ . 這最好讀為: $ y $ 是一致的 $ x $ (短暫停頓)取模 $ n $ . 可以寫
y = x (mod n)
。- $ y=x\bmod n $ 意思是 $ n $ 劃分 $ x-y $ , 和 $ 0\le y<n $ . 這可以讀作: $ y $ 是 $ x $ 模組 $ n $ . 這樣的整數 $ y $ 為給定的唯一定義 $ (n,x) $ . 那 $ y $ 是歐幾里得除法的餘數 $ x $ 經過 $ n $ 什麼時候 $ x\ge0 $ .