Balt CTF 2013 - Crypto 300 RSA - [Team xbios]

For this challenge, public key (e, n) and cipher text (c) is given. We have to find the hex(plain text), which is our flag. With the given data, the first attack that came to mind was to factorize the modulus (n). Fermat's factorization method worked out for us. With (p) and (q) values revealed, we can compute the private key exponent (d) and decrypt the cipher text. Computation was done using sage

sage: e = 0x10001
sage: n = 0x59b7f3a0a6bd10811b05473deb94ae35f84163652e408372ab86cdcb24f21873603ce29059cc9f261b1d5b7cb02221deedc8eb289c8086f797b5bd0be456c249962fecf9faf9846eb91be1ca17234b4e981fb0bc58d2dd97b7124014a0d10a876a57b2dd8a9d9b8ce95998143aa009fa91657864f819883a31d53fcf30d517ded93aae7895a44bf1576d0aa1694f50481504e184b499ad7805974a910a0e31f080eeea700504a8606b0c888f728a543f944334cc72dcb1b1402471c2e7473dbc0ff2743928df51daf2fa3b954c76b4ff95510df1

sage: c = 0x53da088f69a0c11b11f458e9ec6d89034c3b523d7389221dccec4df09f3dcb6fcd92afb29e2ba7d623525c97604a95ac0b16116bae0545cb9d6608d2c1f6712e5acd1b9e1ebf6e4778c7467d2394bd347dff08b2f41f9cd00c31898641daf4fab519a531112f3b2dd87ef1711992871cfc5168c2dab19dee0d645fc8af560d851eb5c87c5a3038fa84ef7f1bde1df4c766b85a10f3ae888ddef4368684b08674382cd41522485f13dce522080f28f9936c5482cf69f96c51f6d1354f265eb2c334b96b9fb114cdb626c6bbeecaaa9ea5d0b072af

sage: a = ceil(sqrt(n))  # Fermat's factorization
sage: b = (a*a) - n
sage: while not b.is_square():
....:     a = a + 1
....:     b = (a * a) - n
....:     
sage: a - sqrt(b)
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111178333333333334444487294872309872209128742098742420984723982734329843732987178261897634983473987323987439874932873402398720978429874230987340298723097527
sage: a + sqrt(b)
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111178333333333334444487294872309872209128742098742420984723982734329843732987178261897634983473987323987439874932873402398720978429874230987340298723103639

# The two primes are close to each other

sage: p = a - sqrt(b)
sage: q = a + sqrt(b)
sage: phi_n = (p-1) * (q-1)
sage: d = inverse_mod(e, phi_n) # d is multiplicative inverse of e in phi(n)
sage: d
954337922767969916908684322511626172153813028433471847116048101750834558256320009222949546736110051489265793707710489453529078417995956007435026641927114607256687547284882784003724373712426598639807261395269322730689854325793227045289600093508768321130231092684779871351143961963991606200867096255924369283753459133254468784782317092964170117014480277377749896360826708246366013560507323222994034704551754940109682559173621578143499090359492462527474301373854713937148548729916280548630343340454397431053024437

sage: m = Mod(c, n) ^ d         # m = (c ^ d) mod n
sage: c == Mod(m, n) ^ e
True
sage: m
15056585307564100396433190076676958000692809023067706122001961903801830300386286
sage: hex(15056585307564100396433190076676958000692809023067706122001961903801830300386286)
'8207fd4917aa8d07ed9b1bfa9cc2dc7803b848edefa1c2dc7803e97822696b03ee'

Flag for the challenge is : 8207fd4917aa8d07ed9b1bfa9cc2dc7803b848edefa1c2dc7803e97822696b03ee