from Crypto.PublicKey import RSA import libnum import gmpy2 import uuid
flag = "flag{" + str(uuid.uuid4()) + "}" print(flag) m = libnum.s2n(flag)
p = libnum.generate_prime(1024) q = gmpy2.next_prime(p) n = p * q e = 65537 phi = (p - 1) * (q - 1) d = gmpy2.invert(e, phi) m = libnum.s2n(flag) c = pow(m, e, n) # c1 = libnum.n2s(int(c))
withopen("flag.pem", "wb") as f: f.write(c1) # 生成公钥 rsa_components = (int(n), int(e), int(d)) keypair = RSA.construct(rsa_components) withopen('pubckey.pem', 'wb') as f: f.write(keypair.exportKey())
题目中把d也传入数据了,直接读取d解密即可
1 2 3 4 5 6 7 8 9 10 11 12
from Crypto.PublicKey import RSA from Crypto.Util.number import *
c = bytes_to_long(open("flag.pem","rb").read()) key = RSA.import_key(open("publickey.pem","rb").read()) e = key.e n = key.n d = key.d
from Crypto.Cipher import PKCS1_OAEP from Crypto.PublicKey.RSA import *
c = open("flag2.pem","rb").read() key = import_key(open("prikey2.pem","rb").read())
newkey = PKCS1_OAEP.new(key) m = newkey.decrypt(c) print(m).
#flag{04bbaad0-9241-42a4-9fd4-7d6e0d8bc5f1}
攻防世界——cr4-poor-rsa
题目给了个无后缀的文件,拖到010发现里面有藏两个文件,于是把后缀改成了zip
打开后得到两个文件,分别是key.pub和flag.b64
key.pub
1 2 3 4
-----BEGIN PUBLIC KEY----- ME0wDQYJKoZIhvcNAQEBBQADPAAwOQIyUqmeJJ7nzzwMv5Y6AJZhdyvJzfbh4/v8 bkSgel4PiURXqfgcOuEyrFaD01soulwyQkMCAwEAAQ== -----END PUBLIC KEY-----
import base64 from Crypto.PublicKey.RSA import * from Crypto.Util.number import * import gmpy2
c = base64.b64decode(open("flag.b64","rb").read()) c = bytes_to_long(c) key = import_key(open("key.pub","rb").read())
p = 863653476616376575308866344984576466644942572246900013156919 q = 965445304326998194798282228842484732438457170595999523426901 n = p*q e = 65537 d = gmpy2.invert(e,(p-1)*(q-1)) print(long_to_bytes(pow(c,d,n)))
#XCTF{SMALL_PRIMES_ARE_BAD}
四、共模攻击
共模攻击:
在对同一明文的加密过程中使用相同的模数n,对同一明文,用不同的密钥e(两个密钥是互素的)进行加密
结果是得到两个不同的c
原理: $$ c_1 \equiv m^{e_1} \mod n\\ c_2 \equiv m^{e_2} \mod n $$ 通过欧几里得扩展算法我们能得到$x,y$满足$e_1x+e_2y = 1$ $$ \therefore c_1^x \times c_2^y \equiv m^{e_1x + e_2y} \equiv m \mod n $$
import libnum import gmpy2 import uuid flag = "flag{" + str(uuid.uuid4()) + "}" m = libnum.s2n(flag) print(gmpy2.bit_length(m ** 3)) whileTrue: p = libnum.generate_prime(504) q = libnum.generate_prime(504) n = p * q phi_n = (p - 1) * (q - 1) e = 3 if gmpy2.gcd(e, phi_n) == 1and phi_n%e !=0: break
c = pow(m, e, n) print("n=", n) print("e=", e) print("c=", c)
#c= 17567615026662297423639652671128685098763112348521263232850922784902991105809108670614334001294254886850775709702759646022208238160649099765454315761185950859820327234504422026634432251632399712621439201146 3091635444512796333373451321795475333496092463760390199602320265733668648810943598505902205569125 n = 1101676297168703265566511587913652821222614528632844563918598090813090976948138058144049294690727841463413972173051671908835164088465174349647584948964206244648736138253802417241570633968307801570794459668533128958442296813160786428069813867034205462528763830205245218089660432399549540588101288362866463 e = 3
exp.py
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
from Crypto.Util.number import * import gmpy2
n = 1101676297168703265566511587913652821222614528632844563918598090813090976948138058144049294690727841463413972173051671908835164088465174349647584948964206244648736138253802417241570633968307801570794459668533128958442296813160786428069813867034205462528763830205245218089660432399549540588101288362866463 e = 3 c = 175676150266622974236396526711286850987631123485212632328509227849029911058091086706143340012942548868507757097027596460222082381606490997654543157611859508598203272345044220266344322516323997126214392011463091635444512796333373451321795475333496092463760390199602320265733668648810943598505902205569125 k = 0
t = gmpy2.iroot(c,e) if t[1]: print(long_to_bytes(t[0])) else: for i in trange() 1: m = gmpy2.iroot(k*n+c,e) if m[1]: print(long_to_bytes(m[0])) break else: k += 1
m = xxxxxxxx e = 65537 ========== n c ========== n = 20474918894051778533305262345601880928088284471121823754049725354072477155873778848055073843345820697886641086842612486541250183965966001591342031562953561793332341641334302847996108417466360688139866505179689516589305636902137210185624650854906780037204412206309949199080005576922775773722438863762117750429327585792093447423980002401200613302943834212820909269713876683465817369158585822294675056978970612202885426436071950214538262921077409076160417436699836138801162621314845608796870206834704116707763169847387223307828908570944984416973019427529790029089766264949078038669523465243837675263858062854739083634207 c = 974463908243330865728978769213595400782053398596897741316275722596415018912929508637393850919224969271766388710025195039896961956062895570062146947736340342927974992616678893372744261954172873490878805483241196345881721164078651156067119957816422768524442025688079462656755605982104174001635345874022133045402344010045961111720151990412034477755851802769069309069018738541854130183692204758761427121279982002993939745343695671900015296790637464880337375511536424796890996526681200633086841036320395847725935744757993013352804650575068136129295591306569213300156333650910795946800820067494143364885842896291126137320
n = 20918819960648891349438263046954902210959146407860980742165930253781318759285692492511475263234242002509419079545644051755251311392635763412553499744506421566074721268822337321637265942226790343839856182100575539845358877493718334237585821263388181126545189723429262149630651289446553402190531135520836104217160268349688525168375213462570213612845898989694324269410202496871688649978370284661017399056903931840656757330859626183773396574056413017367606446540199973155630466239453637232936904063706551160650295031273385619470740593510267285957905801566362502262757750629162937373721291789527659531499435235261620309759 c = 15819636201971185538694880505120469332582151856714070824521803121848292387556864177196229718923770810072104155432038682511434979353089791861087415144087855679134383396897817458726543883093567600325204596156649305930352575274039425470836355002691145864435755333821133969266951545158052745938252574301327696822347115053614052423028835532509220641378760800693351542633860702225772638930501021571415907348128269681224178300248272689705308911282208685459668200507057183420662959113956077584781737983254788703048275698921427029884282557468334399677849962342196140864403989162117738206246183665814938783122909930082802031855
n = 25033254625906757272369609119214202033162128625171246436639570615263949157363273213121556825878737923265290579551873824374870957467163989542063489416636713654642486717219231225074115269684119428086352535471683359486248203644461465935500517901513233739152882943010177276545128308412934555830087776128355125932914846459470221102007666912211992310538890654396487111705385730502843589727289829692152177134753098649781412247065660637826282055169991824099110916576856188876975621376606634258927784025787142263367152947108720757222446686415627479703666031871635656314282727051189190889008763055811680040315277078928068816491 c = 4185308529416874005831230781014092407198451385955677399668501833902623478395669279404883990725184332709152443372583701076198786635291739356770857286702107156730020004358955622511061410661058982622055199736820808203841446796305284394651714430918690389486920560834672316158146453183789412140939029029324756035358081754426645160033262924330248675216108270980157049705488620263485129480952814764002865280019185127662449318324279383277766416258142275143923532168798413011028271543085249029048997452212503111742302302065401051458066585395360468447460658672952851643547193822775218387853623453638025492389122204507555908862
n = 21206968097314131007183427944486801953583151151443627943113736996776787181111063957960698092696800555044199156765677935373149598221184792286812213294617749834607696302116136745662816658117055427803315230042700695125718401646810484873064775005221089174056824724922160855810527236751389605017579545235876864998419873065217294820244730785120525126565815560229001887622837549118168081685183371092395128598125004730268910276024806808565802081366898904032509920453785997056150497645234925528883879419642189109649009132381586673390027614766605038951015853086721168018787523459264932165046816881682774229243688581614306480751 c = 4521038011044758441891128468467233088493885750850588985708519911154778090597136126150289041893454126674468141393472662337350361712212694867311622970440707727941113263832357173141775855227973742571088974593476302084111770625764222838366277559560887042948859892138551472680654517814916609279748365580610712259856677740518477086531592233107175470068291903607505799432931989663707477017904611426213770238397005743730386080031955694158466558475599751940245039167629126576784024482348452868313417471542956778285567779435940267140679906686531862467627238401003459101637191297209422470388121802536569761414457618258343550613
n = 22822039733049388110936778173014765663663303811791283234361230649775805923902173438553927805407463106104699773994158375704033093471761387799852168337898526980521753614307899669015931387819927421875316304591521901592823814417756447695701045846773508629371397013053684553042185725059996791532391626429712416994990889693732805181947970071429309599614973772736556299404246424791660679253884940021728846906344198854779191951739719342908761330661910477119933428550774242910420952496929605686154799487839923424336353747442153571678064520763149793294360787821751703543288696726923909670396821551053048035619499706391118145067 c = 15406498580761780108625891878008526815145372096234083936681442225155097299264808624358826686906535594853622687379268969468433072388149786607395396424104318820879443743112358706546753935215756078345959375299650718555759698887852318017597503074317356745122514481807843745626429797861463012940172797612589031686718185390345389295851075279278516147076602270178540690147808314172798987497259330037810328523464851895621851859027823681655934104713689539848047163088666896473665500158179046196538210778897730209572708430067658411755959866033531700460551556380993982706171848970460224304996455600503982223448904878212849412357
n = 21574139855341432908474064784318462018475296809327285532337706940126942575349507668289214078026102682252713757703081553093108823214063791518482289846780197329821139507974763780260290309600884920811959842925540583967085670848765317877441480914852329276375776405689784571404635852204097622600656222714808541872252335877037561388406257181715278766652824786376262249274960467193961956690974853679795249158751078422296580367506219719738762159965958877806187461070689071290948181949561254144310776943334859775121650186245846031720507944987838489723127897223416802436021278671237227993686791944711422345000479751187704426369 c = 20366856150710305124583065375297661819795242238376485264951185336996083744604593418983336285185491197426018595031444652123288461491879021096028203694136683203441692987069563513026001861435722117985559909692670907347563594578265880806540396777223906955491026286843168637367593400342814725694366078337030937104035993569672959361347287894143027186846856772983058328919716702982222142848848117768499996617588305301483085428547267337070998767412540225911508196842253134355901263861121500650240296746702967594224401650220168780537141654489215019142122284308116284129004257364769474080721001708734051264841350424152506027932
n = 25360227412666612490102161131174584819240931803196448481224305250583841439581008528535930814167338381983764991296575637231916547647970573758269411168219302370541684789125112505021148506809643081950237623703181025696585998044695691322012183660424636496897073045557400768745943787342548267386564625462143150176113656264450210023925571945961405709276631990731602198104287528528055650050486159837612279600415259486306154947514005408907590083747758953115486124865486720633820559135063440942528031402951958557630833503775112010715604278114325528993771081233535247118481765852273252404963430792898948219539473312462979849137 c = 19892772524651452341027595619482734356243435671592398172680379981502759695784087900669089919987705675899945658648623800090272599154590123082189645021800958076861518397325439521139995652026377132368232502108620033400051346127757698623886142621793423225749240286511666556091787851683978017506983310073524398287279737680091787333547538239920607761080988243639547570818363788673249582783015475682109984715293163137324439862838574460108793714172603672477766831356411304446881998674779501188163600664488032943639694828698984739492200699684462748922883550002652913518229322945040819064133350314536378694523704793396169065179
n = 22726855244632356029159691753451822163331519237547639938779517751496498713174588935566576167329576494790219360727877166074136496129927296296996970048082870488804456564986667129388136556137013346228118981936899510687589585286517151323048293150257036847475424044378109168179412287889340596394755257704938006162677656581509375471102546261355748251869048003600520034656264521931808651038524134185732929570384705918563982065684145766427962502261522481994191989820110575981906998431553107525542001187655703534683231777988419268338249547641335718393312295800044734534761692799403469497954062897856299031257454735945867491191 c = 6040119795175856407541082360023532204614723858688636724822712717572759793960246341800308149739809871234313049629732934797569781053000686185666374833978403290525072598774001731350244744590772795701065129561898116576499984185920661271123665356132719193665474235596884239108030605882777868856122378222681140570519180321286976947154042272622411303981011302586225630859892731724640574658125478287115198406253847367979883768000812605395482952698689604477719478947595442185921480652637868335673233200662100621025061500895729605305665864693122952557361871523165300206070325660353095592778037767395360329231331322823610060006
n = 23297333791443053297363000786835336095252290818461950054542658327484507406594632785712767459958917943095522594228205423428207345128899745800927319147257669773812669542782839237744305180098276578841929496345963997512244219376701787616046235397139381894837435562662591060768476997333538748065294033141610502252325292801816812268934171361934399951548627267791401089703937389012586581080223313060159456238857080740699528666411303029934807011214953984169785844714159627792016926490955282697877141614638806397689306795328344778478692084754216753425842557818899467945102646776342655167655384224860504086083147841252232760941 c = 5418120301208378713115889465579964257871814114515046096090960159737859076829258516920361577853903925954198406843757303687557848302302200229295916902430205737843601806700738234756698575708612424928480440868739120075888681672062206529156566421276611107802917418993625029690627196813830326369874249777619239603300605876865967515719079797115910578653562787899019310139945904958024882417833736304894765433489476234575356755275147256577387022873348906900149634940747104513850154118106991137072643308620284663108283052245750945228995387803432128842152251549292698947407663643895853432650029352092018372834457054271102816934
n = 28873667904715682722987234293493200306976947898711255064125115933666968678742598858722431426218914462903521596341771131695619382266194233561677824357379805303885993804266436810606263022097900266975250431575654686915049693091467864820512767070713267708993899899011156106766178906700336111712803362113039613548672937053397875663144794018087017731949087794894903737682383916173267421403408140967713071026001874733487295007501068871044649170615709891451856792232315526696220161842742664778581287321318748202431466508948902745314372299799561625186955234673012098210919745879882268512656931714326782335211089576897310591491 c = 9919880463786836684987957979091527477471444996392375244075527841865509160181666543016317634963512437510324198702416322841377489417029572388474450075801462996825244657530286107428186354172836716502817609070590929769261932324275353289939302536440310628698349244872064005700644520223727670950787924296004296883032978941200883362653993351638545860207179022472492671256630427228461852668118035317021428675954874947015197745916918197725121122236369382741533983023462255913924692806249387449016629865823316402366017657844166919846683497851842388058283856219900535567427103603869955066193425501385255322097901531402103883869
n = 22324685947539653722499932469409607533065419157347813961958075689047690465266404384199483683908594787312445528159635527833904475801890381455653807265501217328757871352731293000303438205315816792663917579066674842307743845261771032363928568844669895768092515658328756229245837025261744260614860746997931503548788509983868038349720225305730985576293675269073709022350700836510054067641753713212999954307022524495885583361707378513742162566339010134354907863733205921845038918224463903789841881400814074587261720283879760122070901466517118265422863420376921536734845502100251460872499122236686832189549698020737176683019 c = 1491527050203294989882829248560395184804977277747126143103957219164624187528441047837351263580440686474767380464005540264627910126483129930668344095814547592115061057843470131498075060420395111008619027199037019925701236660166563068245683975787762804359520164701691690916482591026138582705558246869496162759780878437137960823000043988227303003876410503121370163303711603359430764539337597866862508451528158285103251810058741879687875218384160282506172706613359477657215420734816049393339593755489218588796607060261897905233453268671411610631047340459487937479511933450369462213795738933019001471803157607791738538467
n = 27646746423759020111007828653264027999257847645666129907789026054594393648800236117046769112762641778865620892443423100189619327585811384883515424918752749559627553637785037359639801125213256163008431942593727931931898199727552768626775618479833029101249692573716030706695702510982283555740851047022672485743432464647772882314215176114732257497240284164016914018689044557218920300262234652840632406067273375269301008409860193180822366735877288205783314326102263756503786736122321348320031950012144905869556204017430593656052867939493633163499580242224763404338807022510136217187779084917996171602737036564991036724299 c = 21991524128957260536043771284854920393105808126700128222125856775506885721971193109361315961129190814674647136464887087893990660894961612838205086401018885457667488911898654270235561980111174603323721280911197488286585269356849579263043456316319476495888696219344219866516861187654180509247881251251278919346267129904739277386289240394384575124331135655943513831009934023397457082184699737734388823763306805326430395849935770213817533387235486307008892410920611669932693018165569417445885810825749609388627231235840912644654685819620931663346297596334834498661789016450371769203650109994771872404185770230172934013971
n = 20545487405816928731738988374475012686827933709789784391855706835136270270933401203019329136937650878386117187776530639342572123237188053978622697282521473917978282830432161153221216194169879669541998840691383025487220850872075436064308499924958517979727954402965612196081404341651517326364041519250125036424822634354268773895465698920883439222996581226358595873993976604699830613932320720554130011671297944433515047180565484495191003887599891289037982010216357831078328159028953222056918189365840711588671093333013117454034313622855082795813122338562446223041211192277089225078324682108033843023903550172891959673551 c = 14227439188191029461250476692790539654619199888487319429114414557975376308688908028140817157205579804059783807641305577385724758530138514972962209062230576107406142402603484375626077345190883094097636019771377866339531511965136650567412363889183159616188449263752475328663245311059988337996047359263288837436305588848044572937759424466586870280512424336807064729894515840552404756879590698797046333336445465120445087587621743906624279621779634772378802959109714400516183718323267273824736540168545946444437586299214110424738159957388350785999348535171553569373088251552712391288365295267665691357719616011613628772175
n = 27359727711584277234897157724055852794019216845229798938655814269460046384353568138598567755392559653460949444557879120040796798142218939251844762461270251672399546774067275348291003962551964648742053215424620256999345448398805278592777049668281558312871773979931343097806878701114056030041506690476954254006592555275342579529625231194321357904668512121539514880704046969974898412095675082585315458267591016734924646294357666924293908418345508902112711075232047998775303603175363964055048589769318562104883659754974955561725694779754279606726358588862479198815999276839234952142017210593887371950645418417355912567987 c = 3788529784248255027081674540877016372807848222776887920453488878247137930578296797437647922494510483767651150492933356093288965943741570268943861987024276610712717409139946409513963043114463933146088430004237747163422802959250296602570649363016151581364006795894226599584708072582696996740518887606785460775851029814280359385763091078902301957226484620428513604630585131511167015763190591225884202772840456563643159507805711004113901417503751181050823638207803533111429510911616160851391754754434764819568054850823810901159821297849790005646102129354035735350124476838786661542089045509656910348676742844957008857457
n = 27545937603751737248785220891735796468973329738076209144079921449967292572349424539010502287564030116831261268197384650511043068738911429169730640135947800885987171539267214611907687570587001933829208655100828045651391618089603288456570334500533178695238407684702251252671579371018651675054368606282524673369983034682330578308769886456335818733827237294570476853673552685361689144261552895758266522393004116017849397346259119221063821663280935820440671825601452417487330105280889520007917979115568067161590058277418371493228631232457972494285014767469893647892888681433965857496916110704944758070268626897045014782837 c = 14069112970608895732417039977542732665796601893762401500878786871680645798754783315693511261740059725171342404186571066972546332813667711135661176659424619936101038903439144294886379322591635766682645179888058617577572409307484708171144488708410543462972008179994594087473935638026612679389759756811490524127195628741262871304427908481214992471182859308828778119005750928935764927967212343526503410515793717201360360437981322576798056276657140363332700714732224848346808963992302409037706094588964170239521193589470070839790404597252990818583717869140229811712295005710540476356743378906642267045723633874011649259842
n = 25746162075697911560263181791216433062574178572424600336856278176112733054431463253903433128232709054141607100891177804285813783247735063753406524678030561284491481221681954564804141454666928657549670266775659862814924386584148785453647316864935942772919140563506305666207816897601862713092809234429096584753263707828899780979223118181009293655563146526792388913462557306433664296966331469906428665127438829399703002867800269947855869262036714256550075520193125987011945192273531732276641728008406855871598678936585324782438668746810516660152018244253008092470066555687277138937298747951929576231036251316270602513451 c = 17344284860275489477491525819922855326792275128719709401292545608122859829827462088390044612234967551682879954301458425842831995513832410355328065562098763660326163262033200347338773439095709944202252494552172589503915965931524326523663289777583152664722241920800537867331030623906674081852296232306336271542832728410803631170229642717524942332390842467035143631504401140727083270732464237443915263865880580308776111219718961746378842924644142127243573824972533819479079381023103585862099063382129757560124074676150622288706094110075567706403442920696472627797607697962873026112240527498308535903232663939028587036724
n = 23288486934117120315036919418588136227028485494137930196323715336208849327833965693894670567217971727921243839129969128783853015760155446770590696037582684845937132790047363216362087277861336964760890214059732779383020349204803205725870225429985939570141508220041286857810048164696707018663758416807708910671477407366098883430811861933014973409390179948577712579749352299440310543689035651465399867908428885541237776143404376333442949397063249223702355051571790555151203866821867908531733788784978667478707672984539512431549558672467752712004519300318999208102076732501412589104904734983789895358753664077486894529499 c = 10738254418114076548071448844964046468141621740603214384986354189105236977071001429271560636428075970459890958274941762528116445171161040040833357876134689749846940052619392750394683504816081193432350669452446113285638982551762586656329109007214019944975816434827768882704630460001209452239162896576191876324662333153835533956600295255158377025198426950944040643235430211011063586032467724329735785947372051759042138171054165854842472990583800899984893232549092766400510300083585513014171220423103452292891496141806956300396540682381668367564569427813092064053993103537635994311143010708814851867239706492577203899024
n = 19591441383958529435598729113936346657001352578357909347657257239777540424811749817783061233235817916560689138344041497732749011519736303038986277394036718790971374656832741054547056417771501234494768509780369075443550907847298246275717420562375114406055733620258777905222169702036494045086017381084272496162770259955811174440490126514747876661317750649488774992348005044389081101686016446219264069971370646319546429782904810063020324704138495608761532563310699753322444871060383693044481932265801505819646998535192083036872551683405766123968487907648980900712118052346174533513978009131757167547595857552370586353973 c = 3834917098887202931981968704659119341624432294759361919553937551053499607440333234018189141970246302299385742548278589896033282894981200353270637127213483172182529890495903425649116755901631101665876301799865612717750360089085179142750664603454193642053016384714515855868368723508922271767190285521137785688075622832924829248362774476456232826885801046969384519549385428259591566716890844604696258783639390854153039329480726205147199247183621535172450825979047132495439603840806501254997167051142427157381799890725323765558803808030109468048682252028720241357478614704610089120810367192414352034177484688502364022887
n = 19254242571588430171308191757871261075358521158624745702744057556054652332495961196795369630484782930292003238730267396462491733557715379956969694238267908985251699834707734400775311452868924330866502429576951934279223234676654749272932769107390976321208605516299532560054081301829440688796904635446986081691156842271268059970762004259219036753174909942343204432795076377432107630203621754552804124408792358220071862369443201584155711893388877350138023238624566616551246804054720492816226651467017802504094070614892556444425915920269485861799532473383304622064493223627552558344088839860178294589481899206318863310603 c = 6790553533991297205804561991225493105312398825187682250780197510784765226429663284220400480563039341938599783346724051076211265663468643826430109013245014035811178295081939958687087477312867720289964506097819762095244479129359998867671811819738196687884696680463458661374310994610760009474264115750204920875527434486437536623589684519411519100170291423367424938566820315486507444202022408003879118465761273916755290898112991525546114191064022991329724370064632569903856189236177894007766690782630247443895358893983735822824243487181851098787271270256780891094405121947631088729917398317652320497765101790132679171889
n = 26809700251171279102974962949184411136459372267620535198421449833298448092580497485301953796619185339316064387798092220298630428207556482805739803420279056191194360049651767412572609187680508073074653291350998253938793269214230457117194434853888765303403385824786231859450351212449404870776320297419712486574804794325602760347306432927281716160368830187944940128907971027838510079519466846176106565164730963988892400240063089397720414921398936399927948235195085202171264728816184532651138221862240969655185596628285814057082448321749567943946273776184657698104465062749244327092588237927996419620170254423837876806659 c = 386213556608434013769864727123879412041991271528990528548507451210692618986652870424632219424601677524265011043146748309774067894985069288067952546139416819404039688454756044862784630882833496090822568580572859029800646671301748901528132153712913301179254879877441322285914544974519727307311002330350534857867516466612474769753577858660075830592891403551867246057397839688329172530177187042229028685862036140779065771061933528137423019407311473581832405899089709251747002788032002094495379614686544672969073249309703482556386024622814731015767810042969813752548617464974915714425595351940266077021672409858645427346
n = [n0,n1,n2,n3,n4,n5,n6,n7,n8,n9,n10,n11,n12,n13,n14,n15,n16,n17,n18,n19] c = [c0,c1,c2,c3,c4,c5,c6,c7,c8,c9,c10,c11,c12,c13,c14,c15,c16,c17,c18,c19]
for i inrange(len(n)): for j inrange(len(n)): if (i!=j): t = gmpy2.gcd(n[i],n[j]) if t != 1: p = t q = n[i] // p d = gmpy2.invert(e,(p-1)*(q-1)) m = pow(c[i],d,n[i]) print(long_to_bytes(m)) #flag{abdcbe5fd94e23b3de429223ab9c2fdf}
from Crypto.Util.number import long_to_bytes import gmpy2
defGet_Mi(m_list,m): #求衍数 M_list = [] for mi in m_list: M_list.append(m // mi) return M_list
defGet_resMi(M_list,m_list): #求乘率 resM_list = [] for i inrange(len(M_list)): resM_list.append(gmpy2.invert(M_list[i],m_list[i])) return resM_list
defGet_result(a_list): M_list = Get_Mi(m_list,m) resM_list = Get_resMi(M_list,m_list) result = 0 for i inrange(len(M_list)): result += M_list[i]*resM_list[i]*a_list[i] result %= m return result
defcontinuedFra(x, y): """计算连分数 :param x: 分子 :param y: 分母 :return: 连分数列表 """ cf = [] while y: cf.append(x // y) x, y = y, x % y return cf
defgradualFra(cf): """计算传入列表最后的渐进分数 :param cf: 连分数列表 :return: 该列表最后的渐近分数 """ numerator = 0 denominator = 1 for x in cf[::-1]: # 这里的渐进分数分子分母要分开 numerator, denominator = denominator, x * denominator + numerator return numerator, denominator
defsolve_pq(a, b, c): """使用韦达定理解出pq,x^2−(p+q)∗x+pq=0 :param a:x^2的系数 :param b:x的系数 :param c:pq :return:p,q """ par = gmpy2.isqrt(b * b - 4 * a * c) return (-b + par) // (2 * a), (-b - par) // (2 * a)
defgetGradualFra(cf): """计算列表所有的渐近分数 :param cf: 连分数列表 :return: 该列表所有的渐近分数 """ gf = [] for i inrange(1, len(cf) + 1): gf.append(gradualFra(cf[:i])) return gf
defwienerAttack(e, n): """ :param e: :param n: :return: 私钥d """ cf = continuedFra(e, n) gf = getGradualFra(cf) for d, k in gf: if k == 0: continue if (e * d - 1) % k != 0: continue phi = (e * d - 1) // k p, q = solve_pq(1, n - phi + 1, n) if p * q == n: return d
n = 113881698992379349039968368927979997900777221951663104697020683691495129639829918739755194174063944178083527489820939138302751895652076620380510013941997706327553964127612610209509889011613768847759318892303231846117914554931459295347697888260576901354448014917692680573408654658384481284699735788978230690197 e = 39068960413447607023613035707248214114819409621234801785480423979473767995171860917209502861408393208940683687475760366491413173744775811644295874981290403938714121977201901942939425294427737703229098649131737380098596135730392902019429964095866394165971291108245774407908011073271822915371753470010435225545 c = 32897925577913728659288168937025744709859960639901500169867896018406263110205704273203287172003057450591000201857719871686024077615520906540631374442504017489026298422189715372129838501090730593164075113452055617571409044743698645392909829425374093273187125709095368164744188182156849031225036001381531504057
d = wienerAttack(e, n) print(d) m = pow(c, d, n) print(libnum.n2s(m).decode())
defmy_permutations(g, n): sub = [] res = [] defdfs(s, prev): iflen(s) == n: res.append(s[::]) for i in g: if i in s or i < prev: continue s.append(i) dfs(s, max(prev, i)) s.remove(i) dfs(sub, 0) return res
classX_Complex(object): def__init__(self, exp): i = 0 s = '%s' % exp while i < len(s): if isdigit(s[i]): num = 0 while i < len(s) and isdigit(s[i]): num = num*10 + int(s[i]) i += 1 if i >= len(s): self.b = num elif s[i] == '*': self.a = num i += 2 elif s[i] == '/': i += 1 r = 0 while i < len(s) and isdigit(s[i]): r = r*10 + int(s[i]) i += 1 self.b = num/r else: i += 1 ifnothasattr(self, 'a'): self.a = 1 ifnothasattr(self, 'b'): self.b = 0
defR(e, sn): # min u max v ret = X3NNY(1, 1) n = max(e) nn = len(e) l = set(i for i inrange(1, n+1)) debug = '' u, v = 0, 0 for i in e: if i == 1: ret *= W(1) debug += 'W(%d)' % i nn -= 1 l.remove(1) u += 1 elif i > min(l) andlen(l) >= 2*nn: ret *= G(min(l), i) nn -= 1 debug += 'G(%d, %d)' % (min(l), i) l.remove(min(l)) l.remove(i) v += 1 else: ret *= W(i) l.remove(i) debug += 'W(%d)' % i nn -= 1 u += 1 # print(debug, end = ' ') return ret, u/2 + (sn - v) * a
defH(n): if n == 0: return [0] if n == 2: return [(), (1,), (2,), (1, 2)] ret = [] for i inrange(3, n+1): ret.append((i,)) for j inrange(1, i): for k in my_permutations(range(1, i), j): ret.append(tuple(k + [i])) return H(2) + ret defCC(exp, n): cols = [0for i inrange(1<<n)] # split exp texps = ('%s' % exp.exp1.expand()).strip().split(' - ') ops = [] exps = [] for i inrange(len(texps)): if texps[i].find(' + ') != -1: tmp = texps[i].split(' + ') ops.append(0) exps.append(tmp[0]) for i inrange(1, len(tmp)): ops.append(1) exps.append(tmp[i]) else: ops.append(0) exps.append(texps[i]) if exps[0][0] == '-': for i inrange(len(exps)): ops[i] = 1-ops[i] exps[0] = exps[0][1:] else: ops[0] = 1 # find e and N l = [] for i inrange(len(exps)): tmp = 1if ops[i] else -1 en = [] j = 0 while j < len(exps[i]): if exps[i][j] == 'e': num = 0 j += 1 while isdigit(exps[i][j]): num = num*10 + int(exps[i][j]) j += 1 tmp *= eval('e%d' % num) en.append(num) elif exps[i][j] == 'N': j += 1 num = 0 if exps[i][j] == '^': j += 1 while isdigit(exps[i][j]): num = num*10 + int(exps[i][j]) j += 1 if num == 0: num = 1 tmp *= eval('N**%d' % num) else: j += 1 if tmp == 1or tmp == -1: l.append((0, ())) else: l.append((tmp, tuple(sorted(en)))) # construct h mp = H(n) for val, en in l: cols[mp.index(en)] = val # print(cols) return cols
defEWA(n, elist, NN, alpha): mp = H(n) var('a') S = [X_Complex(n*a)] cols = [[1if i == 0else0for i inrange(2^n)]] for i in mp[1:]: eL, s = R(i, n) cols.append(CC(eL, n)) S.append(X_Complex(s)) alphaA,alphaB = 0, 0 for i in S: alphaA = max(i.a, alphaA) alphaB = max(i.b, alphaB) # print(alphaA, alphaB) D = [] for i inrange(len(S)): # print((alphaA-S[i].a), (alphaB - S[i].b)) D.append( int(NN^((alphaA-S[i].a)*alpha + (alphaB - S[i].b))) ) kw = {'N': NN} for i inrange(len(elist)): kw['e%d' % (i+1)] = elist[i]
B = Matrix(ZZ, Matrix(cols).T(**kw)) * diagonal_matrix(ZZ, D) L = B.LLL(0.5) v = Matrix(ZZ, L[0]) x = v * B**(-1) phi = int(x[0,1]/x[0,0]*elist[0]) return phi
flag = "flag{" + str(uuid.uuid4()) + "}" print(flag) m = libnum.s2n(flag) p = libnum.generate_prime(1024) q = libnum.generate_prime(1024) e = 65537 n = p * q phi = (p - 1) * (q - 1) d = gmpy2.invert(e, phi) print("d=",d) dp = d % (p - 1) c = pow(m, e, n) print("n=", n) print("e=", e) print("c=", c) print("dp=", dp)
exp.py
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
from Crypto.Util.number import long_to_bytes import gmpy2
n = 17954000555185130679232377513216924086370205717680723426279833171815673097846434355592747466782173529597978954062272371758852339605432963940809244445748900431763988392120156128524694217746804744076348205536430811607694098089294013508111154514184079159181563040241302764793111632189829652065825442796716027051750043654503172469553222784393034067341575558782690547449884992414106322578261286526556856377419622164651917718772498388922129465042492616904419638034789576380038341882418547113136903862482397767904921157094396562770484669239932933837196899640811033424030302285885080504355934919967693498648701839252087380477 c = 1808490145328726635638705291306162339133116115672167390186563455429486046847680827004544020052978814401354685508506555963361065725012891622174617670820924531959433674273579973778657669162210657120785539629874456938159379512635932223403818177582242406964621317531188027900758868453176575753681627336133481701182056262584118645398172089436811174776978418919803975809158758707062473122656821152108292060156091196577573172937093806159669057467094718771367509856968694209472630329096814023864642219783061245777457366202879949123915168571990229277326042767587009623951348541055835347386485900505749475571895673653225741649 dp =114993440308125678369350484461242628405806013372930792337329972720600942891053460367721272956155528263465552939386621554396883112994907299126303463171544968629898544811159986442249990975328659373544491636958873255689808151391606942912468529923159009459712396428051292828093059494024457367637991626193487727331 e =65537
for i inrange(1,e): t = (dp * e - 1) % i #这是p-1前面的系数 if t == 0: p = (dp * e - 1) // i + 1 if n % p == 0: q = n // p d = gmpy2.invert(e,(p-1)*(q-1)) print(long_to_bytes(pow(c,d,n)))
例题2 e很大
task.py
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
import gmpy2 import libnum import uuid
flag = "flag{" + str(uuid.uuid4()) + "}" m = libnum.s2n(flag) p = libnum.generate_prime(1024) q = libnum.generate_prime(1024) e = libnum.generate_prime(128) n = p * q phi = (p - 1) * (q - 1) d = gmpy2.invert(e, phi)
dp = d % (p - 1) c = pow(m, e, n) print("n=", n) print("e=", e) print("c=", c) print("dp=", dp)
在e很大的情况下,我们爆破$(0,e)$的值就显得不现实。需要用其他方法 $$ \because d_p \times e = k(p-1)+1 $$
$$ \therefore dp ×e \equiv 1 \mod (p-1) $$
取一个与$p$互素的常数$a$,则有
$$ a^{d_p\times e} \equiv a^{k(p-1)+1} \equiv a \mod p $$
$$ \therefore a^{dp×e}-a =kp $$
然后与n求公因数即可得到p
exp.py
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
from Crypto.Util.number import getPrime,long_to_bytes import gmpy2
from Crypto.Util.number import * import gmpy2 import itertools
defsmall_roots(f, bounds, m=1, d=None): ifnot d: d = f.degree() print(d) R = f.base_ring() N = R.cardinality() f /= f.coefficients().pop(0) f = f.change_ring(ZZ) G = Sequence([], f.parent()) for i inrange(m + 1): base = N ^ (m - i) * f ^ i for shifts in itertools.product(range(d), repeat=f.nvariables()): g = base * prod(map(power, f.variables(), shifts)) G.append(g) B, monomials = G.coefficient_matrix() monomials = vector(monomials) factors = [monomial(*bounds) for monomial in monomials] for i, factor inenumerate(factors): B.rescale_col(i, factor) B = B.dense_matrix().LLL() B = B.change_ring(QQ) for i, factor inenumerate(factors): B.rescale_col(i, 1 / factor) H = Sequence([], f.parent().change_ring(QQ)) for h infilter(None, B * monomials): H.append(h) I = H.ideal() if I.dimension() == -1: H.pop() elif I.dimension() == 0: roots = [] for root in I.variety(ring=ZZ): root = tuple(R(root[var]) for var in f.variables()) roots.append(root) return roots return []
n = 108867023585283899312601516631596145998654767437612286040742902945694826711187570537876759789643259431350352590412655898964386234903475482280911808566497936037152171435317938413515356868240854632004961172899360272761406519077380255802700944002126599829184693692273637230349297388495886988988512631044494610227 c = 55610391226438079690691299914193010897347055835338032942001645697966587672596937470425142446679815934940962159432814479063990621696064239924347523289515556844359094065042974221093712989000153444928594999529082105262409273370242062803004814801742763253605838374098344711160380314529928211369000469059015996052 e = 14257237624892167181 leak = 2451130625204471881762267484243564297625381377098677997721378436579042927693972537775392209546509688501306219327699327137859174235486735043842710630825984
R.<x,y> = PolynomialRing(Zmod(n)) f = e * (leak + x) + (y - 1) res = small_roots(f,(2^64,2^64),m=1,d=3) for root in res: dp_low = root[0] dp = leak + dp_low tmp = pow(2,e*dp,n) - 2 p = gmpy2.gcd(tmp,n) q = n // p d = inverse(e,(p-1)*(q-1)) m = pow(c,d,n) print(long_to_bytes(m))
flag = "flag{" + str(uuid.uuid4()) + "}" print(flag) m = libnum.s2n(flag) p = libnum.generate_prime(512) n = p ** 5 e = 65537 c = pow(m, e, n) print("n=", n) print("e=", e) print("c=", c)
本题考查$n = p^r$
exp.py
1 2 3 4 5 6 7 8 9 10 11
from Crypto.Util.number import * import gmpy2
n = 109671394618534156590716540772306636060550711465455829526382945168271125218007503161807386153286648328529071790130095763349089936429151343426469415497138306284842512691195220650548494501337831207724397925027651025644976364368511262187227825083865690186591571250267479440100917127211656877566179258870510690665025580200477574123634259670039152125607834855408269848826938902407472374892693266119859709658788565014195766992713646832624001067898323913639712284673673557898135411273837250194079399384826384835709060797351332323930309379071015140548478132323474993964925055399350661600068568602468295748573856804293659942047543032878436316918991716636681116631322082919386178460096115355963882313682994343822128626370850455024905542367255179074441679461101331332093019368492643 e = 65537 c = 83166081100602571613112201467626632459949037182633475449066025299006894059443612622701975752551708249083077180755342065457682925338233793688583913228361068561515321097016501900442865692643652803949920987493441500744743553498018003210308290969303190355756775977367324120441564693220728163622472865572357639056734898022442794130514936425334924283145153496702507951466618177405870656868713199816223765264228006032228439676574053839549440372521050502986043855511540855864034336902304414848547480112182226920285820386643015671106933140105835060319823245206934565859078021518312305243997612804935774414840491355098017977514736057368000596388974956265042651277403519473262257945986199408278855335170546242641727930526697102351648388874227840119205560199015181257296591985205818 p = 10186351850605898834333098258639828910824016865517013383611935945131883947448223014077315468253377357594775340263769153442019216205089695821439736926082483
phi = p**5-p**4 d = gmpy2.invert(e,phi) print(long_to_bytes(pow(c,d,n)))
例题2
task.py
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
import gmpy2 import libnum import uuid
flag = "flag{" + str(uuid.uuid4()) + "}" m = libnum.s2n(flag) p = libnum.generate_prime(512) q = libnum.generate_prime(512) n = p ** 3 * q e = 65537 c = pow(m, e, n) print("q=", q) print("n=", n) print("e=", e) print("c=", c)
$\because n = p^{3}×q$
$\therefore \phi(n) = (p^{3}-p^{2})×(q-1)$
exp.py
1 2 3 4 5 6 7 8 9 10 11 12
from Crypto.Util.number import long_to_bytes import gmpy2
q = 13345672330679418443866848695749753384841350112452462690350565885192764753702964893062035116023096943358384379827500462723016224486435032522188166109529147 n = 4663711063632671446966617442890809468548735750386480905820144168615122369358088158709822723959108989276525102755551604204514586528122441075489492157644479194671784485228731421500391142158401889177506319977349707503678947872777602384171260874359045585814189677748712566088220734735479518470883541166059233676170283938881683675790979128058243582825012415020019043126740915522571217495119060031729061070896580899732991209113679151755713858497630999746612658308778711613697038750661479517187094033129979714688161348844542070263109259258937863241431480105798790363889436471998002323269704182369356300287043940743500087239 e = 65537 c = 4050303218893912343776312253598257474375000778822229482734626960955864773175090306426885201033332266573903303684635688485414725284644108123459136702775991157244389086147955395682206311752151842740679445903864544823592773331496589661187968392779340028173948172003460012051289357755574536619241969492822938688821287700132262703677149526846356206143053559703859606442209340834979412336031660590507709503830013770022485005101363701272279629510056964018618212014677531338026866748075406283893942248599825641124694672878533987994699411744521757385858889763503705242690212615083634186373933214686193717950163215308138805348
p = n // q phi = (p**3-p**2)*(q-1) d = gmpy2.invert(e,phi) print(long_to_bytes(pow(c,d,n)))
flag = "flag{" + str(uuid.uuid4()) + "}" m = libnum.s2n(flag) p = libnum.generate_prime(512) q = gmpy2.next_prime(p) r = libnum.generate_prime(512) n = p * q * r e = 65537 c = pow(m, e, n) print("r=", r) print("n=", n) print("e=", e) print("c=", c)
r = 12328943069972158868300333965019293732240349172933398867374450193780676916633106046545397891902123683693837126404908611670219604587587151306224914062663729 n = 928445951911850156618541782850215900925329423880533465612155142015978599609287623859912813317551629221695490535012732781489396534420011145723987610606038091488823086647363964394753700158320900867101659445170118179077194271099520502633316318889163873291574934282498061117736456183503867870294570083013883365868242889035609602940685335912371326827533418614992221705810476710807373254363162373986374486325350746366851935451369892949745302442034805629514003196071631 e = 65537 c = 327716655224470059950709685055600963837116578216483343492948888372401723689223347212508532985781828794786448842515029515358422017875793926582832247025212149474404973170422295165602666360784347416812528617973764432916955654602356835327769633635513894485943553309743509322858937973710628023758816806471875016815994664897320150855163109437521642800230902661034555151514311149333258071668655344069451897282357234220538922127548822361859943829665459953651351620958628
$$ \because n = p\times q \times r $$
$$ \therefore \phi(n)=(p-1)×(q-1)×(r-1) $$
exp.py
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
from Crypto.Util.number import long_to_bytes import gmpy2
r = 12328943069972158868300333965019293732240349172933398867374450193780676916633106046545397891902123683693837126404908611670219604587587151306224914062663729 n = 928445951911850156618541782850215900925329423880533465612155142015978599609287623859912813317551629221695490535012732781489396534420011145723987610606038091488823086647363964394753700158320900867101659445170118179077194271099520502633316318889163873291574934282498061117736456183503867870294570083013883365868242889035609602940685335912371326827533418614992221705810476710807373254363162373986374486325350746366851935451369892949745302442034805629514003196071631 e = 65537 c = 327716655224470059950709685055600963837116578216483343492948888372401723689223347212508532985781828794786448842515029515358422017875793926582832247025212149474404973170422295165602666360784347416812528617973764432916955654602356835327769633635513894485943553309743509322858937973710628023758816806471875016815994664897320150855163109437521642800230902661034555151514311149333258071668655344069451897282357234220538922127548822361859943829665459953651351620958628
t = gmpy2.iroot(n//r,2)[0] p = gmpy2.next_prime(t) q = n // p // r
phi = (p-1)*(q-1)*(r-1) d = gmpy2.invert(e,phi) print(long_to_bytes(pow(c,d,n)))