# 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 :

N: 009cff15eb53f29b343be4d363b892f5e11fd642ad77146dc856fc9a5c8f96dd3ceb5aa4fc05829e77d49855dbcc9af74023785d2cbc6278de83ad0603bf424697868ddba2f2a6d4bce559934cf2a960e8d35bb99c20fae7155bc8b6ef7ba1e843738e41964d8cc843f65273847a5c6a9548118d63b25b8f0e7090990f2379f16e9edbc8c17fe440198acc654c5aa9173cc2e86d1d442d521e5c80eb84722de103aed5269636cd0280be08bd422c03d03a409bbeb8a390a1a382b06cdd2610ce21ad23c74c834df0ee4dd845d54c766fa9c9295b3a8531edacf187d0fc16a82b8a1eb4f8adef7e4888cef91be81ace3e4fb6db643847f4a7ab489bfeaf42e317a9

e: 3

p: 00cb7b290d0527d2408809087e280aabb9544138efb5e3e283870936411484a587Â¡s^,Ãº:Â§Ã‡Â¹cÃšO

• C is the encrypted text – Dcoder Jun 4 '16 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. – Robert NACIRI Jun 4 '16 at 7:55
• any helpful document please :) – Dcoder Jun 4 '16 at 8:01

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 – Dcoder Jun 4 '16 at 9:30
• @Dcoder: what about sharing a link to the particular Capture The Flag statement? – fgrieu Jun 4 '16 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...}