借助簽名對 RSA 加密中的密鑰進行逆向工程
考慮以下：
- $ i $ 消息， $ m_i $ , 處於原始狀態。
- $ i $ 消息， $ M_i $ , 加密消息 $ m_i $ 使用公鑰。
- 公鑰， $ p $ ， 在一個 $ b $ -bit RSA 加密設置。我們可以隨時訪問它。
- 密鑰， $ s $ .
- 簽字，簽字人 $ s $ . 我們將其表示為 $ sg $ .
場景是這樣的，我們會收到一條加密的消息 $ M $ ，用於加密的公鑰和消息 $ m $ ，已使用密鑰解密並恢復其原始狀態。我們也有一個簽名，簽名為 $ sg $ .
我明白，簡單地給出 $ m_i $ , $ M_i $ ， 和 $ p $ , 不可能向後工作以獲得 $ s $ . 但是，是否有可能向後工作並獲得密鑰 $ s $ 給定足夠多的相應消息實例？假設我們得到一對消息， $ (m_1, M_1), (m_2, M_2), \ldots (m_n, M_n) $ ，那麼當我們接近某個特定位置時，我們是否會更接近獲得密鑰（或者甚至可能增加我們進行暴力搜尋的機會） $ n $ ? 在那種情況下有多高 $ n $ 我們在談論嗎？
現在考慮我們可以改變 $ n $ 達到我們想要的程度。 $ n \rightarrow \infty $ 本質上，我們已經獲得了 RSA 實現的前端，這樣我們就可以給它一個消息，它會將加密的消息返回給我們，我們想要多少次都不會洩露 $ s $ （明顯地）。在這種情況下，我們能否進行逆向工程 $ s $ ?
我最近了解了非對稱加密，這些問題是更好地理解它的一部分，所以如果有人能提供一些有價值的見解，我將不勝感激！
在 RSA 中，假設知道公鑰但不知道私鑰，分析任意數量的匹配消息、加密消息和簽名的三元組 $ (m,M,sg) $ , 對恢復私鑰沒有幫助（據我們所知） $ s $ （也不是等價物）。這與使用的合理填充或 RSA 變體無關（只要既不填充也不選擇 $ m $ , $ M $ ， 或者 $ sg $ 直接洩漏有關私鑰的資訊，例如在一些真正隨機的填充欄位中，但實際上並非如此）。
事實上，更強有力的假設是，知道公鑰的人也可以暫時使用包含私鑰的黑匣子 $ s=(N,d) $ 允許計算原始 RSA 私鑰函式 $ x\to x^d\bmod N $ 對於任何 $ x $ （這反過來允許解密或簽署任何消息），不（據我們所知）以任何方式幫助找到私鑰，也不分解 $ N $ , 也沒有建立一個獨立於計算原始 RSA 私鑰函式的原始黑盒 $ x\to x^d\bmod N $ 對於隨機 $ x $ 有相當大的機率。
沒有證據證明這一點；證明（或反駁）它是一個開放的研究問題。
注意：正如在另一個答案中指出的那樣，訪問*“RSA 實現的前端，這樣我們就可以給它一個消息，它會返回加密的消息”*顯然沒有幫助，因為可以使用公鑰執行相同的操作, 成本增長慢於 $ O(b^3) $ . 但是，問題提到我們也得到了一些簽名，我們缺乏證據證明這沒有幫助。
我們知道的所有對 RSA 的攻擊：
- 在沒有找到私鑰的情況下解密或簽署消息（僅在不正確使用 RSA 的情況下，例如加密不良或簽名填充）；
- 或從公鑰中找到私鑰（通常通過從公共指數和公共模數的因數計算私人指數 $ N $ ，通過因式分解恢復，因為 $ N $ 太小或其因素選擇不當）；
- 或使用一些資訊洩漏提取/a 私鑰。