在 RSA 公鑰中翻轉多少位來進行簽名偽造？
場景：Alice 想要驗證 Bob 的簽名。Alice 知道 Bob 的 RSA 公鑰 (e, n)。然而，Alice 正在從攻擊者 Eve 那裡獲取數據、數據簽名和公鑰。假設簽名符合 PKCS# v1.5。
現在我知道 Eve 可以生成一個 RSA 密鑰對並自己簽署數據並將偽造的公鑰和偽造的簽名發送給 Alice。但我要限制夏娃。Eve 無法生成她喜歡的任何密鑰對。甚至必須翻轉（e，n）。
我的問題：為了偽造簽名，她需要翻轉 (e, n) 的最少位數是多少？
注意：她可以從 Bob 的私鑰生成簽名，或者她可以從她可以從損壞的公鑰或她可以提出的任何攻擊中計算的其他私鑰生成簽名。只要她能說服愛麗絲，簽名就來自鮑勃。
如果夏娃能找到一個 $ n’ $ 這是素數（和 $ n’-1 $ 相對質數 $ e $ ），然後她可以輕鬆地用它簽署任何消息 $ n’, e $ 一對。
所以，問題是：存在素數的機率是多少 $ n’ $ 使得兩者之間只有一位差異 $ n $ 和 $ n’ $ ， 和 $ n’ \not\equiv 1 \pmod {e} $ ? 答案是，如果 $ e > 3 $ ，而且體面，即使 $ e = 3 $ . 我們假設 $ e $ 是素數；在實踐中，幾乎總是如此。
有 $ log_2 n $ 與 有一位差的整數 $ n $ （我們假設 Eve 不能翻轉會增加 $ n $ ); 翻轉位 0 顯然會產生復合；翻轉任何其他位將產生一個奇數。大小約為的“隨機”奇數整數 $ n $ 有一個大約 $ 2/{\log_e n} $ 質數機率；如果我們將每個奇數建模為“隨機”，那麼我們期望大約 $ (\log_2 n - 1) 2/{\log_e n} \approx. 2.89 $ 素數大約有一點翻轉 $ n $ ; 或者，大約有一個機率 $ (1 - 2/{\log_e n}) ^ {\log_2 n - 1} \approx. 0.044 $ 沒有任何值相距 1 位 $ n $ 恰好是素數。當我們包含條件時 $ e $ ， 我們知道 $ n $ 總是滿足條件，所以稍微翻轉的值就有機率 $ 1/(e-1) $ 滿足它；從中，我們可以看到 $ e=3 $ , 我們有一個期望 $ 1.44 $ 滿足它的值（因此我們的機會高於平均水平）；為了 $ e>3 $ ，機率更高。
而且，一旦我們考慮 $ n’ $ 不是素數但很容易因式分解的值（它們是一個大素數乘以平滑數），機率變得更高）