BackdoorCTF17 - STEREOTYPES

gistfile1.txt

# https://github.com/mimoo/RSA-and-LLL-attacks/blob/master/coppersmith.sage

length_N = 2048  # size of the modulus
Kbits = 8*30      # size of the root
e = 7

n = 17128253199894018356121352721813384810490073007249104944917185889284458477972764510189878223087898232323989051389196334498213309997968573900259909767276527308390944053199244416237135384010089907191097552095732629493007104656712229046898881071816439581052398074559706748835744846278126604658780761748930367026870270721107608579738966885369180506986732756678936607083412698682076417247965156736007257325263626024309893180725648019322055002425052139312236077136949139163190290260407572716784894091812931974782646175099495402465049210759703810960600180113684855659892187079557217272929145318759442388534032426335197492209
# message with X:s replaced with \x00
m2 = 115187245656325575698875729790282642212930548748463092065204369418708216291155665989205021047468838142025051843099835931219635476459638358291768944024977260201839742782124859088529873971905522340780587673634963892906501655934652033065483105959124652995675375187226593058645297329744588405060727900047060073362881226582222539170913146258434555654371489139229050690663311680730101709133573886961243713446437623231124732560606386944666112685417134293162413492709060639338136519444676948426963320805588894438876123699208985971986627457388344748617780375247355235008512
c = 16768000818369650889473559179857307617096849495067449693804334440548683786080925998924968845371027870195306782363841871878252727444315225702098433390849264252615398314400665446243852603373259054016218424683794322933348880746198728162331379599026123529958387779190655128497504562593049906246714173433169399750037556852559463956061776795503391238160470277336939163376458673901203757299613128011426324959660380444801286927470035485316258454878382925995639032456074428942239326572440716770568356877580223855914055294867723365148065190093239459597133031328583142313206369820921355612469447937193929098112988814615719024063

N = n
ZmodN = Zmod(n);
M = ZmodN(m2)
C = ZmodN(c)

P.<x> = PolynomialRing(ZmodN) 
pol = ((M + x)**e - C).monic()
dd = pol.degree()

beta = 1                                # b = N
epsilon = beta / 10                      # <= beta / 7
mm = ceil(beta**2 / (dd * epsilon))     # optimized value
tt = floor(dd * mm * ((1/beta) - 1))    # optimized value
XX = ceil(N**((beta**2/dd) - epsilon))  # optimized value

roots = coppersmith_howgrave_univariate(pol, N, beta, mm, tt, XX)
print hex(roots[0]).strip("0x").strip("L").decode("hex")