第三题思路:
baby_rsa_8aefaad6f5e5874117b451af77b0646b
如下:
c^ed = c mod n
=>
c^(eg) = c^(ed* (p - w)) = c^(p-w) mod n
=>
c^(eg) * c^w = c^(p-w) * c^w = c^p mod n
因为:
c^(p-1) = 1 mod p
c^p = c mod p
所以:
(c^p - c) = 0 mod p
所以,本题意图求解:
(c^p - c) = k*p mod N
=>
p = gcd(c^p - c, n )
w = 77656C636F6D65 = 33607038427688293
gcd = (c^(eg) * c^w - c , n) = gcd (A - c , n)
令 A= (c^e)^g *c^w mod n =
382141886864987308712417586085910706698771279375086451092726661839223487734520078633477081709732720290423641877981892520892113421592544980399655300931886103530286563862965475533564430306344078677595855655030788754938039694446657877996476427696301070187055289812118977936197499043495473343804934938392522317093776125411365553573957742476749963725540547089912943143835009296253734607879416459767974815399094402622011573874236710084175071473052000674933649409764838748595950978332859398007884454462076950785664736932903155379640575220118139462907188351350981174359809978289891331145204446561841305982790451277575751847307025251038709436717291293489523255573511316620691412233217940114951311060018315488483085834092596926394188220412445317525238756649605959435428786008344882258507520976487770865864615068446684838169574074371713986275689202288141053906898881179278664396991492862084739168540376134968302505394849111526859083621365152305540972782921663117480295073687437353941717419708291929081965755844337194817460705609134065901074176148321744780286582524562911792005763181917328603486874580031903402363732000786987191028423813004092704835762929929727263019614015378294642929448473445740912968382817165290942517731294289884105427871787
A-c=
370519343982672062602219204305726791088885759580208812586838067520661438707644197859939606103311659438994552325460092665835085534689455934822545487800548691608799226397214941942933222809864979189407556592088609958763484525771945309617817569619078889242444424869689471864263673799864152882775532231341607567936918453456246180748072947296749819510407971247372475299550707131910660645140776047608537383316948968452906936769743556161367255746391653635366303968254179485856478126999334112045218275065366399721463886434779258177984209410150313376935786927630261205967514224190001122811600232004579182548841222930061935245448082980932804408051749710141002868128153466011192523022067804854520192778109403702151525320008594816969800493355405308897150364887605921538887470423476825253942137213697837655550219570099554693482971365645651578680606893375843749926936688283277072519153321843384587911640203697954414896481327470285653561886842357354100336232216484528474566823505722347065566501695323744230110024571040229212277500792880870816460851657435781253421057225518381110091877487613689274639628432194032670467107834129317563810143013653018122731660140277147173476055527268064060376756350993063775286330620794723888750378291819984940521668263
p = gcd(A-c, N) =
23658856578566664036074501485429989229455255516521292212959419992149510519356671554795698662654628692053900089792393475218409910408344452879588770173081769770320270512822300780941160922817303688693928118157032899864579509909174844148460266860491370340877842968271910736819183160271817262857958140204473419785812025774484915797179815146246088754035908262746993793208465849630916811013982500911032146632563811803652243833261155445760670498827351358579952017846756896116504118614786540976807658494096254787782221936877352811354405828384364405688582283337469223364051449717177972827813998362406921041521587441458932542779
q= N/p=
24851949526238664338611899087073156378901501538457150925032350137121033161937359929077259595668363332110563044885605929437453685507111041051811632837720922027595220259046162273538453908783279801556003518826645020095508452031712240986754040076410300803211509243489288677395647935061355472814982579273381817695054375333011308040149912373530319912197574688979302503690852764814673678709936983186197776200567023649023158200165794968924491126994907164381184838800721298655915460238965954896597356588137128303303060657925718782380814767864374969680835189795113335493411826863656213063627023223927318463484894232154685605733
d =
578548578238937599474570602076587622840107091595962248936826176911867144607690129268833938144134573601551917945862635510329681485564422316025283461082785539366005641186476403222501732801133246056666098392878155996935304563051171826781306840514560336235542568893956293454327391684465544210904003995778439985661684569950268655618178159037826594508694042175936887693190413669502478652945873631283166773857609991800809627249658156519414100000332082853325779429279325400164657971607675800447250290349621640424972162968322891570076256839967963344649526270627025974694982543559205919665900663757500109343502409692100628126993516373291768674156690559371408999771620821771396233379516920095622914850099520946999591315831765648905525643842412431675457683208867062603322250485716729226778522665751355453970091081319071366274107687659109439167405391512776895919976540258847805596654038082729634561963877943466255970558782346029466626207603386686033981029259959416838835654138533910307591597909919748753104366874665390999193169824888425594237640779137818318564615315021934374501186592213150310735448602774858378648172926067739019215578294471645835297231530475626607874412908814016634674801073144336123810987074144546647620301187366706860917788569
m=pow(c, d, n) =
56006392793406553292769797366390438674411080408462327899182934918087372261966594651588266724494501501
m.hex=
666C61677B37366635346436342D336238312D346662322D383831662D3232393766393863626339667D
m.str=
flag{76f54d64-3b81-4fb2-881f-2297f98cbc9f}
最后于 2019-5-6 10:20
被readyu编辑
,原因: