Writeup for InCTF 2014 - Crypto 200 - Solved RSA 4096 bit

Writeup for InCTF 2014 - Crypto 200 - Solved RSA 4096 bit .py

#!/bin/python 
import gmpy

n = 0x00d10ba0e9cd6dd6c3895fcdf417db21e581226089c6c7587fc41b3d78dff52c0f8c29dc6be9fccf316832e6ff6ff0496e9e566ecbc131064eb8475d6c1bc828be4af454ad62cbf0d1d2cd5a598a241c52b16d8ee1da0ca9cc56303cd070710e6c181f2a31c6887e52cf14bd76f62580a84692f88198a938490fb2de1941b11085833dedca16673f4ae54be60fe0da6624a53db232dca6c5887d723c7739c476ef306019a057f1c6be37a5b820d0919acffd1863d22c6fa730fe12e815359d68a4ece1c01ef7b0ecd95991b3d971d00927995ed66ed6c9933644c4f99ec752809eaf731e69c5c0f9b034e1b8330fefd40590c46fa179614f7ad28cd18b997369182f46f9e9ba2548c65380e53e22c99beaa69bf6f863874530bdce9a68ee6afba4e9ae0781be5b3df1a517c57ec1b52b4b84b71863a88a35f1c0df0a1f8ee36c9161d2ef60472a129db81666223edd07f3e9d1da4bfdd2171dbe58a036804deffd8fd58eb57a2a454b25c5de925a1654d5fe670204b840129b8bc5a2d397faf2157a8bb209a27aff89b2f8bf18abda5371e0c1cf3d68c20b5e3e195f6f6312a3f8ef9788cafb7661b79af752159f885017bde86c7a2eb34e277dac367d9f5633c5900ad115ef4c8fae5328da215cb220b8aefb09e302628a2be0569ee7dc171ef3147c6ace610271e06d5ba71403d32e2ab530765f06a1f1024cd642c49788f1df
e = 0x3
cipher_str = 0x075a1ec729bc48da7edd3b5820f7b1112c2da1d61398b9ff8c52d47132a185e18fec092789a1f0706551d529182f27c086b882dfbd38fa494110c66957c49bceebad7074cc163017c294709f59ab0efb793b95a44c388f6afedaba16c85813b6127f99b8b44496c90d44cb1c70b8a5185997e1c023a28f8166b584d85aa4fbce9ab5936c006ad63786351eea286e0d5639fef4255727fc77fff0c4b7df42ac4f7e3b2601767a0b3be82a69f024063fc580c1ca05075cf21b394970f4c07b1dd194d8b3dac66da1603b31a0ef9f02345c6c885d4c60661534c89d46e9535bd81c1cb8ff1f6a7212bb0dfddb410800949a84206680e043a6b57ed95099e01d6230149544e856879f74907cc460ac753e856c67aaa565d6792343e1ecfc858445901cc1d3afd8c272dced8ff8159a95f2bdac213c2c95aeba689365b34275e6126ddb49d324735de32406783fa92c3b23acb677a13cb895bb31b511216cc3b84178c6d99fe838

 
gs = gmpy.mpz(cipher_str)
gm = gmpy.mpz(n)
g3 = gmpy.mpz(3)
 
mask = gmpy.mpz(0x8080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808000)
test = 0
while True:
  if test == 0:
   gs = gs
  else:
   gs += gm
  root,exact = gs.root(g3)
  if (root & mask).bit_length() < 8:
    print root
    break

print '\n',hex(int(root))[2:-1].decode('hex')