# Factoring RSA weak modulus

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.

Thank you

• 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. – Maarten Bodewes Feb 17 at 16:28
• 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. – fgrieu Feb 17 at 17:24
• – fgrieu Feb 21 at 17:04

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$$.