题目:
import hashlib import sympy from Crypto.Util.number import * flag = 'GWHT{******}' secret = '******' assert(len(flag) == 38) half = len(flag) / 2 flag1 = flag[:half] flag2 = flag[half:] secret_num = getPrime(1024) * bytes_to_long(secret) p = sympy.nextprime(secret_num) q = sympy.nextprime(p) N = p * q e = 0x10001 F1 = bytes_to_long(flag1) F2 = bytes_to_long(flag2) c1 = F1 + F2 c2 = pow(F1, 3) + pow(F2, 3) assert(c2 < N) m1 = pow(c1, e, N) m2 = pow(c2, e, N) output = open('secret', 'w') output.write('N=' + str(N) + '\n') output.write('m1=' + str(m1) + '\n') output.write('m2=' + str(m2) + '\n') output.close()
给了N
、m1
和m2
的值,使用yafu工具可以求解出p
和q
:
有了p和q可以求解出c1和c2啦:
import gmpy2 p=797862863902421984951231350430312260517773269684958456342860983236184129602390919026048496119757187702076499551310794177917920137646835888862706126924088411570997141257159563952725882214181185531209186972351469946269508511312863779123205322378452194261217016552527754513215520329499967108196968833163329724620251096080377748737 q=797862863902421984951231350430312260517773269684958456342860983236184129602390919026048496119757187702076499551310794177917920137646835888862706126924088411570997141257159563952725882214181185531209186972351469946269508511312863779123205322378452194261217016552527754513215520329499967108196968833163329724620251096080377747699 e=0x10001 m1=90009974341452243216986938028371257528604943208941176518717463554774967878152694586469377765296113165659498726012712288670458884373971419842750929287658640266219686646956929872115782173093979742958745121671928568709468526098715927189829600497283118051641107305128852697032053368115181216069626606165503465125725204875578701237789292966211824002761481815276666236869005129138862782476859103086726091860497614883282949955023222414333243193268564781621699870412557822404381213804026685831221430728290755597819259339616650158674713248841654338515199405532003173732520457813901170264713085107077001478083341339002069870585378257051150217511755761491021553239 m2=487443985757405173426628188375657117604235507936967522993257972108872283698305238454465723214226871414276788912058186197039821242912736742824080627680971802511206914394672159240206910735850651999316100014691067295708138639363203596244693995562780286637116394738250774129759021080197323724805414668042318806010652814405078769738548913675466181551005527065309515364950610137206393257148357659666687091662749848560225453826362271704292692847596339533229088038820532086109421158575841077601268713175097874083536249006018948789413238783922845633494023608865256071962856581229890043896939025613600564283391329331452199062858930374565991634191495137939574539546 n=p*q phin=(p-1)*(q-1) d=gmpy2.invert(e,phin) c1=pow(m1,d,n) c2=pow(m2,d,n) print "c1="+str(c1) print "c2="+str(c2)
得到:
c1=2732509502629189160482346120094198557857912754 c2=5514544075236012543362261483183657422998274674127032311399076783844902086865451355210243586349132992563718009577051164928513093068525554
已知想要求得flag,必需求得F1和F2:
F1 = bytes_to_long(flag1) F2 = bytes_to_long(flag2)
而F1和F2与c1和c2存在以下关系:
c1 = F1 + F2 c2 = pow(F1, 3) + pow(F2, 3)
用sage或z3库一把梭:
转成人话: