2024beginCTF-Crypto部分wp
pad
题目描述
某同学在学习RSA得时候,觉得仅仅靠着比特位得RSA是不安全的,于是参考了部分资料后,灵光乍现
task:
import random, math
from Crypto.Util.number import *
from flag import flag
flag=flag[:64]
assert len(flag) == 64
class RSA():
def __init__(self, m: int):
self.p, self.q, self.e, self.m = getPrime(512), getPrime(512), getRandomRange(1,8), m
self.n = self.p * self.q
def Publickey(self):
return (self.n, self.e,self.c)
def Encrypt(self):
pad = PAD(m=self.m, e=0)
pad.PAD()
self.c = (pad.e,pow(pad.M, self.e, self.n))
class PAD():
def __init__(self, m: int, e):
self.e, self.m, self.mbits = e, m, m.bit_length()
if e == 0:
self.e = getRandomRange(2, 7)
def PAD(self):
self.M = pow(self.e, self.mbits) + pow(self.m, self.e)
GIFT = bytes_to_long(flag)
with open("GIFT.txt", "w") as f:
for i in range(40):
rsa = RSA(m=GIFT)
rsa.Encrypt()
f.write(str(rsa.Publickey()) + "\n")
GIFT:
(139329448802200365204643384874650838375239731051279501742482436021687824615856259435793266692888609317385849433612898172371273648308592637149501006357403743064987953526585824190508402758679436987099618136010109850018989047771175507549657750612877669584571828107592205920344667936941485585453799033655630372459, 2, (5, 8707388950912021842766566951233081141718992288274320731385784912290619588460328801184727100044056285361852901660810699476512136373858134747632397830290649655491799664610059262639023198488867144223014477308987004448445138689878292055673036415945113882551653334624324979393738007883635365074732304270369302694))
(74261058069979384646242460106138838646214987200972209574962002693100589594088615664635937326989768595850003214680089421604785240889166659793192736019726821909673133045566922433651975093325938207849240998879088237221423097706362933444212667937950496966368148198884630172120004228571714485429745508318483263693, 7, (4, 12606475410139384028606121530509800888961339059001547830652223606152191625234314909699904350064011927410469551809919500380831042251936324854873408781555173721088413282216896930299520672255675921153143008989807592351608473708691456511071012842625101826442899543748066768155158771764882536269020497008006587202))
(102370765897478217412094609970060540003973885799734673503337215387553738901423096493266801215750419944920243844601143420143081218881795264146001191490072712627960260821697854080037201586274637829737392065645053661247941244439013085232000932182987207724201238408254187196757319372473098931710334706996175155837, 5, (3, 68218754205568076255358435491331738959297793043515462001216055039362505491240170703064555213098072842840492325193331256534426670109466958454719439823776361626854946223115394761661586751267808635944279764770452643926307518829348049305370945456462962397744261064012240851949738376144290768633557483226708214999))
(54431684186957192730506300438748169224388774505651232093234714552457837284504774629979775880103634154567410423015997745317800125380030769864290423507529695713966782839865919907971475791296070929225744873583508754240957320343431920100231870305112289951300268413129912726914051048306311483524023350804339296313, 4, (3, 46878874653006920939051134477619740870655147778074332928263094091749871450979474874656304999300200726499281830798834836124082043309193044537146788469327672134938915475224341483351020129437651349819447222749854081578904834843633432450052425776214277700529711125228436079840174439272510878115043621061624428504))
(96684242430324194678958447569932022640449349632666282189783673735691440136267227869719376999373793585796743310141824853472442650254082562374151845588167789515836464719144849274329281720378577429843040472234115886659443286173798086528181859405894015423282069930491007899985951757313046135398735616561255981921, 1, (6, 40316373591615621466182035849374268170000050692485463995791507365022759310949121704411152966140347312227589970395614672592555330421324045697305583824391373372729675681613833261737136372346545503837478481267251209611704028357308553942292755209813342142217784026320008579991433152370269191316426345707368886335))
(118605111132319762282137647473841627186711650903984626034572907959670044412004726397391156233170420162835354881825058467891657865538176707527342780038966703465225959245156387142243996324146943624757462270511428236284769144977408275645435898732646900339854974294633616658245290087926840638425764919520943271517, 5, (5, 38989790603878521285254217996944207153752017687346981506461668695054283785100683043185048855612267434675541740423399643295248996143928711172320103600647104145891348376911467949369856149075087830375851303089881868419887126330052137638091107807715290732169205892933117956938965853506939525055114296410995279136))
(157162217487046234445152380413862750663608362850823519234744343936199439788069176680328786509388482190959419537181688477016735505032503326111603399627845457770102374153119664813051263425159846325708856915369284346269559820930970735780507890810638647869205879782845489959650156267939184187947663630829158907547, 6, (6, 22600800675391040049508186599867874877875580677344971071125444610328765720244780173443298051806320525210383038805950927586173155262639854598618957695556678104678152113457694494410254356263140221933082684923391823777341958485972425825676962965725950525615481990017197915023620261471377877979119807336832945988))
(82012627201407056460036989561339698637332477776118488454189460673791868792602099260011966840945514952527593036654845298634483520064328323144649640235623594073128015052282653512132155124791049464144246468526673438023854309851665011532401790386519200823848405753086385633127877779112778210104214577688025275439, 3, (4, 26319175915814016367985135793972308222072459276961500817724619425565671037688402043258597047127661752472261748350714612909325520193252679379021608242184759023118207803874541918013203659802684335657673484176907865420655242295344373730254397697266286958607352825222812615173911991638934457500756493762159923455))
(143052640286854243786790211445854242617077295173239564647012161558851966031434997450170844340348362070059825173952898656345884754887972389093444629273662387027168411880533711555873420112712342698509515828033026803874478635442656750693401027595298495577448067393868347002554138007369698770897505993264047580303, 6, (3, 142778947488233564454786801921070707334097189885016357069214903710584303199510284820527435557167225494338362685754433346849686947448993958892223783853365466652543810214080717759820647020505053465556438791591682755147335461798798128104351531916490944946012009473770606561103619889748998993983958623247620730111))
(103304091017820043026362882509604085586504908948516523601573010863770660568559389277014410445640796730297053921142565742486954075294578119528318645927782417743426620444476648266902253451677644490677338593049833406161585606662592075509171478935992551399329224886991154495436983913164148868188173295884063524151, 4, (3, 66783495013092592043648088278334433908427212438480527512595488565561060904843871123410058201568445880387512840100553265930497975274450118839659652585082045245723965130095200368316667116250219370203352605921132713173382343656166004417883537932865972922654962868997139450972948292756080058096045777145659805790))
(48771716300230837970084331681829773883457165537932703132363505741027743847443906107696536603517387444676004009323689033384448222536259598221796701708337817836161632306549521784772555346560766983980810640911591590165745858546582276775283310185382587388028278911751699193259517106445761279228434925242445275961, 2, (4, 6749963676095373926138002299239321829877620514076871917790658048621512204388295714478191035065356799263464442530114439109963533792659187989966583174773084719952048156065197043002299900015968411250851993177496764544421730773505236445716427394089348364744703967999348506404277800026050779517523515879607180926))
(77975934986443674925142370755647311455152001387661359356443338770586496504616711078334544398807547504046794422570567457387671982153914628991417498276028838215228267279351232581050948930031045109990798194870640902230437508783940326630721958499884855252531676637574898827595127567993415100892742629101576883851, 4, (3, 1873289447130995944738969658719449872514747388039541071942817563906790650450541266143942575696570827600970685202534246135231793051971609136228361030179201613739377712500977625361133494693724700214134605781433667068193398641088331621638593201069127225646856400233184365145486717595323292715968708251943499213))
(68573803382438704650861056867082883216638898753767871305110285276051418994863496435913579530495617361317410869146067196056642024567780011217745787011680353733128770009895900413689096643579242273128608944276904503348760719687850859110460795988616231955958478856241515694197313841948610421805086503023549047051, 4, (2, 13341528847520700037117774963374932962681045239551830393171366620452808140866865034393136470083097776975919772331873902858069542241072488796977682763101009994357063154819356925991624087046657985144832866642845538592674651348846675150701162124745082337694526850845767485999093232102485750639839756010130266360))
(83816545119110014232282234345373163875279069996491512281511055759136679147632415212902455395380173346580926317795815266315804899277714802657827273986573410029293594811555395620841650201025354748632513355223635539403395131786817226609461643499971303968671758299621024055603889054250768643982721582834752815807, 3, (2, 82797269854692809418108201827371627062834651644844486525974230792238334196167484598616757323611480425034420291790709649820426671902478299865730904069344331236745822614105711843199634122769159871765900320147923658774310523769502601131849741780221544160393131096244058736125450841469193845266898225223404669392))
(100132685826497449447678593572184780148341328022510945043566572208008037757813963668684268303234968016128801804116465249220539151977076729026489623573829107107579500008487800026760245718834647872821982631931905593841331516716389959434487216645429254786992414233194506076593680426980389055511674812267142956861, 3, (4, 60966274681111243041878972277773136254322648343705841809203272448520769525889090572825058491856369138681668536306759661818110900830108164291836188241744378637777832823901453632051900154608961989577003892844586733314274203891736904795656786190783491495680773545800255353287023524189958462644082904204363497315))
(66774173046867106978564392807774188269534394449840296405910777832911685835495393323180077968974708562688760938291099725499683301622430513476820311716679706861971145656513111211588447567157066572973454278697174902701179905913830295650932313907414913975102061018460218742766703308850479537206120634422169081427, 1, (3, 9947849848628394040911390578513458759307204504154925933108800760285314551328261356068666838417233200825260136676377138010240930409364211389785744843760837346711809102522170726809372344662827652364290577950806740613036994404769812936985438300111324782034383266110793322048638372472511933383991308991836303085))
(131789085200671396463290845501819070666477925486735061147545292615108392861868406011434425213310557094538274536122724958084009346160369548992661788581244537160859249932666055953953735968747780105361104711883725787311705991031888315377393172242146738786048640742807971341193747739454235320453301337100523275371, 6, (3, 102478917662803277056725083665824857223578307849960395832910990004320616149918757967918639090569335203242588936181257339660736012685107163815591877947126361703702799574691460257625802899357270997917659907999007098461130469562889203631743201878826535796083078682912623026726872352011352374227771702040215286887))
(142645316171905970655865246770896501751416713320396838746605045027324337914881190589389381571295760864773267840317674562190411977111651213017704826651252035402558772071286082165193732594114661841746685533799286096833149679922677645640061333063838585930696124181718921801403214067222710835766569617376122396003, 3, (5, 80965465159712789997446805451976020946560456500924444635080125327224756977399942348225803989037122541142707974125761581528112615956090670627938951721934704132226392563571786133466747486067373906391853265086021632282677467719862727947997490596202655350569102050586071431900986599007796832710385865311072125043))
(75687829588098401896897837586334591533855549374367866596685693025886532298999960263570124596429881741755295474110093990874474838997866594245473345925519838773200684677845168868040223509954629297892445717009631665426163593257867706587083061668921585455510135822646248277046830976018358499005064325157211280903, 3, (6, 73611520995000187457911435042939226182170542169101788180417584999395642870737166547569295524178087570605696969943951113429183640659334646141963965065765033314049588053913620607309580317238520309909294011004229967214430631675647813076553562386768535659181106992785723105572968921648194333746834708358239944739))
(119038957851463065679653115266137995260994640621190521090636379832845645914963274121238049126245943835773531769586966645417239321272968622323134883764627076101176850143708080392909193505699121506190368958212935526111168417671026716818361108117912197214218143004306208957360743297359764756490199293336981817761, 4, (2, 41068994750374018152771102461566723009272404600840527762434534125638626087851971238375806851330596733034340262270652296558005231982415051786977384681758105374314735298990426766578444788121316114776883224542465418359071022516499975959708881401559330833936661596649713917304203216766586121301774177538501422747))
(95878181894436684758571463504665784652006875861011327393591227131343863366827114266773103418149049983792756044380856062533066710395070130792338532700043145464743568325282774785292819336943208908234150877994539578827970158469003156092565746890718669558222683472016255014210486192806736484268081630930273800397, 5, (4, 7115738889540479961095821577185061150120180444264038031226044550996413320208176967498632464042430694038617238758503422365362977879028585676345778115404293585081724942343264703728497922177666148025542202526443189396700332218044881527648894576261506783472128543539590938903631173389099488452966401075562815685))
(135208319497092736323375440874158574300507698922520948651663471688372715441542933126646720102231626718228648170728079431419619013430534800140396239184056257702689024903709187488527193359584554393036158260518109091724262232510413541501190332556218128353329455432989940399791514006900006184835648677326055727479, 5, (5, 62811170570201820584138091477600497403576797064833857190712579686007215684520915867410332445854175926716680557677366796224399102151198278784755325043521981011297101982559559658863609348878676866161301968275107541138561528452351995436115460111715767357209141340267789986966486017905388509579152423850438483240))
(132902518145083058084952511758622280387154060007083381711007154395889138113261141558281496668882272485301434024855642179492534762018694487737653444760483133377189477431254753320300151712014617394222574514680858887405950759403401539326606683563262555248258272785951700055089969291143622621311021266072676229783, 6, (5, 37598860153503326615581015264830503264865439433720385724035242772061120046130081792407193640652835538254512406303470640131620919301399155133536640682246312309639422058051791501551716051609729577898380989120342082971743672218424296416355157566877696371417163805566252146112591578657005764258727033072675000575))
(94203879714411075167693395760278665092845192540339087028074155550605364038650928731470462349493820943164351851894217720178999348097429581200752516414496552930205934529466142682247187451915442413470854706823635555129513505872411508900473661330856493735202798025504060751741339114765634239235833469441169454709, 4, (2, 66254581236728338338283623693407544512187662729708198115638405041385573107103102613037167973425508890121262429869314247358260350170638188762543953033574146516314035091158802101428564158289474524134426528678836510089273869505719918531587587508111879964956204370559300419207825477068161650885479208853766795945))
(82484515527933436314862722406828495676246947139430301053857075088169129948590121219894005778576879724903513832345672704413594009939165462685658550539080040090926272416654584839536965195283308515940714860706907910021133951756458494612198139649449332729327651072804437183926542600634510021387934939145883256063, 3, (6, 64253470899599978277673729773429163871258081804097975126218264211245840173223193415510912178705366536492884696431567067721436402847845493174631363821285986046814165306187694563035170891782671806287280998226358975118749836279719835138074743529451535116551301475568785331848776550801450654825130016891286702595))
(63129582252115812876876098072974133308617030112230114657230846572302651753863476449972796479730742593668963548289774302261205249916473730666190387086391416067961343929371640909070497058510800716142810460359047020957392182630497490514411697665388627025622951203256147356264343277033558277767826961280263920879, 7, (5, 32040195143771637466047735563497261772214232151770874890349933606170723450261033423073717795254490832770468101050365479837502184040110727216552088679393190287014035047741379708539723852281504663346661571491674205292933898303979398233106213051899679809877917953175686709873979930922291413922662244982225231663))
(82123372613136714459156569333257331545605845241605434740354227238876037600094408627627248649255600435606239448987399266238144430361505536692139590177923746144746595371366840483248199792839556700816038491908148008548078304301151913645577581079882241126679478340521671742983209397074479052123727523674368961717, 2, (5, 68195354940369255596894870753982239909691851368769929717683369435347556111603832322851163851678458985803166967118905714291967682765870001662700022257496669458446696522592058624190566287316223103830213471648666252924546092276560714043235737600816881612733744722464493214125004134277358134818888303150018823470))
(97059366511354200923170281830486490669707082663955952924034212181245076135863837435461304733088049491071455167346647483865571832607357955265492505979515329057027054912433771180608461881351312978726821062531036935425132908369051722378284206633046536899706413078723808568985139042527100780397806504907172522467, 7, (6, 42960719492240169177640811618664735893395651515101390305301235855009506839293928482200022633855058040719324142325935109690627923272541585074092592118141192555851194000380531012398940653731056771528503530139249214363212920322748639173101734757330569904077758832732898521810931309073153483553726442341308789356))
(124612844775854160417460421031967470481675599037571380345158350610497752615412041495452840713073784725530207944908969019280296970818054631304250386996988444285535841120774828903383525805906335433772152369955191492549945412285603782759269619839065572556558249265688203646803455717091783022044776251395661207671, 3, (3, 94215423371687246972968185935638473517233362106722110552921981792563669045521362309443377133021474638524502896141118112806373200966310582432060297126659388553078279814287181974153799277527312608030722521484725788514236675782645534235477991388929176575975759511570996895694852377282473535661115998515618249058))
(91219371700865781854562186062579928874439015855662001562145510502090396170342124332408660523664347247223256675916488335162658397441350447165273654469441312780764081953508249314917856407332785941862815646942571020149606829600788841187645472872772464231490024062334699908969227588480032665151838700810410472299, 4, (3, 31991631004075735465238524121512133645927477010510096878015653346411934913911331505528545282226211214351521506518006049074023982251221381409349550762145845962277955357590563626350341043897572699952662130196019507293042543846552815270373260706585089341970446582853397899903118758991369413894595335527639509841))
(89961058108400125693691176577387073616302400912159554024697817802079307872615351647774127466390726140454048903435494181143233149498607920015400497007950628988508444723360810340074876396383207755755965310771735794257081212370938261207139331007071056077632052317077662063495273341381588292092439134097892407359, 3, (6, 80381510573978467430860699126323788205996162902660367130438307495048762300997977131047931101705858082224551767197552856205219350179972599906242362396000721296036756180586135390082122081942102880835400350021766469363183770363878568255105088232838741774079718427747986299995448240213907965268691979754821844149))
(159276866750542613126889504329196747043087837693360849351391256477229906753323710113000524638346004408974948174446857777589268633916357186564983730793222293264794851485864172633565276329861959799187147260796063080255058394575656288578419573870446950478303582619364136204398441211899216431296209352674161843041, 4, (4, 12741177851216859945276067188980883586836387630931007781023278694578641898947578916304922136249922822085391465002451422074134596460600488712373288600984309588357688177830646387391297659849709393791306058806928686814141443671912974159810681343569815252195462055497138236755060197077981086028091890996312388437))
(105678642983915215385381376305223814110790000587197935265999008572043997465767513557023436758120675887733474523316764476016236409966556155550283925286184235562906733250338672560435530022244594160423652686808548559677361122885001095196419333122279892626631026471414848331666289464795615746483809776492261260361, 4, (3, 46901293443554168727970573408630219515612427423923142282853589770175864627680612402128722622661959245653215843430498595052292761459089336230318031385415139499140586859821116202556079670915803370283699966056405454975406049783883072925933264760620760504276028547452930259883724589715045142607461267249274551529))
(106767898023371218423152864353657990206786844053323081814367566137791462861076105612953165101095459965355888579793001990295079328576934744471072610716783059331039361374403506527014277102323143521611845402119843273520129773940304491841977534175178588819814003499404957816785446454296240881137075499584543716543, 1, (3, 89474175499710650627045495122991228821208419287337065022608137539886067322214114776519065277932934505966581338351557710626859066870067797237993034195327754930798089606782234426788890149635194335859611625615400875535638986318875397799112650671284135301549889548440675440686889599236878052391294453286500547277))
(105489743033600776618404736924014082773234739025040235918547880079849719971737127359304073614094075884043630513694448370483208184306027684643273284267932051217742004175757404293643624264846421545917186078199365762796141089940330731024030929168374696605389962930325106070659194496163327222019090112724836643593, 1, (2, 26557762379124264922132214420209728936796452559751033517820166259647971200493029434772959145551662395540203237914969022639479368547265045300822940244603592956901947131088363115332681941180989239355596363143445708865429254462912210194997411474244175252940834791770566886483490068164580622099300335891131365129))
(92649696558766536575835361479589265227177664671481709952659648273344968049013151511491578948283281217549726387434021237388731255593197828072103732383754177185203784976031230438849318969254902487153878539568858112556152122527818071247748006572214226782809611871901361780095622189288570333894755805123541378147, 6, (5, 33447033840940031501830974305420415381234464158515359814788369611222322247008890012981111052090347119586469500504039317368127637491191523542182796717537232573006878762426015103030561584594695096685549694453699936839427930738231154128737500526227666001792431062804217777031726093561668232485490284381066887217))
(127157004365398117544532117776112769069692789011163338176599181049073329340301845288420330302563163172370963213630381077217404276349206367514610928296301102253903572902914318728223609137375021438414149315150331591256858482610103001255904387809659032044885413891496203296595343203031504521035473193565028121911, 7, (3, 50025493627230000724608865692768971503166285903670139688144694228459053581492995275423349036982745076726824698575009675113343802407426686681347482965233753221437709271829355446876874170487514241650202999148942769604127231312416355294772891000080963718198020025634107131629224397418311490302171734592396335445))
(88295183004312129550543093079893198823858351882514656006356820312504814708154416307557338716883518915436848939542718816605045702210894877307691283146470428503232319058003092442859738276868762291698421608549266923466797426069739793937737945306545183362005840876234796815932148917908700723297171667224604578311, 2, (4, 51623901705952955705071032399082866493300796369168906435790873371832236864909996251604003060860382864357746297636670961213085969683081049076536277189601418895633500834154622223840478009921554523521932329778721667763597400545040410518278940050438559141339858626190761595017705223120306088879965347780678337089))
(82222555113197474749550821986652385198371552497993599385588806191426500976195995825889899201173386966081632108827647740073371041232277734708577461009071941353682071406029226380143642861651711730129422629631731669979141914553290786097117751258884265715048428345956445085053834467039654684780545734695022065659, 6, (6, 35518784000619035388330095164994274973089077902052979472229581589622601324729405526501894031786138050651571656687198177189159642739969039040433138216363800160673708671322047879556211581853963839891919355155659822459946184939528603630274344879870156192909772306951080743746848749056512992225394878635722001209))
(106652387286388317007583833986592919310278069654729029192709718656826515113279633852853094252765426080848624426648686070351494414901692795307468821515208561523364840241471031931114239190483929594863460657107230920763364935425824514016430563962917956194734428888157787592501771549676430077774655840679102514449, 7, (3, 76484188718093008155763263489221052121298328689555068354685798167382146663397625882210619281822122448199172062874872694916589627368040702879065467566513514489915663971275153594395645410848640387994688516763090105043749672548547431840021874241933965677791903638845921199178671244609003056554524906583003159883))
思路
观察题目可以知道题目大概由两个部分组成:
- 填充部分:$m_{pad}={e_2}^{m_{bits}}+m^{e_2}$($m_{bits}=511或512$)
- 加密部分:$c\equiv {m_{pad}}^{e_1}\pmod n$
首先为什么不能直接还原?
- n为两个512的素数相乘得到,n的大小在1024位左右
- $m_{pad}$的大小取决与$e_2$的大小,就算是$e_2=2$,$m_{pad}$也有1024位左右,如果$e_2>2$,$m_{pad}$将远大于1024位
- 所以在大多数情况下$m_{pad}>n$,如果我们直接进行还原,由于是在mod n下,就会出现信息损坏的情况
其中的$e_1$为1-8的数,$e_2$为2-7的数,每一组的n各不相同,给出每组数据中的$e_1,e_2,n,c$还原m
最直接的想法,其实就是观察数据中是否有比较好算的,假如我们能在数据中找到$e_2$相同的数据,则代表我们有相同的多组$m_{pad}$,这时我们只需要考虑加密部分也就是$e_1,n$带来的影响。那如果我们在找到$e_2$相同的基础上找到了$e_1$也相同的数据,则很明显,该问题变成了经典的CRT,此时我们即可直接使用CRT解决(要注意CRT后得到的n要大于$m_{pad}$,否则也是无效的,所以我在这里选择了$e_1=1,e_2=3$的两组数据)
实际上这题$m_{bit}=511$,数据中$e_1=1,e_2=2$的数据可以直接进行解密
Exp
from Crypto.Util.number import *
from gmpy2 import *
n1, e1, cipher1 = (66774173046867106978564392807774188269534394449840296405910777832911685835495393323180077968974708562688760938291099725499683301622430513476820311716679706861971145656513111211588447567157066572973454278697174902701179905913830295650932313907414913975102061018460218742766703308850479537206120634422169081427, 1, (3, 9947849848628394040911390578513458759307204504154925933108800760285314551328261356068666838417233200825260136676377138010240930409364211389785744843760837346711809102522170726809372344662827652364290577950806740613036994404769812936985438300111324782034383266110793322048638372472511933383991308991836303085))
n2, e2, cipher2 = (106767898023371218423152864353657990206786844053323081814367566137791462861076105612953165101095459965355888579793001990295079328576934744471072610716783059331039361374403506527014277102323143521611845402119843273520129773940304491841977534175178588819814003499404957816785446454296240881137075499584543716543, 1, (3, 89474175499710650627045495122991228821208419287337065022608137539886067322214114776519065277932934505966581338351557710626859066870067797237993034195327754930798089606782234426788890149635194335859611625615400875535638986318875397799112650671284135301549889548440675440686889599236878052391294453286500547277))
e = e1
pad_e = cipher1[0]
c1 = cipher1[1]
c2 = cipher2[1]
print(e)
n_list = [n1, n2]
c_list = [c1 % n1, c2 % n2]
c = crt(c_list, n_list)
c = c - (pad_e ** 511)
m = iroot(c, pad_e)
print(m[1])
print(long_to_bytes(m[0]))
#begin{8E6C79D2-E960-C57A-F3E4-A52BC827ED6B_Dragon_Year_happy!!!}
总结
- 代码审计能力
- 对数据的观察
- CRT
pad_revenge
题目描述
M=C?
task:
from Crypto.Util.number import *
from flag import flag
assert len(flag) == 64
class RSA():
def __init__(self, m: int):
self.p, self.q, self.e, self.m = getPrime(256), getPrime(256), getRandomRange(1,9), m
self.n = self.p * self.q
def Publickey(self):
return (self.n, self.e,self.c)
def Encrypt(self):
pad = PAD(m=self.m, e=0)
pad.PAD()
self.c = (pad.e,pow(pad.M, self.e, self.n))
class PAD():
def __init__(self, m: int, e):
self.e, self.m, self.mbits = e, m, m.bit_length()
if e == 0:
self.e = getRandomRange(1, 9)
def PAD(self):
self.M = pow(self.e, self.mbits) + pow(self.m, self.e)
GIFT = bytes_to_long(flag)
with open("GIFT.txt", "w") as f:
for i in range(100):
rsa = RSA(m=GIFT)
rsa.Encrypt()
data=rsa.Publickey()
if data[1]*data[2][0]<=2:
continue
f.write(str(data) + "\n")
GIFT:
(8855849848395338140023625078448418335927173696518011383251492587400039666725516914029649358396641049557905045666173111971559868559811467327798346891817467, 2, (3, 4784948017938842097551279082108551665347572133220948615097720598611736477366966303222662471510132309795929920608717764658274574462713718992144719332277372))
(4205338792881421548510609645647062608905484696099258750943039118994520455106270839395319116980996505132271552239717225130972438536887110724158402296232289, 1, (3, 590242556810530557883636062945321456666605165279521102134969558150863508014273375308372904949297413593224978273122299933502842450872249868557340596692448))
(11215096878440533394082882017840664678152612619267805619437502570274983792975956014516967722931372062670050413431322736352622791490509134076852109223402583, 6, (1, 4207445634289020119344405563478546001240651738534009815465142867764254050253567769807370881110212225012934434541551388600446854034348352011118334867814995))
(8934591037839153992305170521685622866064425788727131535511240468158487918859006295259678469641401498568390825787184593823628276058446515383155804865617669, 7, (7, 8537429624056099694485145254993078853490634574249263495066655000326743686838855194392108916855034963065604539340098305777146075156815482122183834966763092))
(5812672638031109844052765117303762451483132620300873699008875126947177112666513960463239995745944449724752301438941490937625242466104181934700354817093919, 4, (2, 1131451402834974986864913900797286711640773952320855913093317750149174529977356051884036428495342821015857200015915858999591451582604216675958012275313836))
(6887522294758197970095515960385622790295767060336384618834090506881872434391273028933475141306559967150666969321023439377545889721116055657514675862552701, 6, (1, 3277799552992960022327022148736641502146613501414713376931832825333712603305219948984921446547175353017304633035544981309863777537096262193109304392395236))
(4881521717586677593176805884447317653586767909819657991040209735913106416242604868118730853499555039694404080938725914839061941459900171308246585279408161, 5, (7, 2226793882828909252238714685958981703825214945151076647785741550382264883944398461285024527093807422548366707500897559991597770733060289668310981414532101))
(4586285627698526960748021073805875389739357539923351949915131309032582722664905156515911641198450688946516926543866585098630724630880252716439806186829727, 4, (1, 167719723472101107383324135394118208274771864392381165361762483510455348156737558460020269637944545335639182968854669970930682315939309220382045417686916))
(6188178287484437587694498743955171641571833564030565395991821104104085602834998936930877738940926564944723804824878810129662354024643801999845782819781109, 1, (6, 350852016571834213774557572711891716600195357176742093965821363608843315563863534918814930101388409082144770532318469098325248704740897900347672582160374))
(9555223357453151395503968349872227568330724153134304991751185139846474844020397573180508538615338507009472020289930811339195094994624289852917427156761401, 2, (4, 3946753015469035572417751047020288004807450101758953968427084123302293974711460400292595533438588088899644490888444873274802971089433903919659150144290321))
(6797448182932673372417235140414778246279613137240621137397661568928320532844650980948032452187493065548951180334727401476239875917152294199737874721223243, 4, (7, 1854590554396091779058432947753944647215930762849257750834582401208192958843670849409016740586034708832905192529269186351274623737443830405872054712609915))
(9019914251160945872502569189610688366425924239771264557312997444787589015016989824375551153582125414512497916796724695155551420754950421337638069567052417, 6, (2, 3519768453437888934613094277084343829983313743161874721676185747351348901420251702693261955172229835611957967432140232561758501969039180673545178601843299))
(7575507226957891430917029983870075245992090767941686165625804188294797798901581313491844988744306110645526945694283175599583632807276664172890750500382477, 8, (1, 1000554446646416979861212287247499855873715502154974851131711924063797995606601223585096644010418177911576675799969019466894525311357818804536466058697398))
(10198381955491908550548306279930576222493707414712707893956814638613187015614579876768191559830958083813483477447417005152412656333213869239620275521528253, 7, (1, 1532040734580289302546092077409669749462310589692993528249171196204106114514030735690676750869662425209674718329819200887572755825569838874499894100104357))
(6790356052746298804979992077143525257557250247118780977503805248228344126522320780266462196843537585104421372657574956988499841755985739482863851992922677, 4, (3, 2140867665433721496876978655693229109188118631336390526162482395412726277607228573413640108519455914154577667769274759802782537700150915770242124039728194))
(8070976720381189709198333790110883692397196020536263728330624393045157482574665246026016675221474896354185714280586255228611447409680020044539965582837299, 7, (8, 1944029668739929937052643855796127343061212672370112401331535037424602946021103525245733173260140402720865306508145620743078982163005718165121883386267145))
(9493905409251364124905632137495767317283658890026460744689549557403283577020738174907468877425459402696288080133852212952390373106533066866622482742576101, 5, (7, 2834267857720170049317115897820750807171503146870727298085135451296320057380040565974445710092078785474687244498847335577530764779713992348621612522668387))
(9258541594570641697616087438143204829403964409521145061823010574368072777261032846946143864357903269095307217415228369684958893627975819163723492212115067, 7, (5, 2076145683058788735842556451156950190745061155040886023478720515488511944906939807938363760086706536645815828263069078642697717571095804439822892211384260))
(6663738189598212428133580446212254463826881298905556470655045611826238959696557589334949884220036357115512932754296739115007331889617299185745340317395989, 6, (2, 5970223871689061720295303779971559280872251195664378581391940129802367013702419232105601146747506104445532585449995822100368828708190679048101358962338969))
(7050174313884434729593139368893291621548368062755985279847850232740992709140864927641348128276777490337461431355020263819014375471971053422267553276559149, 1, (3, 2893746834891731849952475353675823291920101887211621827992533553019484178344684430992593454765874180526901317935813716254980891868014768672217101779002964))
(6860766020768617954507543045457284208128078684634601366590481943173574411184342918290049016261542988890274041130129764495376182683243025935072068337020869, 8, (3, 3367492775076969826876723349315611221433695905901243680009782755669100685988446789488039159399556995700174113809033027180310787233832497122892314393368412))
(8726255872185169951572755067739584540890099982784833866037986500074006148984523346676854239780842121187040035989811881151851699503204849187743308736062173, 5, (8, 2338652446602989481377796923057510376495776358986497886665729133271563221230952636802369307607593378851102679219613286678066317280261973892487491487567445))
(6875393046356667890072010500439384804067341988614406806670026953227028885388238656116614903825439897416536767858782314074914575489926301708358537654645687, 3, (5, 2426034681185452821950546464804404195330095340836375370662896135666681513327574518524491962524397675355983165703004021650989525423857594123092608088446377))
(6772010530308329049692148630651746567641077281730703990391285811267192456649653116465770326223051827199728095643353398471879242902724073778699599784789407, 8, (3, 5867539271413491379511836939575775761812303937825504334093591412148354754378077531280490337829612679215819363287122271448539751850310869052007733348362372))
(6574412401685851019642322758771695815953413540746339551263009043056720640042174888338839677286954038532401589026427226519868758198062515534518529853486217, 1, (5, 197700808849626355488826621003080669984259842098622338164005982359485887096478463411294443411698069377857231658472076557418397550976418280596759194172960))
(6449649961283866145929326501156930775951324655306266812760954343659705042928767510972068398362056080071030112416205675262559116705380456201329872717666461, 5, (4, 3857902449056488630765942750086171540018190682717766705786088173807611674322530983568492334375364927032320829627775274999351888954673132010619343758157578))
(4395658946777613285041813597867303002043780108563840615677761527396261055633634264034632345374256112802919509886845442198521359123140905184934100715773027, 5, (7, 3745996775983148410149770124612320710815511338584684283740648299903676247218945895906924184031016047667269405885593721603118044785984606117343897062678079))
(8966288415170334178265878193620126253854731637969549921416804055371964215515963611229361019725718684781308655003931555840082058656267518147828922014568469, 7, (5, 3108555244780552553871701667964197906854234512935263072240559570379710391384949969564619517878480747252214993514436243229625459874679127074110867005784329))
(12307807182576775779509563507102806719522121911241436032931405936872213159698301580910817660431797573386957331482539875658622393869230533268285081986045283, 3, (7, 9264209488267006322031733755066121573298341462805203865471808009623863498525171124732089258489687535892865345023695172958338142393982297054168394188782266))
(8018516650865093433602633471555107234987215489052863595434284860961179924680646076283307817578075902696758988932322530943259417593826728573735123846377651, 2, (4, 2114599246188425478409388072503155255671198534780504494792133804688504176106864029963264684443868145136172269675299947201099478354616485962278510588900683))
(9788829982984802411888878094077310208963250462380432155609619791166334818756356719680677665513527768524910133899263798991743945954587727954149239682588673, 7, (8, 4014022148216751342120978080242763079214180350282146223123109762115031853817202191920270142944751201412007687294249153023526566787096033746280686616184328))
(6239728410069193459977634097658969250717772047236223446322514489715295318976362113734813328044297046996850539689188631159439108648252251466400073302525943, 2, (5, 3494302863907912567742830405958964875097230844505273315967638774191408186806775752592434083535434915678623858184176444124044814554267636005703416513470208))
(11463769383911711416338770737478285544753342020941224859801510327952586406282692285731036905589040540502846762194871149935499793315616829329406596843989429, 1, (4, 1297025021851176486122476821943457006899776368915670322366718251429537756055933567342427996953297342256021913310813818160232587956537389637666592876790196))
(7695312868320303154724182556869744062740975850081486948529306458791551745279043014584922518803724721857725624240269226703220670466322322864253572576548333, 1, (3, 4853546005581242275031566639028865993927807758919394191424484984623935750674499388240409403735193793296025751636464209778684176500380928091202873126090673))
(7601513259439923680780596512649283150041991787398730741667934858931417781553787727953594558133271606019506789963367748928806549300976621276359003975980679, 1, (8, 4953662678990626149868897765281189454607094212306633726844222997247516056445995745113449521733053290906231327187284525216788799439103940785377822868119726))
(10412166201384696935472805366946716746166114532984331098307071122384415670512513633342418109742435460051958088884198027561159352830694840417613490863785581, 4, (2, 7634575717386213308089062201017689683232882951067220348828456189146298334583086826302246594610102272495485504476951282394636226944881210060676677715584459))
(9555212562259530053106977689044196800238257109245914769132462740486629967886398149393676919056040615108327314142989755539886970030930647084885275336899009, 8, (2, 4485082751612363913575305784762362383053816396915422582061859146086183773864820665195548215535722063416726343661381626690528445478919206493858874890159227))
(4672142898737771956849827527824854679089759532436087107972222395061160489904795229960065448520433027869148651917013523375934596387424589296353872215294053, 8, (8, 2107763328843398890173673385078229966079672921695729931271990428720173058510154464392784036494778309872574146052779269905652743405301809753189762153312380))
(6306138046140746730146383180321768120186957845782939639208815833612422876418702958049033874634089375616700015339286045582172384350622704319192503603887371, 5, (6, 613043746372369642426085136175020969625351578455325746004613814209795052222791286006827269022958490196805837381159733583428684687146982235555073477173167))
(9290009524414381060968453488737483793985268399599888861180929681604540291966466763190007270818860349370345664168541651812141273261043764978303686737453413, 2, (7, 531393544296138135465945168076882273680522082003403097306053761528122502751211932739390766935738741726557549798698987001249997958986917441100373689103118))
(7893079443810667202463864372797371673984487315090529765300164036571909114113150706264454212517285559167118194339785373676508721411813949852370269057292099, 8, (2, 7113122075893748606324527289538165414737434737544740668661837565416299704580236224946933549628078808970400145390312044554656138878221277990465642878039803))
(10249222874848714757086358411771918416232016359861468139376756219319269807032106625386117590089620360989688684275159239506662517395572366999069456616960313, 3, (5, 9133083965184070296627811984926672207117148421264617933381495651618092108430927475774032633465370663269903897078744457339733256156603146302365951841514559))
(6048132520285344098812629186204418021276234409853249924076072972879047498516825898446221607223507823867175610406994940700315426228132154276818999506097969, 8, (3, 3359860417920997935533415449970805289454165666054368704534640309687995124600694236427924742186447306431751325049126261338024331790350628235698924688612265))
(8319865088200850525973476369537334283753257062460057411863317181946948133935469817093699209683422488866736503846734683951037777988059727187895666881648517, 3, (3, 1916797016413370202844174959883427496649775638508714780017708194442848545752137985721061213957285229651394753580269985462634671337539425000735740580469064))
(6965184662487667137270728204799564698772766282357354431607926789037564796934403145297171233060419087922841366347355024400490688336667736097886841959294953, 7, (2, 6484499429091421194389324914930106396159398912793398930569291436490185878295879818299992899172108351943959879875187375438298309620943736803975126455721481))
(3554531698848960213842892197711017585928196988270508363540045045985979866041520734383459016114536600185670754225322557415507349745896215608329256539394687, 3, (8, 1752621674866294911280403064947563928675105120470372472664424410321779419914726315208223641587663745225331235591694072894733186919551370690032494955486868))
(8682953628585137178753379466672187210964501319367297984321979906026292643570729518936001146206006143052548474622183774980529625679025944432093759535596879, 3, (5, 6110975333815266704408003144276958160091381443263235091073725614613131886934367805795794747528249213981468831533169157996387529247926268113189904738167071))
(5056107053745907191292138122958319558568083945723361929317321602021196075602340312072900422569489966130422417481339070361420041976287124065694774585425669, 5, (2, 2843199049263099759618648299183858447629994287617933925445790953545153869285118168221478043458911753995694462936889870459389293558566350631292609660481741))
(4164854865964734292665453249163907666957464008217415039112818857712293934823958191839564663568440357047632496652018065915148903621316002776091356363159507, 5, (1, 2880974091632993550849982195771652799813673141889143791374016258848127888804442730341300484276267347119441332996861690539985888123561419949985542999686509))
(7027575645268735150433397706265599171637048709606279811445124604604628161162053100461465482304023814679815243864333947665970886135956983803922664089278883, 7, (7, 860193652332532496575611496474093579619454833860928783851656254381277431611374212477797358167693081382964129400649745160771317501149873746157704514814433))
(6364826568320581946269493213328775416260128466138692192700789415627375875461684797855838140486834386917716707011641370696584718362947097590146214735407859, 5, (7, 1366359150492761476963206747940271368320716676947271648502965252199012900827299479708128086805683447586594374140105744036924849722287548262526533905509979))
(5312843764626628169609078591014436002027108437130491308653317928298092801315777431382660818096425009489282098941883487503594005082977388712712469820167693, 4, (6, 2577099935315158225031336143957709532097892924162048760324005870018758896030516391163328108026856955639340488138216393216312427677493183197700561870785871))
(10068061586609704264105620896183602633543091710704724639505922851586279785011437615052812809439569145692488329285928641125760206478785195773721150722489381, 2, (8, 3922199560546227520263303873798645620318393615618356884888770710241384137925573621127883839185514894164050391290813130990596162916351364584330305443650772))
(8347347105607845926027773568543010446709951712782503192085355127926384069526655650721823568822649527610208485225564483789699201746960748319135863169889953, 2, (2, 7623880886508227733028994078809593281794742682773253093003146003950546642168805838740478313141710587544266831759748680927271948139306467548144016517048600))
(7175189792802984941517130886179147226692061802486821802633347386534230535377496767557413493122787795633908756400634871271380143719490529755063009119784379, 2, (4, 2699485382199809468341488461503893535653759313485814615196291451188266651341030885252568701437521735031694546565438583926711577341243680415026330144265427))
(5295044378299077172714190189621587271774293018549094379643754896241645861460163920723411723305169519639179781842214122168155186850812596797461298853657383, 8, (5, 3128659819046013908666093530719336501463136400551365303326779864602257202942394659800992423657360975442220301678405524034305893960546872546303284812338016))
(12406544078162753395312946857065318938250342704094990579200889485467975367964738262104140484974099080035821723719402813216753324353832943754546039467297911, 3, (5, 11485630515936669893825031601229887258944555325671568519842998080605886349540289671300960067172710622350232478369833621568074708624723362159011793155880968))
(9675657760508472116807137503977589019490154480993834799028779335614153454492938174391509712800500760462276823148696972801604603380850430326530714037210927, 7, (5, 8722844835111427855693054913265074531808860218555895135827144951859001332742682770383190355702920644872633440742680662694198415969016865660631749566497895))
(8548074827565370378587102499176736109903466362581692175991805938857358602523612106965370045928219591439564682359121303843914531654528736398343681285805813, 5, (3, 3746350573219440244700671348955456948076828780767335982048171820560139658767953067970964110939914314882854437416309667186340512079626549953224875236809032))
(8105733178244786481889651268034779706130154545397333751543668714722575317429848029170911335670386244013496051185006484626300013007952750085800262913820059, 8, (4, 6529303770623449000387547422714436653367215448103526457846973726623863763985178482334675686878682460372630533303186196994561909930315021177958247272899128))
(5716453423972261520596691310596225480593269774997771707018146488118034341972348045978184223218600649466245475052649092817738616954991076982976423670354019, 3, (7, 5603848604757077971991954551703873870415384834263216749901796154801964886905681416429987842851501996997697340277809449847903009250342995212954492335755389))
(5392341039797688655443420547292239235295882662887810282049695624717974866123564641367118247399181045384997707070792319987289305645828114497582434063398333, 6, (5, 4654695828250634979662160304746468701723364721971365470941275373750263673387516082180625609288755923816710030977350140014821243344546141008748284064959292))
(5290027408070154192994402490458534310761384030515981064041334581608866060656541638824981224196027863722921772593804415753719178725058925939749548290577181, 2, (5, 4856432318314512733460384047083784154006508899714901202957599504186309886243454745511319347024792119540153024568373411582481299424015225602460994739141469))
(5840603737989701154068039443035930142296828453387429986090074034763910556734063721590249475815606637759063967620088995128613151351703029625811298879859033, 6, (4, 4802415715793457252505431674255647480691049381330647936397834572888178846332310664682351037127954756301943584764491364248200137368825232783859726489909222))
(8463537131630898943156516073157048439509714168725314931980579189958132429628450408067979756860027664212560415029495177440237307106767201463246537257682613, 1, (7, 6907419187610279929242806738751500377415643938307524271676865586713914536072122782542129211725127330626658982357651853278920950404453205993815036159425550))
(10430855686113867827243821561200066048101550031129989695053799510175002394440818609245151679281260321764742676004721969601290321494415639544273517991323321, 8, (7, 5625479309558965500154326617517953383819454142160341385359567350813659650282729160440975315667385837658726205904038149721670681594065538152551368395398846))
(6606827139273302971199982183487951829111310367778241557336510094585762340891340955893504353700011602108943359882528659551205362529610371853759484216803109, 6, (7, 4063401860234746087473525138310263545247862420047317620748633315904322934956334994077903368692273232321945652920070639306641240767459651084747852638664569))
(9569810341158554726577307668950127348662610250861893506361249082573964510791715467149597808252825826853881704351468150342288333402062573905839159995173281, 7, (1, 4693964606476112273535989205734666285336266314482859140621449879931721033714023319541774782420429614195250596644005617408954126221380015434487286449746815))
(8078435182248405502326335119555007315679577930045851976645134937988912053427366994269036387589861231706325969817984577756475439220521043922322872237859943, 3, (5, 6373140305722943718245092629070502671481393569667830184689245957179661922231650549521826628837724772755898003134621466023973438502896122789084527314839541))
(6087159618260035751225533392277169651638747283786787495371703934017716194782699119427421466639732509800597205146273514261924931950051256587812578690689961, 4, (5, 1413617244448439076934595112776196601033686598093937803892689959213082264095344163399422109540791498303992499323756794534144550151134355883426126275868259))
(6859828663560090979482203905780700510762149352138223106137343633114888834809397639786450091066332197124018421972774472215650562516742223057123713274457293, 5, (8, 5472321620934457966470829314088661404656964580766275708056427336115399461877995867185666069577039718205686133890256805320926301175330337395734284015295448))
(9548470101431799543665234954420672836174952002192352199187435677136122512997311901066281878830523434040673963093573567011334309807390066535236862005274311, 2, (4, 6226139130344412721661370209149360634050042967507558775303404537593916995801280664400355932496855404751586386338519754058799116886650996860153314535607747))
(7933973433280907045799665577467779483197651652165109959945976326936978169572086533861806562289624821502520607680028814257637041330220368053548253036599977, 8, (6, 3794385171534372224589514982777548533304258489910575096619779724884619285648446170593402400411221373507362797845490540742615699165113164212759740608962126))
(8816412442848084752430208462728505728967061521196265166559796986916365604612785245325857381292111380116562659839716235296770530694903814491053459247508511, 4, (3, 4804498094364859861589340725254206238062934532967163603395764066656438590819895907269086266203597095663308975131080289461716438205120436887541973817451946))
(4592012330551423476358646992033661463388085801654358392175134462035847759528604347743309357953030024273755902565596889089247690619477581157668726328948371, 3, (4, 310391283501196670132828142714574115642526992041554327703287736138458740180671543650703582813426116200551277438212565166345802069264155799723605891145968))
(7197392029126640245776995292015442602166984026804951059944864350713021582318543556634587965327078767603194002255963591985493844372664106573298523187067299, 7, (2, 410173889637950824388683006438586641958495421252950925988859098100963653594161198836705976097237708727685482427660255067171318826761561608647373238457134))
(5880719722053558284267749913549227404845613659496166037821630041448685328612806945582316706218787862713129944913840122219756058977369824663832712979229751, 4, (4, 1406096621885395060802842904603010565230193378835674773798028249135284745864702123590175941921308332741668188238357086968599334785739087052001812057899919))
(6047049624433352374022075278190080859028828709616262482279442113479020326445050651001081845371768964280789254141978745564737305295563668917890701976160119, 6, (6, 5713507093411290853042873772441495463570266562423726323195621253719573732801110808516964381888884228534543773918350127229625733110002631458384980480076290))
(5739759301840750445496475410254414186344410991212950590613821079939426023394215413585128098736454862217923276493263853044780332607072249915281789435261749, 2, (3, 3632805967700586367865538288948810588542402238449981477249693083862395834876632803287040921155214852514729541015018144706531998338603155687201797275635172))
(4781686379870656621208108607285929161149462721256505744314752897394670442437750894973952444881948643002276068022367574130393049775486955875425635394733847, 7, (5, 2951116577664475595600638365699788121304139724237338735174243599997896208589601341337261424149951062945737875417602414942831857076692305612931841303779230))
(5837241998515052730448920075221823120540795242393327617465399259493565419288914252240247121521344677292758403466058671167172035040653244700693513558698077, 4, (4, 1767058918509073669316932458999805899894082338385868298389425483177408707618141596346061779136829127687689639479351675106248214135793248649685254517630196))
(6159791021941401704903001994332435158281917897670740024782182017343543314955662362293164505508951765716395730660812343804030847043678541232530950266172589, 5, (2, 1988959643089451521941579291470223075553068825052323482846013410842305587266306230060039757049623414195840166268232679640184352785227993208538716601342488))
(9710162071095981974839032781863290931236247431388099717431071631893257220015743337276175516389263413091969840160362967936973702605625052955159690665690109, 3, (2, 2636612298987826682286139509726120778140889201025348997038600478690143339898630490375678733987106155526715233728850191465221058594420027025482690544258086))
(6247089750875599150125901185315412269096777922916076521869518172551765197341216812323749348646268890548391898094244085741475335774541057832869646674419947, 7, (4, 5795969353732915778888279657055430461100444021372996940395810588102247035527332702386057969312219463465800258008382535118927614576523937721159516234123215))
(5688917219199318991002118202778643011244902109317698877873162738329417323224630426075300225033914851827313913035002912624438674232242063736410280759166591, 8, (1, 383298754368204489334589525261802411023292588890024403697068950816384093934864553457188223977008658971510243727603407812656922859693717685324945087038832))
(6701108183140725736517678608553093305315406422681301970325600768026141742635089730585999892092765093014333147170304382944311815968508073525496879970609989, 6, (7, 4339360311700506249405424065389944129592413242442175002805441192657124888639452897292172157091828267802699553523817544531341309658710717330441205463435802))
(5766343519592672284019995842338087197429969796567396256311430844193383588698749268690647799736164281687878646588288078406179070840227006983455787748303611, 2, (5, 256666927732284041980193989451224021309046622613385071669022109514934185343221829162127437807769822917212198734080010376899342718895218076239594688618266))
(8848902804676605614404072370283082219106064195450909901005613953963119517798440672554546710103845804108301200137381693045929054083608101416879503032534253, 6, (7, 7319183280541266465817969081125906600952550456515847894986379211314032030793526688438619542500803276391597655446281351166226050112153629499062040865356167))
(4298819643357102556549854201531155496670461457358312493403639704372503748227941837243852792067616456642999975219857072473504077546235436477569241731724989, 4, (3, 3006137347089333084216844901512109821048836226927811141793264532131449761231213651531665890018544846832047730111277440800278220366456884209653568976351055))
(7366123774722032725582020274406946788478538027663741894909308120350318683646376016540840552430393496045784081985828039319946601762685079012607819644605653, 4, (7, 2892559025669652236531070142947195252778876366814600214617321094374691831172628272049419395391964210384841053073227776614706700210144534573169989180904860))
(5036712961655285432706559948918343051105318118343694839360093467007748859716716873199596483044597626858041356048086639916991540731336182686439517049429277, 8, (8, 2168236239488780497764597685307338449696981217102084066446321498540037161260437827251837188809847690066947054977145919266954610204182323475993093976254852))
(3785631600711654285531808541889683402195265162867880078739866435724588878554872363212521866285772433495274302150111988565671125541267648022312404911077209, 1, (6, 1575467179152990371411036722043889285634721450504030625602196854527650615668991695348739091918150121085507267954580819836200196931927274626499080093042574))
(5297284598118210286808450570897558672605006648389679970689985107235217747648131205630284820289307619210178471266285618190714931570695987133055656619886003, 5, (7, 2440384005429386275070894171650506854969826874062582709819438571004590345990136544533830083882536647609162643882919020500856987364779484710089259713866440))
(6497995813868395830268079685723777222018671544196307635811302118984360632862490665803738963305815098291117094408723801272560004489569583936285665248125303, 2, (5, 2512177198404981455679103469710582798545916219057318160334576950773397945007488672026834657957119447460916017146356399450918779821460314010423888323499713))
(5237328740759645061128935982381344041688470424619681134678220410346715178563027792951504134361125938914296673325808634706088078482520087386512175222006673, 4, (7, 4895763226717936615571684443579733552224224149944869108088058478967067187370169670263292182225626673593693098170600300820318412464965854764994622155981267))
(9101057232192261947361948468170916430302112914584327362562597324566382885363724817411092783019220888278190179337126371601783474648762323891582020480156989, 7, (7, 1834370257457759880889497314274050334929094943009641426914402570148060376543764415103562502818317464197530765072641252404356184854361610503480961772071527))
(8312288075348438476560549233069169293742093063457457757524428863647607330647265022656375035766907644662534920266346074528342349507883118021141072278923291, 3, (1, 6321753472897262440624141291063114426852337123775831518716990057019609775651674347170702259328741868715987920583173843377418934417208880390939484171974180))
思路
同pad
ps:其实是想考一元模多项式方程组求根问题吧...
Exp
from Crypto.Util.number import *
from gmpy2 import *
n1, e1, cipher1 = (7050174313884434729593139368893291621548368062755985279847850232740992709140864927641348128276777490337461431355020263819014375471971053422267553276559149, 1, (3, 2893746834891731849952475353675823291920101887211621827992533553019484178344684430992593454765874180526901317935813716254980891868014768672217101779002964))
n2, e2, cipher2 = (4205338792881421548510609645647062608905484696099258750943039118994520455106270839395319116980996505132271552239717225130972438536887110724158402296232289, 1, (3, 590242556810530557883636062945321456666605165279521102134969558150863508014273375308372904949297413593224978273122299933502842450872249868557340596692448))
n3, e3, cipher3 = (7695312868320303154724182556869744062740975850081486948529306458791551745279043014584922518803724721857725624240269226703220670466322322864253572576548333, 1, (3, 4853546005581242275031566639028865993927807758919394191424484984623935750674499388240409403735193793296025751636464209778684176500380928091202873126090673))
e = e1
pad_e = cipher1[0]
c1 = cipher1[1]
c2 = cipher2[1]
c3 = cipher3[1]
print(e)
n_list = [n1, n2, n3]
c_list = [c1 % n1, c2 % n2, c3 % n3]
c = crt(c_list, n_list)
print(int(c).bit_length())
c = c - (pad_e ** 511)
m = iroot(c, pad_e)
print(m[1])
print(long_to_bytes(m[0]))
#begin{There_wonot_be_any_surprises_this_time230E03984617EEEEE13}
总结
- 无
fake_N
题目描述
来道rsa吧!咦?这n怎么是假的?
from Crypto.Util.number import *
from secret import flag
def fakeN_list():
puzzle_list = []
for i in range(15):
r = getPrime(32)
puzzle_list.append(r)
p = getPrime(32)
q = getPrime(32)
com = p*q
puzzle_list.append(com)
return puzzle_list
def encrypt(m,e,fake_n_list):
fake_n = 1
for i in range(len(fake_n_list)):
fake_n *= fake_n_list[i]
really_n = 1
for i in range(len(fake_n_list)-1):
really_n *= fake_n_list[i]
c = pow(m,e,really_n)
print("c =",c)
print("fake_n =",fake_n)
if __name__ == '__main__':
m = bytes_to_long(flag)
e = 65537
fake_n_list = fakeN_list()
encrypt(m,e,fake_n_list)
'''
c = 6451324417011540096371899193595274967584961629958072589442231753539333785715373417620914700292158431998640787575661170945478654203892533418902
fake_n = 178981104694777551556050210788105224912858808489844293395656882292972328450647023459180992923023126555636398409062602947287270007964052060975137318172446309766581
'''
思路
先看fake_n_list的生成,可以发现fake_n_list的前15项是随机生成的15个32位质数r,第16项是由两个随机生成的32位质数p,q相乘得到的n
而fake_n即是fake_n_list中所有的乘积,really_n则是前15项目的乘积。本题的素数都不大,我们可以直接将之分解,即可得到17个质数。然后我们只需要枚举p,q的可能情况即可知道really_n,从而解密
Exp
from Crypto.Util.number import *
from factordb.factordb import FactorDB
from gmpy2 import *
c = 6451324417011540096371899193595274967584961629958072589442231753539333785715373417620914700292158431998640787575661170945478654203892533418902
fake_n = 178981104694777551556050210788105224912858808489844293395656882292972328450647023459180992923023126555636398409062602947287270007964052060975137318172446309766581
e = 65537
f = FactorDB(fake_n)
f.connect()
fs = f.get_factor_list()
phii = 1
for i in fs:
phii = phii * (i - 1)
for p in fs:
for q in fs:
n = fake_n // p // q
phi = phii // (p - 1) // (q - 1)
d = invert(e, phi)
m = powmod(c, d, n)
flag = long_to_bytes(m)
if b'begin' in flag:
print(flag)
#begin{y0u_f1nd_th3_re4l_n}
总结
- 对欧拉函数$\varphi$的理解
baby_classic
题目描述
你这辈子就是被古典密码给害了,后面我忘了
from random import *
from string import *
import numpy as np
from secret import plaintext
ls = ascii_uppercase + '_.*'
def generate_str(length):
s = ""
for i in range(length):
s += choice(ls)
return s
def str2mat(s):
res = np.zeros((len(s) // 6, 6),dtype=int)
for i in range(0,len(s)):
res[i // 6, i % 6] = ls.index(s[i])
return res
def mat2str(mat):
s = ""
for i in range(len(mat) * 6):
s += ls[mat[i // 6, i % 6]]
return s
def encrypt(plaintext,key1,key2):
mat_plaintext = str2mat(plaintext)
mat_key1 = str2mat(key1)
mat_key2 = str2mat(key2)
enc_matrix = np.dot(mat_plaintext,mat_key1) % 29
for i in range(len(enc_matrix)):
for j in range(len(enc_matrix[i])):
enc_matrix[i][j] = (enc_matrix[i][j] + mat_key2[0][j]) % 29
return mat2str(enc_matrix)
if __name__ == "__main__":
assert len(plaintext) == 72
m = generate_str(48)
key1 = generate_str(36)
key2 = generate_str(6)
c = encrypt(m, key1, key2)
ciphertext = encrypt(plaintext, key1, key2)
'''
flag = "begin{" + hashlib.md5(plaintext.encode()).hexdigest() + "}"
'''
print(f"m = {m}")
print(f"c = {c}")
print(f"ciphertext = {ciphertext}")
'''
output:
m = VOWAS*TED.AE_UMLVFV*W*HSSSTZIZZZDAKCLXZKM_E*VR*Y
c = QLOKQGUWMUTGZSDINCQVIVOLISFB_FC.IC_OSPLOBGOVSCZY
ciphertext = MHDTBJSZXLHH.Z.VWGLXUV.SDQUPAMEPNVQVQZX_CBDZHM_IBZRGLJP_YSBDXN.VACLDGCO_
'''
思路
简单梳理题目加密流程,可以分为以下几个部分:
- 字符串和矩阵之间的转换:将每个字符用在ls的序号将之替换,按照顺序每行排6个,也就是排成一个n*6的矩阵。矩阵转字符串同理可得。
- 将明文矩阵$M_{t*6}$和密钥一${KEY_{1}}_{6*6}$在mod 29下进行矩阵乘法得到密文矩阵$C_{t*6}$
- 将$C_{t*6}$的每一行在mod 29下加上$KEY_2$(也可以把$KEY_2$当作一个每行相同的一个$t*6$的矩阵,则要做的即是将$C_{t*6}$和${KEY_2}_{t*6}$在mod 29下做加法),再将之转换回字符串即得到ciphertext
写在同一个式子也就是:$CIPHER_{t*6}=M_{t*6}*{KEY_1}_{6*6}+{KEY_2}_{t*6}\pmod {29}$
题目给出了一组长度为48的已知的明密文对m、c,并且给出长度为72的ciphertext,要求我们解出ciphertext对应的明文,对明文进行md5处理得到flag。
首先我们要做的肯定是得想办法将$KEY_1$和$KEY_2$求出,那最直接得思路其实就是爆破$KEY_2$,然后算出$C_{t*6}$,再根据$M_{t*6}$和$C_{t*6}$解出$KEY_1$(sage中可以通过solve_right直接求出,如果想用groebner手撕也不是不行...),这样的时间复杂度其实也是足以解出这道题目的。
但我们也可以不用爆破的方法求$KEY$,对于明文来说,其实每一行都是独立的进行加密的,所以cipher的每一行其实都可以表示为这样一个式子:$CIPHER_{1*6}=M_{1*6}*{KEY_1}_{6*6}+{KEY_2}_{1*6}\pmod {29}$,那这样的话,我们用cipher的每一行两两之间做差即可消除$KEY_2$带来的影响,然后将差排成一个新的矩阵,也可以解出$KEY_1$(因为本身是个$8*6$的矩阵,两两相减后得到的差可以排成个$7*6$的矩阵,且明显这七组差之间都线性无关,$KEY_1$我们只需六组线性无关即可求出,所以我们完全可以求出$KEY_1$),然后再正向把$KEY_2$解出即可。
解密流程只需要将加密流程逆过来:将$CIPHER_{t*6}$在mod 29下减去$KEY_2$,乘上$KEY_1$的逆矩阵,即可得到明文矩阵
Exp
from string import *
import numpy as np
import hashlib
def str2mat(s):
res = np.zeros((len(s) // 6, 6),dtype=int)
for i in range(0,len(s)):
res[i // 6, i % 6] = ls.index(s[i])
return res
def mat2str(mat):
s = ""
for i in range(len(mat) * 6):
s += ls[mat[i // 6, i % 6]]
return s
def sub(cipher_matrix):
dec_matrix = Matrix(GF(29), 7, 6)
for i in range(1, len(cipher_matrix)):
for j in range(len(cipher_matrix[i])):
dec_matrix[i - 1, j] = (cipher_matrix[i, j] - cipher_matrix[i - 1, j]) % 29
return dec_matrix
def solve_key(c, m):
c_matrix = str2mat(c)
m_matrix = str2mat(m)
cc_matrix = sub(c_matrix)
mm_matrix = sub(m_matrix)
key1 = mm_matrix.solve_right(cc_matrix)
enc_matrix = np.dot(m_matrix,key1) % 29
key2_matrix = enc_matrix
for i in range(len(enc_matrix)):
for j in range(len(enc_matrix[i])):
key2_matrix[i,j] = (c_matrix[i,j] - enc_matrix[i,j]) % 29
return key1, key2_matrix[1]
def decrypt(ciphertext, mat_key1, mat_key2):
mat_ciphertext = str2mat(ciphertext)
mat_key1 = mat_key1.inverse()
for i in range(len(mat_ciphertext)):
for j in range(len(mat_ciphertext[i])):
mat_ciphertext[i][j] = (mat_ciphertext[i][j] - mat_key2[j]) % 29
dec_matrix = np.dot(mat_ciphertext, mat_key1) % 29
return mat2str(dec_matrix)
m = "VOWAS*TED.AE_UMLVFV*W*HSSSTZIZZZDAKCLXZKM_E*VR*Y"
c = "QLOKQGUWMUTGZSDINCQVIVOLISFB_FC.IC_OSPLOBGOVSCZY"
ciphertext = "MHDTBJSZXLHH.Z.VWGLXUV.SDQUPAMEPNVQVQZX_CBDZHM_IBZRGLJP_YSBDXN.VACLDGCO_"
ls = ascii_uppercase + '_.*'
key1, key2 = solve_key(c,m)
plaintext = decrypt(ciphertext, key1, key2)
print(plaintext)
flag = "begin{" + hashlib.md5(plaintext.encode()).hexdigest() + "}"
print(flag)
#YOU_KNOW_THE_MYSTERY_OF_THE_MATRIX**BUT_THIS_IS_BEGINNING_OF_CRYPTOLOGY.
#begin{d70c49eebc8158985f33a5eb3caa5733}
总结
- 代码审计能力
- 矩阵的相关知识
- 对算法的逆向能力
Hard_ECC
题目描述
baby不是真baby的话,那hard当然也不是真hard的啦
from flag import flag
A = [0,
3,
0,
973467756888603754244984534697613606855346504624,
864199516181393560796053875706729531134503137794]
p = 992366950031561379255380016673152446250935173367
ec = EllipticCurve(GF(p), [A[0], A[1], A[2], A[3], A[4]])
T = ec.random_point()
secret = int.from_bytes(flag, 'little')
Q = T * secret
print(T, Q)
# (295622334572794306408950267006569138184895225554 : 739097242015870070426694048559637981600496920065 : 1)
# (282367703408904350779510132139045982196580800466 : 411950462764902930006129702137150443195710071159 : 1)
思路
模数很小,直接discrete_log
Exp
from Crypto.Util.number import *
A = [0,
3,
0,
973467756888603754244984534697613606855346504624,
864199516181393560796053875706729531134503137794]
p = 992366950031561379255380016673152446250935173367
ec = EllipticCurve(GF(p), [A[0], A[1], A[2], A[3], A[4]])
print(ec)
T = ec(295622334572794306408950267006569138184895225554, 739097242015870070426694048559637981600496920065)
Q = ec(282367703408904350779510132139045982196580800466, 411950462764902930006129702137150443195710071159)
flag = T.discrete_log(Q)
print(long_to_bytes(flag)[::-1])
#begin{it_is_hard?}
总结
- 离散对数问题
- ecc
OEIS2
题目描述
听说可以查表?
from hashlib import *
upper = 2**28 + 5
res = 1
for i in range(1, upper + 1):
res *= i
flag = 'Beginctf{' + sha256(str(sum([int(i) for i in str(res)])).encode()).hexdigest() + '}'
思路
强网杯speed up的加强版
还能咋办,挂着让他跑
Exp
from hashlib import sha256
x = gamma(2 ** 28 + 6)
b = str(x)
res = 0
for i in b:
res += int(i)
print(sha256(res))
#c60a2e5c9e9572ed848776f282a9c90d6ca0fe29f8308b0b9b43c61d493133e9
总结
- 电脑性能
- patience
baph
题目描述
签到题1.0(flag格式为flag{})
from base64 import b64encode
from Crypto.Util.number import *
from string import ascii_letters
from secrets import flag
ls = ascii_letters + '!,.? {}' + '01232456789'
assert all([i in ls for i in flag])
ba = b64encode(flag.encode())
baph, key = '', ''
for b in ba.decode():
if b.islower():
baph += b.upper()
key += '0'
else:
baph += b.lower()
key += '1'
baph = baph.encode()
key = long_to_bytes(int(key, 2))
enc = b''
for i in range(len(baph)):
enc += long_to_bytes(baph[i] ^ key[i % len(key)])
f = open('flag.enc', 'wb')
f.write(enc)
f.close()
'''
flag.enc的字节流
b'\xf7.\x1cf\x94\\\x11\x82\x8c\x1c\x9ba\xce."\x1e\xaa\x18\x1d\xae\x8aI\xe2y\xcf-)f\x87\x1c \xa1\xbb\x1c\x97{\xf7\x1b6~\xac\x183\xbc\xa7I\xd8\x1b\xce\x04\x1cx\xad]\t\xd4\xb4]\xccg\xc9\x0b6f\x97]\x11\xbc\xa7I\xc0g\xcf*&g\x94\x1c\'\xaa\xb4c\xd4c\xf4P6~\xaa"0\xae\xa7]\xc8\x16'
'''
思路
题目将明文base64之后,根据大小写来构造密钥比特,随后将密钥比特转成字节作为key,循环自身异或大小写翻转的明文base64。这里密文总长度为96个字符,这意味着key的长度只有 96 / 8 = 12 个字节。我们只要知道前12个base64编码后的字符即可。而这里我们知道flag会是以“flag{”开头,这里转换为base64即泄露了 5 8 / 6 = 6个字符,仍然不够,但我们可以选择爆破“flag{”后的四个字符,这样转换为base64就泄露了(5+4) 8 / 6 = 12个字符,就足够知道key了。然后根据key解密,判断解密出来的明文是否是我们需要的即可(比如flag标识,明文是否在字典中)。
Exp
from base64 import b64encode,b64decode
from string import ascii_letters
from itertools import *
with open("2024beginctf/flag.enc","rb") as f:
enc = f.read()
print(len(enc))
dic = ascii_letters + '!,.? {}' + '01232456789'
def solve(msg):
ba = b64encode(msg)
baph, key = '', ''
for b in ba.decode('utf-8'):
if b.islower():
baph += b.upper()
key += '0'
else:
baph += b.lower()
key += '1'
baph = baph.encode('utf-8')[:12]
key = b""
for i in range(len(baph)):
key += (baph[i] ^ enc[i]).to_bytes(1, 'big')
dec = b""
for i in range(len(enc)):
dec += (enc[i] ^ key[i % len(key)]).to_bytes(1, 'big')
flag=""
try:
for b in dec.decode('utf-8'):
if b.islower():
flag += b.upper()
else:
flag += b.lower()
t = b64decode(flag.encode('utf-8')).decode()
if 'flag{' in t:
if t.endswith('}'):
print(t)
except:
return
msg="flag{"
for i in permutations(dic, 4):
m = msg + i[0] + i[1] + i[2] + i[3]
solve(m.encode())
#flag{Congratulations!!! Sometimes explosive attacks can be effective!!!}
总结
- base64
- 爆破
- 代码审计能力
我玩青水的
题目描述
开局霸体螺旋丸起手,替身反手飞雷神,我们青水玩家实在是太有操作啦!所以为什么不能用玩青水的大脑做这题呢?
from Crypto.Util.number import *
from secret import flag
m = bytes_to_long(flag)
e = 2
p = getPrime(512)
c = pow(m, e, p)
print(f"p = {p}")
print(f"c = {c}")
'''
p = 7709388356791362098686964537734555579863438117190798798028727762878684782880904322549856912344789781854618283939002621383390230228555920884200579836394161
c = 5573755468949553624452023926839820294500672937008992680281196534187840615851844091682946567434189657243627735469507175898662317628420037437385814152733456
'''
思路
第一眼过去枚举k,发现不行。
那我直接有限域开根
EXP
from Crypto.Util.number import *
from gmpy2 import iroot
p = 7709388356791362098686964537734555579863438117190798798028727762878684782880904322549856912344789781854618283939002621383390230228555920884200579836394161
c = 5573755468949553624452023926839820294500672937008992680281196534187840615851844091682946567434189657243627735469507175898662317628420037437385814152733456
e = 2
funcp = Mod(c, p).sqrt(all=True)
for i in funcp:
print(long_to_bytes(int(i)))
#begin{quadr4ticresidue_i5_s0_3asy}
总结
- 二次剩余
begin_rsa
题目描述
也许,这只是开始呢
from Crypto.Util.number import *
from gmpy2 import *
from secret import flag
m = bytes_to_long(flag)
while True:
e = 65537
p1 = getPrime(512)
q1 = getPrime(512)
n1 = p1 * q1
p1_xor_q1_low = (p1 ^ q1) & ((1 << 402) - 1)
if p1_xor_q1_low >= 10**121 and p1_xor_q1_low <= 10**122 - 1:
p2 = next_prime(p1_xor_q1_low)
q2 = int(str(p2)[61:] + str(p2)[:61])
n2 = p2 * q2
if isPrime(p2) and isPrime(q2):
delta = p2 - p1_xor_q1_low
c = pow(m, e, n1)
print(f"delta = {delta}")
print(f"n1 = {n1}")
print(f"n2 = {n2}")
print(f"c = {c}")
break
'''
delta = 61
n1 = 150838784531830142890659431841610000561921043629625618437510373123377520444955469509903631548754842609295975005302780725591929018884805452687677684641162979092069629817740554095750189248769936750051172301891394503776919559958638203717583333429953061416588208428893436430392654983424277005324307321992921302331
n2 = 102603788692700558034198259394482879736866145355211103067657972779629890324418113112441175321034955422723378003769267804892308121194871227786783930178021669484220789624643889449429959522560822967157677629720685465873700893389751397027159036419
c = 100199300622156732994823007073822662584719346985430234367094043002848132740563819931486477742264272832060136969084318984512567787814048659200236334994498141562184235841854521058494238451300610422156322926341430748222140189349893444976932184031798101999886029853099171189139509539715437105818418407563733036131
'''
思路
题目加密过程大概分为两个部分:
- 首先生成了两个512位的质数$p_1$和$q_1$,然后计算它们异或的低402位p1_xor_q1_low,确保这个值是122个十进制数字
- 求p1_xor_q1_low的nextprime记为$p_2$,将$p_2$的十进制前61位和后61位交换了一下得到$q_2$,确保$q_2$也是质数后,给出$p_1$和$q_1$的乘积$n_1$,用$n_1$作为模数和e=65537加密flag
题目给出了$p_2$和$q_2$的乘积$n_2$,以及$p_1$和$q_1$的乘积$n_1$,$p_2$和p1_xor_q1_low之间的差delta和密文c,要我们还原flag。那我们首先想到的肯定是得把$p_2$和$q_2$求出来再求出$p_1$和$q_1$。
观察$p_2,q_2$,因为是将$p_2$的十进制前61位和后61位交换了一下得到$q_2$,所以可以把他们写成:
$$ p_2=a*10^{61}+b\\ q_2=b*10^{61}+a $$
那么$n_2=p_2*q_2=(a*10^{61}+b)(b*10^{61}+a)=(ab*10^{122}+(a^2+b^2)*10^{61}+ab)$
可以发现$n_2$泄露了$ab$的高位和低位(a,b各为61位,所以ab大概率为121位或122位,$(a^2+b^2)$大概率122位,那我们这就相当于是泄露了$ab$的高60位和低61位),我们可以枚举下中间那一位,然后就可以得到正确的$ab$,从而求出$(a^2+b^2)$,然后就可以解出a和b,就可得到p1_xor_q1_low。
只会我们只需要根据p1_xor_q1_low去爆破$p_1$和$q_1$的低位(这里需要加低位剪枝),然后就变成了已知$p_1$的低位,用copper求解即可得到$p_1,q_1$,从而算出flag。
Exp
from Crypto.Util.number import *
from gmpy2 import *
n2 = 102603788692700558034198259394482879736866145355211103067657972779629890324418113112441175321034955422723378003769267804892308121194871227786783930178021669484220789624643889449429959522560822967157677629720685465873700893389751397027159036419
ab_low = n2 % (10 ^ 61)
ab_high = n2 // (10 ^ 183)
low = str(ab_low)
high = str(ab_high)
x_list = [""] + [str(i) for i in range(10)]
for x in x_list:
try:
ab = int(high + x + low)
a2_b2 = int((n2 - ab * (10 ** 122) - ab) // (10 ** 61))
x1 = iroot(a2_b2 + 2 * ab, 2)[0]
x2 = iroot(a2_b2 - 2 * ab, 2)[0]
h = (x1 - x2) // 2
l = (x1 + x2) // 2
p2 = int(str(h) + str(l))
q2 = int(str(l) + str(h))
if p2 * q2 == n2:
print(p2)
print(q2)
except:
continue
delta = 61
p1_xor_q1_low = p2 - delta
n = 150838784531830142890659431841610000561921043629625618437510373123377520444955469509903631548754842609295975005302780725591929018884805452687677684641162979092069629817740554095750189248769936750051172301891394503776919559958638203717583333429953061416588208428893436430392654983424277005324307321992921302331
c = 100199300622156732994823007073822662584719346985430234367094043002848132740563819931486477742264272832060136969084318984512567787814048659200236334994498141562184235841854521058494238451300610422156322926341430748222140189349893444976932184031798101999886029853099171189139509539715437105818418407563733036131
e = 65537
pre_sol = [""]
cur_sol = []
for i in range(402):
cur_sol = []
for pre_p in pre_sol:
for j in range(2):
p = str(j) + pre_p
l = len(p)
pp = int(p, 2)
q = (pp ^^ p1_xor_q1_low) % 2 ** l
if pp * q % 2 ** l == n % 2 ** l:
cur_sol.append(p)
pre_sol = cur_sol
for p in cur_sol:
pp = int(p, 2)
PR.<r> = PolynomialRing(Zmod(n))
f = r * (2 ** 402) + pp
f = f.monic()
roots = f.small_roots(X = 2 ^ 113, beta = 0.4)
if roots:
p_ = int(roots[0]) * (2 ** 402) + pp
print(p_)
q_ = n // p_
try:
d = invert(e, (p_ - 1) * (q_ - 1))
m = long_to_bytes(powmod(c, d, n))
if b'begin' in m:
print(m)
except:
continue
#begin{just_the_beginning_of_the_RSA}
总结
- 数据泄露
- 爆破
- 剪枝
- copper smith
叼茂SEO.bfbikes.com