2022年4月9日和山大打了一场校赛，打了两校个人第六，密码分项第一，密码方向放了七个题出了四道，感觉这次密码难度梯度设置的有点离谱，简单的那几道板子题一放出基本就能秒，做了道难的题死磕了一天。不过我觉得最后能出这道比较难的题还是挺有意义的，也感谢学长的一些战术提示才能最终解出这道难题，先来分享一下：

Random-RSA

from gmpy2 import next_prime
from gmpy2 import invert as inverse_mod
from random import getrandbits
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_v1_5
from sys import exit
from sage.all import Zmod,matrix,vector
from secret import flag
e = 0x10001
e1,e2 = 6163,7411
encrypt_flag_times = 1

def generate_prime(bits:int):
    p = (getrandbits(bits - 32) << 32)
    return next_prime(p)

def generate_private_key(bits:int):
    p,q = generate_prime(bits),generate_prime(bits)
    n,phi = p * q,(p - 1)*(q - 1)
    d = inverse_mod(e,phi)
    privateKey = RSA.construct((int(n),int(e),int(d),int(p),int(q)))
    return privateKey,p>q

A = matrix([[13,11],
            [19,29],])

BANNER = rb"""
.--------.--------.--------.--------.     .--------.--------.--------.--------.--------.
| C.--.  | A.--.  | R.--.  | D.--.  |.-.  | S.--.  | H.--.  | A.--.  | R.--.  | K.--.  |
|  :/\:  |  (\/)  |  :():  |  :/\:  (( )) |  :/\:  |  :/\:  |  (\/)  |  :():  |  :/\:  |
|  :\/:  |  :\/:  |  ()()  |  (__)  |'-.-.|  :\/:  |  (__)  |  :\/:  |  ()()  |  :\/:  |
|  '--'C |  '--'A |  '--'R |  '--'D | (( ))  '--'S |  '--'H |  '--'A |  '--'R |  '--'K |
`--------`--------`--------`--------'  '-'`--------`--------`--------`--------`--------'
"""

global_bits = 2048


if __name__ == "__main__":
    print(BANNER.decode())
    print("Welcome to the world of random RSA.")
    print("Please make your choice.")
    for _ in range(6):
        choice = input()
        if choice == '1':
            privateKey,signal = generate_private_key(global_bits)
            N,p,q = privateKey.n,privateKey.p,privateKey.q
            x = vector(Zmod(N),[p,q])
            
            y1,y2 = A*x
            print(N)
            print(pow(y1,e1,N))
            print(pow(y2,e2,N))

        elif choice == '2' and encrypt_flag_times:
            
            privateKey,signal = generate_private_key(global_bits)
            Cipher = PKCS1_v1_5.new(privateKey)
            c = (Cipher.encrypt(flag.encode()))
            print(c)
            exit(0)
        else:
            exit(0)

了解代码

先看完了一遍代码，大致的思路看到需要解RSA，无论是加密y1y2还是flag他们的模数因子生成全部依靠随机数，那就还需要进行mt19937随机数预测，注意到素数生成：

1
2
3

def generate_prime(bits:int):
    p = (getrandbits(bits - 32) << 32)
    return next_prime(p)

这题定义了随机数生成为2016位63组左移32位的下一个质数，这里我们先测试生成一个：

import random
import gmpy2

def generate_prime(bits:int):
    p = (random.getrandbits(bits - 32) << 32)
    return gmpy2.next_prime(p)

print(bin(generate_prime(2048))

跑出一个大素数：

0b110001100101101110001111011011000111111000010010001011000111101000010001101010011000001011111001110100001111100111100110100001010001110001110000111001000110001110000101010111011011010011010011010000100010100101110100101010100001101101000001000110111101101011001011101100000111011101000100001100011011001011110010001101010000010011010011110010101011011001101101110100001001011111100110111011001000101111011000000001111000101101100001000111100111110101001100011000001100010111001001010001011010110011110000010110100010000000011100010111011100000000100110001010111111110011110100010100011100101100110101100110101000101101110111000111110100110110111111100001110000110011101000001000111011001011001110001101100101010000011101111100001000111111011111011001100111101011001011001111100000010100100110010111100101100011110010111010011100001111100100010010000001010101111110001101011101010111010111101111100010011011000000001010010110000010110100001000111110110101111100010111100111001101110011111100011010000110111110001010110111010101101011001100101001110101010000100101001010111100000001000000001100010100110101111100000100001001101001100101010110000010111101011000101101001101010010110001000101011101101101010110000100010110001100110111011001100111110111100010110100101111101100010000001000111001111000100000100100001000101100111100001101001111101111101001101011001111110001010000010100101101001111011011011110101010001001011001100000000111101101011100010101110100100001000011111101111101100000110100111010111100011111110000001110001110111100100011000000111000011111111111100000100110001000101111010101001101101010100000110101000010111110000110110100000100111010010001110100110100101001011001101111101000010100000101011101010010111110111111000101011000010100001101100010011111001010000101100111001110110100110011110000101001110000001101011000100000000010000110010100101000101000001001010110011011000001101100000100001001001010101000111001101000001000010110100010111000100100111001000010110011101100101100111010100110110000000000000000000001000011000001

观察最后32位，左移32位补0后求了下一质数相当于加了一个小数，实际得到的因子素数我们再对它右移32位就能得到最开始生成的63个32位随机数流。

每次选择1时，题目只返回N值，需要因式分解才能得到这些随机数，而且一组可以得到63×2=126个，五组可以得到630组随机数，足够进行随机数预测，程序交互主体的大循环有6次，卡的非常好，所以这题如果需要破解，需要先交互五次1生成足够的随机数，再交互2得到加密flag：

nc 43.143.252.108 5244

.--------.--------.--------.--------.     .--------.--------.--------.--------.--------.
| C.--.  | A.--.  | R.--.  | D.--.  |.-.  | S.--.  | H.--.  | A.--.  | R.--.  | K.--.  |
|  :/\:  |  (\/)  |  :():  |  :/\:  (( )) |  :/\:  |  :/\:  |  (\/)  |  :():  |  :/\:  |
|  :\/:  |  :\/:  |  ()()  |  (__)  |'-.-.|  :\/:  |  (__)  |  :\/:  |  ()()  |  :\/:  |
|  '--'C |  '--'A |  '--'R |  '--'D | (( ))  '--'S |  '--'H |  '--'A |  '--'R |  '--'K |
`--------`--------`--------`--------'  '-'`--------`--------`--------`--------`--------'

Welcome to the world of random RSA.
Please make your choice.
1
319921123311250552662963566647233721176500532097925505551548615965620926886290107004282962564396760204590468753354087637632596627283389303984969095543538774832852895025313854336617682706352197362418638206543073301189608132934178272448280700099991086560803792660780736921365654510536546191545903820825352164469145200595638053567489038365292280396297682441017231601120272720968293290636862864945870109310394015619502123336027505110147899564501295941242844401235448208551347533131793232155203435166720019251796222917958737174696093799200811639151889416773884099138368196585180556987089906154502751274251702921482591707082824826896528955613182269483843333285568738360741886640681092035773605438887662505159270796669448808076856295823895234264196954633882031001724935347719732441864407930514810976560093125404511952867209059623444494325114594996641049835394499590618767684304963563299049578241522328014002403690904185320105830639934733326227045308680083189915718559098864854510435072431091298351365139202359934453258210782585368099447241705559813727602307985927435898194839439434163080058496044725980779306785235534486901948642672517025391781421160093032191831056281446632496876808397979406212517252958889052537024809161355990518029929969
248292875804004341487193963587418460793015860983343659729627383649600562154259358584129320729975693092182850315023754970095027674177520062160081385829489999398851656460396267064471651504991787753897600165464399162714333725852108264765404549646356689169774328016897055213513659098660700163238808314499831273389824485995857140645954536717894810800060744488273316547697541161681415958432943782338051016988235483006770823488933136897020554203178244197502012795053551048100276519840224992613689013732623028934965584811831143911305441779886260797220241977972033615990028418358826359968343897398821106856094954413945798907918678293183082235577560119112547038959525148322763823839046696386613319994738999783947199590531544768775692808847538511358347345961677089604593395682205308621002457663787631613273274022455500740217424160275888894292062475958187405993289602952730106121166185714356643453390540638758319675521881312024226126409644961686094789094555539949200025541322509192008502810890673721136882951683534363469649407225558267779718952546008673217922105075461128591140566706367413899119360441045405844432445235817784608668283513141813047885521529347709023277444323912888989918220180834119379811483872772135494735140660228469428830964530
296180744100107627758305803516955340735558610309703831618835666444138490117343532242009220325303295510764934839650890329415913083510508318219183867155229006613035882800097723061091284831633060962879325372568115856456841602547580917291722852871793433471643367474974123185317625795292746401531802938675718785468748265718598756597678742309285333084753463463911170855807120117785391014177340178847064198532628205532901940135177816329079615728225052445221533435398969165247298426483478788736418651645495975740824617906545979330594372548117600367071940846614291762730294798674263510602807627691374990413772565733031188485081012803619040113850825410586940777678530030755343410465305025316354508831191088580419179330492687487852916636844333217073647477740970328528182474872923076646152213713921452837288812643386947407603759919404325424354630405612235758684539078304413046133956422960652314198670078399947591407271051787044259051554945886192870328524690468787651125309448228277503786656782815364975714286271137126118656004127038041167492890493455265764937552969782098992644454795704577084669939924649658297313008791286459600996857834780090659852975185140737006153546204113199194069050763512604482342589174038583411788997367584415563743340790
1
599110224308422610498885243404312429997177742018723070681626765267732786181152678750071483014346760950051734617610980049030890074185326986414140752740945426043572643718817292642671545022342097343164320475481125005511915062386511192750531215560323637471972117741700673604936286573301916241384756976273580685682913548756589981155428792124150225941178642113257150679698880071645553511181173883345101469622719344233722291848031318477750188110862073613213668753924645928575076145217645286278155576444910095487452856165516739845826060854104698626407038868953736697171989625407302305007912084794500759881256763408658774527496156696874315726095000344088043895258903767834768991583323537732703746682458050075635230240429775422444182740441361192690178542018467094016140059649350780667573179467800446685269685769332444562674125273351147969810077129441223813961453867316628820306319223876400075876373647814797515239817206564861314231194035802487996534734716180541499231064733286600825832248720133058267665225372986667999830641679212573884132642066093974917737361905234891402070297053289894322630861180118358700800642277403667514430348500006973280512066703404817926073682890049469420438004128393903376795534421609536502403618737354345776767809557
176931389707528532333643293274655713467866080265053285136083463468262516271121733861463524578770503903299476192462414217588405103808830287418952647224740674444215065272324677390543276613816896053074302438652440655659641657537193059597393638416182901134595550137990263713298057951419194342430107780930999038188587153994124570186567704205312650035672893717801156504083484824727347400152678323131659525133752194372791942803899593097694860937464143593457219248740023332020372072436505120470558928852088434764645410055511263334761560328097444749789959966376288430211336459557555092046090064609896642870596113288694780225634647867281210671117808505871363263226868334708852922005728999508478078595523108156621337361245586806939274383146616685906803790102031200753657833809494074618641106092244627257806217431922190455598898638812355858202024312198560056114954424987895506430303657593394391539732055591630532027063746485277742767328761858501447181667397420384446040681677602749514035730844334140735074282955968546966184623952444350809497205207100479517975199861131974671098056262855687103144442821719415871807018371037443387516644803223973850308829061960130368378893261176986431944217973608429502911805758922786547560778452649318154612861967
207825535879623865503097506381310741807898563342999422545658227690482860570590516383855935273188527718395578010504901652766942519822324143510275994937930872623748070639611098588454967901146797122950194632033675562625783763405679992217014873537762961389175695619305119730391390356873938973446359987881369521735928896421165165050426604099270352684944316840363736268429526864889718104018006472013834578999658151840662269815703540065548283955329961781918836244179184012652332665537289529366969067032441841608013817519301029589854737293888059968854497590399682532480192708166880928264360458819249385985000132745990937500956684132997265337340990054223510325085325876943187026146893100295481827820789579613628373021305786762272014306651642062049190186870382876032234837379443353344294059752180789659187717099411362684483418311653654534993658405246985723278808212555344671100837992053963688157637616963241685755348784040248979693639307270954751360300904564908809513136996918206562709964367755857169510548126386207318744970653803079758998769906758394220917327699200076235635461400456496200309572279548621825633543713359900504179332751555630351786079010244112977343569035465586377711479592257479060619330888392439487337503238360580548529118774
1
384998826819481882761848191143359204391153792102936797952487123431795928602128228587925293269182641167333316395663009756616057078812914618103709914853868671213075759006388222112859289793312785125519599636704794089696100330011788336290676549232518198379997908178761546709231733881624365460039160081054662380632396689836832546615865310275182804640492770868708692058413252519866099664032024736179195034707926990571556586839756024744587488152752561291138873158856991517081521016889242469285819552719905725580617648713215279020396226216541318638673492101090271474958210917505042292032944041085352664672037560206133336097289055143608958748235476744694786360538392614406079700804431378395467269765783246340309258568191256941214374291469991923243836682113882179730002144373914685785923439171546254291846453692663231157825191665781110039101517064225839961966881165888243102656766016651525006389085782969509941189752601844238960885306992131990050538920017436228174787367041358825007811717342276269001986620224870765641387156394784345759115202096559242992905646357564409484140096867391264765421036587476574846172385130923429202440439497574125845193100612292676551657321277120751650068237013326247682286358745901149134831233360299637481478476501
263412959517528061532217746494794166082281553294199674428880147566246392753433764409953717919033289918824130484554076531357124324259498287499308866073220118826317609200284908288861969777215595841788765768992142011859613032976380802799562284652189395740386141224142260554976714706959099938813238493527211646768966072650649975671968174558189981715133171111486170067853989114337687853470560553517486354345050390387023851238181351095655806518004184932302016785690637561739925436741947888687661210178752387715595895021756008188472827201005709762448457715023486287232182254910421892998725128850133130650731062190401584089260857064324303526505680880583681332678447312646319534097554377495547408990027316588003909189937934533078846641447285404727313766068726950684894154368494881686483287672487479510050747957229496328638768715372506730837466648041842900978823550603103981055081374871877726693269296223748736317192577870785252905659796624463797774864114025525725228963680130973220639435350168518740097315345932723631297793189729156242238540526331759878310860878056060933673445786292478116901951419570480091573958293874614303092653905723270744036932717042344970542962385957902035661776041125118772704377131246174272394870998129203448444725457
379141106506112115015622970987612647085791358706332228662782435574383644676152728354901732525171316822080494398925057112244202125081035390441248680561723571333542354357533545503976082670155532027042252094502311476538022286377130159789512873129175565554261137462364776243241919928277766680994345146728975502967017499701417224964087080949167650105441912270149179803259414150473042807136414890312876902363747748668355388769973433905232133239745960886638184079596160490921229840436293043438908796367159430939249778899061028907959673137331957622949868497019067787519906919985945944030095789832143522630084187060738458996618923101199548583721210230171193521188080450859417547063660379782992717082989353180071369686174809343601715811054580233823428833882027715672990671564114924057482648920909420857280646240681251922428786226530645228543301278988185748803982479105788150494880973738178008614500089746956457868272279069731491447479881552976484627779476305213007190643556674347291191236876757632291557039643125132398701129213344780986150303277782898113196403386247175084953623350120919113636506905440280334789880530385758785840713823113405103518810269832345160384661926888648035985189080612407421214999677760298747251058236414655245095652118
1
507245232253935808341536559251331701837149042018245019668938390550258643891056371194634189150221240155457817416421363647814996662621617987154459880940024087015512695828164012075638713135374561699637353865381550036798462896607057683996864793778246319726533085915823440503386062570616735640817366048926965475520405031088255626435556375118364904199343749626096845737830245083121927192440465061149995552046837833655802716107749310515199355826503474221188405390489548162218224078084930458858844022022203284778087366338961303096801879481188705227078317196089916431962827446006365294990445055140495563290653579866892084838798684512066717774937577495068990501882865117535740192140050077440367096171641020261519561740232716507034084869012311774817541750130260940359846263173411914427496187682304043909136422023155688402393218661215002088157756621995273150568685973008999888016136364741781537185135514968218047327827360747635729718588277278127875340312839143652808925545634557874389933187090989855613050361001333248189225142340998930410951347842736412211513706668693633697675716280682959923184620261330324601504956687173647392045782974315575577535746568626528305515290788891435427759726584517509669935697997687347132761440317609787903713772833
124638905226754098806817101032457294027818026677971494020638032730715562312579631139751218085640891949824822961987590218693524984007767250952367221316577733970586428863363878927365121159858236201167468626199615437062864556583857137289152391101677883335117179636284725331078154446512795545548931320054604998696082561634212484005423084065746123675833928694573342777178903003218928956661006433506308115777403479769915801463593189394473925162998131129243252794347652208444796343551190165683495708053585943387165983026025225586503213521312728373798714099368812992550361456831878231181647979530725168365995127709512315425979943920184175875442833726779334700048052511922581466302999698402150250186533257302131814434773611410298304884512272663506831636174410056656041397953118791283468037077063062708252083364173645585027774359881969362081243862169106816969337560807708649492829423385487494334863325503464356219720923038079727910572046592552101622371785835982457894422429358259579858598897194842634038228873614534636634007653502390072087089687058833448985840998420852204735268996943085994666303766339029914202026076638444002681704238375403865888266480808789084663776141406753983837131363745790160009558260880255569728540795480657163657953946
240874010959668572995066513021604834764425643168141336894751714170296379975601634819243224391219902974304208195520659715789892844864738149125965473223544126222013293617461267503458636090904173180107731144768965660013134268114307083405057958491695370283309157490331842423852627395173777572162434426061609818108992902161232015774852198644380599273195910771743171014623866805104568008513252647009041342172177979593802063541085021499402512275261687814491161889425621836508791077467516208035467145268972515958642850076780236306042263622373425617254539706702530330405735315726694484094775104562223077864142620431567761301838030348639899377905928432490666515339610677294311293479799667949121649960116150972134318394444739737272007852466589632871830703701132556614595722322861845953059129079861248033694808791728994607709310890273990485928972362823137452455159402426525721873635741495732972480271703895019278619443851067282718022260194750835579691315723727049269118671182042116905641098827646351397474435913964966466682503360896184533601267594244407375573099196467997005589139020291661910118149590407846330309321371481613870685679721311438357073570062809730718699957486858818038505720111013693243248156523750763299063756297514168747750465364
1
75854144701123527418530520540977973114878453670553534643882219139491306909566751873750088176758684406436763229689376208407654442423255987090092395561042196383263162614865941727286943944745838052909841040506558873374230692573883334829385258214209222741721762230873266837628111684878771035789992785928300972636174142008029210264139228479951126872954369317657960423521963247660759233472768720444568215447251655176638426038985154193450561951816088995111813541660720177003733108376803395757709839771329616920135924277014003893558451863445470200895348470550668369618940621168047082007338039930373702266500734062873406094876687795832254523678271245825888065478094110511855190455844712670793471844450310564737613914997090950777618290642586363118592128104505864959053007490232765809998928156931039879283271663032882671695655080563521554598143954434024975211054267751406687119778148675259865111763405130922970467957254060273774851666343187015289979493015079684632598195423790807537053192669844475177043837267953013535247975192331371568028242008149496566482991252297048372190860668946369071350187804162802690175670871752785725929028598825704746328553329263200182801618773131210391323623123571074275034668806644923614133111322181107531343085387
18582470997758640686236228908085341038225622737681493954917063804738618898712419270474742101006315492643318433628598836816813533694824248045884321325595355841890943617828532403616000912577086644372202645330628765396827331380955730706619925614732897050719845498551519550042822486465698195700395659904399923479294949397360252564375164859658616041418783814270575835086070762241270955845077325769080603136408519397135675438167569509930641059447928283246362575761844787578057228391227525081316282399980870403873890449190699742629249363843763135077397266696525295092990498552303934211282420029219947701605216360988122204256860869270689055525413147030046394542537903178052990908980917559477900583662402097831568581585052609194631770523816521340882539563826686094386375094443448598008561338600827387911487385354500338504586485019285499176828964556777072527901936660378309368240614930466339417396968133120970452985733610014213518831608075125802060973854607667508011882267568402764873808900800530842521638480088265537279572527763624288660923616067565629543911677095001915898330229238955774055979207056770208399757003820338235282968934221437095086547128506770210235670418776763190654482110170379918285673805215053246401040193192956953268331622
36556408746463787647283291114860926084413826323975417331434236048369702899209317319855560955590864192980782669198910310936181985421958079062881820644235108707192257485969915113992379078661833478031287158013175864666970600816660558242592871154648216509709983408883311441271602215006472852599820626284218983903315950977073113838522988854157274942417491019423863187664036084886644310321834557183890672959568588214257812855069344050724095175516876437188197231118651365186333270059336126359640577335038523088705217626982898565060228333852801777246535752352869165095573855823735948174922865697264235706020909965539426748047857344444377027906644389172847633205817227611876561360167890871362131163526710133933874191746985120960174155658259035142224982293368618632585314179241305046091688155868339662942690390026928413114752446130829479006328954698902214804311094329442527936226008602543427388390619871852403255213365039241085741171761358361595544674241102035055481032109678589244247237183299614969715231782356450004560306100702155980392220392264655796593332021713202404108089398392228728950513946676310772066670151815602341071035026748525468559749558951651958536761376736909403873653366739774373625807219500731753314833571602901919383375427
2
b'6\xe1\x1c\xd8n\x1e\xeb\x97$\xb3L\xf3=\xb5\xd3p\x12\xd5OM\xa6\x87qqb\xc5>\x92]5g\xb4\xc2cS\xc6\x99\xb3\x9d\xa6\xd3\xdd\x1ci\xbd\xd6\xfd\xe9\xcc\xc7\xb4V-\x8c\xb8\x1c\xa7\x18b\x84F\xc2\xa9Cy\xd8\x83u\x0c_\xbf<\x96a{\x16M\xc8.\xab\x92\xb1\xa4\xf7cGN\x9c@,\xf7\xffrrV\x01\x03\x9e\x07\xe8Q\x7f\xa5D\xc6*~#\x0b\x91\xbch\xf5\x92N(\xd4\x02\xf5-\xf2\x15\xdeG\xbb\xfc\xb6\xb9\x1d7\x086\xbf=\x9es\xd2\x1d\xae\xb4\xd61\xe4\xcc\x7f\xdf\xe0!=\x14 \xbdP2pI!a\xc7+_{\x88\x19r\x8cf"<\x94\xb1\xce\xbd#\xa4\x9c\x92\xbcw\x92\\\x87\xad\xb9\xdf\x88,\xf2\x14\x00\xbd\xb8\x9e^R\xd0_i4k\xe2\x08\x1c\x0bF\xbb\xa63\x94\xd4\xb5\xe0\xd1\x93\x00\xd4\x9c\x96\xe5\xfc\xff9\xb8J;\xd3\x94YCr\xac\xf6\xc2\x96T\x17M\xb1=z\xd4TI\xb7\x84C\xc3\x92.\xb7\xe4\xfe\xe0\x14}YVc \x1c\x1d.\xcd\'\xber\xa9\x175W\xd8\xd6\xd0F\xc7\xe3\x86K*.m/A\xaak\xf6\x12\xd5\xe3-\x0c[\\$\xbe\x05\x95B\x04\xfd\x1e\xbc>S\xbc>w\x15\n*\xb7\x8b\xe7w\xbf\xed\x05\xca\xda\xb7\xdbs^r{\xb5\xe6e0\xb4\x90v\xaf\xbbV\xcd\xa9\xd8\xc5P\x01J\xe4\x02/\xef\xe7N\xc3\xcd\x81P2\x83\xf8C\x06sq8\x91?\xaf\xf5q\xfaN\x9c\xfd\xfdJ.\xa7\x1cb/O\xaf&\xb0\xae\xc4d>o\xbf\xe9s\xcd\xa7\x01=\x81\xdc\x9c\xc5\xfe\x81\xbe\xf9H\xae\xc6\x19\xec\xa8\xa1w\x115\x8b\x81\xca\xce\xcdH b\x8a\x87q\x1d\x12\xa3\xc7\xfe\xda\x90\xd9G\x84\x94\xd6\xe0\xcc"@\xfb\x07\xdd\x96\xbb\xc5\xfb\xd0:8\xb8q\xa8L\xc1\x04\xb1a\xf0`\x9e\xd7"p\xe1\x03=\xeb\xd9lQ\x17\x84\x87\x8e\xe3\x10\xb6\xf8\xb7\x85\xeb\xb1Y\\\x17\x12\xc6xGf\xc2\xe1\x17\x1f\x08\x0fV\x94T Em\x1b\x86\xc3o\x9e\x1f\x82\x80\xce\x1e\xbc\xa6'

解二元线性同余方程组

准备工作做完之后，先研究选项1的RSA加密：
$$
x=(p,q)
$$

$$
c_1\equiv y_1^{e_1}(\bmod n)
$$

$$
c_2\equiv y_2^{e_2}(\bmod n)
$$

而对于y1y2的生成，我在做的时候一开始把矩阵的运算搞错了，导致第一遍解解不出，可以用sage定义个变量算一下，当时打草纸验算应该是让矩阵右乘了，晕：

A = matrix([[13,11],
            [19,29],])

p,q=var('p q')
x = vector([p,q])
y1,y2 = A*x
print(y1,y2)
#13*p + 11*q 19*p + 29*q

知道了y1y2之后，代入同余方程：
$$
c_1\equiv (13p + 11q)^{e_1}(\bmod n)
$$
$$
c_2\equiv (19p + 29q)^{e_2}(\bmod n)
$$

这个二项式幂运算之后，中间含有pq乘积项的全部模掉了，只保留了最两边的项：
$$
c_1\equiv (13p)^{e_1} + (11q)^{e_1}(\bmod n)
$$
$$
c_2\equiv (19p)^{e_2} + (29q)^{e_2}(\bmod n)
$$

pq为未知数，由于e1e2已知，所以可以把pq的e次方看做整体，但是现在两式这样有四个未知数，两个式子解四个未知数不行，但是两个未知数可以解，所以两式同时乘方处理一下，将四个未知数改成两个：
$$
\begin{cases}c_1^{e_2}\equiv 13^{e_1e_2}p^{e_1e_2} + 11^{e_1e_2}q^{e_1e_2}(\bmod n)\\c_2^{e_1}\equiv 19^{e_1e_2}p^{e_1e_2} + 29^{e_1e_2}q^{e_1e_2}(\bmod n)\end{cases}
$$
前面的系数已知e都能求了，现在这就是个在模n下的二元线性同余方程组，百度找一下解的公式（太懒了懒得推了）：

对于二元方程组：
$$
\begin{cases}ax+by=m\\cx+dy=n\end{cases}
$$
有解：
$$
\begin{cases}x=\frac{md-bn}{ad-bc}\\
y=\frac{mc-an}{bc-ad}\end{cases}
$$
所以把本题的所有值都量化进这个公式里，注意到由于是同余方程组，同余方程组对于除法有一定的限制，所以处理分数直接用逆元即可，由于结果是在模n上的，所以结果需要模n：

import gmpy2

N=[
319921123311250552662963566647233721176500532097925505551548615965620926886290107004282962564396760204590468753354087637632596627283389303984969095543538774832852895025313854336617682706352197362418638206543073301189608132934178272448280700099991086560803792660780736921365654510536546191545903820825352164469145200595638053567489038365292280396297682441017231601120272720968293290636862864945870109310394015619502123336027505110147899564501295941242844401235448208551347533131793232155203435166720019251796222917958737174696093799200811639151889416773884099138368196585180556987089906154502751274251702921482591707082824826896528955613182269483843333285568738360741886640681092035773605438887662505159270796669448808076856295823895234264196954633882031001724935347719732441864407930514810976560093125404511952867209059623444494325114594996641049835394499590618767684304963563299049578241522328014002403690904185320105830639934733326227045308680083189915718559098864854510435072431091298351365139202359934453258210782585368099447241705559813727602307985927435898194839439434163080058496044725980779306785235534486901948642672517025391781421160093032191831056281446632496876808397979406212517252958889052537024809161355990518029929969,
599110224308422610498885243404312429997177742018723070681626765267732786181152678750071483014346760950051734617610980049030890074185326986414140752740945426043572643718817292642671545022342097343164320475481125005511915062386511192750531215560323637471972117741700673604936286573301916241384756976273580685682913548756589981155428792124150225941178642113257150679698880071645553511181173883345101469622719344233722291848031318477750188110862073613213668753924645928575076145217645286278155576444910095487452856165516739845826060854104698626407038868953736697171989625407302305007912084794500759881256763408658774527496156696874315726095000344088043895258903767834768991583323537732703746682458050075635230240429775422444182740441361192690178542018467094016140059649350780667573179467800446685269685769332444562674125273351147969810077129441223813961453867316628820306319223876400075876373647814797515239817206564861314231194035802487996534734716180541499231064733286600825832248720133058267665225372986667999830641679212573884132642066093974917737361905234891402070297053289894322630861180118358700800642277403667514430348500006973280512066703404817926073682890049469420438004128393903376795534421609536502403618737354345776767809557,
384998826819481882761848191143359204391153792102936797952487123431795928602128228587925293269182641167333316395663009756616057078812914618103709914853868671213075759006388222112859289793312785125519599636704794089696100330011788336290676549232518198379997908178761546709231733881624365460039160081054662380632396689836832546615865310275182804640492770868708692058413252519866099664032024736179195034707926990571556586839756024744587488152752561291138873158856991517081521016889242469285819552719905725580617648713215279020396226216541318638673492101090271474958210917505042292032944041085352664672037560206133336097289055143608958748235476744694786360538392614406079700804431378395467269765783246340309258568191256941214374291469991923243836682113882179730002144373914685785923439171546254291846453692663231157825191665781110039101517064225839961966881165888243102656766016651525006389085782969509941189752601844238960885306992131990050538920017436228174787367041358825007811717342276269001986620224870765641387156394784345759115202096559242992905646357564409484140096867391264765421036587476574846172385130923429202440439497574125845193100612292676551657321277120751650068237013326247682286358745901149134831233360299637481478476501,
507245232253935808341536559251331701837149042018245019668938390550258643891056371194634189150221240155457817416421363647814996662621617987154459880940024087015512695828164012075638713135374561699637353865381550036798462896607057683996864793778246319726533085915823440503386062570616735640817366048926965475520405031088255626435556375118364904199343749626096845737830245083121927192440465061149995552046837833655802716107749310515199355826503474221188405390489548162218224078084930458858844022022203284778087366338961303096801879481188705227078317196089916431962827446006365294990445055140495563290653579866892084838798684512066717774937577495068990501882865117535740192140050077440367096171641020261519561740232716507034084869012311774817541750130260940359846263173411914427496187682304043909136422023155688402393218661215002088157756621995273150568685973008999888016136364741781537185135514968218047327827360747635729718588277278127875340312839143652808925545634557874389933187090989855613050361001333248189225142340998930410951347842736412211513706668693633697675716280682959923184620261330324601504956687173647392045782974315575577535746568626528305515290788891435427759726584517509669935697997687347132761440317609787903713772833,
75854144701123527418530520540977973114878453670553534643882219139491306909566751873750088176758684406436763229689376208407654442423255987090092395561042196383263162614865941727286943944745838052909841040506558873374230692573883334829385258214209222741721762230873266837628111684878771035789992785928300972636174142008029210264139228479951126872954369317657960423521963247660759233472768720444568215447251655176638426038985154193450561951816088995111813541660720177003733108376803395757709839771329616920135924277014003893558451863445470200895348470550668369618940621168047082007338039930373702266500734062873406094876687795832254523678271245825888065478094110511855190455844712670793471844450310564737613914997090950777618290642586363118592128104505864959053007490232765809998928156931039879283271663032882671695655080563521554598143954434024975211054267751406687119778148675259865111763405130922970467957254060273774851666343187015289979493015079684632598195423790807537053192669844475177043837267953013535247975192331371568028242008149496566482991252297048372190860668946369071350187804162802690175670871752785725929028598825704746328553329263200182801618773131210391323623123571074275034668806644923614133111322181107531343085387
]

C1=[
248292875804004341487193963587418460793015860983343659729627383649600562154259358584129320729975693092182850315023754970095027674177520062160081385829489999398851656460396267064471651504991787753897600165464399162714333725852108264765404549646356689169774328016897055213513659098660700163238808314499831273389824485995857140645954536717894810800060744488273316547697541161681415958432943782338051016988235483006770823488933136897020554203178244197502012795053551048100276519840224992613689013732623028934965584811831143911305441779886260797220241977972033615990028418358826359968343897398821106856094954413945798907918678293183082235577560119112547038959525148322763823839046696386613319994738999783947199590531544768775692808847538511358347345961677089604593395682205308621002457663787631613273274022455500740217424160275888894292062475958187405993289602952730106121166185714356643453390540638758319675521881312024226126409644961686094789094555539949200025541322509192008502810890673721136882951683534363469649407225558267779718952546008673217922105075461128591140566706367413899119360441045405844432445235817784608668283513141813047885521529347709023277444323912888989918220180834119379811483872772135494735140660228469428830964530,
176931389707528532333643293274655713467866080265053285136083463468262516271121733861463524578770503903299476192462414217588405103808830287418952647224740674444215065272324677390543276613816896053074302438652440655659641657537193059597393638416182901134595550137990263713298057951419194342430107780930999038188587153994124570186567704205312650035672893717801156504083484824727347400152678323131659525133752194372791942803899593097694860937464143593457219248740023332020372072436505120470558928852088434764645410055511263334761560328097444749789959966376288430211336459557555092046090064609896642870596113288694780225634647867281210671117808505871363263226868334708852922005728999508478078595523108156621337361245586806939274383146616685906803790102031200753657833809494074618641106092244627257806217431922190455598898638812355858202024312198560056114954424987895506430303657593394391539732055591630532027063746485277742767328761858501447181667397420384446040681677602749514035730844334140735074282955968546966184623952444350809497205207100479517975199861131974671098056262855687103144442821719415871807018371037443387516644803223973850308829061960130368378893261176986431944217973608429502911805758922786547560778452649318154612861967,
263412959517528061532217746494794166082281553294199674428880147566246392753433764409953717919033289918824130484554076531357124324259498287499308866073220118826317609200284908288861969777215595841788765768992142011859613032976380802799562284652189395740386141224142260554976714706959099938813238493527211646768966072650649975671968174558189981715133171111486170067853989114337687853470560553517486354345050390387023851238181351095655806518004184932302016785690637561739925436741947888687661210178752387715595895021756008188472827201005709762448457715023486287232182254910421892998725128850133130650731062190401584089260857064324303526505680880583681332678447312646319534097554377495547408990027316588003909189937934533078846641447285404727313766068726950684894154368494881686483287672487479510050747957229496328638768715372506730837466648041842900978823550603103981055081374871877726693269296223748736317192577870785252905659796624463797774864114025525725228963680130973220639435350168518740097315345932723631297793189729156242238540526331759878310860878056060933673445786292478116901951419570480091573958293874614303092653905723270744036932717042344970542962385957902035661776041125118772704377131246174272394870998129203448444725457,
124638905226754098806817101032457294027818026677971494020638032730715562312579631139751218085640891949824822961987590218693524984007767250952367221316577733970586428863363878927365121159858236201167468626199615437062864556583857137289152391101677883335117179636284725331078154446512795545548931320054604998696082561634212484005423084065746123675833928694573342777178903003218928956661006433506308115777403479769915801463593189394473925162998131129243252794347652208444796343551190165683495708053585943387165983026025225586503213521312728373798714099368812992550361456831878231181647979530725168365995127709512315425979943920184175875442833726779334700048052511922581466302999698402150250186533257302131814434773611410298304884512272663506831636174410056656041397953118791283468037077063062708252083364173645585027774359881969362081243862169106816969337560807708649492829423385487494334863325503464356219720923038079727910572046592552101622371785835982457894422429358259579858598897194842634038228873614534636634007653502390072087089687058833448985840998420852204735268996943085994666303766339029914202026076638444002681704238375403865888266480808789084663776141406753983837131363745790160009558260880255569728540795480657163657953946,
18582470997758640686236228908085341038225622737681493954917063804738618898712419270474742101006315492643318433628598836816813533694824248045884321325595355841890943617828532403616000912577086644372202645330628765396827331380955730706619925614732897050719845498551519550042822486465698195700395659904399923479294949397360252564375164859658616041418783814270575835086070762241270955845077325769080603136408519397135675438167569509930641059447928283246362575761844787578057228391227525081316282399980870403873890449190699742629249363843763135077397266696525295092990498552303934211282420029219947701605216360988122204256860869270689055525413147030046394542537903178052990908980917559477900583662402097831568581585052609194631770523816521340882539563826686094386375094443448598008561338600827387911487385354500338504586485019285499176828964556777072527901936660378309368240614930466339417396968133120970452985733610014213518831608075125802060973854607667508011882267568402764873808900800530842521638480088265537279572527763624288660923616067565629543911677095001915898330229238955774055979207056770208399757003820338235282968934221437095086547128506770210235670418776763190654482110170379918285673805215053246401040193192956953268331622
]

C2=[
296180744100107627758305803516955340735558610309703831618835666444138490117343532242009220325303295510764934839650890329415913083510508318219183867155229006613035882800097723061091284831633060962879325372568115856456841602547580917291722852871793433471643367474974123185317625795292746401531802938675718785468748265718598756597678742309285333084753463463911170855807120117785391014177340178847064198532628205532901940135177816329079615728225052445221533435398969165247298426483478788736418651645495975740824617906545979330594372548117600367071940846614291762730294798674263510602807627691374990413772565733031188485081012803619040113850825410586940777678530030755343410465305025316354508831191088580419179330492687487852916636844333217073647477740970328528182474872923076646152213713921452837288812643386947407603759919404325424354630405612235758684539078304413046133956422960652314198670078399947591407271051787044259051554945886192870328524690468787651125309448228277503786656782815364975714286271137126118656004127038041167492890493455265764937552969782098992644454795704577084669939924649658297313008791286459600996857834780090659852975185140737006153546204113199194069050763512604482342589174038583411788997367584415563743340790,
207825535879623865503097506381310741807898563342999422545658227690482860570590516383855935273188527718395578010504901652766942519822324143510275994937930872623748070639611098588454967901146797122950194632033675562625783763405679992217014873537762961389175695619305119730391390356873938973446359987881369521735928896421165165050426604099270352684944316840363736268429526864889718104018006472013834578999658151840662269815703540065548283955329961781918836244179184012652332665537289529366969067032441841608013817519301029589854737293888059968854497590399682532480192708166880928264360458819249385985000132745990937500956684132997265337340990054223510325085325876943187026146893100295481827820789579613628373021305786762272014306651642062049190186870382876032234837379443353344294059752180789659187717099411362684483418311653654534993658405246985723278808212555344671100837992053963688157637616963241685755348784040248979693639307270954751360300904564908809513136996918206562709964367755857169510548126386207318744970653803079758998769906758394220917327699200076235635461400456496200309572279548621825633543713359900504179332751555630351786079010244112977343569035465586377711479592257479060619330888392439487337503238360580548529118774,
379141106506112115015622970987612647085791358706332228662782435574383644676152728354901732525171316822080494398925057112244202125081035390441248680561723571333542354357533545503976082670155532027042252094502311476538022286377130159789512873129175565554261137462364776243241919928277766680994345146728975502967017499701417224964087080949167650105441912270149179803259414150473042807136414890312876902363747748668355388769973433905232133239745960886638184079596160490921229840436293043438908796367159430939249778899061028907959673137331957622949868497019067787519906919985945944030095789832143522630084187060738458996618923101199548583721210230171193521188080450859417547063660379782992717082989353180071369686174809343601715811054580233823428833882027715672990671564114924057482648920909420857280646240681251922428786226530645228543301278988185748803982479105788150494880973738178008614500089746956457868272279069731491447479881552976484627779476305213007190643556674347291191236876757632291557039643125132398701129213344780986150303277782898113196403386247175084953623350120919113636506905440280334789880530385758785840713823113405103518810269832345160384661926888648035985189080612407421214999677760298747251058236414655245095652118,
240874010959668572995066513021604834764425643168141336894751714170296379975601634819243224391219902974304208195520659715789892844864738149125965473223544126222013293617461267503458636090904173180107731144768965660013134268114307083405057958491695370283309157490331842423852627395173777572162434426061609818108992902161232015774852198644380599273195910771743171014623866805104568008513252647009041342172177979593802063541085021499402512275261687814491161889425621836508791077467516208035467145268972515958642850076780236306042263622373425617254539706702530330405735315726694484094775104562223077864142620431567761301838030348639899377905928432490666515339610677294311293479799667949121649960116150972134318394444739737272007852466589632871830703701132556614595722322861845953059129079861248033694808791728994607709310890273990485928972362823137452455159402426525721873635741495732972480271703895019278619443851067282718022260194750835579691315723727049269118671182042116905641098827646351397474435913964966466682503360896184533601267594244407375573099196467997005589139020291661910118149590407846330309321371481613870685679721311438357073570062809730718699957486858818038505720111013693243248156523750763299063756297514168747750465364,
36556408746463787647283291114860926084413826323975417331434236048369702899209317319855560955590864192980782669198910310936181985421958079062881820644235108707192257485969915113992379078661833478031287158013175864666970600816660558242592871154648216509709983408883311441271602215006472852599820626284218983903315950977073113838522988854157274942417491019423863187664036084886644310321834557183890672959568588214257812855069344050724095175516876437188197231118651365186333270059336126359640577335038523088705217626982898565060228333852801777246535752352869165095573855823735948174922865697264235706020909965539426748047857344444377027906644389172847633205817227611876561360167890871362131163526710133933874191746985120960174155658259035142224982293368618632585314179241305046091688155868339662942690390026928413114752446130829479006328954698902214804311094329442527936226008602543427388390619871852403255213365039241085741171761358361595544674241102035055481032109678589244247237183299614969715231782356450004560306100702155980392220392264655796593332021713202404108089398392228728950513946676310772066670151815602341071035026748525468559749558951651958536761376736909403873653366739774373625807219500731753314833571602901919383375427
]

e1,e2 = 6163,7411

for i in range(5):
    n,c1,c2=N[i],C1[i],C2[i]
    c1,c2=pow(c1,e2,n),pow(c2,e1,n)
    a=pow(13,e1*e2,n)
    b=pow(11,e1*e2,n)
    c=pow(19,e1*e2,n)
    d=pow(29,e1*e2,n)
    p.<x,y>=PolynomialRing(Zmod(n))#这句可以不要，不过为了解释一下还是加上吧
    x=((c1*d-b*c2)*gmpy2.invert(gmpy2.mpz(a*d-b*c),n))%n
    y=((c1*c-a*c2)*gmpy2.invert(gmpy2.mpz(b*c-a*d),n))%n

得到的xy为在模n下的$p^{e_1e_2},q^{e_1e_2}$，可以直接求公因子进行因式分解，得到最开始生成的随机数pq注意后32位无效位可以先去掉，避免等会忘了：

这里为了保证pq的顺序，应该先p后q存入数组方便后续进行随机数预测，原题目还返回了一个signal值判断p>q，现在看似乎是混淆信息：

1	return privateKey,p>q

import gmpy2

N=[
319921123311250552662963566647233721176500532097925505551548615965620926886290107004282962564396760204590468753354087637632596627283389303984969095543538774832852895025313854336617682706352197362418638206543073301189608132934178272448280700099991086560803792660780736921365654510536546191545903820825352164469145200595638053567489038365292280396297682441017231601120272720968293290636862864945870109310394015619502123336027505110147899564501295941242844401235448208551347533131793232155203435166720019251796222917958737174696093799200811639151889416773884099138368196585180556987089906154502751274251702921482591707082824826896528955613182269483843333285568738360741886640681092035773605438887662505159270796669448808076856295823895234264196954633882031001724935347719732441864407930514810976560093125404511952867209059623444494325114594996641049835394499590618767684304963563299049578241522328014002403690904185320105830639934733326227045308680083189915718559098864854510435072431091298351365139202359934453258210782585368099447241705559813727602307985927435898194839439434163080058496044725980779306785235534486901948642672517025391781421160093032191831056281446632496876808397979406212517252958889052537024809161355990518029929969,
599110224308422610498885243404312429997177742018723070681626765267732786181152678750071483014346760950051734617610980049030890074185326986414140752740945426043572643718817292642671545022342097343164320475481125005511915062386511192750531215560323637471972117741700673604936286573301916241384756976273580685682913548756589981155428792124150225941178642113257150679698880071645553511181173883345101469622719344233722291848031318477750188110862073613213668753924645928575076145217645286278155576444910095487452856165516739845826060854104698626407038868953736697171989625407302305007912084794500759881256763408658774527496156696874315726095000344088043895258903767834768991583323537732703746682458050075635230240429775422444182740441361192690178542018467094016140059649350780667573179467800446685269685769332444562674125273351147969810077129441223813961453867316628820306319223876400075876373647814797515239817206564861314231194035802487996534734716180541499231064733286600825832248720133058267665225372986667999830641679212573884132642066093974917737361905234891402070297053289894322630861180118358700800642277403667514430348500006973280512066703404817926073682890049469420438004128393903376795534421609536502403618737354345776767809557,
384998826819481882761848191143359204391153792102936797952487123431795928602128228587925293269182641167333316395663009756616057078812914618103709914853868671213075759006388222112859289793312785125519599636704794089696100330011788336290676549232518198379997908178761546709231733881624365460039160081054662380632396689836832546615865310275182804640492770868708692058413252519866099664032024736179195034707926990571556586839756024744587488152752561291138873158856991517081521016889242469285819552719905725580617648713215279020396226216541318638673492101090271474958210917505042292032944041085352664672037560206133336097289055143608958748235476744694786360538392614406079700804431378395467269765783246340309258568191256941214374291469991923243836682113882179730002144373914685785923439171546254291846453692663231157825191665781110039101517064225839961966881165888243102656766016651525006389085782969509941189752601844238960885306992131990050538920017436228174787367041358825007811717342276269001986620224870765641387156394784345759115202096559242992905646357564409484140096867391264765421036587476574846172385130923429202440439497574125845193100612292676551657321277120751650068237013326247682286358745901149134831233360299637481478476501,
507245232253935808341536559251331701837149042018245019668938390550258643891056371194634189150221240155457817416421363647814996662621617987154459880940024087015512695828164012075638713135374561699637353865381550036798462896607057683996864793778246319726533085915823440503386062570616735640817366048926965475520405031088255626435556375118364904199343749626096845737830245083121927192440465061149995552046837833655802716107749310515199355826503474221188405390489548162218224078084930458858844022022203284778087366338961303096801879481188705227078317196089916431962827446006365294990445055140495563290653579866892084838798684512066717774937577495068990501882865117535740192140050077440367096171641020261519561740232716507034084869012311774817541750130260940359846263173411914427496187682304043909136422023155688402393218661215002088157756621995273150568685973008999888016136364741781537185135514968218047327827360747635729718588277278127875340312839143652808925545634557874389933187090989855613050361001333248189225142340998930410951347842736412211513706668693633697675716280682959923184620261330324601504956687173647392045782974315575577535746568626528305515290788891435427759726584517509669935697997687347132761440317609787903713772833,
75854144701123527418530520540977973114878453670553534643882219139491306909566751873750088176758684406436763229689376208407654442423255987090092395561042196383263162614865941727286943944745838052909841040506558873374230692573883334829385258214209222741721762230873266837628111684878771035789992785928300972636174142008029210264139228479951126872954369317657960423521963247660759233472768720444568215447251655176638426038985154193450561951816088995111813541660720177003733108376803395757709839771329616920135924277014003893558451863445470200895348470550668369618940621168047082007338039930373702266500734062873406094876687795832254523678271245825888065478094110511855190455844712670793471844450310564737613914997090950777618290642586363118592128104505864959053007490232765809998928156931039879283271663032882671695655080563521554598143954434024975211054267751406687119778148675259865111763405130922970467957254060273774851666343187015289979493015079684632598195423790807537053192669844475177043837267953013535247975192331371568028242008149496566482991252297048372190860668946369071350187804162802690175670871752785725929028598825704746328553329263200182801618773131210391323623123571074275034668806644923614133111322181107531343085387
]

C1=[
248292875804004341487193963587418460793015860983343659729627383649600562154259358584129320729975693092182850315023754970095027674177520062160081385829489999398851656460396267064471651504991787753897600165464399162714333725852108264765404549646356689169774328016897055213513659098660700163238808314499831273389824485995857140645954536717894810800060744488273316547697541161681415958432943782338051016988235483006770823488933136897020554203178244197502012795053551048100276519840224992613689013732623028934965584811831143911305441779886260797220241977972033615990028418358826359968343897398821106856094954413945798907918678293183082235577560119112547038959525148322763823839046696386613319994738999783947199590531544768775692808847538511358347345961677089604593395682205308621002457663787631613273274022455500740217424160275888894292062475958187405993289602952730106121166185714356643453390540638758319675521881312024226126409644961686094789094555539949200025541322509192008502810890673721136882951683534363469649407225558267779718952546008673217922105075461128591140566706367413899119360441045405844432445235817784608668283513141813047885521529347709023277444323912888989918220180834119379811483872772135494735140660228469428830964530,
176931389707528532333643293274655713467866080265053285136083463468262516271121733861463524578770503903299476192462414217588405103808830287418952647224740674444215065272324677390543276613816896053074302438652440655659641657537193059597393638416182901134595550137990263713298057951419194342430107780930999038188587153994124570186567704205312650035672893717801156504083484824727347400152678323131659525133752194372791942803899593097694860937464143593457219248740023332020372072436505120470558928852088434764645410055511263334761560328097444749789959966376288430211336459557555092046090064609896642870596113288694780225634647867281210671117808505871363263226868334708852922005728999508478078595523108156621337361245586806939274383146616685906803790102031200753657833809494074618641106092244627257806217431922190455598898638812355858202024312198560056114954424987895506430303657593394391539732055591630532027063746485277742767328761858501447181667397420384446040681677602749514035730844334140735074282955968546966184623952444350809497205207100479517975199861131974671098056262855687103144442821719415871807018371037443387516644803223973850308829061960130368378893261176986431944217973608429502911805758922786547560778452649318154612861967,
263412959517528061532217746494794166082281553294199674428880147566246392753433764409953717919033289918824130484554076531357124324259498287499308866073220118826317609200284908288861969777215595841788765768992142011859613032976380802799562284652189395740386141224142260554976714706959099938813238493527211646768966072650649975671968174558189981715133171111486170067853989114337687853470560553517486354345050390387023851238181351095655806518004184932302016785690637561739925436741947888687661210178752387715595895021756008188472827201005709762448457715023486287232182254910421892998725128850133130650731062190401584089260857064324303526505680880583681332678447312646319534097554377495547408990027316588003909189937934533078846641447285404727313766068726950684894154368494881686483287672487479510050747957229496328638768715372506730837466648041842900978823550603103981055081374871877726693269296223748736317192577870785252905659796624463797774864114025525725228963680130973220639435350168518740097315345932723631297793189729156242238540526331759878310860878056060933673445786292478116901951419570480091573958293874614303092653905723270744036932717042344970542962385957902035661776041125118772704377131246174272394870998129203448444725457,
124638905226754098806817101032457294027818026677971494020638032730715562312579631139751218085640891949824822961987590218693524984007767250952367221316577733970586428863363878927365121159858236201167468626199615437062864556583857137289152391101677883335117179636284725331078154446512795545548931320054604998696082561634212484005423084065746123675833928694573342777178903003218928956661006433506308115777403479769915801463593189394473925162998131129243252794347652208444796343551190165683495708053585943387165983026025225586503213521312728373798714099368812992550361456831878231181647979530725168365995127709512315425979943920184175875442833726779334700048052511922581466302999698402150250186533257302131814434773611410298304884512272663506831636174410056656041397953118791283468037077063062708252083364173645585027774359881969362081243862169106816969337560807708649492829423385487494334863325503464356219720923038079727910572046592552101622371785835982457894422429358259579858598897194842634038228873614534636634007653502390072087089687058833448985840998420852204735268996943085994666303766339029914202026076638444002681704238375403865888266480808789084663776141406753983837131363745790160009558260880255569728540795480657163657953946,
18582470997758640686236228908085341038225622737681493954917063804738618898712419270474742101006315492643318433628598836816813533694824248045884321325595355841890943617828532403616000912577086644372202645330628765396827331380955730706619925614732897050719845498551519550042822486465698195700395659904399923479294949397360252564375164859658616041418783814270575835086070762241270955845077325769080603136408519397135675438167569509930641059447928283246362575761844787578057228391227525081316282399980870403873890449190699742629249363843763135077397266696525295092990498552303934211282420029219947701605216360988122204256860869270689055525413147030046394542537903178052990908980917559477900583662402097831568581585052609194631770523816521340882539563826686094386375094443448598008561338600827387911487385354500338504586485019285499176828964556777072527901936660378309368240614930466339417396968133120970452985733610014213518831608075125802060973854607667508011882267568402764873808900800530842521638480088265537279572527763624288660923616067565629543911677095001915898330229238955774055979207056770208399757003820338235282968934221437095086547128506770210235670418776763190654482110170379918285673805215053246401040193192956953268331622
]

C2=[
296180744100107627758305803516955340735558610309703831618835666444138490117343532242009220325303295510764934839650890329415913083510508318219183867155229006613035882800097723061091284831633060962879325372568115856456841602547580917291722852871793433471643367474974123185317625795292746401531802938675718785468748265718598756597678742309285333084753463463911170855807120117785391014177340178847064198532628205532901940135177816329079615728225052445221533435398969165247298426483478788736418651645495975740824617906545979330594372548117600367071940846614291762730294798674263510602807627691374990413772565733031188485081012803619040113850825410586940777678530030755343410465305025316354508831191088580419179330492687487852916636844333217073647477740970328528182474872923076646152213713921452837288812643386947407603759919404325424354630405612235758684539078304413046133956422960652314198670078399947591407271051787044259051554945886192870328524690468787651125309448228277503786656782815364975714286271137126118656004127038041167492890493455265764937552969782098992644454795704577084669939924649658297313008791286459600996857834780090659852975185140737006153546204113199194069050763512604482342589174038583411788997367584415563743340790,
207825535879623865503097506381310741807898563342999422545658227690482860570590516383855935273188527718395578010504901652766942519822324143510275994937930872623748070639611098588454967901146797122950194632033675562625783763405679992217014873537762961389175695619305119730391390356873938973446359987881369521735928896421165165050426604099270352684944316840363736268429526864889718104018006472013834578999658151840662269815703540065548283955329961781918836244179184012652332665537289529366969067032441841608013817519301029589854737293888059968854497590399682532480192708166880928264360458819249385985000132745990937500956684132997265337340990054223510325085325876943187026146893100295481827820789579613628373021305786762272014306651642062049190186870382876032234837379443353344294059752180789659187717099411362684483418311653654534993658405246985723278808212555344671100837992053963688157637616963241685755348784040248979693639307270954751360300904564908809513136996918206562709964367755857169510548126386207318744970653803079758998769906758394220917327699200076235635461400456496200309572279548621825633543713359900504179332751555630351786079010244112977343569035465586377711479592257479060619330888392439487337503238360580548529118774,
379141106506112115015622970987612647085791358706332228662782435574383644676152728354901732525171316822080494398925057112244202125081035390441248680561723571333542354357533545503976082670155532027042252094502311476538022286377130159789512873129175565554261137462364776243241919928277766680994345146728975502967017499701417224964087080949167650105441912270149179803259414150473042807136414890312876902363747748668355388769973433905232133239745960886638184079596160490921229840436293043438908796367159430939249778899061028907959673137331957622949868497019067787519906919985945944030095789832143522630084187060738458996618923101199548583721210230171193521188080450859417547063660379782992717082989353180071369686174809343601715811054580233823428833882027715672990671564114924057482648920909420857280646240681251922428786226530645228543301278988185748803982479105788150494880973738178008614500089746956457868272279069731491447479881552976484627779476305213007190643556674347291191236876757632291557039643125132398701129213344780986150303277782898113196403386247175084953623350120919113636506905440280334789880530385758785840713823113405103518810269832345160384661926888648035985189080612407421214999677760298747251058236414655245095652118,
240874010959668572995066513021604834764425643168141336894751714170296379975601634819243224391219902974304208195520659715789892844864738149125965473223544126222013293617461267503458636090904173180107731144768965660013134268114307083405057958491695370283309157490331842423852627395173777572162434426061609818108992902161232015774852198644380599273195910771743171014623866805104568008513252647009041342172177979593802063541085021499402512275261687814491161889425621836508791077467516208035467145268972515958642850076780236306042263622373425617254539706702530330405735315726694484094775104562223077864142620431567761301838030348639899377905928432490666515339610677294311293479799667949121649960116150972134318394444739737272007852466589632871830703701132556614595722322861845953059129079861248033694808791728994607709310890273990485928972362823137452455159402426525721873635741495732972480271703895019278619443851067282718022260194750835579691315723727049269118671182042116905641098827646351397474435913964966466682503360896184533601267594244407375573099196467997005589139020291661910118149590407846330309321371481613870685679721311438357073570062809730718699957486858818038505720111013693243248156523750763299063756297514168747750465364,
36556408746463787647283291114860926084413826323975417331434236048369702899209317319855560955590864192980782669198910310936181985421958079062881820644235108707192257485969915113992379078661833478031287158013175864666970600816660558242592871154648216509709983408883311441271602215006472852599820626284218983903315950977073113838522988854157274942417491019423863187664036084886644310321834557183890672959568588214257812855069344050724095175516876437188197231118651365186333270059336126359640577335038523088705217626982898565060228333852801777246535752352869165095573855823735948174922865697264235706020909965539426748047857344444377027906644389172847633205817227611876561360167890871362131163526710133933874191746985120960174155658259035142224982293368618632585314179241305046091688155868339662942690390026928413114752446130829479006328954698902214804311094329442527936226008602543427388390619871852403255213365039241085741171761358361595544674241102035055481032109678589244247237183299614969715231782356450004560306100702155980392220392264655796593332021713202404108089398392228728950513946676310772066670151815602341071035026748525468559749558951651958536761376736909403873653366739774373625807219500731753314833571602901919383375427
]

list=[]
e1,e2 = 6163,7411
e=0x10001

for i in range(5):
    n,c1,c2=N[i],C1[i],C2[i]
    c1,c2=pow(c1,e2,n),pow(c2,e1,n)
    a=pow(13,e1*e2,n)
    b=pow(11,e1*e2,n)
    c=pow(19,e1*e2,n)
    d=pow(29,e1*e2,n)
    x=((c1*d-b*c2)*gmpy2.invert(gmpy2.mpz(a*d-b*c),n))%n
    y=((c1*c-a*c2)*gmpy2.invert(gmpy2.mpz(b*c-a*d),n))%n
    p=gmpy2.gcd(gmpy2.mpz(x),gmpy2.mpz(n))
    q=(n//p)>>32
    p=p>>32
    list.append(int(p))
    list.append(int(q))
print(list)

MT19937预测

得到了五组处理后的pq随机数，下面进行随机数预测。

一开始我用了randcrack库进行预测，需要先把pq分解出63个随机数然后取后624个随机数提交预测：

from randcrack import RandCrack
import gmpy2

list=[3600265381355011800604369729661573963612710583856212506545658333074852429990600726314135674548759570858351262908012949282212891542519305106962751727007362149708469686819748050996483865271557123237235648703377421566137839034113010750191629064356634517368870402690058113717875558312794512374974885601202863799749046561385365768063498784814448786640372932810512239460911099581866725281270129457067796775074394695587754248229141673874819102350216092845573296781783861707029124711116336816170035789910773422844025959034069644139823743187425115167175093301548318030822470998819584829825906212545143905770241396368, 4817133463471453198428421724055510657300236861968071382969324879726323848060330555371547119808753420047534779374579128185549253172742713334594545998949652767249840813701426174426518547280870584064238611099900203404065005465511964677141340532671932434023046148664909131354411362314994560484009837116140892946013884868181058158225451545677966491404463355910291955883702634244436917274121422968501861212369587093053816220793024776593440099061813499603413938552891122263176441219237760895847492692282759544436521394939331277943772962636951401825442292010598866502339863473831351796439464211956633336140714936091, 5320985707957182464040016394767710336981155975260726958323250923521354629117853764934556740947855596798863238401760126048848459985182048990865607049236087766457632811795814296090981304235470780746115486653453233629654840725302888729555750551634791327737624021914530218194896080743108937438723209634695487781051652819143405638999309562786198289918933798259419294897022898320243694222932439360673535068138044883752460243760791362190060387472043568148435580879715644013128735121643766648176565421872828379995558920914383623712812039193491820705844857517386299044583692230500293902134456103817887941918137670476, 6103724407510629902108247826148113166486441306090215047925636496596244026431075146089318097310457535274545145720087483352023263429259853031395440800707590279250812628751259981104988389130473778474422554471991638062721194954559286056509663416143268183106221134570350825574093156385007706993953846837310675668273336245684705824074684533975599446369202277889983471718721612625780600896262842621115391081844839614819550798593632699449553122181971701082078292484491250676416128435898685973887339369321495919025223496171602845899319026056945842903604676049073160779149208311182579527170884638290725668737779393295, 4869952293485307201849272034040709529173145583179893663678794036912765707481488928691048416481685293644454346754026194189471394243420189635244241971617405219211600574534934416803366472721950176394073491033943471502102861891549695312488491782258470680771475748815344888320267529711937062436449859623328312832801208512387507383929100722015207891279245089052514428882052674399575458791619778703599539124366156305525344914435281805520385759704242333183054601193188696526631006422498353677164131887595128324852413268542447360634055039317080283700647542464128697047944776564629428419660592398742380439552234852792, 4285632992754820150722119126482059603267423755331360028619749952541858328581118679369849121044325280796994891397111220877798027444951860158453235210630805079844816773804421837113424171851171976359484628498874866924424398454233437952901025012211593258761248604409143201629679222686633593211289120293853353030289988193401376986399585011496182072908570769332510733651794324562258036980781567190606205973835714060131764319664288798714340741293275917472294478304013955046434808568768542848882878382183636989281256602389408475343914392096292108626471238918229714731498007494271904546308577038076210571781147001419, 7173054866684378506127542172995536857120071023414954611535911778323161990600202047335812665236784695821980802955007050498160452829335477036119094303084915004277044629605907318407566397947664875330421853665929397509331583528834929255899450417904186939731193700897256466874521689876651920775127696250029782179636421293187877495167406739363993300464326043851435232800170688751911040563657868691602313438006658399905588477903008432737611309689920219111154889672094733947549930020772196936809370758645952282470566570267239081126094098804731799692246636833036294225587427647304535913226512570873761776688206348639, 3833487914242313378819434108513688065627053691673983399608816921037602279374665152466695797123518267472832291732929809630714718230349407600852873072577454103567815651064683889858737858018988859887176799209107555610438029038043054702761434525520274938268708893703912968012456019114312059390879789473695971924061681499028042066517835303765320298462149699451255600608805120538746592023873172054049004171036273586873464146373622260020112654077623486675212766201276689676571210051907878213084583848695347494156467728525890779923873668537276542348558358575241654156832473179828811659942819978821509757832704754102, 884227670301398205806036237885673489794589850916644991891316845355535910849089165148992511580569462415839175544365378399036605530483114930797785738701486865318815579925386056940082723247786053203405513311413178004668290711216587279976585956250945661068384229033276896637767269133468294453361946807302113316626996610774665370812483815977665776730496695745394936570558772561143550268132809202487575906268004922083529768692530533859783390704320143874455669268023976446372139379522701512501394589897184977389430053743420453631029844597271734806480741536979368531348102390185496618858890658761515126456780417806, 4650455490097655733832976488186981781238392107709968153352076282056842201764978521727907715782183489476319465552057260508930486914669731797157749432557079029041275092304723059583215482390327108225429675695013416156981588697480833307299663208604124180200503283285180334391844471906737604676557044887200881064774900407043728813855022543758024084817381712776718182436736938987065511700086314031431391661790894563388470040282287566233461568242932038165013498642883061075598932213704092468246869085189344221886205865611423386220335789711983635779742200439278570653010650269085339842540595107623433736216721309357]
num1,num=[],[]
for i in list:
    num1.append(str('0'*(2016-len(bin(i)[2:]))+bin(i)[2:]))
for i in num1:
    for j in range(1984,-1,-32):
        num.append(int(i[j:j+32],2))
r = RandCrack()
for i in range(6,630):
    r.submit(num[i])
p,q = gmpy2.next_prime(r.predict_getrandbits(2016)<<32),gmpy2.next_prime(r.predict_getrandbits(2016)<<32)

学长嫌这样有点麻烦怕错了，让我用之前分享在群里的一个预测的库，这个库的提交随机数可以直接提交大数，不需要分解：

from extend_mt19937_predictor import ExtendMT19937Predictor
import gmpy2

list=[3600265381355011800604369729661573963612710583856212506545658333074852429990600726314135674548759570858351262908012949282212891542519305106962751727007362149708469686819748050996483865271557123237235648703377421566137839034113010750191629064356634517368870402690058113717875558312794512374974885601202863799749046561385365768063498784814448786640372932810512239460911099581866725281270129457067796775074394695587754248229141673874819102350216092845573296781783861707029124711116336816170035789910773422844025959034069644139823743187425115167175093301548318030822470998819584829825906212545143905770241396368, 4817133463471453198428421724055510657300236861968071382969324879726323848060330555371547119808753420047534779374579128185549253172742713334594545998949652767249840813701426174426518547280870584064238611099900203404065005465511964677141340532671932434023046148664909131354411362314994560484009837116140892946013884868181058158225451545677966491404463355910291955883702634244436917274121422968501861212369587093053816220793024776593440099061813499603413938552891122263176441219237760895847492692282759544436521394939331277943772962636951401825442292010598866502339863473831351796439464211956633336140714936091, 5320985707957182464040016394767710336981155975260726958323250923521354629117853764934556740947855596798863238401760126048848459985182048990865607049236087766457632811795814296090981304235470780746115486653453233629654840725302888729555750551634791327737624021914530218194896080743108937438723209634695487781051652819143405638999309562786198289918933798259419294897022898320243694222932439360673535068138044883752460243760791362190060387472043568148435580879715644013128735121643766648176565421872828379995558920914383623712812039193491820705844857517386299044583692230500293902134456103817887941918137670476, 6103724407510629902108247826148113166486441306090215047925636496596244026431075146089318097310457535274545145720087483352023263429259853031395440800707590279250812628751259981104988389130473778474422554471991638062721194954559286056509663416143268183106221134570350825574093156385007706993953846837310675668273336245684705824074684533975599446369202277889983471718721612625780600896262842621115391081844839614819550798593632699449553122181971701082078292484491250676416128435898685973887339369321495919025223496171602845899319026056945842903604676049073160779149208311182579527170884638290725668737779393295, 4869952293485307201849272034040709529173145583179893663678794036912765707481488928691048416481685293644454346754026194189471394243420189635244241971617405219211600574534934416803366472721950176394073491033943471502102861891549695312488491782258470680771475748815344888320267529711937062436449859623328312832801208512387507383929100722015207891279245089052514428882052674399575458791619778703599539124366156305525344914435281805520385759704242333183054601193188696526631006422498353677164131887595128324852413268542447360634055039317080283700647542464128697047944776564629428419660592398742380439552234852792, 4285632992754820150722119126482059603267423755331360028619749952541858328581118679369849121044325280796994891397111220877798027444951860158453235210630805079844816773804421837113424171851171976359484628498874866924424398454233437952901025012211593258761248604409143201629679222686633593211289120293853353030289988193401376986399585011496182072908570769332510733651794324562258036980781567190606205973835714060131764319664288798714340741293275917472294478304013955046434808568768542848882878382183636989281256602389408475343914392096292108626471238918229714731498007494271904546308577038076210571781147001419, 7173054866684378506127542172995536857120071023414954611535911778323161990600202047335812665236784695821980802955007050498160452829335477036119094303084915004277044629605907318407566397947664875330421853665929397509331583528834929255899450417904186939731193700897256466874521689876651920775127696250029782179636421293187877495167406739363993300464326043851435232800170688751911040563657868691602313438006658399905588477903008432737611309689920219111154889672094733947549930020772196936809370758645952282470566570267239081126094098804731799692246636833036294225587427647304535913226512570873761776688206348639, 3833487914242313378819434108513688065627053691673983399608816921037602279374665152466695797123518267472832291732929809630714718230349407600852873072577454103567815651064683889858737858018988859887176799209107555610438029038043054702761434525520274938268708893703912968012456019114312059390879789473695971924061681499028042066517835303765320298462149699451255600608805120538746592023873172054049004171036273586873464146373622260020112654077623486675212766201276689676571210051907878213084583848695347494156467728525890779923873668537276542348558358575241654156832473179828811659942819978821509757832704754102, 884227670301398205806036237885673489794589850916644991891316845355535910849089165148992511580569462415839175544365378399036605530483114930797785738701486865318815579925386056940082723247786053203405513311413178004668290711216587279976585956250945661068384229033276896637767269133468294453361946807302113316626996610774665370812483815977665776730496695745394936570558772561143550268132809202487575906268004922083529768692530533859783390704320143874455669268023976446372139379522701512501394589897184977389430053743420453631029844597271734806480741536979368531348102390185496618858890658761515126456780417806, 4650455490097655733832976488186981781238392107709968153352076282056842201764978521727907715782183489476319465552057260508930486914669731797157749432557079029041275092304723059583215482390327108225429675695013416156981588697480833307299663208604124180200503283285180334391844471906737604676557044887200881064774900407043728813855022543758024084817381712776718182436736938987065511700086314031431391661790894563388470040282287566233461568242932038165013498642883061075598932213704092468246869085189344221886205865611423386220335789711983635779742200439278570653010650269085339842540595107623433736216721309357]

predictor = ExtendMT19937Predictor()
for i in range(10):
    predictor.setrandbits(list[i], 2016)
for i in range(2):
    print(gmpy2.next_prime(predictor.predict_getrandbits(2016)<<32))

不过最终事实证明，两种都没啥问题，只是第二种比较方便。

最后的处理

这题加密的RSA库的加密方式与传统的RSA有所不同：

from Crypto.PublicKey import RSA

from Crypto.Cipher import PKCS1_v1_5

利用这两个库进行加密的时候会进行pad填充处理，其实理论上不影响，用long_to_bytes解直接能看到flag：

from randcrack import RandCrack
import gmpy2
from Crypto.Util.number import *

list=[3600265381355011800604369729661573963612710583856212506545658333074852429990600726314135674548759570858351262908012949282212891542519305106962751727007362149708469686819748050996483865271557123237235648703377421566137839034113010750191629064356634517368870402690058113717875558312794512374974885601202863799749046561385365768063498784814448786640372932810512239460911099581866725281270129457067796775074394695587754248229141673874819102350216092845573296781783861707029124711116336816170035789910773422844025959034069644139823743187425115167175093301548318030822470998819584829825906212545143905770241396368, 4817133463471453198428421724055510657300236861968071382969324879726323848060330555371547119808753420047534779374579128185549253172742713334594545998949652767249840813701426174426518547280870584064238611099900203404065005465511964677141340532671932434023046148664909131354411362314994560484009837116140892946013884868181058158225451545677966491404463355910291955883702634244436917274121422968501861212369587093053816220793024776593440099061813499603413938552891122263176441219237760895847492692282759544436521394939331277943772962636951401825442292010598866502339863473831351796439464211956633336140714936091, 5320985707957182464040016394767710336981155975260726958323250923521354629117853764934556740947855596798863238401760126048848459985182048990865607049236087766457632811795814296090981304235470780746115486653453233629654840725302888729555750551634791327737624021914530218194896080743108937438723209634695487781051652819143405638999309562786198289918933798259419294897022898320243694222932439360673535068138044883752460243760791362190060387472043568148435580879715644013128735121643766648176565421872828379995558920914383623712812039193491820705844857517386299044583692230500293902134456103817887941918137670476, 6103724407510629902108247826148113166486441306090215047925636496596244026431075146089318097310457535274545145720087483352023263429259853031395440800707590279250812628751259981104988389130473778474422554471991638062721194954559286056509663416143268183106221134570350825574093156385007706993953846837310675668273336245684705824074684533975599446369202277889983471718721612625780600896262842621115391081844839614819550798593632699449553122181971701082078292484491250676416128435898685973887339369321495919025223496171602845899319026056945842903604676049073160779149208311182579527170884638290725668737779393295, 4869952293485307201849272034040709529173145583179893663678794036912765707481488928691048416481685293644454346754026194189471394243420189635244241971617405219211600574534934416803366472721950176394073491033943471502102861891549695312488491782258470680771475748815344888320267529711937062436449859623328312832801208512387507383929100722015207891279245089052514428882052674399575458791619778703599539124366156305525344914435281805520385759704242333183054601193188696526631006422498353677164131887595128324852413268542447360634055039317080283700647542464128697047944776564629428419660592398742380439552234852792, 4285632992754820150722119126482059603267423755331360028619749952541858328581118679369849121044325280796994891397111220877798027444951860158453235210630805079844816773804421837113424171851171976359484628498874866924424398454233437952901025012211593258761248604409143201629679222686633593211289120293853353030289988193401376986399585011496182072908570769332510733651794324562258036980781567190606205973835714060131764319664288798714340741293275917472294478304013955046434808568768542848882878382183636989281256602389408475343914392096292108626471238918229714731498007494271904546308577038076210571781147001419, 7173054866684378506127542172995536857120071023414954611535911778323161990600202047335812665236784695821980802955007050498160452829335477036119094303084915004277044629605907318407566397947664875330421853665929397509331583528834929255899450417904186939731193700897256466874521689876651920775127696250029782179636421293187877495167406739363993300464326043851435232800170688751911040563657868691602313438006658399905588477903008432737611309689920219111154889672094733947549930020772196936809370758645952282470566570267239081126094098804731799692246636833036294225587427647304535913226512570873761776688206348639, 3833487914242313378819434108513688065627053691673983399608816921037602279374665152466695797123518267472832291732929809630714718230349407600852873072577454103567815651064683889858737858018988859887176799209107555610438029038043054702761434525520274938268708893703912968012456019114312059390879789473695971924061681499028042066517835303765320298462149699451255600608805120538746592023873172054049004171036273586873464146373622260020112654077623486675212766201276689676571210051907878213084583848695347494156467728525890779923873668537276542348558358575241654156832473179828811659942819978821509757832704754102, 884227670301398205806036237885673489794589850916644991891316845355535910849089165148992511580569462415839175544365378399036605530483114930797785738701486865318815579925386056940082723247786053203405513311413178004668290711216587279976585956250945661068384229033276896637767269133468294453361946807302113316626996610774665370812483815977665776730496695745394936570558772561143550268132809202487575906268004922083529768692530533859783390704320143874455669268023976446372139379522701512501394589897184977389430053743420453631029844597271734806480741536979368531348102390185496618858890658761515126456780417806, 4650455490097655733832976488186981781238392107709968153352076282056842201764978521727907715782183489476319465552057260508930486914669731797157749432557079029041275092304723059583215482390327108225429675695013416156981588697480833307299663208604124180200503283285180334391844471906737604676557044887200881064774900407043728813855022543758024084817381712776718182436736938987065511700086314031431391661790894563388470040282287566233461568242932038165013498642883061075598932213704092468246869085189344221886205865611423386220335789711983635779742200439278570653010650269085339842540595107623433736216721309357]
num1,num=[],[]
for i in list:
    num1.append(str('0'*(2016-len(bin(i)[2:]))+bin(i)[2:]))
for i in num1:
    for j in range(1984,-1,-32):
        num.append(int(i[j:j+32],2))
r = RandCrack()
for i in range(6,630):
    r.submit(num[i])
p,q = gmpy2.next_prime(r.predict_getrandbits(2016)<<32),gmpy2.next_prime(r.predict_getrandbits(2016)<<32)
e=0x10001
c=b'6\xe1\x1c\xd8n\x1e\xeb\x97$\xb3L\xf3=\xb5\xd3p\x12\xd5OM\xa6\x87qqb\xc5>\x92]5g\xb4\xc2cS\xc6\x99\xb3\x9d\xa6\xd3\xdd\x1ci\xbd\xd6\xfd\xe9\xcc\xc7\xb4V-\x8c\xb8\x1c\xa7\x18b\x84F\xc2\xa9Cy\xd8\x83u\x0c_\xbf<\x96a{\x16M\xc8.\xab\x92\xb1\xa4\xf7cGN\x9c@,\xf7\xffrrV\x01\x03\x9e\x07\xe8Q\x7f\xa5D\xc6*~#\x0b\x91\xbch\xf5\x92N(\xd4\x02\xf5-\xf2\x15\xdeG\xbb\xfc\xb6\xb9\x1d7\x086\xbf=\x9es\xd2\x1d\xae\xb4\xd61\xe4\xcc\x7f\xdf\xe0!=\x14 \xbdP2pI!a\xc7+_{\x88\x19r\x8cf"<\x94\xb1\xce\xbd#\xa4\x9c\x92\xbcw\x92\\\x87\xad\xb9\xdf\x88,\xf2\x14\x00\xbd\xb8\x9e^R\xd0_i4k\xe2\x08\x1c\x0bF\xbb\xa63\x94\xd4\xb5\xe0\xd1\x93\x00\xd4\x9c\x96\xe5\xfc\xff9\xb8J;\xd3\x94YCr\xac\xf6\xc2\x96T\x17M\xb1=z\xd4TI\xb7\x84C\xc3\x92.\xb7\xe4\xfe\xe0\x14}YVc \x1c\x1d.\xcd\'\xber\xa9\x175W\xd8\xd6\xd0F\xc7\xe3\x86K*.m/A\xaak\xf6\x12\xd5\xe3-\x0c[\\$\xbe\x05\x95B\x04\xfd\x1e\xbc>S\xbc>w\x15\n*\xb7\x8b\xe7w\xbf\xed\x05\xca\xda\xb7\xdbs^r{\xb5\xe6e0\xb4\x90v\xaf\xbbV\xcd\xa9\xd8\xc5P\x01J\xe4\x02/\xef\xe7N\xc3\xcd\x81P2\x83\xf8C\x06sq8\x91?\xaf\xf5q\xfaN\x9c\xfd\xfdJ.\xa7\x1cb/O\xaf&\xb0\xae\xc4d>o\xbf\xe9s\xcd\xa7\x01=\x81\xdc\x9c\xc5\xfe\x81\xbe\xf9H\xae\xc6\x19\xec\xa8\xa1w\x115\x8b\x81\xca\xce\xcdH b\x8a\x87q\x1d\x12\xa3\xc7\xfe\xda\x90\xd9G\x84\x94\xd6\xe0\xcc"@\xfb\x07\xdd\x96\xbb\xc5\xfb\xd0:8\xb8q\xa8L\xc1\x04\xb1a\xf0`\x9e\xd7"p\xe1\x03=\xeb\xd9lQ\x17\x84\x87\x8e\xe3\x10\xb6\xf8\xb7\x85\xeb\xb1Y\\\x17\x12\xc6xGf\xc2\xe1\x17\x1f\x08\x0fV\x94T Em\x1b\x86\xc3o\x9e\x1f\x82\x80\xce\x1e\xbc\xa6'
n=p*q
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
print(long_to_bytes(pow(bytes_to_long(c),d,n)))
#b'\x02\x8ao]\xb7\xa0:\xa0\xd5\x07\xcf\xb5\xbb\xcc\x8dB\xbdQ\xad)\xf7-\xe4\xdfE\x98A\x11f\xd1}\xd3\x1e;O\xfcs\xaeSUK\x91\x1do\xaek\x12\xf8\x1f\x08\xb9\xfc\xfa\x83\xa1\xb4\xd1\xa2\xe3\xa1<t\xa3\x056\xbfL\x16\xca\xdb3I\x1a\xc9\x19\xad\xf1\xa4\xbd\x1d\xe5C$\x96\xee\xc8\xcc\x8fk\xec\x87\xe1\xbb\x03\xf4\x04\xac\x1d\x0e\x81\xdb_\xd1\xf8L\x84\xfd\xbd\x86\xd1%\xde>\xf3\xc1\xfd\xe9\xb6\r\x18\x8b!\x88\xbe\xfeB\xde\xde\xc05\xed\xa8/\x98}H\x0e\xe5\xf1\xf6T\xc6\xff\xf8\xd7\x04\xd8\x17\x83\xa9\xf6\xe6\xa6\n\xa6\xe4\xaf(j\xcf\xae@5\x7f\xb2\xda\x91\xd7>\xb9\'9$\xa8\x8f\x15\xbfH\xc8\xd0~\rY\x9a\xe9\x03D\xa0=\x1d\x80\xc7\xebh\x1c%&\x91\xce\x11v\xa9\x1dc\xca\xfe\x1b\xa5\xde\x08B\xb3\x1e\x80\xb7\xd2*\x9d\xad\x08\x9e\xe5\xbdO\x7f\x13\x91\x8b5\xde\xf4#6\xae\xe4\xa6b\x12B2\xf6v\x03!^+\x01\x85\xf6\xac\x8d\x05;\x1e\xc3\xfb\xa8\xbf\xacu\xbe\x07%\xb1\xb8\x05\x84Jp\xc4=\xfa\xe6\x14\xb3\xbd\xc1\xc5\xd9\xa9\xae\xf9\x1c%\xb94\xc5{\x1eP\xc0Qo\x8ctO6\xb9\x1c\x1f\xda\xc0R\x03\xe4/d\x1b\xf7OI\xa2\x917\x83\xc4s\xd8,\xb18\x97\xf4f\x10x@2\xa3v^\x18]a=L\xba}H\x9ajvz\'n\x0f\x96\xf9\xe1]\x86\x1a\xd0X;\x11W1\x9e7C"5\xdb~1\xe3\x7f\xdd\x9b\xd5\xc2pT\x07\x9e\xe9\x9c\x8b#mFe\xb7\xd4\xc7\xc0\xbfA\xb2\xc2\xb9\x93y\x90\xc4\xaf\x97[\xea3\xc3\xc3Z\xdb\xf6"+\x93\x06\xae\xd4\x12\xe9\xd4xa\x88{t\xea\xd2\xa2\xc4T\xa7\xbb\xf7\xe2\xbe\x1c\xdc\x81\x98\x16\xf6\xdd\xb3\x98\x00TKHASH{ec15c30d9abc2fd671c7ecbfbf03293b02052aeda790da5fdd20236ecca549b}'

用那两个库联合来解的话大致代码是这样，注意最后在decrypt的时候需要加一个额外的sentinel参数，最简单的是像我这样放个0，或者用sentinel=None，'error'：

from randcrack import RandCrack
import gmpy2
from Crypto.Util.number import *
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_v1_5

list=[3600265381355011800604369729661573963612710583856212506545658333074852429990600726314135674548759570858351262908012949282212891542519305106962751727007362149708469686819748050996483865271557123237235648703377421566137839034113010750191629064356634517368870402690058113717875558312794512374974885601202863799749046561385365768063498784814448786640372932810512239460911099581866725281270129457067796775074394695587754248229141673874819102350216092845573296781783861707029124711116336816170035789910773422844025959034069644139823743187425115167175093301548318030822470998819584829825906212545143905770241396368, 4817133463471453198428421724055510657300236861968071382969324879726323848060330555371547119808753420047534779374579128185549253172742713334594545998949652767249840813701426174426518547280870584064238611099900203404065005465511964677141340532671932434023046148664909131354411362314994560484009837116140892946013884868181058158225451545677966491404463355910291955883702634244436917274121422968501861212369587093053816220793024776593440099061813499603413938552891122263176441219237760895847492692282759544436521394939331277943772962636951401825442292010598866502339863473831351796439464211956633336140714936091, 5320985707957182464040016394767710336981155975260726958323250923521354629117853764934556740947855596798863238401760126048848459985182048990865607049236087766457632811795814296090981304235470780746115486653453233629654840725302888729555750551634791327737624021914530218194896080743108937438723209634695487781051652819143405638999309562786198289918933798259419294897022898320243694222932439360673535068138044883752460243760791362190060387472043568148435580879715644013128735121643766648176565421872828379995558920914383623712812039193491820705844857517386299044583692230500293902134456103817887941918137670476, 6103724407510629902108247826148113166486441306090215047925636496596244026431075146089318097310457535274545145720087483352023263429259853031395440800707590279250812628751259981104988389130473778474422554471991638062721194954559286056509663416143268183106221134570350825574093156385007706993953846837310675668273336245684705824074684533975599446369202277889983471718721612625780600896262842621115391081844839614819550798593632699449553122181971701082078292484491250676416128435898685973887339369321495919025223496171602845899319026056945842903604676049073160779149208311182579527170884638290725668737779393295, 4869952293485307201849272034040709529173145583179893663678794036912765707481488928691048416481685293644454346754026194189471394243420189635244241971617405219211600574534934416803366472721950176394073491033943471502102861891549695312488491782258470680771475748815344888320267529711937062436449859623328312832801208512387507383929100722015207891279245089052514428882052674399575458791619778703599539124366156305525344914435281805520385759704242333183054601193188696526631006422498353677164131887595128324852413268542447360634055039317080283700647542464128697047944776564629428419660592398742380439552234852792, 4285632992754820150722119126482059603267423755331360028619749952541858328581118679369849121044325280796994891397111220877798027444951860158453235210630805079844816773804421837113424171851171976359484628498874866924424398454233437952901025012211593258761248604409143201629679222686633593211289120293853353030289988193401376986399585011496182072908570769332510733651794324562258036980781567190606205973835714060131764319664288798714340741293275917472294478304013955046434808568768542848882878382183636989281256602389408475343914392096292108626471238918229714731498007494271904546308577038076210571781147001419, 7173054866684378506127542172995536857120071023414954611535911778323161990600202047335812665236784695821980802955007050498160452829335477036119094303084915004277044629605907318407566397947664875330421853665929397509331583528834929255899450417904186939731193700897256466874521689876651920775127696250029782179636421293187877495167406739363993300464326043851435232800170688751911040563657868691602313438006658399905588477903008432737611309689920219111154889672094733947549930020772196936809370758645952282470566570267239081126094098804731799692246636833036294225587427647304535913226512570873761776688206348639, 3833487914242313378819434108513688065627053691673983399608816921037602279374665152466695797123518267472832291732929809630714718230349407600852873072577454103567815651064683889858737858018988859887176799209107555610438029038043054702761434525520274938268708893703912968012456019114312059390879789473695971924061681499028042066517835303765320298462149699451255600608805120538746592023873172054049004171036273586873464146373622260020112654077623486675212766201276689676571210051907878213084583848695347494156467728525890779923873668537276542348558358575241654156832473179828811659942819978821509757832704754102, 884227670301398205806036237885673489794589850916644991891316845355535910849089165148992511580569462415839175544365378399036605530483114930797785738701486865318815579925386056940082723247786053203405513311413178004668290711216587279976585956250945661068384229033276896637767269133468294453361946807302113316626996610774665370812483815977665776730496695745394936570558772561143550268132809202487575906268004922083529768692530533859783390704320143874455669268023976446372139379522701512501394589897184977389430053743420453631029844597271734806480741536979368531348102390185496618858890658761515126456780417806, 4650455490097655733832976488186981781238392107709968153352076282056842201764978521727907715782183489476319465552057260508930486914669731797157749432557079029041275092304723059583215482390327108225429675695013416156981588697480833307299663208604124180200503283285180334391844471906737604676557044887200881064774900407043728813855022543758024084817381712776718182436736938987065511700086314031431391661790894563388470040282287566233461568242932038165013498642883061075598932213704092468246869085189344221886205865611423386220335789711983635779742200439278570653010650269085339842540595107623433736216721309357]
num1,num=[],[]
for i in list:
    num1.append(str('0'*(2016-len(bin(i)[2:]))+bin(i)[2:]))
for i in num1:
    for j in range(1984,-1,-32):
        num.append(int(i[j:j+32],2))
r = RandCrack()
for i in range(6,630):
    r.submit(num[i])
p,q = gmpy2.next_prime(r.predict_getrandbits(2016)<<32),gmpy2.next_prime(r.predict_getrandbits(2016)<<32)
e=0x10001
c=b'6\xe1\x1c\xd8n\x1e\xeb\x97$\xb3L\xf3=\xb5\xd3p\x12\xd5OM\xa6\x87qqb\xc5>\x92]5g\xb4\xc2cS\xc6\x99\xb3\x9d\xa6\xd3\xdd\x1ci\xbd\xd6\xfd\xe9\xcc\xc7\xb4V-\x8c\xb8\x1c\xa7\x18b\x84F\xc2\xa9Cy\xd8\x83u\x0c_\xbf<\x96a{\x16M\xc8.\xab\x92\xb1\xa4\xf7cGN\x9c@,\xf7\xffrrV\x01\x03\x9e\x07\xe8Q\x7f\xa5D\xc6*~#\x0b\x91\xbch\xf5\x92N(\xd4\x02\xf5-\xf2\x15\xdeG\xbb\xfc\xb6\xb9\x1d7\x086\xbf=\x9es\xd2\x1d\xae\xb4\xd61\xe4\xcc\x7f\xdf\xe0!=\x14 \xbdP2pI!a\xc7+_{\x88\x19r\x8cf"<\x94\xb1\xce\xbd#\xa4\x9c\x92\xbcw\x92\\\x87\xad\xb9\xdf\x88,\xf2\x14\x00\xbd\xb8\x9e^R\xd0_i4k\xe2\x08\x1c\x0bF\xbb\xa63\x94\xd4\xb5\xe0\xd1\x93\x00\xd4\x9c\x96\xe5\xfc\xff9\xb8J;\xd3\x94YCr\xac\xf6\xc2\x96T\x17M\xb1=z\xd4TI\xb7\x84C\xc3\x92.\xb7\xe4\xfe\xe0\x14}YVc \x1c\x1d.\xcd\'\xber\xa9\x175W\xd8\xd6\xd0F\xc7\xe3\x86K*.m/A\xaak\xf6\x12\xd5\xe3-\x0c[\\$\xbe\x05\x95B\x04\xfd\x1e\xbc>S\xbc>w\x15\n*\xb7\x8b\xe7w\xbf\xed\x05\xca\xda\xb7\xdbs^r{\xb5\xe6e0\xb4\x90v\xaf\xbbV\xcd\xa9\xd8\xc5P\x01J\xe4\x02/\xef\xe7N\xc3\xcd\x81P2\x83\xf8C\x06sq8\x91?\xaf\xf5q\xfaN\x9c\xfd\xfdJ.\xa7\x1cb/O\xaf&\xb0\xae\xc4d>o\xbf\xe9s\xcd\xa7\x01=\x81\xdc\x9c\xc5\xfe\x81\xbe\xf9H\xae\xc6\x19\xec\xa8\xa1w\x115\x8b\x81\xca\xce\xcdH b\x8a\x87q\x1d\x12\xa3\xc7\xfe\xda\x90\xd9G\x84\x94\xd6\xe0\xcc"@\xfb\x07\xdd\x96\xbb\xc5\xfb\xd0:8\xb8q\xa8L\xc1\x04\xb1a\xf0`\x9e\xd7"p\xe1\x03=\xeb\xd9lQ\x17\x84\x87\x8e\xe3\x10\xb6\xf8\xb7\x85\xeb\xb1Y\\\x17\x12\xc6xGf\xc2\xe1\x17\x1f\x08\x0fV\x94T Em\x1b\x86\xc3o\x9e\x1f\x82\x80\xce\x1e\xbc\xa6'
n=p*q
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
privateKey = RSA.construct((int(n),int(e),int(d),int(p),int(q)))
Cipher = PKCS1_v1_5.new(privateKey)
c = Cipher.decrypt(c, 0)
print(c)
#b'TKHASH{ec15c30d9abc2fd671c7ecbfbf03293b02052aeda790da5fdd20236ecca549b}'

坏男人

4.24官方wp发布，补充一道题：

n=28743528431024344617680737414913106476511322306414619055395106718152677406354611490244660644658908122314212254737913466167460186811153249608791381688088132332606543760622284548113425802123604359986160331524999684372630367816298739938262574623254151758410930291127039505423300547979760870363488617069325577882894536182534099316753592885148029517047329911315977951646330684583948360132273605993290571537792956857145028945406852800817208586203447517926942521712639423933712291615508436052513532364715976987187880267353667818607096597541374344389394428837399446009168995807575173853558117282387639314617529093142344155137
e=0x10001
enc_to_itself=21884802678342960251926179503823259930768742823965214543770966066083075460872859624925099212884772287487921054646946811502384680382668329804607223512229155483259929429827359716506150173084370385813417536768929555624622792207918611995301393993847242171021991001236264441512444616732564521692242164942377415737801191016092987279301050474632427841915368175408625100568974326877708399000769449792840064795397513381418062004179944827406924915572126936126670701693169619468231180857076968443201948002890391112514596191975462107407208346817691153895187771215136124605449425342375920766802783143720442864156673768877874262510
ct=11477002885978764094640005747666297892652635979942793178031845789152667395230315749335098741226454094422185987973567769802943863647999276315842957951570544805757278108589269160010493870759819086699538819431731597636830531205583387337016133458696657488788603285862983857525879489957904400845863000711211960636523336534109938942596381803864140137363035398119619200104279840763198791912576282374066227592705415594283866426101690802207884729578550094942197986608731522562087517317195064804631740453324034579979422504367912537121313835055574661470474094742846950766589183024166060646234528365778013825681264962170510572829

当时最后看的题就是这一道，由于剩的时间太短了没研究出来开摆了，看了看wp发现好像不是很难……

根据题目，可以得知：
$$
a^e\bmod n=a
$$

$$
a^{e-1}\equiv 1(\bmod n)
$$

这题接下来需要对上式因式分解，找规律求公因子，先把1移过去：
$$
a^{e-1}-1\equiv 0(\bmod n)
$$
e是65537，e-1就是65536，有趣的是65536是0x10000，也就是2的16次方，进一步变形：
$$
a^{2^{16}}-1\equiv 0(\bmod n)
$$
不断使用平方差公式对其进行因式分解：
$$
[(a^2)^{15}+1][(a^2)^{14}+1]…(a-1)\equiv 0(\bmod n)
$$
所以，得到的同余式左边的项中具有p或者q的倍数，可以逐个检验求最大公因子：

import gmpy2
from Crypto.Util.number import *

n=28743528431024344617680737414913106476511322306414619055395106718152677406354611490244660644658908122314212254737913466167460186811153249608791381688088132332606543760622284548113425802123604359986160331524999684372630367816298739938262574623254151758410930291127039505423300547979760870363488617069325577882894536182534099316753592885148029517047329911315977951646330684583948360132273605993290571537792956857145028945406852800817208586203447517926942521712639423933712291615508436052513532364715976987187880267353667818607096597541374344389394428837399446009168995807575173853558117282387639314617529093142344155137
e=0x10001
k=21884802678342960251926179503823259930768742823965214543770966066083075460872859624925099212884772287487921054646946811502384680382668329804607223512229155483259929429827359716506150173084370385813417536768929555624622792207918611995301393993847242171021991001236264441512444616732564521692242164942377415737801191016092987279301050474632427841915368175408625100568974326877708399000769449792840064795397513381418062004179944827406924915572126936126670701693169619468231180857076968443201948002890391112514596191975462107407208346817691153895187771215136124605449425342375920766802783143720442864156673768877874262510
c=11477002885978764094640005747666297892652635979942793178031845789152667395230315749335098741226454094422185987973567769802943863647999276315842957951570544805757278108589269160010493870759819086699538819431731597636830531205583387337016133458696657488788603285862983857525879489957904400845863000711211960636523336534109938942596381803864140137363035398119619200104279840763198791912576282374066227592705415594283866426101690802207884729578550094942197986608731522562087517317195064804631740453324034579979422504367912537121313835055574661470474094742846950766589183024166060646234528365778013825681264962170510572829
assert gmpy2.gcd(k-1,n)==1
for i in range(15):
    if gmpy2.gcd(pow(k,2**i)+1,n)!=1:
        p=gmpy2.gcd(pow(k,2**i)+1,n)
        break
q=n//p
phi=(q-1)*(p-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))

校赛感悟和两道难题

Random-RSA

了解代码

解二元线性同余方程组

MT19937预测

最后的处理

坏男人