2
$\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)

If we remove the first 01 for the sign, we have a 2048 modulus and we can remove the zeros. So I guess the modulus will be :

219FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEF845

My problem now is to factorize this 1036 bit modulus. I think that the FF pattern gives us a hint but I can't find it.

Could you please help?

Thank you

Improve this question
$\endgroup$
3
  • 4
    $\begingroup$ That leftmost byte valued 01 cannot be removed. The least significant bit in it that has been set to 1 is not a sign bit. It is part of the modulus value. First of a, the most significant bit could be a sign bit, but it is set to 0, so it doesn't contribute to the value. Second, if that 1 bit in the byte would not be part of the modulus then the key size would not be 2049 bits as the key size for RSA is defined to be the modulus size in bits. $\endgroup$
    – Maarten Bodewes ♦
    Commented Feb 17, 2019 at 16:28
  • 4
    $\begingroup$ Your modulus is $2^{2048}+\mathtt{0x21a}\cdot2^{1024}-\mathtt{0x107bb}$. That's special! Also, the order of magnitude of the middle coefficient is twice the square root of the negative of the right one. $\endgroup$
    – fgrieu ♦
    Commented Feb 17, 2019 at 17:24
  • 1
    $\begingroup$ Followup question about the prime factors. $\endgroup$
    – fgrieu ♦
    Commented Feb 21, 2019 at 17:04

1 Answer 1

Reset to default
6
$\begingroup$

As fgrieu points out, the number to factor can be written as $$ n = 2^{2048} + 538\cdot 2^{1024} - 67515\,. $$ We can identify this number with the polynomial $f(x) = x^2 + 538x - 67515$, with $n = f(2^{1024})$. Furthermore, if we factor this polynomial as $f(x) = g(x)\cdot h(x)$ then $n = f(2^{1024}) = g(2^{1024})\cdot h(2^{1024}) = p\cdot q$ since polynomial evaluation is homomorphic.

Since this is a simple quadratic equation, it is easy enough to find that $f(x) = (x - 105)(x + 643)$. Thus, the factors are $2^{1024} - 105$ and $2^{1024} + 643$.

The Fermat factorization algorithm is particularly efficient for integers whose factors are very close together. This happens to be the case here.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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