分解 RSA 弱模量

給定 RSA 的公鑰，我提取瞭如下所示的模數：

Public-Key: (2049 bit)
Modulus:
   01:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
   00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
   00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
   00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
   00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
   00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
   00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
   00:00:00:00:00:00:00:00:00:00:00:00:00:00:00:
   00:00:00:00:00:00:00:02:19:ff:ff:ff:ff:ff:ff:
   ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
   ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
   ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
   ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
   ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
   ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
   ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
   ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:fe:
   f8:45
Exponent: 65537 (0x10001)

如果我們刪除符號的第一個 01，我們有一個 2048 模數，我們可以刪除零。所以我猜模數是：

219FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEF845

我現在的問題是分解這個 1036 位模數。我認為 FF 模式給了我們一個提示，但我找不到。

能否請你幫忙？

謝謝

正如fgrieu指出的那樣，要考慮的數字可以寫為 $$ n = 2^{2048} + 538\cdot 2^{1024} - 67515,. $$ 我們可以用多項式來辨識這個數字 $ f(x) = x^2 + 538x - 67515 $ ， 和 $ n = f(2^{1024}) $ . 此外，如果我們將該多項式分解為 $ f(x) = g(x)\cdot h(x) $ 然後 $ n = f(2^{1024}) = g(2^{1024})\cdot h(2^{1024}) = p\cdot q $ 因為多項式求值是同態的。

由於這是一個簡單的二次方程，因此很容易找到 $ f(x) = (x - 105)(x + 643) $ . 因此，這些因素是 $ 2^{1024} - 105 $ 和 $ 2^{1024} + 643 $ .

費馬分解算法對於因子非常接近的整數特別有效。這恰好是這裡的情況。

引用自：https://crypto.stackexchange.com/questions/67384