Rating: 2.0

After reversing the binary, we find out that the RSA primes are:


p = 2*x*r1 + 1
q = 2*x*r2 + 1

Where x = a+b, we choose a, and b is very small. x is prime and has the same size of r1 (or r2).
We can just search for next_prime(a) until we find x at some point based on the information below:

Because N = p*q = 2*2*x*x*r1*r2 + 2*x*r1 + 2*x*r2 + 1 and x, r1 and r2 can be of the same size, we can reduce re = N % (2*2*x*x), so we obtain the equation system:

N = 2*2*x*x*r1*r2 + 2*x*r1 + 2*x*r2 + 1
re = 2*x*r1 + 2*x*r2 + 1

Solving this system we obtain r1 and r2, so we can reconstruct p and q. No coppersmith needed.