RSA 簽名 - 存在偽造和消息前綴問題。這是一個奇怪的
我是新手。請善待。我有一個理論上的問題，我想檢查一下：
Bob 和 Alice 在沒有散列函式的情況下進行 RSA 簽名——只是輸入一條消息，然後取出一個簽名。
Bob 和 Alice 相互發送的消息是隨機數。
在不涉及雜湊函式的情況下，攻擊者可以創建帶有他們想要的簽名的消息。但他們無法控制資訊。
然而，由於 Bob 和 Alice 相互發送隨機數，該攻擊者可以創建一個看起來有效的消息。也就是說，一個看似隨機的數字上的有效簽名。
但是 Bob 和 Alice 想讓這個方案安全，所以他們在他們的消息中添加了一個已知的前綴。他們增加了一些結構。
因此，而不是消息看起來像：484262 它看起來像：prefix_484262
這是我想要檢查理智的事情：
通過添加已知前綴，攻擊者只能通過暴力破解來偽造消息，因此該方案的安全性與前綴長度成正比。
也就是說，前綴的長度很重要。例如，如果前綴只有一個八位字節，那麼攻擊者可能只需要大約 255 次嘗試就可以偽造一條有效的消息。但是，如果前綴是兩個八位字節，攻擊者將需要 65,536 次嘗試。
我要檢查的另一件事是：
知道前綴並不是暴力強制消息的優勢（除了攻擊者知道輸出需要看起來像什麼的事實）。
謝謝你的幫助。我很感激。
通過添加已知前綴，攻擊者只能通過暴力破解來偽造消息，因此該方案的安全性與前綴長度成正比。
這是我對場景的理解（如果這是不正確的，我所說的將變得無效）：
- Alice（和 Bob）願意計算 $ M^d \bmod n $ , 對於任意消息 $ M $ 只要 $ M $ 有商定的前綴（和秘密 $ d $ , 但公開 $ n $ 和 $ e $ （這是對應於私有指數的公共指數 $ d $ ).
- 您正在考慮的攻擊是盲目的 RSA 攻擊；攻擊者有消息 $ M’ $ 他們想計算 $ M’^d \bmod n $ ， 然而 $ M’ $ 不以前綴開頭。所以，攻擊者所做的是選擇一個隨機值 $ R $ , 計算 $ R^eM’ $ ，並檢查是否恰好有前綴——如果有，他們把它交給愛麗絲，愛麗絲簽名，形成 $ R M’^d $ , 攻擊者分裂 $ R $ 他們贏了。
這種攻擊成功的機率（每次迭代）取決於 $ R^eM’ $ 恰好有前綴，它與前綴長度成正比。
如果是這種情況，那麼，這不是我們需要關注的唯一攻擊。
另一種攻擊是，如果攻擊者找到大量都以前綴開頭的平滑整數，並讓 Alice 為它們“簽名”；平滑整數是只有小因子的整數。如果攻擊者能找到 $ k $ 這樣的平滑整數，每個僅包含第一個 $ k $ 素數，然後（忽略線性方程不獨立的可能性；這可以很容易地通過額外的幾個來解決），攻擊者可以學習這個值 $ p^d \bmod n $ 首先 $ k $ 素數 $ p $ .
攻擊者可以通過多種方式利用這一點，最有可能的方式是改進原始攻擊的搜尋時間：如果我們假設攻擊者可以學習 $ 2^d \bmod n $ ，然後他們可以測試 $ 2^z M’ $ 對於增加的值 $ z $ ; 對於每個失敗的測試，他們會加倍，這比原來的便宜很多（乘以 $ 2^e \bmod n $ 似乎是最有效的）。