# Factoring an RSA modulus given high bits of a factor

I have {e,N,C} and part of p; can I get q from this example :

e: 3

p: 00cb7b290d0527d2408809087e280aabb9544138efb5e3e283870936411484a587Â¡s^,Ãº:Â§Ã‡Â¹cÃšO
• C is the encrypted text Jun 4, 2016 at 7:08
• @Dcoder, there is a lot of documentation about this subject. The work was initiate by Don Coppersmith which consist of finding small roots of bivariable equation ( the variables are the lsb of p and those of q). Look also to the publication of Dan Boneh and many other autors. Jun 4, 2016 at 7:55

Here is the solution to M^e is less than N:

http://asecuritysite.com/encryption/crackrsa2

An alternative method is here as a fun article:

http://asecuritysite.com/encryption/crackrsa5

Do you have the Cipher value?

A simple way to consider the question is: Can we factor a given 2048-bit RSA modulus $N$, assumed to be the product of two 1024-bit primes $p$ and $q$, if also given the 256 high-order bits of $p$?

That class of problems is studied by Don Coppersmith: Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities, in Journal of Cryptology (1997) 10: 233–260 (or perhaps a blind Google search?). He shows how to factor $N$ given ${1\over4}\log_2(N)$ high-order bits of $p$. I'm not aware of a better result for the balanced two-primes case, and that would be big news.

Here we have only $\approx{1\over8}\log_2(N)$ bits, so the approach won't work. Perhaps the author of the question tried to make one that can be solved, but goofed. Or perhaps there's some trap; like $N$ could be the product of more than two factors; or heavily unbalanced; or there might be information to extract from the apparent gibberish on the right side of $p$; or there could be a detectable flaw in the generator for $p$; or..

In the end, the present answer really has nothing to do with the original RSA Fun problem from which the question is extracted. Hint for that one: in RSA encryption, usually, $\log_2(C)\lesssim\log_2(N)$ (where $C$ is the ciphertext); but here we have $\log_2(C)\ll\log_2(N)$; combined with the low $e$, we can guess that..

• thanks, this is a old task in ctf that has been solved but i still not get the solution how Jun 4, 2016 at 9:30
• @Dcoder: what about sharing a link to the particular Capture The Flag statement?
– fgrieu
Jun 4, 2016 at 10:03

What you might have used back then was the 'Chinese Remainder Cube Root' attack, given the small public exponent of 3. actf{1_w4s_l0st_1n_tr4nsm1ss14n...}