Neltharion_and_Arthas task:
在这个奇怪的地方卡了很久，题目不难，就是**。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 import binasciiimport hashlibfrom Crypto.Cipher import AESfrom Crypto.Util import *import osflag = b'flag{4ff732dd-2B74-45fd-a3ea-e82b4c491e0e}' key1 = os.urandom(32 ) key2 = b'tn5-ix6L#tCaG}i6' key_len = len (key2) assert flag.startswith(b'flag{' )assert (flag[13 ] == 45 and flag[18 ] == 45 and flag[23 ] == 45 and flag[28 ] == 45 )flag1 = b"2023: " +flag[:13 ]+flag[14 :18 ]+flag[19 :23 ] flag2 = b'a3eae82b4c491e0e' h = binascii.unhexlify(hashlib.sha256(key2).hexdigest())[:11 ] gift1 = b'***********************************************************************************************' gift2 = b'I tell you this, for when my days have come to an end , you, shall be King.' +h def encrypt1 (message, key ): cipher = AES.new(key, AES.MODE_CTR, counter=Counter.new(128 )) ciphertext = cipher.encrypt(message) return ciphertext.hex () def encrypt2 (message, key, iv ): padding = bytes ((key_len - len (message) % key_len) * '&' , encoding='utf-8' ) message += padding cipher = AES.new(key, AES.MODE_CBC, iv) ciphertext = cipher.encrypt(message) return ciphertext.hex () print ("enc_gift1 = " +encrypt1(gift1, key1))print ("enc_flag = " +encrypt1(flag1, key1))print ("enc_gift2 = " +encrypt2(gift2, key2, flag2))
数据：
1 2 3 enc_gift1 = bad7dbcff968d7cdbf51da011fe94e176fc8e7528e4dd85d2d5fc20ba69cefb7bfd03152a2874705bd2d857ea75b3216a830215db74772d9b9e9c218271d562694d3642d2917972fdb8c7363d8125730a50824cd8dc7e34cd4fa54be427cca enc_flag = c1c78891e30cd4c0aa5ed65c17e8550429c4e640881f9f1d6a56df enc_gift2 = ********c********b**************4***5********3****6a*****a**2********c*8******7***********3***5***2********e*5*************a******5**c***74***********fee046b4d2918096cfa3b76d6622914395c7e28eef
思路：
第一部分：是CTR分组模式，加密的时候KEY和计数器基本都是预处理，所以我们不需要去找到key1，直接求出原有的keystream就好，利用keystream去还原明文，而在此之前我们可以利用2023: 这个已知明文，去还原一部分的明文，根据明文I am D，以及简单的社会工程搜索，就得到了原文。有已知明文之后直接还原就可以。
详细说明一下：可以看到与密钥有关的加密块都在上面，我称之为keystream，是可以通过明文与密文异或直接得到拿去当做密钥用的。
前提是“已知明文“，想办法找到这部分就好。
第二部分：是CBC分组模式，其中部分key已知，我们只要暴力求解，使得还原的密文末端与题目所给的相符即可，思路是这样的：
我将中间AES解密的部分设为D，当前密文与明文设为：C,M
(C_i\bigoplus D_i)\bigoplus M_i =C_{i-1}
按照这个去推C_i，当D正确的时候，我们就可以得到正确的密钥。
之后按照正常CBC回推的思路就好
爆破密钥大概要一根烟的功夫。
最后组合一下数字。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 256 import binasciiimport hashlibfrom Crypto.Util.strxor import strxorimport itertoolsimport stringfrom Crypto.Cipher import AESfrom Crypto.Util.number import *import osdef xor (a,b ): assert len (a)==len (b) A = bytes_to_long(a) B = bytes_to_long(b) return long_to_bytes(A^B) c = long_to_bytes(0xbad7dbcff968d7cdbf51da011fe94e176fc8e7528e4dd85d2d5fc20ba69cefb7bfd03152a2874705bd2d857ea75b3216a830215db74772d9b9e9c218271d562694d3642d2917972fdb8c7363d8125730a50824cd8dc7e34cd4fa54be427cca ) t = long_to_bytes(0x0c1c78891e30cd4c0aa5ed65c17e8550429c4e640881f9f1d6a56df ) keystream = (xor(c[:54 ],b'I am Deathwing, the Destroyer, the end of all things. ' )) print (xor(t,keystream[:27 ]))def xor (a,b ): assert len (a)==len (b) A = bytes_to_long(a) B = bytes_to_long(b) return long_to_bytes(A^B) def recover (m,c,key ): tmp = AES.new(key,AES.MODE_ECB) return xor(tmp.decrypt(c),m).hex () text = long_to_bytes(0x918096cfa3b76d6622914395c7e28eef ) dict1 = '\'\"?<>,.!@#$%^&*()-+=/\\{}[]:' for i in itertools.product(string.ascii_letters+string.digits+dict1, repeat=4 ): key = 'tn' +i[0 ]+'-ix6L' +i[1 ]+'tCa' +i[2 ]+'}i' +i[3 ] key = key.encode() h = binascii.unhexlify(hashlib.sha256(key).hexdigest())[:11 ] msg = b'I tell you this, for when my days have come to an end , you, shall be King.' +h padding = bytes ((16 - len (msg) % 16 ) * '&' , encoding='utf-8' ) msg += padding result = recover(msg[-16 :],text,key) if (result[-10 :]=='fee046b4d2' ): print (key) break key = b'tn5-ix6L#tCaG}i6' h = binascii.unhexlify(hashlib.sha256(key).hexdigest())[:11 ] msg = b'I tell you this, for when my days have come to an end , you, shall be King.' +h padding = bytes ((16 - len (msg) % 16 ) * '&' , encoding='utf-8' ) msg += padding msgs = [msg[ii:(ii+16 )] for ii in range (0 ,len (msg),16 )] msgs.reverse() IV = binascii.unhexlify('918096cfa3b76d6622914395c7e28eef' ) def decry (key,IV,ms ): aes=AES.new(key,AES.MODE_ECB) return strxor(aes.decrypt(IV),ms) for ms in msgs: IV=decry(key,IV,ms) print (IV)
Share: task:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 import random from secret import flag, secretfrom Crypto.Util.number import *n = 21 t = 21 A = [secret] for i in range (n-1 ): A.append(random.getrandbits(1024 )) X = [] for i in range (n): X.append(random.getrandbits(1024 )) p = getPrime(1026 ) def f (x ): res = 0 tmp = 1 for i in range (n): res = (res + tmp * A[i]) % p tmp = tmp * x % p return res % p R = [] for i in range (n): R.append(f(X[i])) P = secret Q = getPrime(1024 ) N = P * Q m = bytes_to_long(flag) e = 65537 c = pow (m, e, N) phi=(P - 1 ) * (Q - 1 ) d = pow (e,-1 ,phi) print (long_to_bytes(pow (c,d,N)))fi = open ('output.txt' ,'w' ) for i in range (t-1 ): fi.write(str (X[i])+' ' +str (R[i])+'\n' ) print ("leak = %d" %R[-1 ])print ("p = %d" %p)print ("c = %d" %c)print ("N = %d" %N)''' leak = 158171468736013100218170873274656605219228738469715092751861925345310881653082508445746109167302799236685145510095499361526242392251594397820661050281094210672424887670015189702781308615421102937559185479455827148241690888934661637911906309379701856488858180027365752169466863585611322838180758159364570481257 p = 667548632459029899397299221540978856425474915828934339291333387574324630349258515018972045406265448494845331262999241448002076917383740651362641947814545076390796789402373579283727117618532504865966299599663825771187433223531022829811594806917984414530614469374596457149431218829297339079019894262229453357029 c = 9658009093151541277762773618550582280013680172161026781649630205505443184765264518709081169475689440555639354980432557616120809346519461077355134139495745998317849357705381020225760061125236265304057301286196004542729553944161451832173970613915423841610378207266606500956362098150141825329354727367056070349148059780287916811442861961254066733726576151134458892613951223277692935141880749737598416235307087782001086096114978527447987308876878393763055893556123029990282534497668077854186604106027698257663251502775547705641708624619340185646943640576690633662704397191379303254341343433077302686466850600522990402912 N = 11790604055677230214731474049594783873473779547159534481643303694816346271798870343160061559787963631020684982858033776446193418629055210874285696446209220404060653230407249409973790191858423402504530660556839353260629987853933304089439885784684686555554108157760445567974629355878575105480273451284714281430590737346099023372211403461861104391534461524711472734572409128196536805998116015230502045333769525693468193385557827209520108839913096017750428926467123493650506193757937746017474062985480713594474378324234033232933140389879312722642144536418253323908290256009510135710208223393009237664704631175216240376891 '''
数据：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 27322282703709511636610535806856853612612796524565963685352821215367702697670029638291472271242231649191714479260517868076984065989639273952206721225394449809512736309152963717666213669565294618889004878502587203292128915123582846437035618297859622373514552659661751919687138158714389205196365694996691846589 48569244180151557205855904296808011040310995626104180491157243372509052545941856322458676083637192423759673249488348244220016168699221727901608142636001227515271570470832957720323162015971262916929310707561503164723954043820660896942792324593262461443662124187475159194385198887788939215142063719188348359051 91805670014258342004112051538515158497977951249015335208828337677065661825541672701641011001509677094927054079355384880161339840664535548572711525978354947655159331190183669338379535914171636373271711777662899462412133698069202075760175522929409084089926367963132890460921167025666146228784502671381146711019 399560428917764748532974912549579755263000603891290776423346071350694440330590365031312031331274402458285677563081638572382883720599282186196046608483533823720739712120092762382758124206813101015928952314835833408960456083078746116580899849811889743359253318716527623535224217277574914341453477162101109304521 66920426958285786458658248767160362920977647430969423155679844462544037512659182174429654322739226216034435833627040279237803034255254749729584723025199164153117416758037930376665769001615518843769072788984118288795594844920830871790000441610452127329422157793240336858492947908675187651204641324347460068225 544937610110319318485732752819003299421900030583201619755186005418563198983178922830516722630658659738570688423587906326520697827239870483140381321035311084086872965680985895264808839131965351704781276541438910273061170401708989341983455583148675268945159916067944049744805262336310315984482684477033006734287 5635003138990118507194506070175086831788576611651929217926664518872856396687497543355452282932759792957815071333069987192436081970967301109108636547955400620912244311244917063515500624803643902206301188548901042409824866123277584384961209855675044800618682367677428510425729333590673520619706804051348640739 216744037211012509915361607447276981890614637104708083303422302996997658600655325492799426696396129495740380030328486134561677905050895542824084902986133831827678164847190414920208201189028697970734101241668427915881431218718486605095651504942024880541330783245275847421981881418579001271393784051391703426641 42911212495890251189243677773682023641022813626312578449123776026147091248993904833237700742589532896024024290404122897946672451644535270088285040557715419433742408043822628453894022912746599564701384030731888203683342200542550299021286164291609827209395613247858235556551967071480178477133096158123879827699 358625812085590413825860316781088505612223852757468112073999439178735803245018313087878704846077887688463179850461438873261474235563220723161414348183847290126780153336526214025645436877174640254582752642464699350692290355463838062957644227630261763964930791440438099097640358707938365934460765509770713422802 76393649631519338646914577444953093042692772742019473672660460181129677128343169843350211463697634615281051117955282687134957585026912161500321667521577171255986824727912674810018184784281896427202094684250866650111325600908495879530295097533881586073569958225485019114664641193908557023741440163457101525203 329857997030576972729986815876777011654061886138716155424533348668225264710995265453134377944058890193085147694227229106567976594481366856016163332702128728982600129466565167735283489379015199424332093096162272256722421083932784837620468049877168507039726118947169347011547142986416984741443370137649949904461 79331720524907914908041917436319036255433828287857696014126718015259444328868691897077115926451094233087906865422458137916362681754241848523015955481140065721679824678490152910531795497192050173146826300375546645932629884190392808650921115445830421927238985963684104496062702531620988113510613763043301631209 521812627987763620197812504899506910796946504850708570349667428211492401785051233252744740254058319678959842396710646375803470815528610618211136953181796072686187773678649762524131730689630306575027480171902373722358678386430941181209464823845330723780859962168995759134414896419704465387883718956885830089204 34982047515239854027766260430773762615551551624040650169394931537920509836795394460680530502277933252344187876902284046236616780767724165813414385632503982500888235012434695560644146038269348824756839799255778718600829638272259933042402900324341026396868817418250681063616205184019449176410323763562609906256 620605218346899770429088593442355698411635752845778736545505196875522232769153705673917137123151382118878693457232039690080398947092819660645917999264381455940649845030563994094759265923737413658758514560434230280086651591011706752452769554749328591613510563389443179182520711924593818729897121279090347342924 152419925215633402551037300484006425703951620959940334562270582763998688826301000834158083436618204487451531847804246279293440954881219913553470971941979760351736535195521294640333019382215259554425750740788262905693120027837778006639912907313405166887419201498400381605572044667968915799849914769886304855469 534016646028730727016209888504911167747835078463480349483097394578844831015450227232096300754745773717118904569821782762146568167060585024245190142726454552015507956174745334336178848983708347742569471390328051491668238788357493167057460607669219247924675410096486695085439718252206048534436114032676610106347 7879488845815070796446980042322339499701160196159748256186513316298957679171765636643576866967308539398870809808590995575054707633585889782359230149070757943670854204408729244422811261494912348733104477093541158692065916137178255072991528458124264991587844119002172895462900656781795781239777162351236329010 88871679849011995091477347542680893996957786653924621705917895209560005458566552006873467270402185918706978818367798743110976595300781848502254399030378598802075501163781912730014790884964070072432678736909128727529050058640555516131888412874572332236693843543870582425734398659970857777429709921292338764056 127514038284722450386599280575918286761060061225148526034466492640545892790142008459404252129894996614536417849770574953585543450549469396103606474736901175227788222676384874264401431651217507860669506781393523454290522077615631381023377385798837961138591946856445250933293025411868935836885350047926486897489 77024841353020037736072564671223528105040202905964518913084686725674447555778849580882283151820241410917813178127609045792603404416216635536183501218256797138848233777386900397758052436048023588018973775841429672943588531118120531410941119451112420484244073744860360930771612798228353879418110447613074103121 73523397212562449962797322407800812476585158706372414597501601851658987192829920809491154804458216832212324494892234069944533082031068984251998442644045753330748501446440305199570609290581400456976816997103538669480916305434314437973807842397862244118575425198027445648296131215572682266387781847672276278105 358131172545144245017725954943677533669555698100417873957892816178502113778385580423968891034087567143540060215845324391804373505677355257229040486254496477702089813554705646138200115877254745085768546159462550014224359419574896275660358462631189412166193397952134507043404147073495973377634175173793168251233 147348014782035263557672447461924770257688598176948741569841957313948631675235455168853571742962013610522674191595258437726941866803703946285611136667070559549648062172513441677274884328986422767953568184453855423313870118663236611714535321243624425127415452246621538957156768109051856015526921750034402814181 595636882372433751112400377321820719222073583356736222414778628384644623278463447644996314505722523949309416112422725194730843858188224367723911893838329601709038981556011159397788345709995936511801237268248578658463705897357408752571102163768839107050797667376601808299838509114230891979045461260911946415320 107396275167806069862891568873373042687841775147343147252292584080352003252925523814251826627764872245643578589633919368796490434000761591564932634968812847926559005905574630301932715978159346119216934096015784765061798867698507880003720720252714582289061793936959096457352973294797409716470781535683208662390 395153432543738329086362624068574193255148332584492341243454102818775521905404929692387305225461869410602734064349062513722129355095148212452014041134124275764033437990333449975234478218955405224252839531173866658663372361601107447751367104423527019655871175001744848253584734158351726745551407103825286804486 111553464316331929637928443274530253217732988900086332463018159619552721468104642096142476958790984335379754112570481423047457696400188847850295271972015619208861578167810076654492163584804626343101458265888573313262592215690879907819608901681957001286346406746245896172209892822686784252329450759497940157817 511651161619212591638982125008326295422605195202233521320827338823708335474320214987121320809834264020752488400694820412703895872293388034242395958165882000777796549830919064001864919411540442573874044781198129468230793584507078981976925332170577699344654086418908951152825866266645119298895702972413286583958 152943203796417374728939496393486026220901654584673108139041097288333960510566510856084351323729904924640199712274885275910827036984793221821982353991291820643933058458639690879406578278096815789977814737418245161029735350306516366692394206323956675431185964629143452067819609148096407834611672577927865412392 601919715680710925447421076338078877766683489886991843150153117466383328925764100913643134608445665513170565014760605822708267601346612031986281277217875335899155526135282569237278337539198315798958944970975021604720637053079350115793916435033122479416157536224071649845398032404766802667331247026412465230897 166939346435092804149361985966477026395490869535977170373479116381554623702088662590719710620315106535772321371981485114999353813392487182004380368980412304867141197881584179316802946420573712884869207029807032629508803275758495901655593573546020371363238621118513519707566850164838945538265367877703756561143 234820987787318061334406237477763453845428872967687650137534289159784627741552971152526376041477941966693305257682995443922827379938186523574311761092208293391813942996139561570362972331975732091581332378414745250571717259039007898729580445364373819332663464831222506646891337600543033325723536694430603794811 26423433781831557303965218555715659459964805457875828323769054957811368313465747671809917056868138188812894920739462390440860614780050790166810205409831687879766298929374237068956851330280802672993787657036328401560347701569533751904003924033296103431436132762238032533631035466975563403490612905290747500034 564564388847953966153849841262670748320376369154008357907963983929690302350574296789978591185246923974920161797995189321841257011791368992972604074119872162539552292552362460968499190796503841035750507639233595470833894116053816701560762298879109510469040808411623441894361241720213857716595525048872499260906 67047973882442026847054596043723251652019181826511387455752441275468608245799296406017022023236054643173589545621722148324431435563020855357273526765167504290556087855144498047600331414488129605467552541562176094510433084299150667280746009871632940612151871433089450237469253872190728223812058292760792048327 190023992656957817692909813007060815279103259429273681430127196398700351704377473750794054807013341268132331757606642253453911294388801612173064841530999650755116853772677649649669913317951539550313189351839325961495963700012333982508285993230904890545000476087981313109451079110864357972818329854737276461934 105924866908333941056520542136279835222849349889633638544229314020165638653054683617844504431167584527725854457445810982830025832114705779346552001573819055283000133195971409988231558773967828820675125138322725072735898886865540351014422681184954059397593545246946913932272750078695992276555307091275819914167 590597067702351181983043135203878889479903130263737024839941242154123057325926009112777887235038694551309864253859910817785607380293492455212053557033975616644911248422981687394189486917578693691299595122658518879946708562394161159104748320544408107959224087679644857953504156164164979544525935685064483284685 22827549191923182771489295711738278961861882520382713026567330278695323394935257991730321079754157090063352969061001902180325794883825872692652931785445692861461395156956235124264369455654332939694635497992858109543951936728702559248172903917628186351382458456283437757539314944836549691976645744141289561930 158171468736013100218170873274656605219228738469715092751861925345310881653082508445746109167302799236685145510095499361526242392251594397820661050281094210672424887670015189702781308615421102937559185479455827148241690888934661637911906309379701856488858180027365752169466863585611322838180758159364570481257
仔细观察可以发现这个就是简单的线性代数，我们只要把数学关系式列出来，然后通过随机数预测去还原X矩阵的状态，求逆之后乘起来就好。
f函数是这样的：
x{0}*A_{0}+x {1}*A_{1}+x{2}*A_{2}+……+x {20}*A_{20}=result
稍微动动笔，列一下就发现总的来说就是矩阵乘，我们只要求出X的逆矩阵乘过另一边就好。
补齐x，用随机数预测的办法去找，很累，很无奈。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 import random from Crypto.Util.number import * from gmpy2 import next_prime, invert as inverse_mod from math import lcm def invert_right(m, l, val=''): length = 32 mx = 0xffffffff if val == '': val = mx i, res = 0, 0 while i * l < length: mask = (mx << (length - l) & mx) >> i * l tmp = m & mask m = m ^ tmp >> l & val res += tmp i += 1 return res def invert_left(m, l, val): length = 32 mx = 0xffffffff i, res = 0, 0 while i * l < length: mask = (mx >> (length - l) & mx) << i * l tmp = m & mask m ^= tmp << l & val res |= tmp i += 1 return res def invert_temper(m): m = invert_right(m, 18) m = invert_left(m, 15, 4022730752) m = invert_left(m, 7, 2636928640) m = invert_right(m, 11) return m def clone_mt(record): state = [invert_temper(i) for i in record] gen = random.Random() gen.setstate((3, tuple(state + [0]), None)) return gen def qiege(n): te = [] while n!=0: te.append(n%pow(2,32)) n = n>>32 return te def hebing(n): tmp = 0 for i in range(32): tmp += n[i]*pow(2,32*(i)) return tmp def getrandbits1024(): num = [] for _ in range(32): num += [g.getrandbits(32)] return (hebing(num)) X = [27322282703709511636610535806856853612612796524565963685352821215367702697670029638291472271242231649191714479260517868076984065989639273952206721225394449809512736309152963717666213669565294618889004878502587203292128915123582846437035618297859622373514552659661751919687138158714389205196365694996691846589 ,91805670014258342004112051538515158497977951249015335208828337677065661825541672701641011001509677094927054079355384880161339840664535548572711525978354947655159331190183669338379535914171636373271711777662899462412133698069202075760175522929409084089926367963132890460921167025666146228784502671381146711019 ,66920426958285786458658248767160362920977647430969423155679844462544037512659182174429654322739226216034435833627040279237803034255254749729584723025199164153117416758037930376665769001615518843769072788984118288795594844920830871790000441610452127329422157793240336858492947908675187651204641324347460068225 ,5635003138990118507194506070175086831788576611651929217926664518872856396687497543355452282932759792957815071333069987192436081970967301109108636547955400620912244311244917063515500624803643902206301188548901042409824866123277584384961209855675044800618682367677428510425729333590673520619706804051348640739,42911212495890251189243677773682023641022813626312578449123776026147091248993904833237700742589532896024024290404122897946672451644535270088285040557715419433742408043822628453894022912746599564701384030731888203683342200542550299021286164291609827209395613247858235556551967071480178477133096158123879827699,76393649631519338646914577444953093042692772742019473672660460181129677128343169843350211463697634615281051117955282687134957585026912161500321667521577171255986824727912674810018184784281896427202094684250866650111325600908495879530295097533881586073569958225485019114664641193908557023741440163457101525203 ,79331720524907914908041917436319036255433828287857696014126718015259444328868691897077115926451094233087906865422458137916362681754241848523015955481140065721679824678490152910531795497192050173146826300375546645932629884190392808650921115445830421927238985963684104496062702531620988113510613763043301631209 ,34982047515239854027766260430773762615551551624040650169394931537920509836795394460680530502277933252344187876902284046236616780767724165813414385632503982500888235012434695560644146038269348824756839799255778718600829638272259933042402900324341026396868817418250681063616205184019449176410323763562609906256 ,152419925215633402551037300484006425703951620959940334562270582763998688826301000834158083436618204487451531847804246279293440954881219913553470971941979760351736535195521294640333019382215259554425750740788262905693120027837778006639912907313405166887419201498400381605572044667968915799849914769886304855469 ,7879488845815070796446980042322339499701160196159748256186513316298957679171765636643576866967308539398870809808590995575054707633585889782359230149070757943670854204408729244422811261494912348733104477093541158692065916137178255072991528458124264991587844119002172895462900656781795781239777162351236329010 ,127514038284722450386599280575918286761060061225148526034466492640545892790142008459404252129894996614536417849770574953585543450549469396103606474736901175227788222676384874264401431651217507860669506781393523454290522077615631381023377385798837961138591946856445250933293025411868935836885350047926486897489 ,127514038284722450386599280575918286761060061225148526034466492640545892790142008459404252129894996614536417849770574953585543450549469396103606474736901175227788222676384874264401431651217507860669506781393523454290522077615631381023377385798837961138591946856445250933293025411868935836885350047926486897489,147348014782035263557672447461924770257688598176948741569841957313948631675235455168853571742962013610522674191595258437726941866803703946285611136667070559549648062172513441677274884328986422767953568184453855423313870118663236611714535321243624425127415452246621538957156768109051856015526921750034402814181 ,107396275167806069862891568873373042687841775147343147252292584080352003252925523814251826627764872245643578589633919368796490434000761591564932634968812847926559005905574630301932715978159346119216934096015784765061798867698507880003720720252714582289061793936959096457352973294797409716470781535683208662390 ,111553464316331929637928443274530253217732988900086332463018159619552721468104642096142476958790984335379754112570481423047457696400188847850295271972015619208861578167810076654492163584804626343101458265888573313262592215690879907819608901681957001286346406746245896172209892822686784252329450759497940157817 ,152943203796417374728939496393486026220901654584673108139041097288333960510566510856084351323729904924640199712274885275910827036984793221821982353991291820643933058458639690879406578278096815789977814737418245161029735350306516366692394206323956675431185964629143452067819609148096407834611672577927865412392,166939346435092804149361985966477026395490869535977170373479116381554623702088662590719710620315106535772321371981485114999353813392487182004380368980412304867141197881584179316802946420573712884869207029807032629508803275758495901655593573546020371363238621118513519707566850164838945538265367877703756561143 ,26423433781831557303965218555715659459964805457875828323769054957811368313465747671809917056868138188812894920739462390440860614780050790166810205409831687879766298929374237068956851330280802672993787657036328401560347701569533751904003924033296103431436132762238032533631035466975563403490612905290747500034 ,67047973882442026847054596043723251652019181826511387455752441275468608245799296406017022023236054643173589545621722148324431435563020855357273526765167504290556087855144498047600331414488129605467552541562176094510433084299150667280746009871632940612151871433089450237469253872190728223812058292760792048327,105924866908333941056520542136279835222849349889633638544229314020165638653054683617844504431167584527725854457445810982830025832114705779346552001573819055283000133195971409988231558773967828820675125138322725072735898886865540351014422681184954059397593545246946913932272750078695992276555307091275819914167 ] T = [] tmp = [] for _ in range(20): tmp+=(qiege(X[_])) g = clone_mt(tmp[:624]) for _ in range(20): T.append(getrandbits1024()) assert T[-1] == X[-1] print(getrandbits1024()) #通过随机数预测，补齐X的矩阵
以上部分是用来补齐矩阵数据的。
接下来正式利用逆矩阵去求解矩阵A。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 p=667548632459029899397299221540978856425474915828934339291333387574324630349258515018972045406265448494845331262999241448002076917383740651362641947814545076390796789402373579283727117618532504865966299599663825771187433223531022829811594806917984414530614469374596457149431218829297339079019894262229453357029 G = GF(p) R = [48569244180151557205855904296808011040310995626104180491157243372509052545941856322458676083637192423759673249488348244220016168699221727901608142636001227515271570470832957720323162015971262916929310707561503164723954043820660896942792324593262461443662124187475159194385198887788939215142063719188348359051 , 399560428917764748532974912549579755263000603891290776423346071350694440330590365031312031331274402458285677563081638572382883720599282186196046608483533823720739712120092762382758124206813101015928952314835833408960456083078746116580899849811889743359253318716527623535224217277574914341453477162101109304521 , 544937610110319318485732752819003299421900030583201619755186005418563198983178922830516722630658659738570688423587906326520697827239870483140381321035311084086872965680985895264808839131965351704781276541438910273061170401708989341983455583148675268945159916067944049744805262336310315984482684477033006734287 , 216744037211012509915361607447276981890614637104708083303422302996997658600655325492799426696396129495740380030328486134561677905050895542824084902986133831827678164847190414920208201189028697970734101241668427915881431218718486605095651504942024880541330783245275847421981881418579001271393784051391703426641 , 358625812085590413825860316781088505612223852757468112073999439178735803245018313087878704846077887688463179850461438873261474235563220723161414348183847290126780153336526214025645436877174640254582752642464699350692290355463838062957644227630261763964930791440438099097640358707938365934460765509770713422802 , 329857997030576972729986815876777011654061886138716155424533348668225264710995265453134377944058890193085147694227229106567976594481366856016163332702128728982600129466565167735283489379015199424332093096162272256722421083932784837620468049877168507039726118947169347011547142986416984741443370137649949904461 , 521812627987763620197812504899506910796946504850708570349667428211492401785051233252744740254058319678959842396710646375803470815528610618211136953181796072686187773678649762524131730689630306575027480171902373722358678386430941181209464823845330723780859962168995759134414896419704465387883718956885830089204 , 620605218346899770429088593442355698411635752845778736545505196875522232769153705673917137123151382118878693457232039690080398947092819660645917999264381455940649845030563994094759265923737413658758514560434230280086651591011706752452769554749328591613510563389443179182520711924593818729897121279090347342924 , 534016646028730727016209888504911167747835078463480349483097394578844831015450227232096300754745773717118904569821782762146568167060585024245190142726454552015507956174745334336178848983708347742569471390328051491668238788357493167057460607669219247924675410096486695085439718252206048534436114032676610106347 , 88871679849011995091477347542680893996957786653924621705917895209560005458566552006873467270402185918706978818367798743110976595300781848502254399030378598802075501163781912730014790884964070072432678736909128727529050058640555516131888412874572332236693843543870582425734398659970857777429709921292338764056 , 77024841353020037736072564671223528105040202905964518913084686725674447555778849580882283151820241410917813178127609045792603404416216635536183501218256797138848233777386900397758052436048023588018973775841429672943588531118120531410941119451112420484244073744860360930771612798228353879418110447613074103121 , 358131172545144245017725954943677533669555698100417873957892816178502113778385580423968891034087567143540060215845324391804373505677355257229040486254496477702089813554705646138200115877254745085768546159462550014224359419574896275660358462631189412166193397952134507043404147073495973377634175173793168251233 , 595636882372433751112400377321820719222073583356736222414778628384644623278463447644996314505722523949309416112422725194730843858188224367723911893838329601709038981556011159397788345709995936511801237268248578658463705897357408752571102163768839107050797667376601808299838509114230891979045461260911946415320 , 395153432543738329086362624068574193255148332584492341243454102818775521905404929692387305225461869410602734064349062513722129355095148212452014041134124275764033437990333449975234478218955405224252839531173866658663372361601107447751367104423527019655871175001744848253584734158351726745551407103825286804486 , 511651161619212591638982125008326295422605195202233521320827338823708335474320214987121320809834264020752488400694820412703895872293388034242395958165882000777796549830919064001864919411540442573874044781198129468230793584507078981976925332170577699344654086418908951152825866266645119298895702972413286583958 , 601919715680710925447421076338078877766683489886991843150153117466383328925764100913643134608445665513170565014760605822708267601346612031986281277217875335899155526135282569237278337539198315798958944970975021604720637053079350115793916435033122479416157536224071649845398032404766802667331247026412465230897 , 234820987787318061334406237477763453845428872967687650137534289159784627741552971152526376041477941966693305257682995443922827379938186523574311761092208293391813942996139561570362972331975732091581332378414745250571717259039007898729580445364373819332663464831222506646891337600543033325723536694430603794811 , 564564388847953966153849841262670748320376369154008357907963983929690302350574296789978591185246923974920161797995189321841257011791368992972604074119872162539552292552362460968499190796503841035750507639233595470833894116053816701560762298879109510469040808411623441894361241720213857716595525048872499260906 , 190023992656957817692909813007060815279103259429273681430127196398700351704377473750794054807013341268132331757606642253453911294388801612173064841530999650755116853772677649649669913317951539550313189351839325961495963700012333982508285993230904890545000476087981313109451079110864357972818329854737276461934 , 590597067702351181983043135203878889479903130263737024839941242154123057325926009112777887235038694551309864253859910817785607380293492455212053557033975616644911248422981687394189486917578693691299595122658518879946708562394161159104748320544408107959224087679644857953504156164164979544525935685064483284685 , 158171468736013100218170873274656605219228738469715092751861925345310881653082508445746109167302799236685145510095499361526242392251594397820661050281094210672424887670015189702781308615421102937559185479455827148241690888934661637911906309379701856488858180027365752169466863585611322838180758159364570481257 ] R = Matrix(G,R) R = R.transpose() def make (x ): X = [] for i in range (21 ): X.append(x^i) return X x = [27322282703709511636610535806856853612612796524565963685352821215367702697670029638291472271242231649191714479260517868076984065989639273952206721225394449809512736309152963717666213669565294618889004878502587203292128915123582846437035618297859622373514552659661751919687138158714389205196365694996691846589 , 91805670014258342004112051538515158497977951249015335208828337677065661825541672701641011001509677094927054079355384880161339840664535548572711525978354947655159331190183669338379535914171636373271711777662899462412133698069202075760175522929409084089926367963132890460921167025666146228784502671381146711019 , 66920426958285786458658248767160362920977647430969423155679844462544037512659182174429654322739226216034435833627040279237803034255254749729584723025199164153117416758037930376665769001615518843769072788984118288795594844920830871790000441610452127329422157793240336858492947908675187651204641324347460068225 , 5635003138990118507194506070175086831788576611651929217926664518872856396687497543355452282932759792957815071333069987192436081970967301109108636547955400620912244311244917063515500624803643902206301188548901042409824866123277584384961209855675044800618682367677428510425729333590673520619706804051348640739 , 42911212495890251189243677773682023641022813626312578449123776026147091248993904833237700742589532896024024290404122897946672451644535270088285040557715419433742408043822628453894022912746599564701384030731888203683342200542550299021286164291609827209395613247858235556551967071480178477133096158123879827699 , 76393649631519338646914577444953093042692772742019473672660460181129677128343169843350211463697634615281051117955282687134957585026912161500321667521577171255986824727912674810018184784281896427202094684250866650111325600908495879530295097533881586073569958225485019114664641193908557023741440163457101525203 , 79331720524907914908041917436319036255433828287857696014126718015259444328868691897077115926451094233087906865422458137916362681754241848523015955481140065721679824678490152910531795497192050173146826300375546645932629884190392808650921115445830421927238985963684104496062702531620988113510613763043301631209 , 34982047515239854027766260430773762615551551624040650169394931537920509836795394460680530502277933252344187876902284046236616780767724165813414385632503982500888235012434695560644146038269348824756839799255778718600829638272259933042402900324341026396868817418250681063616205184019449176410323763562609906256 , 152419925215633402551037300484006425703951620959940334562270582763998688826301000834158083436618204487451531847804246279293440954881219913553470971941979760351736535195521294640333019382215259554425750740788262905693120027837778006639912907313405166887419201498400381605572044667968915799849914769886304855469 , 7879488845815070796446980042322339499701160196159748256186513316298957679171765636643576866967308539398870809808590995575054707633585889782359230149070757943670854204408729244422811261494912348733104477093541158692065916137178255072991528458124264991587844119002172895462900656781795781239777162351236329010 , 127514038284722450386599280575918286761060061225148526034466492640545892790142008459404252129894996614536417849770574953585543450549469396103606474736901175227788222676384874264401431651217507860669506781393523454290522077615631381023377385798837961138591946856445250933293025411868935836885350047926486897489 , 73523397212562449962797322407800812476585158706372414597501601851658987192829920809491154804458216832212324494892234069944533082031068984251998442644045753330748501446440305199570609290581400456976816997103538669480916305434314437973807842397862244118575425198027445648296131215572682266387781847672276278105 , 147348014782035263557672447461924770257688598176948741569841957313948631675235455168853571742962013610522674191595258437726941866803703946285611136667070559549648062172513441677274884328986422767953568184453855423313870118663236611714535321243624425127415452246621538957156768109051856015526921750034402814181 , 107396275167806069862891568873373042687841775147343147252292584080352003252925523814251826627764872245643578589633919368796490434000761591564932634968812847926559005905574630301932715978159346119216934096015784765061798867698507880003720720252714582289061793936959096457352973294797409716470781535683208662390 , 111553464316331929637928443274530253217732988900086332463018159619552721468104642096142476958790984335379754112570481423047457696400188847850295271972015619208861578167810076654492163584804626343101458265888573313262592215690879907819608901681957001286346406746245896172209892822686784252329450759497940157817 , 152943203796417374728939496393486026220901654584673108139041097288333960510566510856084351323729904924640199712274885275910827036984793221821982353991291820643933058458639690879406578278096815789977814737418245161029735350306516366692394206323956675431185964629143452067819609148096407834611672577927865412392 , 166939346435092804149361985966477026395490869535977170373479116381554623702088662590719710620315106535772321371981485114999353813392487182004380368980412304867141197881584179316802946420573712884869207029807032629508803275758495901655593573546020371363238621118513519707566850164838945538265367877703756561143 , 26423433781831557303965218555715659459964805457875828323769054957811368313465747671809917056868138188812894920739462390440860614780050790166810205409831687879766298929374237068956851330280802672993787657036328401560347701569533751904003924033296103431436132762238032533631035466975563403490612905290747500034 , 67047973882442026847054596043723251652019181826511387455752441275468608245799296406017022023236054643173589545621722148324431435563020855357273526765167504290556087855144498047600331414488129605467552541562176094510433084299150667280746009871632940612151871433089450237469253872190728223812058292760792048327 , 105924866908333941056520542136279835222849349889633638544229314020165638653054683617844504431167584527725854457445810982830025832114705779346552001573819055283000133195971409988231558773967828820675125138322725072735898886865540351014422681184954059397593545246946913932272750078695992276555307091275819914167 , 22827549191923182771489295711738278961861882520382713026567330278695323394935257991730321079754157090063352969061001902180325794883825872692652931785445692861461395156956235124264369455654332939694635497992858109543951936728702559248172903917628186351382458456283437757539314944836549691976645744141289561930 ] X = [] for i in x: X.append(make(i)) X = Matrix(G,X) X_inv = X.inverse() T = X_inv*R print (T[0 ]) (92422003757477651157474383100036998824887848419954840007147868223910074931859933956269885856128093345487882260496791272977844862352094356168399257688148495739541010758727078419554501190171624312463235528402998918943680454965800744650511720557056811235552334860437375771202122918781073950952368367594976459763 ) leak = 158171468736013100218170873274656605219228738469715092751861925345310881653082508445746109167302799236685145510095499361526242392251594397820661050281094210672424887670015189702781308615421102937559185479455827148241690888934661637911906309379701856488858180027365752169466863585611322838180758159364570481257 p = 667548632459029899397299221540978856425474915828934339291333387574324630349258515018972045406265448494845331262999241448002076917383740651362641947814545076390796789402373579283727117618532504865966299599663825771187433223531022829811594806917984414530614469374596457149431218829297339079019894262229453357029 c = 9658009093151541277762773618550582280013680172161026781649630205505443184765264518709081169475689440555639354980432557616120809346519461077355134139495745998317849357705381020225760061125236265304057301286196004542729553944161451832173970613915423841610378207266606500956362098150141825329354727367056070349148059780287916811442861961254066733726576151134458892613951223277692935141880749737598416235307087782001086096114978527447987308876878393763055893556123029990282534497668077854186604106027698257663251502775547705641708624619340185646943640576690633662704397191379303254341343433077302686466850600522990402912 N = 11790604055677230214731474049594783873473779547159534481643303694816346271798870343160061559787963631020684982858033776446193418629055210874285696446209220404060653230407249409973790191858423402504530660556839353260629987853933304089439885784684686555554108157760445567974629355878575105480273451284714281430590737346099023372211403461861104391534461524711472734572409128196536805998116015230502045333769525693468193385557827209520108839913096017750428926467123493650506193757937746017474062985480713594474378324234033232933140389879312722642144536418253323908290256009510135710208223393009237664704631175216240376891 q = 92422003757477651157474383100036998824887848419954840007147868223910074931859933956269885856128093345487882260496791272977844862352094356168399257688148495739541010758727078419554501190171624312463235528402998918943680454965800744650511720557056811235552334860437375771202122918781073950952368367594976459763 p = N//q print (isPrime(q)) e = 65537 phi = (q-1 )*(p-1 ) d = inverse(e,phi) m = pow (c,d,N) print (long_to_bytes(m))
task:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 import randomfrom Crypto.Util.number import *from Crypto.Cipher import AESfrom Crypto.Util.Padding import padimport gmpy2import osimport hashlibdef xor (a, b ): return bytes ([a[i%len (a)] ^ b[i%len (b)] for i in range (max (len (a), len (b)))]) flag = b'flag{xxxxxx}' key1 = hashlib.md5(os.urandom(16 )).hexdigest().encode() key2 = hashlib.md5(os.urandom(16 )).hexdigest().encode() num1 = 5 p = int (gmpy2.next_prime(bytes_to_long(key1 + os.urandom(64 )))) ms = [random.getrandbits(256 ) for _ in range (num1)] qs = [getPrime(1024 ) for _ in range (num1)] ns = [p * qs[_] + ms[_] for _ in range (num1)] num2 = 37 x = bytes_to_long(key2 + os.urandom(32 )) A = [] B = [] for i in range (num2): a = random.getrandbits(512 ) b = a * x % p gift = (2 ** 128 - 1 ) * 2 ** 400 A.append(a) B.append((b & gift) >> 400 ) iv = long_to_bytes(random.getrandbits(128 )) key = xor(key1,key2) aes = AES.new(key1,AES.MODE_CBC,iv) enc = aes.encrypt(pad(flag,48 )) print (f'ns = {ns} ' )print (f'A = {A} ' )print (f'B = {B} ' )print (f'enc = {enc} ' )
思路：
我们的目标是求出key1，而key1就是质数p的高位，要求出质数p就得通过ns的数据去求解，这点很容易想得到
那么观察ns数据的生成办法：
n_{i} = p*qs_{i}+ms_{i}
十分的眼熟，那么来操作一下：
n_{i} -ms_{i}= p*qs_{i}
其中仔细观察就可以知道ms是可以预测生成的！那么这道题就变得很简单了，只要预测出ms之后，正常的GCD就可以了。但是我有懒癌。想到这里就没去预测了，太**了，一个随机数搞两次，实在是无聊。
懒得写了这部分。
另外一种办法就是用AGCD的办法去解：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 from Crypto.Util.number import *from Crypto.Cipher import AESimport hashlibkbits = 256 Q = [38630062416586710341458654419912504176237737247477839749085033080367529539859992076587411537805430366799412095876782912512744262957062106155418341531142309858429218208463637096843365217114990765965110566415965985105403996944993619708417839598461935470469097206342256014086162845948208599334925650727933097059538199199685364793545286980392966271769914201657672004082101110775504946586957241075964270454872257405872181588544468173017149763827540561921126826597515171761064800381983526515300315517818122598179574900255685121991744205071544970 , 41522753602903133841910260331594875922287719226997542592715810409935551768308104573333760854332533376702631593490915962706512143045107096658851885513727202513616813054397657610854303071682604806070009002234312854968365250748142324994926715544722158698813288131533399544263105858513134170084625526223987620550110255872688155827773099232631041345207194483609514502522566888883736218471849075697433311580004701384847571029783514418685068903758509270527252444771313048094566344002411364378658592832008194309873599342916391769027015343562030852 , 41542983120532762175372001624404625565366126179958909731196555044290633581761361918706298428954501507557598076910710787422049443564800530253137695341299743714514361560156305534490483794181933110893966453220306980682146624294992100948497284459992930850081254114996830645068636306625330524465991656430799359422407117440063911943625477783216502523414967017151717597372146324488526509879620785458016456593044828784565522423332830549325397893426472247197776412026158371655860380929692662547882654137064941217130915364306358205055760044763651406 , 42853015443318352230776688785915441259875645365236808434164117288657978345098324019250085686482568413223085548506789311679316323466083886556772338612177680666217592255234589446979456714341877135596118517098603502394776049958587301113539552072352462301070489369653155854389890761241450743607560719433910573462283304103064437843063566946231984094581307498714742271881862348689297267558023093643893310002803310596286441071314219020032740336515363830250477649030557311461077069407775907176409762823453607196260454965048316567154365877848652918 , 31152961872836435078296602982779340735140569916125711058616435902653202922218293684857125091648631460215120167354825278469413413558325850576700866199515219603448136082693185200558425103833947831228064760642508443585470729998592994719564254894176473779555436230174300038353978808432410463449170865897259181312953584408177790825688497584119467820716449210429423337019604137134889051973100340798405991782200038835066294194815913887924272593864934325496116821854183293510325217934617021428710898873475027666892706022106386340733691632884942848 ] L = Matrix(ZZ,5 ,5 ) L[0 ,0 ] = 2 ^(kbits) for i in range (1 ,5 ): L[0 ,i] = Q[i] L[i,i] = -Q[0 ] res = L.LLL()[0 ] q0 = int (abs (res[0 ]) // L[0 ,0 ]) p = int (abs (Q[0 ]) // q0) key1 = long_to_bytes(p)[:32 ]
这样也行。
多余的部分：
至于key2，可求可不求，这里要求的话提供思路：
题目给的公式：\ b = a*x (modp)
目标是求出x，a已知，b部分已知，那么这样来想：
B矩阵中的元素是b的高128位(b共528位)\ b = b_0+b_1\ 我们令b_1为未知数\ 那么有：ax-b_0=b_1(modp)\ emmm这不就是简单的LWE问题\ a x-b_0-k*p=b_1
其中p在求key1的时候已经有了，那么这里就直接按照求HNP还是什么P的问题，直接构造“那个”矩阵规约就好。
[x,k_1,k_2,k_3,……,k_n,1]\left[ \begin{matrix} a & a & a &a& a & a &a\ -p & -p & -p &-p & -p & -p &-p \ -b_0 & 0 & 0 & 0 & 0 & 0 & 0\0 &-b_0 & 0 & 0 & 0 & 0 & 0\0 & 0 & -b_0 & 0 & 0 & 0 & 0\0 & 0 & 0 & -b_0 & 0 & 0 & 0\0 & 0 & 0 & 0 &-b_0 & 0 & 0\0 & 0 & 0 & 0 & 0 & -b_0 & 0\0 & 0 & 0 & 0 & 0 & 0 & -b_0 \end{matrix} \right] =[b_1,b_2,b_3,b_4,……,b_n]
大致就是这样构造，如果不行的话可以试试配平的操作。
比较懒，大致意思就是这样，对中间那个大矩阵规约得到左边那个基就好。
这里在比赛期间没写出来，从这位大哥的博客借鉴一下：
->>糖醋小鸡快
推荐可以去大哥的博客看看剪枝是怎么操作的，以及为什么这样写。
这里补齐我没有写出来的遗憾，简单抄个代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 from Crypto.Util.number import *import syssys.setrecursionlimit(1500 ) nbits=512 leakBits = 262 leakbits = nbits - leakBits e = 65537 n=73822410148110759760164946405270228269255384237831275745269402590230495569279769799226813942899942423718229747478982630879557319063920515141217164980012063064986634632452289290326704640527699568662492105204165609614169349755365956569362139057327962393611139347462018186440108621311077722819578905265976612923 c=71808322808599218331233291542779486534747913572475630198802984648982830332628443972652322590637382696027943799004331488098592525306523343649935216419522329722152742610560398216737030893090641493326477786720839849938277402743820773957184083430369443325368720115515840174745825798187125454448297155036065857691 leak=2223117424030234543005449667053988296724455736030907136592525175314696509716321 leak = leak << leakbits a1 = "0" + str (bin (leak)[2 :]) def find (p,q ): l = len (p) tmp0 = p + (512 -l)*"0" tmp1 = p + (512 -l)*"1" tmq0 = q + (512 -l)*"0" tmq1 = q + (512 -l)*"1" if (int (tmp0,2 ) < int (tmq0,2 )): return if (int (tmp0,2 )*int (tmq0,2 ) > n): return elif (int (tmp1,2 )*int (tmq1,2 ) < n): return if (l == 512 - leakbits): pp = int (tmp0,2 ) PR.<x> = PolynomialRing(Zmod(n)) f = pp + x*2 + 1 f = f.monic() res = f.small_roots(X=2 ^leakbits-1 , beta=0.5 , epsilon=0.01 ) if (res): try : plow = int (res[0 ]) p = pp + plow * 2 + 1 q = n // p d = inverse(e,(p-1 )*(q-1 )) print (long_to_bytes(int (pow (c,d,n)))) except : pass else : if (a1[l] == "1" ): find(p+"1" ,q+"0" ) find(p+"0" ,q+"1" ) else : find(p+"0" ,q+"0" ) find(p+"1" ,q+"1" ) tempp = "" tempq = "" find(tempp,tempq)
(流程图在这里)