為什麼只能使用簽名者的公鑰對 RSA 簽名進行身份驗證？
我是一名本科數學學生，目前正在學習密碼學課程。我有一個關於 RSA 簽名認證機制的問題。
可以使用簽名者的公鑰對 RSA 簽名進行身份驗證。但是，我想知道為什麼它只能使用簽名者的公鑰進行身份驗證。為什麼不能用別人的公鑰錯誤地進行身份驗證？
讓我用一個例子來澄清一下。假設兩個人使用隨機文本[p1Math Processing Error]和[p2Math Processing Error]為他們的簽名。他們的私鑰是 $ p_1 $ $ p_2 $ $ d_1 $ 和[d2Math Processing Error]分別是，它們的公鑰是 $ d_2 $ $ (e_1,n_1) $ 和 $ (e_2,n_2) $ 分別。所以，第一個人的簽名是
[數學處理錯誤] $ s_1 = {p_1}^{d_1} \mod n_1 $
現在，我理解這個簽名可以用第一個人的公鑰驗證的數學，即
[數學處理錯誤] $ {s_1}^{e_1} \mod n_1 = p_1 $
但是，我們怎麼能聲稱以下內容永遠不正確呢？
[數學處理錯誤] $ {s_1}^{e_2} \mod n_2 = p_2 $
使用誠實生成的 RSA 密鑰隨機發生這種“衝突”的可能性極低。從數學上證明斷言可能令人厭煩，但想法如下：
讓 $ s $ 是一個 RSA 簽名，即大小的整數 $ k $ 一些位 $ k $ （例如 $ k = 2048 $ ）。我們考慮 RSA 密鑰 $ (n,e) $ 在哪裡 $ n $ 是模數（大小 $ k $ 位）和 $ e $ 是公共指數，大小 $ r $ 位（實際上大多數人使用 $ e = 65537 $ ， IE $ r = 17 $ ; Windows 的 CryptoAPI 無論如何都不能容忍超過 32 位的公共指數）。我們想估計機率 $ s^e = m \pmod n $ .
如果 $ s^e = m \pmod n $ 然後 $ n $ 劃分 $ s^e-m $ . $ s^e - m $ ，作為一個整數，大小大致 $ k2^r $ 位。該整數不能超過[Math Processing Error] $ 2^{r+1} $ 大小的不同主要因數[Math Processing Error] $ k/2 $ 位。即使 $ s^e-m $ 確實是[Math Processing Error] $ 2^{r+1} $ 大小不同的素數[Math Processing Error] $ k/2 $ 位，那麼只有大約[Math Processing Error] $ 2^{2r+1} $ 兩個這樣的素數的不同乘積 $ s^e-m $ . 換句話說，與 $ k = 2048 $ 和給定的 32 位指數[數學處理錯誤] [265數學處理錯誤] [n數學處理錯誤] $ e $ ，那麼最多可以有大約 $ 2^{65} $ （實際上更少）模值 $ n $ 這樣 $ s^e = m \pmod n $ . 不過大致有 $ 2^{2048-20} = 2^{2028} $ 可能的 2048 位 RSA 模數（兩個 1024 位素數的乘積），這個值要大得多。因此，碰撞的機率非常低。
如果我們允許公共指數很大（ $ r = 2048 $ ) 那麼答案就不那麼簡單了，因為上面的計算將產生最大匹配模數約 $ 2^{4097} $ ，這是完全誇大的，實際上是不可能的。事實上，對於給定的 $ e $ , 整數 $ s^e-m $ 將很大並且可能被認為是“典型的”，因為它在素因數中的因式分解將使用各種大小的因數。Hardy-Ramanujan 定理告訴我們，一個整數的大小 $ k2^r $ 比特將是平均的乘積， $ \log r $ 不同的素數，產生 $ (\log r)^2 $ 可能的匹配模數。這導致與之前相同的結論，儘管假設為 $ s^e-m $ 就因式分解而言，是“典型的”。
以上是隨機碰撞。但是，我們可以問問自己，這種情況是否可以被強迫。事實證明這是可以做到的。也就是說，考慮一條消息[數學處理錯誤] [s數學處理錯誤] $ m $ （填充雜湊值）和簽名 $ s $ 使用密鑰對生成 $ (n,d,e) $ . 我們有 $ s^e = m \pmod n $ 和 $ s = m^d \pmod n $ .
現在，拿[數學處理錯誤] [m數學處理錯誤] $ m’ $ （另一條消息，或與 $ m $ ，它在這兩種情況下都有效）。然後可以計算一個新的 RSA 密鑰對 $ (n’,d’,e’) $ 這樣[數學處理錯誤] $ s^{e’} = m’ \pmod {n’} $ ，這可以用 $ s $ 和 $ m’ $ 單獨（對原始密鑰對一無所知）。構想如下：選擇隨機小素數[數學處理錯誤] [ei數學處理錯誤] [sei=m′(modpi)數學處理錯誤] [pi數學處理錯誤] [pi數學處理錯誤] [n′數學處理錯誤] $ p_i $ ; 對於每個小素數，計算 $ e_i $ 這樣 $ s^{e_i} = m’ \pmod {p_i} $ . 這是一個離散對數，如果 $ p_i $ 是小。一旦你有足夠的 $ p_i $ , 計算 $ n’ $ 作為他們的產品。公共指數 $ e’ $ 那麼是這樣的 $ e’ = e_i \pmod {p_i-1} $ 對全部 $ i $ ， 所以 $ e’ $ 很容易用中國剩餘定理重新計算。那時，你有 $ n’ $ 和 $ e’ $ , 你知道質因數分解 $ n’ $ , 所以計算私鑰[數學處理錯誤] $ d’ $ 很簡單。
當然，這會產生一個相當奇怪的 RSA 密鑰： $ n’ $ 是小素數的乘積（但這要等到有人真正嘗試分解後才能看到 $ n’ $ ）， 和 $ e’ $ 很大（遠大於 32 位）。類似的結構是否可以在保持 $ e’ $ 小不為人知。上面關於隨機碰撞的討論告訴我們，“從道德上講”，針對一個小 $ e’ $ 應該很難。事實上，如果我們針對一個固定的 $ e’ $ ， 然後 $ n’ $ 必須是其中之一 $ (\log r)^2 $ （最多）可能的值；因為我們應該以 $ (n’,d’,e’) $ , 那麼這意味著這個重建產生了部分因式分解[數學處理錯誤] $ s^{e’}-m’ $ ，而且我們知道整數分解很難（確實，RSA 依賴於它）。
另一種查看方式如下：嘗試建構時 $ (n’,d’,e’) $ , 我們實際上是在尋找[數學處理錯誤] [e′數學處理錯誤] $ s^{e’}-m’ $ 這樣他們的產品就具有適合 RSA 模數的大小；如果我們被允許改變，我們可以這樣做 $ e’ $ 和/或 $ m’ $ 以便[數學處理錯誤] [e′數學處理錯誤] [m′數學處理錯誤] [e′數學處理錯誤] [m′數學處理錯誤] $ s^{e’}-m’ $ 很容易分解。越多 $ e’ $ 和 $ m’ $ 受到約束，問題變得越困難。如果 $ e’ $ 和 $ m’ $ 是固定的，那麼問題似乎就像破解 RSA 一樣難。問題何時達到“不可行門檻值”尚不得而知。
有關此主題的更長處理，請參閱本文。底線：數字簽名對給定公鑰的**消息產生保證，而不是相反。
我不記得有人聲稱：
$ s_1^{e2} \bmod n_2 = p_2 $
從來都不是真的。但是，只有一個值[數學處理錯誤] $ s_2 = p_2^{d_2} \bmod n_2 $ ; 如果該值恰好是該值，那將是一個相當奇怪的巧合 $ s_1 = p_1^{d_1} \bmod n_1 $