The challenge gives us output.txt file with RSA parameters (n and e) and a ciphertext (c). We learn from the description that the number generation (for n because e = 65537 is quite common). So we can have a look at n, in base 10 we cannot see anything special but if we convert it to hexadecimal it is rather suspicious:
sage: n = 1797706850172487891975376615658152699342035621208510891791224143990647
....: 34715990794430000078278988633398024403072323955508476586487162411822366599
....: 11141253453943074013719626524237112871455836208288252000174768522265586381
....: 71257336934110584527437688182679186885936483346137560451573214916072337449
....: 02053478170361857
sage: n.hex()
'10000800000000000400000000000000000000100080004420120008002000010014000800008000c004040011002008002000001000000000a0400000010000280004000000000002000000000002000010004801000008102000400000000200200000000100000000000000000000000000000000000000002000000000001'
sage: n.binary()
'10000000000000000100000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000010000000000000000100010000100000000100100000000000001000000000000010000000000000000000010000000000010100000000000000100000000000000000001000000000000000110000000000010000000100000000000001000100000000001000000000100000000000001000000000000000000000000100000000000000000000000000000000000010100000010000000000000000000000000000010000000000000000001010000000000000000100000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000010000000000000000000010000000000000100100000000001000000000000000000001000000100000010000000000000010000000000000000000000000000000000001000000000001000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000001'
Most of the bits of n are set to zero so the number p and q must also have most of their bits set to zero. At this point I tried to factorize it (factor(n)) with sage thinking it will be a piece of cake. But it was not a success, it seems that sage is not able to use this property to factorize the number is reasonable time. We need to be smarter… or find a similar write-up :D
The idea is that we can solve an equivalent problem which is polynomial factorisation. So we first get a polynomial from base 2 binary (we kind of replace 2 by x) and factorize it :
sage: poly = sum(e * x^i for i,e in enumerate(N.digits(2)))
sage: poly
x^1024 + x^1007 + x^958 + x^872 + x^859 + x^842 + x^838 + x^833 + x^824 + x^821 + x^807 + x^793 + x^772 + x^760 + x^758 + x^743 + x^723 + x^707 + x^706 + x^694 + x^686 + x^672 + x^668 + x^657 + x^647 + x^633 + x^608 + x^571 + x^569 + x^562 + x^532 + x^513 + x^511 + x^494 + x^445 + x^397 + x^376 + x^362 + x^359 + x^348 + x^327 + x^320 + x^313 + x^298 + x^261 + x^249 + x^212 + x^49 + 1
sage: poly.factor()
(x^513 + x^348 + x^327 + x^313 + x^249 + x^212 + 1)*(x^511 + x^494 + x^445 + x^359 + x^320 + x^49 + 1)
This time it’s pretty fast. Let’s go back to base 2 by replacing x by 2:
sage: poly_p = x^513 + x^348 + x^327 + x^313 + x^249 + x^212 + 1
sage: poly_p(x=2)
26815615859885194199148049996411692254958731641185360130374543433318025388027501869461427030990935414084875128479962203391492343065290316985075546168754177
sage: poly_q = x^511 + x^494 + x^445 + x^359 + x^320 + x^49 + 1
sage: poly_q(x=2)
6703955111699546927094586295728886856295101772488437969932374169355084483139592121732447937761581686389247431572954518413208217084020226417145371521187841
Now that we have p and q we can get d with d = inverse_mod(e, (p-1)*(q-1)). And it is easier to switch to python to convert numbers to bytes:
>>> from Crypto.Util.number import long_to_bytes
>>> d = 114417730647412629430820619485684217152074385205074089931482279466771262256029540828297957873768617365738344766357581704526837901529189952767987276427661310566041903596256983565797578831660944391348016566794019369504928471670123341627563363736091841042938243155150655076214286350066267496110303508182595469313
>>> c = 0x000c307feca4371acecab2690800586b967909e12ec3e80184666ca161129f86c6cd87e276127a1f9b672b66ba3d715321b24f7d660a928d829c154dcdc0634b99f51e281c2e138f77a04694ff7aeec25c938cf769fbd7d3f2968f0b96fc5d38a8f742f6a46e70d7eae8280ed61f0328df36497f0cb6251b0e13a2bc5adce6344a
>>> n = 179770685017248789197537661565815269934203562120851089179122414399064734715990794430000078278988633398024403072323955508476586487162411822366599111412534539430740137196265242371128714558362082882520001747685222655863817125733693411058452743768818267918688593648334613756045157321491607233744902053478170361857
>>> print(long_to_bytes(pow(c, d, n)))
b"\x02mF\x03\xb9\xe6(s\xb5\xd0\x88\xdd\xdc|N\n\xbbr\xb8~\x0cI\xce\xea{'\xc8\x7f\x1eS\x8dz\xbcf\x87\xb0\n+\xf2\x19=\x0f3\xef\xa8M'\x8f\x02}\xb8\x07\xee\xe7\xb3\\\xbd\x00FCSC{0224e979da8a6069869ccfc040abb680ffd35e3ba61bcc0e0683662c33fa81c0}"