分解安德森的 RSA 後門
1993 年，安德森
$$ 1 $$提出了 RSA 密鑰生成算法的後門。這個後門需要一個後門密鑰（prime） $ A $ 植入 RSA 算法的密鑰生成部分。 而不是通常的方式，素數 $ P $ 和 $ Q $ 使用以下算法生成：
首先定義一個後門素數 $ A $ 和兩個較小的隨機素數 $ P’ $ 和 $ Q’ $ .
讓 $ k=1 $
$ \text{If} \ \ isprime(A\cdot k + P’):\ \quad P = A\cdot k + P’ \ \text{else}: k = k+1 $
模擬執行 $ Q $ 使用 $ Q’ $ .
這裡也描述了這個算法。關於這個 RSA 後門還有更多資訊嗎？
這個後門允許計算 $ N′= N \mod A $ 然後因素 $ N′ $ 進入 $ P′ $ 和 $ Q′ $ . 仍然 $ N’ $ 需要考慮，但現在這是一個更容易的問題，因為 $ N’ $ 只有大約四分之一的大小 $ N $ .
請注意，在我上面的算法中，我使用了 $ k=1 $ ，安德森的原始實現建議起始值 $ k=P’ $ 並且不斷增加 $ k $ 一個直到 $ P $ 是素數。在我的算法中，我從 $ k=1 $ .
我的問題是：
- 確實從 $ k=1 $ 代替 $ k=P’ $ 做出改變？
- 順便說一句 $ N’ $ 生成，什麼是最好的分解方式 $ N’ $ 給出的資訊是如何產生的？是否有某種分解算法可以進行分解 $ N’ $ 很容易？
$$ 1 $$羅斯·安德森。實用的 RSA 陷門。電子信件。29（11）：995，1993。
- 確實從 $ k=1 $ 代替 $ k=P’ $ 做出改變？
如果您從 $ k=P’ $ 然後你得到;
$$ P = A\cdot (P’+i) + P’ $$ 在哪裡 $ i = 0,1,2,\ldots $ . 取模 $ A $
$$ P = A\cdot (P’+i) + P’ \pmod A $$
$$ P = P’ \pmod A $$
因此，它仍然可以揭示 $ P’ $
- 順便說一句 $ N’ $ 生成，什麼是最好的分解方式 $ N’ $ 給出的資訊是如何產生的？是否有某種分解算法可以進行分解 $ N’ $ 很容易？
目前公開文獻中的因式分解記錄是829 位，但建議的密鑰大小至少為 2048，即每個因式有 1024 位。因此大小 $ A $ 必須在附近 $ 1024 $ -少量。一旦你設置 $ A $ ，那麼你可以尋求 $ P = A,k_1 + P’ $ 在哪裡 $ P $ 是素數。
沒有什麼可以阻止一個人為 $ P’ $ 和 $ Q’ $ . 這 $ P’ $ 和 $ Q’ $ 不會增加太多 $ P = A,k_1 + P’ $ 因為它們被添加了。這 $ A $ 和 $ k_1 $ 很重要。
因此您可以選擇 $ P’ $ 和 $ Q’ $ 如下 $ 829 $ -位。
如果你從 $ k=1 $ , 我們希望你能在一些小的地方結束循環 $ k_P $ （而且很小 $ k_Q $ ）。請注意，這使得 $ P-Q=(k_P-k_Q)\cdot A+(P’-Q’) $ 所以它並不少見 $ k_P=k_Q $ 以便 $ P\approx Q $ 和因式分解 $ N $ 有便利。如果你收集了很多很多後門 $ N $ ，你有時可能會成功。（我知道還是 $ P’-Q’\gg1 $ , 但至少可以肯定 $ P’-Q’\ll \sqrt N $ ）。即使你故意避免 $ k_P=k_Q $ ，它們仍然很小並且使 $ \frac PQ\approx \frac{k_P}{k_Q} $ ，這也有助於分解（有同樣的警告）。
如果通過這種方式您設法將幾個因素考慮在內 $ N $ 並且很驚訝 $ \frac PQ $ 總是靠近一些簡單的分數 $ \frac{k_Ü}{k_Q} $ ，你可能會發現數字 $ \frac P{k_P} $ 和 $ \frac Q{k_Q} $ 對於您的所有因式數字，可疑的大小相同。或許可以提取 $ A $ 比希望的努力更少。