當消息是模數時，如何在 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 $ .