Rsa

當消息是模數時,如何在 RSA 選擇的密文攻擊中解密消息?

  • August 24, 2020

在選定密文攻擊的解密的最後階段,我們沒有使用這個等式

$$ 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 $ .

引用自:https://crypto.stackexchange.com/questions/83495