Fermat's factorization method on weak RSA modulus

Question

Given a public key for RSA, I have extracted the modulus which looks like this:

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)

I have successfully factorized the modulus using Fermat's factorization method. This method is fast when the prime factors are close to the square root of the modulus.

My question is, how can you tell that this modulus has its prime factors close to its square root?

Thank you

Answer 1

In general, it is not sizably easier to tell from an RSA modulus that Fermat factorization will succeeds, than it is to perform such factorization.

However here, it is visually easy to notice the long sequence of 00 and ff in the modulus. That translates into noticing that the modulus to factor is $2^{2048}+\mathtt{21a}_h\cdot2^{1024}-\mathtt{107bb}_h$, or equivalently $2^{2048}+538\cdot2^{1024}-67515$.

^{Per comment: the number is 257-byte, with the left 01:00:00:00:, thus just over $2^{2048}$. Cutting where the long ff:ff:ff: starts, the right fragment has 128 bytes, thus has a value just shy of $2^{1024}$, and the :00:00:00:02:19:on its left contributes for an additional $\mathtt{219}_h\cdot2^{1024}$, totaling near $\mathtt{21a}_h\cdot2^{1024}$. The correction to subtract is one more than the bitwise complement of the right fragment :ff:ff:ff:fe:f8:45.
In other words, the modulus is $2^{2048}+\left(\mathtt{0000000219}_h+1\right)\cdot2^{1024}-(\overline{\mathtt{fffffffef845}_h}+1)$.}

That $2^{2048}+538\cdot2^{1024}-67515$ suggests to try if the modulus could be $(2^{1024}+a)(2^{1024}+b)$ for integers $a$ and $b$ of small absolute value, that is if the system $a+b=538\text{ and }a\cdot b=-67515$ has an integer solution. We can

• Solve the second degree equation $x^2+538x-67515=0$ which roots will be $a$ and $b$, and check these are integers. We get roots are $-\dfrac{538}2\pm\sqrt{\left(\dfrac{538}2\right)^2+67515}$, which indeed are integers $643$ and $-105$, and that gives us the factorization as $(2^{1024}+643)(2^{1024}-105)$.
• Or factor $67515=3\cdot5\cdot7\cdot643$, which invites to try $a=643$ and $b=-3\cdot5\cdot7=-105$, with indeed $a+b=538$.

Notice the above factorization method works only because the hex fragments in the middle and in the right of the modulus given have a highly specific property: $\left(\dfrac{\mathtt{0000000219}_h+1}2\right)^2+\overline{\mathtt{fffffffef845}_h}+1$ is the square of an integer. Otherwise that method leads nowhere, and it is likely Fermat fails too.

Fermat factorization works on the given moduli because it is of the form $(2^{1024}+a)(2^{1024}+b)$ with $a$ and $b$ small integers, thus the product of two close integers. Fermat works for many 2049-bit integers not of this form, but still only a negligibly tiny fraction of 2049-bit integers.