給定足夠多的 RSA 簽名值，是否可以確定公鑰值？
給定足夠多的 RSA 簽名值，是否可以確定需要哪個公鑰來驗證這些值？
是否有足夠的資訊來確定需要哪個密鑰？假設可以猜到公共指數，RSA 方案中是否有任何東西可以檢索模數？
只能考慮使用 PKCS#1 v1.5 填充或 PSS 填充來生成簽名的填充 RSA，而不是原始/教科書 RSA。
這個問題與關於 RSA 加密的相同問題的問題有關。
首先，假設有任何填充，fgrieu對您的相關問題給出的答案仍然有效。您可以通過查看哪些簽名始終（最小）小於模數，將公鑰與簽名相關聯。
第二種方法，正如雨披在您的相關問題的評論和這篇文章的評論中所建議的那樣，巧妙地使用小素數分解來查找 $ N $ . 我把它放在這裡，所以它看起來不會在文章末尾“標記”。這個想法與下面的第三種方法相同，但有一個巧妙的轉折。在哪裡我收集了足夠的樣本以獲得一個不錯的機率，即互質數對 $ t_i $ 值，他建議採取更少的配對併計算所有的 GCD $ t_i $ . 這是 $ \gcd(t_1,…,t_k)=\gcd(r_1N,…,r_kN)=N*\gcd(r_1,…,r_k) $ ， 在哪裡 $ \gcd(r_1,…,r_k) $ 可能是一個足夠小的因素（ $ <2^{128} $ ) 通過可以有效找到小素數的方法（例如ECM ）來分解，從而產生所需的 $ N $ ，作為最大的因素。
第三種方法更專業一些。這基本上是對我之前對類似問題的回答的重新陳述，並且比雨披對您的相關問題的回答更詳細一些，同時站在相似的立場上。
假設
需要假設您有一組消息簽名對，需要假設填充是確定性的（即類似於 PKCS#1 v1.5 的東西）並且公共指數是已知的或可以被暴力破解容易地。
方法
假設您獲得了公共 RSA 指數 $ e $ , 消息簽名對的集合 $ \mathcal S = {(m_1,\sigma_1),…,(m_k,\sigma_k)} $ 和 $ |\mathcal S|=k $ 和填充功能 $ \operatorname{Pad}(m) $ . 請注意，填充函式的知識意味著對模數大小的知識或良好估計。
第一步是將這個問題從一個複雜的填充方案減少到一個簡單的原始 RSA 簽名。為此，我們申請 $ \operatorname{Pad}(m) $ 對每條消息 $ m_i $ 在 $ \mathcal S $ 並替換未填充的 $ m_i $ 帶襯墊的 $ m_i’ $ 對於集合 $ \mathcal S’ $ .
現在觀察，按照正常的驗證過程， $ (m_i’)^e \equiv \sigma_i \pmod N \forall 0<i\leq k $ . 這可以重寫為 $ (m_i’)^e = \sigma_i + r_i * N $ . 據我們所知 $ m_i’, e, \sigma_i $ ，我們可以計算 $ t_i=(m_i’)^e-\sigma_i=r_i * N $ . 現在我們觀察到所有 $ t_i $ 共享一個共同因素： $ N $ ，我們可以通過計算所有的成對最大公約數來恢復（以給定的機率） $ t_i $ . 最小的結果可能是我們的 $ N $ . 對此的花哨的寫作將是： $ N=\gcd(t_1,…,t_k) $ . 一旦我們猜測 $ N $ ，我們可以通過檢查所有簽名是否有效來確認它，即是否所有方程 $ (m_i’)^e\equiv \sigma_i\pmod N $ 抓住。
成功機率
首先要觀察或假設的是 $ r_i $ 是隨機的非零整數。由於它們的體積大（超過 $ 2^{100,000,000} $ )，我們將它們建模為隨機分佈的數字。接下來，我們觀察到我們找到了模數，如果 $ \gcd(r_1,…,r_k)=1 $ 成立，即如果該集合是互質的。當我們隨機建模整數時，我們可以使用標準近似值來表示 $ k $ 隨機整數是互質數，即 $ 1/\zeta(k) $ 在哪裡 $ \zeta(x) $ 是黎曼 zeta 函式。所以我們猜測的機率 $ N’ $ 為了 $ N $ 是正確的，等於所有的機率 $ r_i $ 是互質的，因此：
$$ \Pr[N’=N]=1/\zeta(k) $$ 該公式可用於檢索獲得正確機率所需的對數 $ N $ . 機率在 $ 99.99% $ 和 $ k\geq 14 $ .