分解兩個 RSA 模數ñ一世=p一世⋅q一世ñ一世=p一世⋅q一世N_i=p_icdot q_i知道p2=p1+2p2=p1+2p_2=p_1+2?

June 28, 2021

給定兩個 RSA 模數 $ N_1 $ 和 $ N_2 $ , 已知為 $ N_i=p_i\cdot q_i $ ，和 $ p_i $ 和 $ q_i $ 未知素數，這樣 $ p_2=p_1+2 $ . 我們能否利用這種關係來比不成立時更有效地分解模量？
如果這有幫助，如果它們對常見的 RSA 模數合理，請添加額外的假設，例如：
$ p_1<p_2<q_1<q_2 $
$ p_1\equiv1\pmod 4; $ 以便 $ p_1 $ 和 $ p_2 $ 僅由它們的第二個最低位不同
$ 2^{(k-1)/2}<p_i<q_i<2^{k/2} $ 和 $ k=1024 $
這是這個更一般的問題的最小子集。

更新：對於這個特定的問題，有一個更簡單的答案，不需要非常花哨的機器。它是基於撤消的盧-彭-張-林的第 3 節。
讓 $ p_1 = p_2 + 2 $ , 成為雙胞胎 $ n/2 $ 位素數。讓 $ q_1 $ 和 $ q_2 $ 隨機的 $ n/2 $ 位素數。讓 $ n_1 = p_1q_1 $ ，和 $ n_2 = p_2q_2 $ .
因為我們知道準確的距離 $ p_1-p_2 = 2 $ 在這種情況下，我們有關係 $$ 2q_2 + n_2 \equiv 0 \pmod{p_1}, $$ 但此外，這也適用於模 $ p_1q_2 $ . 它有一個小根 $ q_2 $ .
現在我們可以應用Coppersmith 定理，找到一個小的根 $ x + n_2/2 \bmod (n_1n_2) $ 模除數 $ p_1q_2 $ 的 $ n_1n_2 $ ：我們有除數大小 $ p_1q_2 \approx n_1n_2^{1/2} $ 和根大小 $ q_2 \approx \left(n_1n_2\right)^{1/4} \le \left(n_1n_2\right)^{\frac{(1/2)^2}{1}} $ . 所以這變成了 Coppersmith 定理的簡單應用。
由於涉及晶格尺寸和係數大小以及一些蠻力，要在完全平衡的素數上解決這個問題仍然需要相當大的努力。因此，這裡有一個範例，其中添加了一些不平衡的鬆弛位，以使事情更容易在 Sagemath 上展示。以下：
sage: set_verbose(2)
....: slack = 32
....: while True:
....: ^Ip2 = random_prime(2^(512+slack), lbound=2^(512+slack-1)+2^(512+slack-2), proof=False)
....: ^Iif is_pseudoprime(p2 + 2):
....: ^I^Ip1 = p2 + 2
....: ^I^Ibreak
....: q1 = random_prime(2^(512-slack), lbound=2^(512-slack-1)+2^(512-slack-2), proof=False)
....: q2 = random_prime(2^(512-slack), lbound=2^(512-slack-1)+2^(512-slack-2), proof=False)
....: n1 = p1*q1
....: n2 = p2*q2
....: P.&lt;x&gt; = Zmod(n1*n2)[]
....: f = x + inverse_mod(2, n1*n2)*n2 % (n1*n2)
....: f.small_roots(X=2^(512-slack), beta=0.499, epsilon=1/80)
verbose 2 (&lt;module&gt;) epsilon = 0.012500
verbose 2 (&lt;module&gt;) m = 20
verbose 2 (&lt;module&gt;) t = 20
verbose 2 (&lt;module&gt;) X = 3121748550315992231381597229793166305748598142664971150859156959625371738819765620120306103063491971159826931121406622895447975679288285306290176
verbose 1 (&lt;module&gt;) LLL of 40x40 matrix (algorithm fpLLL:wrapper)
verbose 1 (&lt;module&gt;) LLL finished (time = 98.39880900000003)
[0,
2620283760117376406133844025968807462728035897729397199816702715415414363266477530335988526677009061010233108189224508368303968856603325996874289]
sage: q2
2620283760117376406133844025968807462728035897729397199816702715415414363266477530335988526677009061010233108189224508368303968856603325996874289
這個花哨的名字是帶有隱式提示的分解。如果素數不平衡，即，如果 $ \log_2 p_i > 2 \log_2 q_i $ ，我們知道如何分解 $ n_1 $ 和 $ n_2 $ 很容易。讓 $ k $ 是位數 $ p_1 $ 和 $ p_2 $ 相差（一個非常小的 $ k $ , 通常, 對於 $ (p, p+2) $ ); 減少以下格
$$ \begin{pmatrix} 2^k & 0 & n_2 \ 0 & 2^k & -n_1 \end{pmatrix} $$
使用 LLL 或同等學歷。得到的最短向量將是 $ (2^k q_1, 2^k q_2, 2q_1q_2) $ . 這種方法被描述得更籠統（即，在共享 $ p_i $ 位）在Faugère、Marinier 和 Renault（另見May 和 Ritzenhofen、Sarkar-Maitra、Kurusawa-Ueda和Nitaj-Ariffin）。
最近的兩篇論文對上述基於格的方法進行了改進，Lu-Peng-Zhang-Lin 的定理 1似乎暗示了具有平衡模的隱式分解確實是可能的。所以你的問題的答案似乎是肯定的。