1
$\begingroup$

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
Improve this question
$\endgroup$
3
  • $\begingroup$ C is the encrypted text $\endgroup$ – Dcoder Jun 4 '16 at 7:08
  • 1
    $\begingroup$ @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. $\endgroup$ – Robert NACIRI Jun 4 '16 at 7:55
  • $\begingroup$ any helpful document please :) $\endgroup$ – Dcoder Jun 4 '16 at 8:01
1
$\begingroup$

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?

Improve this answer
$\endgroup$
0
2
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ thanks, this is a old task in ctf that has been solved but i still not get the solution how $\endgroup$ – Dcoder Jun 4 '16 at 9:30
  • 1
    $\begingroup$ @Dcoder: what about sharing a link to the particular Capture The Flag statement? $\endgroup$ – fgrieu♦ Jun 4 '16 at 10:03
0
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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