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

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.

• 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 Jun 5, 2021 at 2:06
• @rainbowkitty227 Rainbow tables aren't relevant to integer factorization.
– forest
Jun 5, 2021 at 2:07
• 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/… Jun 5, 2021 at 2:25
• In particular, the site uses a quadratic sieve which is like an extension to Fermat's method.
– qwr
Jun 5, 2021 at 8:54
• IOW, the puzzle designers picked this specific number, just like textbook authors pick nice round numbers. Jun 5, 2021 at 23:49