30
$\begingroup$

I'm working on a CTF. The challenge is to get the contents of an encrypted message given the ciphertext and the 2048-bit RSA public key. I did finally get the flag after a few hours, but I'm still not sure why the first step worked.

The first step -- factor n into its two prime factors is from what I can tell, not supposed to be feasible, but it was done in about 1 second on this website. Why was it so easy?

n=25224507456159163156575877796028456473662369736904878100933060887887244216120260281695328861739056294270643097794317308976759958367437549244808863772906680939521070489582647498438244915199705468395817575606597814019562913707562306397168764567686787293933393417031620511244511892437239390863502308155450078419924080263102978663897532365363981719762081750552627197211945486141442274528746322354522651902908903406950060094343722668988129318030729213169059762443357730983377434699924583492845212206319390320703622866477008711013644010886555820367734996512061432529391693421190426715896428082690439073605633199475981032823
e=65537

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
43
$\begingroup$

That number was so quick to factor because its factors are extremely close together, i.e., it factors as $\left(\lfloor\sqrt{n}\rfloor + 70\right)\left(\lfloor\sqrt{n}\rfloor - 68\right)$.

Some algorithms, like Fermat's, which work best the closer together the factors are, will find this factorization instantly.

Improve this answer
$\endgroup$
5
  • $\begingroup$ ohh, I see thank you. I thought maybe it was something like n was 2^2048-1, or maybe there was some type of factoring rainbow table, but that makes more sense $\endgroup$
    – rainbowkitty227
    Jun 5, 2021 at 2:06
  • 11
    $\begingroup$ @rainbowkitty227 Rainbow tables aren't relevant to integer factorization. $\endgroup$
    – forest ♦
    Jun 5, 2021 at 2:07
  • 8
    $\begingroup$ Ryan Sheasby wrote two good articles describing what rainbow tables actually are (and why they're usually useless these days): rsheasby.medium.com/… and rsheasby.medium.com/… $\endgroup$
    – SAI Peregrinus
    Jun 5, 2021 at 2:25
  • 7
    $\begingroup$ In particular, the site uses a quadratic sieve which is like an extension to Fermat's method. $\endgroup$
    – qwr
    Jun 5, 2021 at 8:54
  • 10
    $\begingroup$ IOW, the puzzle designers picked this specific number, just like textbook authors pick nice round numbers. $\endgroup$
    – RonJohn
    Jun 5, 2021 at 23:49

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.