3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Previous question about the factorization can be found here $\endgroup$ – Maarten Bodewes Feb 21 at 17:32
  • 1
    $\begingroup$ Mzem, if you're satisfied with any of the answers then please accept them; it's the probably the best way of showing gratitude on SE. $\endgroup$ – Maarten Bodewes Feb 22 at 12:09
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Small question, what is the easiest way to extract $\texttt{0x21a}$ form this hex? $\endgroup$ – kelalaka Feb 20 at 18:16
  • 1
    $\begingroup$ @kelalaka 0x21a000… - 1 = 0x219fff… $\endgroup$ – Squeamish Ossifrage Feb 20 at 18:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.