写在前面

化简c1、c2的想法以及最后一步求q感谢：来梦桃子 原博客

题目

from secret import e1,e2,flag from Crypto.Util.number import * msg = bytes_to_long("=========Hint:e1="+str(3)+"=============") p = getPrime(512) q = getPrime(512) N = p*q print (N) print (pow(msg,3,N)) msg = bytes_to_long(flag) p = getPrime(1024) q = getPrime(1024) N = p*q c = pow(msg, e2, N) print (N,e2) #65537 print (c) print(pow(p+q,e1,N)) print(pow(p+e1, q, N)) ''' N = 92492770373119584460081987762423642921257844727187836762004909281192459271971634726161143981458071695340994591107972425352531669271078740978901135762304359798469976380706711716397909327202889036066332030534806956149533263677365472375053769919044969923810993041551455618809123044195807478835222921551845223673 pow(msg,3,N) = 28249132350044579687091110964285446575404805400757326954185222098803605008954490760462246663674360047951197296557689347856716297531621331430289344669498939239588624311221464757652619402073234993515450143594805022438694559765344247838048186137683783869848355994953125 N,e2 = 27015781782143176377305444708803319343811009307670517970464768333771120997045181708841835585570829548449323842457013912871572311489720085833836018287540353234899258733164425361573491416926759037218022548655403489670177828691645649124879974295681372533797388585691439378293643867458900873524289213226600650695273378214798580343627514294295063280759129845430749116891862775979009255567653541999885963152760100703226634896555671676063304361506854160585739743294659176171738147833879545955904927967598053108666430271719503999512230196683852929862867406713611436850146222646354297511499309143157446775247989917315728885081 65537 c = 6960471390887676836770576717723665527999812876556281118485164081998911577875381908446602930344333654944091349042662834710841686602096786488652321359862587616056255592745697363730350424006430304398118412822538778460783959334956287873626339403915923932633438142296099193868446694776583016981952887671846310453413799566390944727222387714300425256165444782922011140095044159890292073622972447390685582541707094791774266611010707510165706469905665511940032155195482276746347896610980037890500866671279623501021060117466463857453415816945239635341057570437059560066260202940898394476654111403345827675113200431405898577228 pow(p+q,e1,N) = 1043358162140860962273728863918690254907683549241317489027248804399285815575770538413854959643097587139967903983728298468193229257795104589966904860928102961617976618240299512928763147662509317818932641083203337246219100049009339117603571633877302978817219689048124475419370026280279605865626353406562716520200330156419718727010377305953369496577186008235640834052476174479818668164269356133941979167253165318046864430749941469717776898395077805761110978284600985034996774850879017975655590682283621730288960471273895327469257980443060594976109602435213897419646191853646130932643009667656100697739228571988907108326 pow(p+e1,q,N) = 2367294939363830936563488061919820815242930281093184747199533909423831655805653462926444204702027721204809679004109764873839689145594088483842010258154637719914884625388278232087919706082381019835448905310742695003695950771324141473767622775925225996118945331612570816055138158026344226500272784973866690432399708551301786027237710788172551956598563031161785118254195771411706070504960683710473948125061842911067623875812101363911946970263021272358739604106737786749756437515890114561301491995915709307108967981619075610635000644793538253463486203886648971971414160634218354735619624263269704236191332074536463815524 '''

题解

0x01求e1:

直接对c开三次方

from Crypto.Util.number import * from gmpy2 import * C1 = 28249132350044579687091110964285446575404805400757326954185222098803605008954490760462246663674360047951197296557689347856716297531621331430289344669498939239588624311221464757652619402073234993515450143594805022438694559765344247838048186137683783869848355994953125 m=iroot(C1, 3)[0] print(long_to_bytes(m))

可得

b'=========Hint:e1=2020321============='

化简c1

c1 = print(pow(p+q,e1,N )) c1 = (p+q)^e1 mod N c1 = (p+q)^e1 mod p*q ∴ c1 = （p+q)^e1 + k*p*q k为整数 向q取模 c1 mod q = (p mod q + q mod q) ^ e1 mod q + 0 => c1 mod q = ( p mod q )^e1 mod q => c1 =( p mod q ) ^ e1 => c1 = p^e1 mod q => c1 = p^e1 + k*q

化简c2

c2 = print(pow(p+e1, q, N))

这里需要用到费马小定理

c2 = (p+e1)^q mod N c2 mod q = ( p mod q + e1 mod q)^q mod q ① 根据费马小定理， ①式可化为： c2 = (p+e1) mod q c2 = p+e1 + k*q c2 - e1 = p + k*q

综上

c1 = p^e1 + k*q ① c2 - e1 = p + k*q (c2 - e1)^e1 = p^e1 + ..... +(k*q)^e1 ② ②-① = (C2 - e1)^e1 - c1 = t*kq ??? gcd((c2 - e1)^e1 - c1 , N） = q

得出q后即可得出结果

exp

from Crypto.Util.number import * from gmpy2 import * from libnum import * c1 = 1043358162140860962273728863918690254907683549241317489027248804399285815575770538413854959643097587139967903983728298468193229257795104589966904860928102961617976618240299512928763147662509317818932641083203337246219100049009339117603571633877302978817219689048124475419370026280279605865626353406562716520200330156419718727010377305953369496577186008235640834052476174479818668164269356133941979167253165318046864430749941469717776898395077805761110978284600985034996774850879017975655590682283621730288960471273895327469257980443060594976109602435213897419646191853646130932643009667656100697739228571988907108326 c2 = 2367294939363830936563488061919820815242930281093184747199533909423831655805653462926444204702027721204809679004109764873839689145594088483842010258154637719914884625388278232087919706082381019835448905310742695003695950771324141473767622775925225996118945331612570816055138158026344226500272784973866690432399708551301786027237710788172551956598563031161785118254195771411706070504960683710473948125061842911067623875812101363911946970263021272358739604106737786749756437515890114561301491995915709307108967981619075610635000644793538253463486203886648971971414160634218354735619624263269704236191332074536463815524 e1 = 2020321 N = 27015781782143176377305444708803319343811009307670517970464768333771120997045181708841835585570829548449323842457013912871572311489720085833836018287540353234899258733164425361573491416926759037218022548655403489670177828691645649124879974295681372533797388585691439378293643867458900873524289213226600650695273378214798580343627514294295063280759129845430749116891862775979009255567653541999885963152760100703226634896555671676063304361506854160585739743294659176171738147833879545955904927967598053108666430271719503999512230196683852929862867406713611436850146222646354297511499309143157446775247989917315728885081 e2 = 65537 c = 6960471390887676836770576717723665527999812876556281118485164081998911577875381908446602930344333654944091349042662834710841686602096786488652321359862587616056255592745697363730350424006430304398118412822538778460783959334956287873626339403915923932633438142296099193868446694776583016981952887671846310453413799566390944727222387714300425256165444782922011140095044159890292073622972447390685582541707094791774266611010707510165706469905665511940032155195482276746347896610980037890500866671279623501021060117466463857453415816945239635341057570437059560066260202940898394476654111403345827675113200431405898577228 ans = pow(c2-e1,e1,N) - c1 q = gcd(ans,N) p = N//q phi = (p-1)*(q-1) d = invert(e2,phi) m = pow(c,d,N) print(long_to_bytes(m))