0x01 题目：Top_secret
task.py
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 from random import *from gmpy2 import *from secret import flagfrom Crypto.Util.number import *e = 0x10001 common_p = next_prime(getrandbits(64 )) common_q = next_prime(getrandbits(64 )) common_n = common_p*common_q common = '(%d,%d)' % (common_n, e) f = open ('test' , 'w' ) f.write(common+'\n' ) test = [getrandbits(64 ) for i in range (512 )] for i in test: f.write(str (pow (i, e, common_n))+'\n' ) top_p = next_prime(getrandbits(1024 )) top_q = next_prime(getrandbits(1024 )) top_n = top_p*top_q top = '(%d,%d)' % (top_n, e) m=bytes_to_long(flag) f = open ('top_secret' , 'w' ) f.write(top+'\n' ) f.write(str (pow (m, e, top_n)))
test
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 (76436798540605363536477649122583467659,65537) 55186050945367642475707075553224810751 25230392976483617195172228672398327555 13402586421932983833466929662539579831 73577334713803339185143437689323273802 38551782957548094407447800753751168665 51711934113503641726046694816046155196 58300886844804359967503608900295384971 30633380627138465592907806456575067479 53301835725940512458121014414629084911 58351996524707437429040101587159043471 46610060507747647253774910292121057656 19342692024098798494578688637191950234 74381356872629590653080604770014608570 49981408798986150620247366439830330294 343345096895071813800587469532294537 17263697045821285813239884204415480640 55510192411883433931942585180431026378 74745674371157413506031135502419954818 58317986979406975295387076969578486745 67575969419043342560344160043521858463 19722181519789161239268079899458123538 49112192134235855326178030632415585433 45633293669673510130908046681991506353 35299411607697175143911073665709375868 43631509536595823002234087112287898161 52044502710786365313804257874283929783 22650150814130355340682778057131051659 27443905251127089688157448960205705107 2853412989187123916524622404120244444 3386450410200548528780578658202470575 34231137980284018396354125341248845163 4828852678059600440594651376729716097 43371979954046153211498507727979736109 53537732436369105085256483146955492234 44759935381236780538186499683770254348 8217839204034217101529742014217694370 5140383132413498698535013439891503428 35014674188828991036961241239489830917 46286379908818627302064904479347854981 50447772104548245055127155839548916161 55469559964575724561475519889794946801 74615511074650335629278954816347193472 6582134264246633258660973017210561275 51884995747430036690532805795300544679 42319797990737834257495597954540149433 23610290115582713978682410086060215158 66881329716839893865471106387111462473 909075398718289963658440530321300364 27756513980293361540523415158728760538 12740080891813608621445227491348491949 40944944366207791916630094620216336171 54370818651306565940441953564893798069 15396423250725553805177184667125594897 76020926204650928876469817909107582268 38180395914849495336268694233478365872 16210473068590040530463270833681952664 28710617260199516258036069513770033887 12775754707987447736193303749999974695 18005977177084028626312365652960774243 68384773149660073962766610150796419611 28325426067872375085710636700774830405 16555151637843597346016287022181363150 12267847175112244361016904522145166264 35304991467264900508031646103662404719 48160800944315308328888108176895789596 24115551551584193553056947224671895413 22244133292157063971991802200151458389 16947252261538876517708030045108230397 70816827019786838086321221858911035540 62159767044487104819355796098670515641 73905871936521551299105764298651286441 1674903898060435537143058710558017411 2638822964061780564962859913102684955 21942892891032557280866602790070207671 40337637415936089200641214557402954135 37221640257854924629129918209333201869 76335156736605168670936336240012218227 9852343908055380610866824978672547275 24990238420951414379757008860824754862 76054651628841021660831807995042682922 17001154513537021776068695541424520742 12254707970983210964070530314282206000 26278573582167989590424099138074019988 60377446267959247227765153981500449302 16646986416606335229554527078603791881 40418467774836669874202305775995692992 26016069727567824992672115324829140868 73081148132111464341568500220808369331 31673047411515577059112127074530487515 67447236827196256091354393855384086836 63047599001494777743421417688382288509 74523044010485896818801708305958434788 33226394205360449017677232326154124512 16687952135509650272359001667799498377 40202014131810502656982568150542291442 48778018271662249535139739038314099859 24613745709524835257275529176536882445 45789595549956580578863392196161928145 69434883406790893718883182461338676609 2654950873299768803648305488717629435 28563768289028017691942730658306461660 21252750302891015742350785525925130526 11980063502410778999893647170227777152 8155241293227470083098294656348728846 14097465343211016960327817851194107955 38682258228726193890138714866033439004 6772934507499279896884630113052591455 11077022556612609543474072167323510664 15570321470508342677531326954632033394 750612858608028032961039967953094363 48942529299328463788718161718501773445 18939172623041301525059363527057319151 63188329443267806641395875189108630997 61922540518669436619243784312637696066 55905928443882307103293066621791023799 45378048949828317745584214789476050546 56029426396155590704783097331267766000 18196725262137636868539077952087282178 53997016308690805344973726153964373973 57905320778151911926668160072363169681 34846145015411191369768173434982580216 54473482351880218528208942017216579033 18908144778734911717864313951037772547 39290129993658324178964052113719363190 67732219003325432115140571029252594040 3994506866605245477866886505944747873 52471756007888304712589215251851137023 1643624760978562436291445470214719763 21742129690789895185807924184624512844 41221992259707251153821196652421572013 75093552499739735977984981754440972836 55371483449781265642875914635444201928 13597468886365387289589588472349534536 52295196303763959838486998791021070611 31029206605576316172938446880964208080 53725579517331114664957961168627149673 75547177264754282663031670895206184334 69118763528437304719951895435725198252 12621663619760751805147079616517495042 37036262893874233922974473510886948658 75926800630911862283187685714646972216 64775156645992063288511100301630865523 3869176818185676946862140272530846584 33606183061067145645254886208456088573 21337279966091050565136681364160619362 41863289780788023808316573532510818687 22367585831790580314785243235628671945 11138423981498017687185182681852324709 48344238493491767429713789300535388916 9114177025706775071291467511403934627 2369807607007867929754201646611078799 32486759255636019003614349998118405844 69430435596711389057146433373308694360 55930545126519744291831576248089084877 44949905516642895985044836973991460730 57665373371282889383097771776533335101 12831141281994670682328945203694621635 56349008735152642234798870173001784343 54937877909358983725137319172947826396 62297220865005149250570213334045625465 26462419478920119496519719765373975300 46652428678273884958618764319582909327 11832792518875771991114957890561831030 47001269316646847708056462464619029608 59815894872435566441080225307252358055 9300274876649918767463730602963445513 40147147455671874524126774061402602264 53041249051778888816455911246843954949 26225020657054410256652347783394776061 23388213736299541535198656983707283908 19827859609131661501172229435226831720 26903124046982232580975472720762700391 472725185495004527275483775876625860 44162113157985293817593797835307709945 35267073589397082942234588444478913562 49164693950593033244235072592572708091 67186670706245446990252877893764564463 39674705819767647185341208083887833315 57501247857224418972134344445747464157 18384086662429630069955335132326044662 46336405320121708411809995165391509167 15328067315155675711792268624344900420 42428447990667337755561298059171545005 22311821917505740799574648650178983648 16657908374331731937243726993406582967 42967637881285518163441704974387925902 43083647853649416577670607419504528923 15227675589017975455675883780354796733 36004364034949587007474604010987430578 64247182931697437675610741428060795874 26011204129148864838768926563419479804 32387937896808623479315066138817124816 23467148540610175486782722270025351188 8138407575510542083316697741986966097 40448303323971138825399153219375312702 20990492979204755386711680804831950284 5032606622393700413563463028167480919 45572320595285804672546763004570475751 2697576927615136653521949312116319781 47820135134907957585261729032015508196 1801531631085730512559601612268846981 22300256815919904331477566105597371026 71601461186037515618460987018278878662 8840939986946157215272346953853993228 28541506760429312739759900541722804837 48716769662931571436165166434862016906 70245545857311291757824176752090615172 72326775881046625170993909304066950686 62693914265302512592049721833597075251 67577499750796736165581464710247788128 49484194507940175452408696241071251001 73518745770174706188500807549243278316 27231609289614889000589658851451000168 2463548219333709244854244236845935718 12003422850687820576020815049726339839 53222386855355299629986636639369454205 10862975889084472710944307131367926576 50263517279131247737773774178607028570 31572036226127813503878363109108131748 57742833213538630708641038141663214300 69064042415684932588294428395311336487 64147265955473613434432650164469617580 70275605025151141516550884220388466652 7478914588285598946881384891628027915 72179208123914556413783478949233045945 35102602984410184005567053836926866695 54676821516466471549230185756839223486 38778602498370176753958043897798075671 29523714028544863436392981978883327716 66096492639124474390384964712038288880 39524200952875756531303031617075324147 72116659779321139845384070158829301292 59621197327660998024510304332636068730 39782242801577043017045223978824221862 37368910667551147233029611392557181920 9069978015303196519230781714197951610 30483323264468964802469215142437392402 6113193036135292828722459078321304832 19318053896535523877158427256105938493 29822420662360453942709795394346292272 37526232600770913105544476534683757431 717452638395587204712922294788413723 33654741029814987313369351505856888049 8249320145240412310879642108542724682 60589858556148301355533054957471357241 46825454914848374408725197167114383784 58045847545255936799980570400201087833 52684847322422803581616720340195826090 46756711105421535556512667480197418191 71541708119416001212390621268612714301 2961403394813646436071997927847813540 15599269970911350005712695323277260819 22353254010752206848791930161686846952 12237896986738270934749855268265991922 61121897232244732020015169561707142944 12101534951800077461421353783996152672 41136167420472243931727728189359791477 28389349055504342282484038293437366577 69569769478414256145187182082569097325 74557943847613270784984637439329892780 34296665055599999304276235527067174566 64073534244906816410984119644410800813 55675356397221125159947807887992291783 71421200741022101087676649036860191345 39650216979025258991250496728501620557 28549209769356157258095587304686248327 33120081756034861686619426460249594792 26466049654773455860498972496517418132 28125016278291229091392810824821443495 35813535540236641327500527074068036861 64903840966563947959341031040196273695 1051247119041415582933381694025019339 8549537254365025592173327908288435537 57664154946360838545913075634144291449 6813116627832393154625416082804538117 73630574545074922135319459708379278283 14358412386115976898503805642784221937 58833762887768796127831667670843321838 49419680129380264666560862372241189173 70293110766410147397475690753162241844 60403179385577249261914169983862264489 1857812368505314880093639460129737996 75708221341718233888382436277764721660 16000721960732720296850944542171787251 44773886866430755281512192595014044623 74860301591643958332635470790110365833 32601072483171297153664725328253380691 46277488001461470531992550020278593701 40072732400541289217096896037501008183 70437122485443889632095484536864729564 5842231245291871561968630134635129910 71698996783347707866616461709082652562 27405571487555279714409256700681248821 67237149436936991771698502836361675612 70178422435080783462679134162451977658 48333038453762490983454185987130958179 8092347608893768629361778076069841773 37175192888660586255240074676139579549 5293489249216440974720528384995400609 14822718954662237332590158650848520892 31723616116690600961965364878394601601 52553228094114915018035985338629190088 10618829930027960669603837372135346232 2999382201018958987293425344575505964 501152901028905946071059928996232708 49338932744169602184404313095712344343 49568336589022292055373203312489388219 69223238645170476437475272952089182817 24710351085309602112527472563294525799 26664485026381528714139836103757761547 37024790340621890323056196686751145267 52858759042397569015012889379681703702 75067026536051838775779037733876437534 39683454180624399773767172920132905966 26387728022564006469934467314246884742 38956008011908076426993601023845651905 19114854026343954755487642350620866070 60269197580330253129929245772477733815 69425453988923884737185316492846064115 72049276247372004048001915547341492198 27020444298586136228512630810329361074 24514179828719805466049854770253300672 11387398938803280585770690925793807672 26981871177397542951894305683949006935 24890471248712877564487138622567803026 43569028689336718065355608958517719198 2841243383547217099989435276945505801 73114881462300024483651416174045717904 42287476880242010040554175714650635974 44387197665316392336941587961756795931 3912083375057737515892821795530340552 38254271733791723843796557727576796542 62387378560483901614667567690245695051 23353983253954117749671083584281745587 11890380775113551648722094612394458547 20212903792749344150387728605925026282 74341466346640978646687114436924172716 73302262117671217990837163662899246984 30303887392666513555231880880783311198 32171960639631813641629490317007528021 61097812909217317035183512169585829209 25792757414809254112556517604042651422 2820971132615398466647131671303007788 55092077264423661113641038963748334578 49554788238292628062732887189816139467 74771934831620321047412964987910590357 67720656448229753088547213144415993466 6718602819829121903616500132600299386 27403277384867425295835181972291535760 21856765603433909157069432483294899155 52678542842084120195158191310376903919 27036289905859519421045186459510769221 53949529951404075903480041220342404144 19869158060062892518001670873247684384 21423368194161529926258495179468700524 15507218173048511539722818882254911898 58493624846849739048541398955639821997 18576248300905745165463542420158250609 33123623650401168824226984597730163145 5066561639920535540525523322940514981 46154189500068014623011135729116964258 61348714290534129521581036579172409441 23497842736356918887959512603100822443 27643071511142367413891425427930557465 67224926973909923980664247289143460037 38507367295460233967001519975014449439 65229466825082379355511302750084744719 38171949543563355675378790857959496479 2659199859629667662736644420333889395 43081036380115727547920396392357586996 17531206520351950500333574552272373827 10628064469094293265451454157816993474 39730594027417919397834671829171945470 62006545314185270363347307768996407030 19572570545397883143255842308868014886 6699357463853099807412464562835728675 14376397955073247432491739119348089407 57192377840729275677048082982125179172 4513552466499363414186222664580980268 56598943604580243366799057800523215202 15444274163958164496791776375191715284 34658197184327096368877820299201518217 18406594343439425514333446513894410548 53128300939957954481962394611182805927 10389424837760798282728087275080561564 45849244041180773739540685723027640839 48561962867547472875257047808667489498 48076863048502996904376254792233103056 31887732291237149005229642171395782146 20298905340839730417185964185442148927 22293988118950779143063828473572525194 60713814077324533346139485956092939670 59144307497264927028473801484182140103 70979914751063744850455347535871745789 48051923036769777739685675552089813085 15779320762096918132913190473779633026 72860747964178449434821841961897160795 68158422453785776448496625604852512896 75430359970533662718610416885248746103 39733138524461500034189776711952631136 23461522873961039627762115204279810425 67751781759615895801076984903269465961 55059308664727791650672545472787246580 62702570052506263845880682002090128305 8429676534985343397917920218059103540 31210534661845991977138598033717576126 56970958856331042229656334983727387926 51854496037160531880091901578118555580 17532958091849925993863271115127233227 75636304487977328653964399096355223348 47582528286780842346286920497648121539 59889453489880466198129715991695437909 71460535859867816389289890166577713886 11061888269887829363399225472887739506 26940999471527483474663193401432672973 9124798074059122045009030126969177244 17272172828976609206263497076670286903 9953781736684486658170184214564469563 3726435727193783980418902889173734926 24487365843010309788231226154551870489 24739090888075445918159490045608899107 59209165445424686024941838268459504117 13318192398726657948875374860980352981 67476353536101821326389660329109412849 1384718306590060544856527893425647463 1287391443400184368176229041521636354 40369991385882907331114817073400604517 73239753442912730698468595505762923718 33816391019462744010106232817010306280 6979293363164184625652874445245822514 33727278198510261153645899991881447632 18568313418586732598578014107797498271 58602442666031882232311625755800803561 42168548859211219151345015430381822802 39052432118990439618873824576207426221 55836500526512599901511278282763611693 42531945108161301145085989554596973069 3369025802088037815201828185795922075 58204450257533473367605797891898368484 23718822442805478730889493054809272273 63772639552111404065900883768370553629 76065307277615491785591405085816741627 70396249590333813912567930498934643546 43803070237166649396998160133628691407 63918161247510715740930443389992865782 61381651756402419177093925122018840294 54101408524701045409560353981004106388 46851688461070740257378225455520117795 15436308325251486223084723227745268731 23218631189170791422703640138470721801 75392280750504295953961664073218456783 66553532300634957416615528619088258065 72698787393965395194772232749518395438 19535384035609800081997654944702946500 39422173474990368057574374977824381951 40004813095058812542774172239636346189 942552610107287472181207404395965160 2585006493032030325573369561874973416 56657207473342746341618346391857068882 45353439056243093600420538583717284727 5326381030912940100950496754663527881 52574740508116783755236913015296354008 60767386508248278010316067650127924939 58968728780343858041625641034398259578 58606164016904507514212988506101806192 18587467254459798712802505313686639678 55422346534536990733696073415992919046 28624375483769614463607152503350572643 13148327912755642168524248255048779122 31467720336603914934067757647369482012 10683634146896984139628804526913660661 76170402968596187847701210126889782108 47374612181202618634027600446937096913 36089678865849269171689697815903972364 21217406106453015897742453966622893380 14970412705963434083222359708019347920 53290629357146512929566264012966296410 38712736084222125437711235986824516170 62976649126413695078446179985640722909 9926589243987961026927307135335663637 64567995678465294136351877671450464565 46713540283782404531686555202144638278 10440888409743354127954409246855165474 31956593614000844675478120015331054528 55499046927817135319918513704109758455 46214390544824746266723894169001319601 49296377915776716441676864874017783736 67334769101867458205450877829547803545 433192196347974048429577633048338499 52872806532639448089006834738347612861 16836366767861888570007546478334091897 12953440266362047492520847213284651421 58814022084376292773896013187507972687 48946546513435459728242095354620767484 16690101992080929788000902609809364938 48643514269766943371008693864376158458 57301152785552158653026734737845206739 36092926765017106701667283136511092626 36503239268458633197504443728223255639 20035053854728219741356182859230335102 27448195615098643105059278634289103728 804096397543961679227858842556568221 42387391011062645905124272356232649581 61914204868112989399807194774948928854 50471281425013685325792812544053391833 69199839034721925215627350821951487646 28714477419050742199181961190943977649 64352578296187124006749631627623859099 66417142292403444690306408437925436539 16917869489156458807988614612206952611 62433740855979549009477295935969264632 54703498276817055998735161171803303420
top_secret
1 2 (6778341886512983471750645456950728290523536616361299371741958671360393083882319627518672438545115814129137657182781214208816455570796241668174521203607532582846713044946980024783900646043967377749611378975743784775184880644929838298609658208272073728954171415761808451070649956713090699363828704967425598555240857728605492559334918924364181243615109772911597831275788990921847678043264311757080086808770372237384343263695430482298224638114383481163242159396421912093570982271665015871698548239583006809079195143432434252317382780354946136908751753704879594650848364606279745816610061533345112504778579863240146035803,65537) 418919112322035719080296282188262556318147208740019952103384898777739260429989830467043589948286391778496053290993573572770668930715827948954387013380968757428438279330384918638646330090780491358345953558632784799412654785756895941844475592045474255714700612603241873989982425698945208444003573618381342067450033353217477323111093274062491515883275867746619738296397569905705052009378569807157998159800021519653031832333686380591812114745289471610313845110578057278593565079742329184877876988624852591803357662165422951088131736792374156848783221486055402017298046164798460834330495680663944310194208485613787684535
0x02 解题思路 分析源码，第一部分代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 e = 0x10001 common_p = next_prime(getrandbits(64 )) common_q = next_prime(getrandbits(64 )) common_n = common_p*common_q common = '(%d,%d)' % (common_n, e) f = open ('test' , 'w' ) f.write(common+'\n' ) test = [getrandbits(64 ) for i in range (512 )] for i in test: f.write(str (pow (i, e, common_n))+'\n' )
通过两个64 位的common_p和common_q生成公钥$(N,e)$存放到test文件中。
这对公钥common_n,e用来加密512 串64 位的随机数，也将其存放到test文件中。
e和common_n题目给出，且common_n位数较低，直接通过大数分解即可得到common_p和common_q
然后就可以逆向出512个随机数了。
再看看第二部分代码：
1 2 3 4 5 6 7 8 9 10 top_p = next_prime(getrandbits(1024 )) top_q = next_prime(getrandbits(1024 )) top_n = top_p*top_q top = '(%d,%d)' % (top_n, e) m=bytes_to_long(flag) f = open ('top_secret' , 'w' ) f.write(top+'\n' ) f.write(str (pow (m, e, top_n)))
第二部分比较简单，
通过getrandbits(1024)生成一个1024 位的随机数，再通过next_prime()取这个数的下一个素数，
从而生成$p$和$q$，再用$p$和$q$计算得到的公钥对flag进行加密，将公钥$(n,e)$和密文$c$存储到top_secret文件中。
本题的漏洞点是getrandbits()函数，
最终可以利用第一部分代码给出的大量随机数，预测出top_p和top_q。
我使用的是python3的randcrack进行预测
安装方法：
首先需要解出第一部分所给出的512个随机数，
大数分解common_n得到common_p和common_q:
具体代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 from Crypto.Util.number import *from gmpy2 import *e = 65537 common_n = 76436798540605363536477649122583467659 common_p = 5105923512372711233 common_q = 14970220050375442123 common_phi = (common_p-1 )*(common_q-1 ) common_d = gmpy2.invert(e, common_phi) test = open ('test' , 'r' ).readlines() with open ('deTest' , 'w' ) as deTest: for i in test: if i == "(76436798540605363536477649122583467659,65537)\n" : continue deTest.write(str (pow (int (i),common_d,common_n))+'\n' )
得到原512个随机数：
1 2 3 4 5 6 7 8 9 6664610210323177003 17661097700361369885 303206696427486439 16389245002373137587 5670728676319485833 12056818099668268163 ······（此处省略...） 1106083047604041265 17146900470736302356
由于RandCrack()所需的随机数为32位，而题目中getrandbits(64)是64位，
了解一下getrandbits对于高位随机数的生成方式，即可将64位的随机数分解为32位的随机数。
具体原理如下：
1 2 3 4 5 6 7 8 9 10 11 import random random.seed(0 ) a=random.getrandbits(32 ) b=random.getrandbits(32 ) print (a)print (b)print ((b<<32 )+a)random.seed(0 ) print (random.getrandbits(64 ))
输出：
1 2 3 4 3626764237 1654615998 7106521602475165645 7106521602475165645
即先得到32位随机数作为低位，然后再用下一个32位随机数作为高位，组成一个64位随机数。
得知原理后，编写python脚本进行预测最后的top_p和top_q。
这里面还有一个小坑，randcrack中最多提供624个32bits的随机数进行预测，否则会报错：ValueError: Already got enough bits
所以只需要取最后624/2=312个随机数就行，前面200个舍弃，具体在下面给的代码中会有体现
最终exp如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 from Crypto.Util.number import *from gmpy2 import *e = 65537 common_n = 76436798540605363536477649122583467659 common_p = 5105923512372711233 common_q = 14970220050375442123 common_phi = (common_p-1 )*(common_q-1 ) common_d = gmpy2.invert(e, common_phi) test = open ('test' , 'r' ).readlines() with open ('deTest' , 'w' ) as deTest: for i in test: if i == "(76436798540605363536477649122583467659,65537)\n" : continue deTest.write(str (pow (int (i),common_d,common_n))+'\n' ) from randcrack import RandCrackrc = RandCrack() bitsum = 0 with open ('deTest' ) as f: s = f.readlines() for l in s: a = int (l) % (2 ** 32 ) b = int (l) // (2 ** 32 ) bitsum += 1 if bitsum <= 200 : continue rc.submit(a) rc.submit(b) p = next_prime(rc.predict_getrandbits(1024 )) q = next_prime(rc.predict_getrandbits(1024 )) n = p * q print (f"n = {n} " )top_n = 6778341886512983471750645456950728290523536616361299371741958671360393083882319627518672438545115814129137657182781214208816455570796241668174521203607532582846713044946980024783900646043967377749611378975743784775184880644929838298609658208272073728954171415761808451070649956713090699363828704967425598555240857728605492559334918924364181243615109772911597831275788990921847678043264311757080086808770372237384343263695430482298224638114383481163242159396421912093570982271665015871698548239583006809079195143432434252317382780354946136908751753704879594650848364606279745816610061533345112504778579863240146035803 c = 418919112322035719080296282188262556318147208740019952103384898777739260429989830467043589948286391778496053290993573572770668930715827948954387013380968757428438279330384918638646330090780491358345953558632784799412654785756895941844475592045474255714700612603241873989982425698945208444003573618381342067450033353217477323111093274062491515883275867746619738296397569905705052009378569807157998159800021519653031832333686380591812114745289471610313845110578057278593565079742329184877876988624852591803357662165422951088131736792374156848783221486055402017298046164798460834330495680663944310194208485613787684535 phi = (p-1 )*(q-1 ) assert gmpy2.gcd(e, phi) == 1 and n == top_nd = gmpy2.invert(e, phi) m = pow (c, d, n) print (long_to_bytes(m))
运行后即可得到flag：
1 flag{4f43bb3f-12bc-4c85-a19a-833185d1deae}
Wechat
Alipay
