はじめに
先日開催されたSECCON CTF13にチーム"full_weak_engineer | Please subscribe! -> https://asusn.online"の一員として挑みました。結果は1チーム差で決勝へ行けず、という惜敗で、エースのt-chenはリーダーのアスースンオンラインを差し置いて臍を噬む思いだった様です。
とは言え、どれでも良いのであと一問正解していれば決勝へ進めたという状況だったので、参加者全員に責任があると考えています。よって本稿はその戒めとして、解くことが叶わなかったCrypto問題をひとつ抜粋し、復習を兼ねたWriteUp記事に代えたいと思います。
問題
- タイトル: Tidal Wave
- 正解数: 19
- 配布コード:
chall.sage,output.txt
chall.sage
import random
from Crypto.Util.number import getPrime
import secrets
from flag import flag
def get_Rrandom(R):
return secrets.randbelow(int(R.order()))
def make_G(R, alphas):
mat = []
for i in range(k):
row = []
for j in range(n):
row.append(alphas[j]^i)
mat.append(row)
mat = matrix(R, mat)
return mat
def split_p(R, p, prime_bit_length, length):
step = ceil(prime_bit_length/length)
res = []
while p > 0:
res.append(ZZ(p % (2**step)))
p >>= step
return vector(R, res)
def make_random_vector(R, length):
error_range = 2^1000
res = []
for _ in range(length):
res.append(R(secrets.randbelow(int(error_range))))
return vector(R, res)
def make_random_vector2(R, length):
error_cnt = 28
res = vector(R, length)
error_pos = random.sample(range(length), error_cnt)
for i in error_pos[:error_cnt//2]:
res[i] = get_Rrandom(R)*p
for i in error_pos[error_cnt//2:]:
res[i] = get_Rrandom(R)*q
return vector(R, res)
n, k = 36, 8
prime_bit_length = 512
p = getPrime(prime_bit_length)
q = getPrime(prime_bit_length)
N = p*q
R = Zmod(N)
alphas = vector(R, [get_Rrandom(R) for _ in range(n)])
G = make_G(R, alphas)
dets = [G.submatrix(0,i*k-i,8,8).det() for i in range(5)]
double_alphas = list(map(lambda x: x^2, alphas))
alpha_sum_rsa = R(sum(alphas))^65537
keyvec = vector(R, [get_Rrandom(R) for _ in range(k)])
pvec = split_p(R, p, prime_bit_length, k)
p_encoded = pvec*G + make_random_vector(R, n)
key_encoded = keyvec*G + make_random_vector2(R, n)
print(f"{N=}")
print(f"{dets=}")
print(f"{double_alphas=}")
print(f"{alpha_sum_rsa=}")
print(f"{p_encoded=}")
print(f"{key_encoded=}")
import hashlib
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
key = hashlib.sha256(str(keyvec).encode()).digest()
cipher = AES.new(key, AES.MODE_ECB)
encrypted_flag = cipher.encrypt(pad(flag, AES.block_size))
print(f"{encrypted_flag=}")
output.txt
N=164154991219443437626081332614158730243917037448199716655783585386114084944921014678446140961950779185987551082302233189672777124070342896078792406421295367843743938975018623106720031195121691323765575499580580898542615857150538031740984848418002758286176739690774217960569804300041578781846805528383738052213
dets=[121915670423707921083577303353189290105753205383086881070909346847225721867189982304974229518005262154762849226647440342352684619218902684092877409646116087748803226587133413523670397361656258896033054738138430731654935305944293063008598790319170718134139499489852902861615117239766986756325340620341359067059, 63343907682857872607878509945567224921486563246612523881799516305479378868588450586885797937963326267999856247491496316934335364287874172156617589213358253481042121811294542969712559236194280744424138336229118925434936952405022974349635501863559419746472305473002537267130657528843088873920749884958517776126, 59960940183998431136384918539675756934170966091163467968520767153325645962136560671200068950396298697758136800457041389740969533526365341358324980190789364851288082349097074921667208036518844755233710743624208158407186069232568793687577332891891135060205909769204793547540419736438724970172276973830128775865, 108829408922942286612721982361373572260936023961587946486169403040578253579440829820239010566478578127114799035116326113203711182797112095383021696613374475555658419352073960982578022913638292695421891513852370755068743452809789583651874851084460405580493329353438531990864035467217374707867753237831662340107, 136082277584358575685361011661023085616417237875634179263934704936748315191376928549108194130709358128225664890650216073807367168153144412681870265723476036946837931149035233619755229818204514469041841986545121479167294681734086084733870313961011752655615997585957760731230746666214789210698880358229532415019]
double_alphas=[35976734624879755076455546910624448429959110096420446915522201441214317873079403405124151580270840526492943605740690902430682201738350736215988513774269809076824070253694907241328151914110223882223519124576652872065762376686706012584107268294871909276147135161647110820491522435257355439956983009752615225316, 41929841433364620768930436553939939226147302719747291382882277807486429362374305549200095497594235040370231384277903931053038815220394948440924879470334163225467720360310759024975422849054739415395725991044381502099896399361289805538946601577381059204483874844362784316221294954614171482991957931485813308579, 100547449434142104055114023443315037664493224370916362056937424202176345896609659825070877543812641245277367713064783150812199320588918807953955650569145460369545472494020828621888898364519792631370926183688770458407520869099059437179429342181626401659569553655598330646055509026472527160820737739110878236137, 91518817961778584320929039126279744748940103953769587691825178329705657874684773624316790802396345930926479866453006699915520928582307623610252570796031434001820668350009680289941239045917208419522621120759719064705431452247827183573288040180337187496252847995095834948736164779407456177559436559467020385334, 62316109029508031780652419616264560468599678224746561277597239495871703546118491999216069473026547355949546656145458252722781555646204543526902508048762056616064290195832178667018452846264137349612069453286030414881738989809681189625553529633417168200156045463758802482841856869690681512850398316875039523409, 115868161342525675340016896937309904700095308311039634169749090137087394203148654309806058770246045028348096758474128772639352140327181844581828606266074694049857703794539626378219869823497392326000342290381935026784451322642140001480009767807203228335741924648224785785918503256265049290112556572045761666371, 16086560834405282091375940290951278036247174390915083585386080415103993736350578660099670226864434013444530004015833441516838220163021736309205431717757797919540626073067610694184658630046575345609942776979756194618648293182279331715976763919729226448301521700232385776249532055572056475474870551498347728030, 141575005459307021588084407648402988153702745909796771599597295462927640822173091027699074030629995050118609967694014779262804362593505355390827708882415903781314526593437437022053831158358170777498834049655665462591683454287689365558154486615702566762032949150004109884744132239220334740608769900222567615449, 96881895711292971115231774400582898229460336408567734776758234067609470090604415694667705528660502303056465416290085600662914502502270016645468272256428746603430865104055118751958729087395260239043367759492536124852275293614909619610316513008719031942074448810716094916944698789037732837090885679415532074448, 106790085136134347213961955180572211708729366477696958769234639423855807702823293431846124690314000285731409612719017795170484697598119442174006078713564206866451553921734418845045908826920428242369075983859165228121379600218918637536239397782945473882322256902502267962262388949128175067146018338181596375178, 64237262906961704558713375465849407688367424369343725218424070839236770377214894834760852353334968130824709181617670665428260823173116756879922764250032565901197436821471877498699325239185567340767750533646135872024225664053217702144015558413564974731381186207405888531232968979589353771751906766095653262003, 62845783156553851206350291462739136211462687399996526568519854925680224089068999331307309324615852506217424307051301236421767187527005114044884156660463353264083874693002115090219106937478524166594329809826428932604325191007596749751175248988757038478243208003732029215759328248350643856922078813121789237941, 117030644054989520221802957470544223316754221477429313384830717410184079381288539373616605512466270973525163904234474514571509317794619932213950814149168970599650614591685708235719586343718803640842989407200781802763681542792498064507859763859201178412862436952898741837690157537837993053600803399928209734678, 156366374855343902274634752230450681870996102356245930278826013440402993969950080570265443443274003273932288191405152845592060604630242084227534650890143829235103329546227009099250464620722477565211664143159497375030651693013648813090549078032965889189453737288681774185523747899619308430045018844694186674835, 57918923332317241429999668693508499358564615083472227185434676955255005067055207314205601229604081520331453034228032983015010565219224582119690364210253454179396136787559485001396345310002641870106582387641902625916857028008432062866965410953709151596147542058228053948597543939060228645435617715231248352768, 45633193930929828414386713401863625591395174339494220840697768956129688949062085911848804901408715231245290921225495827382953674866347926179030425951255504112350258934116937757723725213384598121993110281669102865940657853326993888288042401577571370218389522174571287028736533158825742323682474835802536159283, 70792422649666366567754147576248420867486437845705497665094426137043507090046528345939602896037615796018531882554934301631351140490726031240908303280642218440637882169304216206729175459114680415606299114257885513450413364790749422389500869860756341506495048757120512268773595226936220544182508732222278438149, 48528739215257516746775449491370718284155592205449296781406474636114784163493916428173000876180431602689043153521923866039433187364592471745282291185306423644670629285149077643915745180340584222712193552744467862868969301721792068326692809656420036287195343609180926543236413385212714979759367088292306015734, 134569284321762303860634420922505518689744753939099682738804438388007986365217787301946543070508317549258231025825489884946494887455319485933135542581575754167204752690545266068858612808635951273453674583175539981840134461552563395007595119982201855624469978938609828692438316950428018485897224891068651221480, 147679586069710037293289178114385018672442214310569713959936800022589099629926627039224231752647558544565329923294749028387571284423097615025816527180620441222332844888637480581314214781577049167634487990854629380109388162894934646784936186158429771659711763611673443977947886079421509532269541866230566384816, 2640766511029331555549302762192903066801360146412802862818670197997816043033834451652387695255947926172390330726798330869554431037755823477547238746862532023213163183851397976865087860787851411977182817279921536193195213207584969196899949683844509275767082132795549123964915110817486140481196733541817010705, 13357619943809643799559678392194537623999021094029705256850828535073926783373843310224931097963524042285281186063624695644026081373917890998427574447259677342225039171886678464500696007657495797659980863970319028520771708434732767196180204317968655371261529129227353616013889761268613375611224778784826150721, 51295512320726308285655892617044514792893204874689759147372214174708125954380509548709327390975133651268661507913077971227623313439957780730176410103965276840497164645065286649306004797095166919501651558815374845229719558290798722715912515080248435836079534514735907613656803755784577377003359584471488794188, 5998376427560150421714174028484574891417111466342296337287788023345021435021212564757979143030557643112137110417668772738220944197025158960854040073572600685339702643156452664232530867996157096871229820522622176782190901419668370973135038556550398643978514476654003573182778309959292325932984254245617216074, 82239885017193812725844819099621700398562610581637521478254777821044798288489732571701634643779727526519063283530447453387911023097101313619227369077691619594113133792630763990200657565002531095229512883190136680294897911445844450830340980050985395703313686662437003998163656938379726130672479115670573351416, 13956251017227024809944306611520986059246784943055346201343185905745218779409265454032938826848460697068216379964514211312640909189185889307730763981853008646182630165812454068795824166680569362828242403207726355369116814150999874110740080127893655756048368131174600235539138067668079374853661184102125786108, 72787616230402759030225880152781963899639486926040981029892476895566710302259474973698729085878950720946918943027689660756398633255975238966451217320015430723703593875403985161634826218839618019096175149597184978019707082137594738386479537034946690628366496660025456545316066709252885826405142277551905565509, 9809691946987375275388230063563503455503823329470161009741811366961048235752126618679612189863570614295540379930321728024786784117653327227290986637662210533316563807592904405872887559810433371553101316520065601891822528011678224033925821986985923499451436047975327127813032032295236440058317622228296171877, 27425804172289095143067474093494429032970216485813136745505270417995570456004156348545593234399744586643675924284965092723333189239876443263975574466972450551368599180929425206832878706286773342943655458478868200352621321860231818152585723066319475740975964305702744839507896055171524733071416651490971536131, 156146840019461214729565635134751218555741695955421153677396116818657467798939644427776916173638376343491383681350144388073180131386840901579960755694322987185882603130633130053805341338854200770799309566383131101246324896209221985972282042344530437757359339213721077320096282472911825111438910542082628743779, 110584252686181967620214138267450550355373618692514793524435448260892563287967748252983906136062800397855215330196749183330014639760123627401390494582660290439744009062639881830832807688227989575319018880558292603451275479217805406763957399401603714429550051157785214893981581952657960140669527317864786468505, 27677932761748796568630546582704763531623156679453363307762465881258667835012015505262877270146428310205943590935571955798207428723434191063474496920745268408764377544314301450736597712866330348919131232574454679059627092682891387698470697377739962384799403773422020187066589714840143262953492550282805352657, 51516993874973208457649860608327755512042548667174080056934496053342648205507409364823022746122029138819703656898320011798739856892411842284597757073674859607231771427530026978782024963959826326749808207050745827368645517231565199017846649984132335888132556619199355021638975432432968719348254372927670791722, 54294270361651122898452893490559207130765777770203502786624646800300240821134536927597147926091634726889574387545873303044731355296099529307087826339173726311055981562139453930012936404573077320978207695065869897869918005459661493024529867530613348550300900414397308386150135682580324135605918750033791632132, 77488017421949167680650215520753126928767880905928831395766001001290459741860675435289028292515941655870102756918755692075509042862685544780818757231993826509316073070482281687133358280492680848369517953787254614558885071303963402032979366660349456698204080296369064031308740423909983963171997659265414533097, 57652548500079303516717984918989235578710812724320581084480665514766887782392646102399681771777040384545966484100620184557550469480375820835096237770419407677949638307513104322440414363444316217820222094332167123158845517554065594143350235467964510587000401186984316849804180678557373639174701202063170551397]
alpha_sum_rsa=30376441743407240457619770605083020358327364593038851898214086311740828847021656591039214266926585578429330416361902674439939768290731416865031512646209598394537835243441571687566707074614160908195797756824313238963968334537887170500635455862450724181328809238140951460590623319709265869226616018482317589780
p_encoded=(80471099449452624968205295751730888524460741553996297992497597657215211697549806913709807262796923948571814530644971883151042150938045734795330359525899049783096035442032467640594153252890603709380603004118743345482915095598365767899846529558283676670722842204387539447331823052215118214114048940047722753351, 90785745775957709252476591404645638324098559928113559116902820052136199303649556842199070850127940890532658087380842276215650216797317023370001822253263255761532630749769947597187374634421677169016346694409691891564946979397283784187859879813700474274197450114466126660085168405420035079580462958565509914745, 5965366785005534515889132637596331970859971476610528592160659056562856697145934611656659705398363983849561018769627895864290612274264606565158744833326896047651669995966085449904961751367673571443429825241823058603791183336087183721727081845120055326789001448697124084900213371321795041907386531929913436722, 31760079729653511014915597037877381887353490294697227756596603890040422064290031701479127384116273140050090586327411371098278341620767616695719894431032102780395351992907941192679611552583841495797391191131754201561001772871761109276859532173258028172938617623609275905686994485875796189990578533003909020979, 41269953752439631684309420756601921374947830901474121521584970891630655126311139950397688187478564015148471863732092921594026467708192928128603063529939599551179353658408125849157666058187738287412557098347523691286572776915611257271707736497627542217926949117043051608106440900412671687417898398648172408968, 134539758908087404459662546174081618407345337970144850817321428416892688906928700692389687136432352645608147775511691146360886418046816767347334532645047625934805966169916656887678698245628195923721294184952613885586442827000420567496973236266931160545858047808479191029912037002002837839671235361190576371617, 59199534097164109971475039026406192507045362952043735645637391726278564979377853940408349137350172146830195643413660165903076781428830194255429684688438247545978237997088025426418599890557646396932048313995283703459612948692145301651463922984944645347822423376892850647287384894246159946205444364857369210630, 142668218994176291107094867409120677916236135272899532569733455541091205865914816997128371735260318344977912254946836903515006614235547968013379933299858739799378172489885666167337130448475491689028769194176457354266832706887925734108799841907754107664862738064873260391423475184056401359791386161811976551335, 29230245617444079758106014481729918809546440702518378842587063667257842712910354001358088859210493491851467812678352154510516854694474187711866787967202923343679329748544406256271118162719235240470082621421834184954476495195983884467978041380189009785363575061159170635061165218009548496336587665097234368687, 28077612427130351475177150833658372048142710976234828693854836970120575417704833774626109687431496684811728536571557405113938178055692505981995145397227070749140856572142429426633795930379908694194139519895017079483240605724111989169161392806313495168661584434370082811275898124623624580355450408631274259358, 76448103435412300926608179088190472615011809978116294716618039961675317533032756785363788210216599766269129023705196036187648497830939394215779401616200550923701771923710743240974704032773674379934364409446538077617446146459334500024683944431983283454040349470541526859545716428532527043778313285284679910128, 108269188925272063962540415598388652539623036634338694129192862312641584520666587383979062314892397468093763578008725486734596212500991617371536115930242818646409355478158365481901063853095085412542527152880836826536041980108399389488811907907306286461495260428234705013798146077552607655447036284355932515712, 14095111009494820656584827499875601696439630472040509228585937371159061579074282442723602384253950471341251736097476902060180086728895295754799731620825936822863993179433854680063959243786086505288496405220584182820955522166484038019124879277745241315474534903540544240126395182755860502041004969941632063141, 44034954309487558014434950569728607699072863629765317505822332782599674014141619044635392294742641496294706892668562745034036406442211455900633915296435444968578964064990807280676445141702798230001246852814342825710953222137864863467448427177410876799970750030062032477612212343459902751758012251171704714519, 145092454710486842489502724712005852536049629211674897802347391925004671189295184110099055235003682967611488073435275438573519340999311894802290601175003017067063465054827249511720391054161322169629030591223223764940784650088159249530034367740863028089734948942881044281891573528150542598319559315025955798226, 31119948216720513479136061432228526560948445331186705049414470835147479515481258611504647590076330317241827347846428347233257984975302095042416052543118246053638312958880712148441776512443097523358306469794102289248911466717817169602010988231689113387296138088738341161697087587573436927135535070329985595867, 113910544536412437906979684084740671235172506108121007747253458960364586211068492976465883633312525402666880083490086668914684952392786164358316197632355210580245424696296070905661302021563078522256728091962416665854963000839549668080384435922725203069566964917484014969034932347049761291800289239172447123034, 138980472456552600105431597101851850174623115389900514646606154329752721985236695108804305716446563934097218727880853244496051957089629538725751610187549106702228057342359475783209043826864576279524843214354385278562428194401996290045141809672319702892635636333342015513111651830161119505450624974471534512938, 99547001998212505235294679506451539263612994846346926640391653094478320752390115245365086222699738926008132583522255353735104363807933086102304423235629109750589713255949437137352112008737253364724947138492403390740852935501820443949714296762150206037582566290610493394694476240189613904837869364602988749116, 128116248118460617542222941309288663909890101740305445086783214999514940518287121235275892456838214525340291585837625323587131782796435735164641109071938614115208387428926940117433366695212520829643624459655067356944324578559507564855546709980496558613684222230004451410315676477132876396815371568645291183183, 125634328319139704686177238413145894582443512839927698324665828925833375196297624525696782242333641072330610392198278682826921370007988857356031809261595898191013291397638449977666993759786510924708864739171723834421119695871826712027234944011249090303523404538694406319713968286387489261224774929705349338712, 43014126347327199476732134625007873637009086447231410782230664180258375295658231878432865318366990840929929651481317540249632963332773666324663637492906226322960151317407544401045354550822048406469872821293941519038308411807305334105320016485923491535330655313617154766476874942536354114396055313272678108330, 50714247647041931454372920173256605796981129712736715434901470296629102639570736250510140594651958385978936108043372742323606777690367326916859093251886722350611321087087208575859978297554165841248882877556552629337192332871483310485006774563091850680235901099168149812208379862405928373712744177770430455054, 99696176739555253009556924676403903294295279959100754438111780351016342433261305918400413594102512024312796884198846085569468445879909151325942848711635073218921350777734121498696812353593003336529754683660008260561595413208269078035261676366340527982900490824685774005160435596605567782137068595698635822146, 98918861969599773325911296078432425147196324331083837119712208201093292538314353072204384690379806975774232816402417305854721976264354820958868496192954669036966910735247731870749492686091886409756691533926441265174109904957528674808951951874732882202627926559346767091117850255522750251236676799538661865492, 79796797021066003933769894676548293860432652437721970661577368791925921390254381086103447420524107778774366365811040475066863973590662049921313503799324043758906731363573523438637559718435449258593380752319883732498983804677925453295153854871366627151026631556331505791896887054831315313465312403093487258192, 106017554059137051618029161069181027517251330144385729137935523197632201512644057322660243298658449804371583006111780382341699054758215824045878374024176412815419290753845491369383165995154307151900868313084020159497373604632053430369540571077556126488005052742649871431580002955237429164780066663278670828419, 51599438013187689115014441414570278339319329143951150377942586775835515747195159219390156915414842484381385182644604556357730271058366667056764092416499070123342477833880058274928704008547833013460272285682031948195706189636264818213416677627924184311474108473562403596199078038886370006760492663488744867467, 46132015805514609160298575829508830618527269068949383302345892467793990934138068955280592193053385926364930984734995507158642584642677310192393801339018946948063548869075986728649085348679018430644078937535628095594993982460985798076497282772665224238543277367743606212986604632894002436245312027589194737891, 126401138189977864234610464974598083837862216453461072374388992110042910011361616181138178359964713526219623529490986794356666568119586853284486711968627535081832950291461068238381616642429429345019096606482292381994277992888656065068924926448098732132896204635897551633695238494270400391939595115526510552399, 10281560500372807074407372573799521881394549683702019209780179961615717342016603632547814108448235297496649433024087808977201140766798457087752435077342372142696332134023602999748114959655036962618960469290325435963210869396609352811647615878959105429808598807082144041314880674683002280719539311366724801964, 137919066308248846311616875335806472199469948624303720484897602054394336279776055900845911641420587041515951438634474181337628157347257533236771328176989320127115749750276792206783890960405851596145947102528554103822819044323637705379928407920109673104435074433910362881046494164589879296430165077747100779668, 145846450560964212227381993169517108441152443037898836602469909724428902009096378733085748189789244945054039109548623990101893131530311110303610025907240729169797748344948250754309618946407306371396572200163722078116791196711652973769232610458081466821612979469856782248420179045056511294747411994451398394941, 99937982111959810492662783532951188277701710760388504517160775739370191416248823279036221559793783585936444076178125957769143547719063404547153951825511074064739112553470180338929908361578454060689495265982543226596568177069303575723143017847107225559886026066494070459488379119776783720807730297405064248675, 149119278796268131265018313368050492456775758545603645038994609412380215491006639827036645098730433126610579064087071606399683790835721713308556666762069586261279556445455599248690711721297326472450379671172354368547370232416506441153106741019309922273832474333593057836698019114078935800429338889493290221474, 129500315175863684585786657749872353045559334482767613816680003271238079548048065045747411490432670510493319509044802400133680469511477375147073458653233176666609626591994763097434777050038938247789062259664789432895686383012873640552540942192037124133822474432941730079278253683433402163360351643891557449197)
key_encoded=(76704451833336425538713426431421069765487507997951702075405229056526479923448290931959496666748428036106544166557413697450189500863720585442784328912933804534608933194487567933592823089237532053535843319946291738770043588669048281263739612069832072688120184620673988050942640268485370522945124952201213333656, 149761724521319321701683921745638703539798020929299893640337638944307488032669604816778197271596279479609799688012332749565237835474830450361091973667944558109099396001018338097725561323422673672208279632456910399814318665104286178559088309736994668725226115994244804568178096004359287610174890705293056706008, 64266244358847249461289790457574291480524072987759266218757655247124992116978859848297614015756514457875140418862051247490813455913312868838917932880264346031212900634221078878226546876418640064598831911579123839165120465364206159567390610669455310538733729062637769842019684459337611542033534399481724470112, 84871626643611842953174939125607520766622786203262687515877490427188787260981649877080982659686767307165543976576236117351526611334699238935853440011196533316103235850166192612321320295477499001019273314633242187493999094145573886873527704714516795651612991093481514572362451658593344347962882429480340178200, 72298436622346843766968433028513715848188273045687556504293140992152633751964163818578696546632794794195383619270989418883434674393045103129872155420186945590632839913970725772602998689638551948180293746387578644625345120244831799234828666845498824014978913893049575643127345163038268454883207367157742695253, 134253607684057553700547885198292104061360185988665327462071433996167343128420972485432829842258242896050663356007353627897930262782428179001461743730785497404288348539750634861379311800511211622914701747760638225374200890321227494575398839898255701271146194499962911674927310515082260210500499779339783598155, 106463100508483737985745961120940712638110693982061567805515514454867552296824109947006429543007582000906381330404259058230547852021138897913134749698744287360633910577636961158937612005339918963181883151642513963483655451533423079356382788424609354924418985067540039622429962057402299680479914313968923730605, 76907169085856562256062975847508800538121892994730614001973122876771418407867519834641271811837307658020983789074364586616227975778003905906973827585705130339178850390653099540233084272789328783712616718041675207238652724891224751042178182454607831332180161213908138993847269481694256088816187421186562892669, 136265701759067443528409431798971967320011753179240159515408896324451176393662178295284565340891393225741595403812063195921928111656151659467329546354264828003334500590400145431255304109030893425086538148925039386309430745952858536658736809815454061174541933807856062369819110317681291561671791017729232652767, 127067774167762843700750307200704195020810989797064375709113484960055006924628060407804848582012387771395613894518823181147441046213582274875098903221285380221942673871884013147969214632693106064188338464391915663665144377225365471418322914679005998678681077045593415116162566405176058195084494644632945000752, 71888295025737721604356562221525423962536008223297350115014283531447916080119453228836519155653207511592746548984630896267715339110771646173680927634482506920325784805521148160143724020132502803877311731863963747934605100431193584224165695596775745816885467185355252739440999363729513749108261281847900405139, 80854063813740570092632421058525147785609703609053423372606443915339094457122325467824747808681094410564692746402208496942959037232977629402296020475096299673456731629167069474708124517362842855356175707927663050995832585396070601562437629260901154561013963839844123102919398742793144565089470064048987506009, 38301641448059630089959590622564998196751518576964070736947827124033723462081758596673706923128254188724648087582450482865731792946457087582151938121411877019899594624443696551754045706997214821505923276835645006187974213494467466669045305727374235336957621787295928134232426614663148091177593812093638765913, 65495087155590299726385084342458931937782542872110838766539481280007476382315908938832504985106308991284859245548438686541486234366188152770276987108606816536268457209053530866618743989663715917008846124033437453842831021959233141221127249152891452170021303841826096749590245057625680354816975685475558861492, 28919763047505361156482237586776239944273040460456210687183141770538058713467835984315176420076629329234892945640250981931937548617695251948016894955919717292391650130365776720189819627884053764814346538512177659459442533421236320279860091048223702631698474791280824555213668366240275223020760437161454189171, 77059639123096187703486451454097511163372101745278927692251119049930336201732996751702912282630344228642312479433272692271050946267820833945116510902643644502377649093469763106058542957273262433818090666938756469624808860650884570437528384599255529627925731819242003636144110290022246589085383989355528969858, 91889275896310353880089940804552622660650756378844602245174179021149522821169662152009052009788144267450472672439753943217335174845420816278819536000752797277839355014503328252631377282432562176151021136424450754077677429143612080759253159034279320323450515741612663468478179706755376639567371172439288287923, 25242795192083011389690942302023478809108768972884919973250187015881968328956115785269908930647825675449692117580024174248791062579792310965238206446601123051482970278998772747266052690115125421921288078975019479396831521500654023014191471975576498675737057475048585343565387970508265889690411607512334145984, 129483156275628919045068843910344742452634009853786810947224080028111426034004518795335338959165055879455186330976620368854579468497090766486038707694399687913687519074384468509496890836567056356159313857450234213948043650074493112096833906165363180074073985807407567563001385885850515197061156634141788214104, 96205536832301614228542622457865608379171522838718074376622339511222565676052146989267587083399499161872161455915145258558722587580542455339482440721363899166148236386636501172286111572267712759665877802843312173333404607230101502712504060863027290099443336672723202145748397970170298672418650914453569496480, 34214123818957027487235696165456788275122830433775370926588297071920848097367879775077647056055155815137433678804051229927164948818328785307889860480901937051145851130353074493965192373966908843566789841612394158728193096913271753729424954106193911551638199928045601800797792769451642861799254913080877452089, 58453998837137792877927822027054877456323891294944545218158805884472798788849061534149993577981670358217497109694766840679008027028317573869896598392700276580063824575700483419080413997755816203512526330953016741034960352885988710734471812974374429311167632156219016900889993909604249968876560497174599100986, 76808339877577161930570052152108758154683851354663227121285097131140749316302938492853193259436153158132309468690398975483277001982397783211313472166367543469610028445057958548411009023169859321679289806716265477397578832569584736145432700319763024675450237296677662759453829795224021419404260244288916473611, 25053688173095091949405065786991138801960414066093024733236289606864660177971198439198263692564931372606721075454651128106418672298013310834701068730144916992752719620619875335527842250958405897770039541820887425979254725158557653395178119648595193202023111136751688342296371351990179311557018384788206831528, 32424274883869564925790140288498473830983560445056702342488740641169884341274056208014383972386264726136046702765838648005703824879538238456853559702277447994098059604285259473139073228584112125595918926490189795891479767520976306684408188305376003021497396702605873008972130464741822181999751841650309689123, 134257014938152895322424925946076829566706358409006636878618175853547371390955126525150852433387811344940973499514422225104796362680188263359231547118901194083821747207822173450244175421087507551198340698977070951169133175131254738372199114111012977159352518242275021357619599731277645700792289154373144108186, 11215075664875243138148403065135421928804599126381024390890549553509554552370709194535922897375053006709308147573721831668095049316429179261979881698863970291619030585654036248978091467507086601332716768843126874831773114868028691357632203523272974552461833817023679263512264806759671092387187411996198137682, 5330036745470346120935902037041038451780785020343674900454075964716031796686173576529578530873797758496417347502662988138294995119950548166142570479459138063802407552952342537317346878678968180843852658575847637390666138327777764295893252793189523281931091103341597506200703627254553764907357005843567133559, 17617336526675101338092420801183690990560271557355607459044651092902587895170613851043844704590400080525325529761899479020091160215244613880923054628297111895771396828021086608361694280881239327958742392940374518060462645967667769318667205663279004203996825896212822574717882027199873745965039614821475554078, 91057523774689545709233022720011163007405589788778964784432423638363950393584486704781627020700227005133236097123348446554298242183561091739857590519485620266300795039617480675240056657475479881210901574242149538265045273640590523751797666680168537089462232597727882709804435168791893080355218744640941558468, 15001417866949649838643123667240907764404661842522385593088786586374514839139643844061168747108762751056141090110032816023176060265663012438050816537320219278476854874032410679940097404049958976091575264500817359479553266795117409998328433902940343589829871676736734718931403814505351358616434941481456232909, 145819066124732541043717544054700310546056529912569133450585346323083818808264397495172780481687060805190691436305725169311934071854529682012708140045348839626950731728499009922031205672986242857987792715698419292821309463125246971899460467326849832872971616638501798960669230958581718110612388845455129164382, 150652204632895996999954449201970184498805985347817776774858699178504376091050711224227581855584653629915707887588415918920883023848269022049448333798740437073534136889875717369319995745338664799630034320864093430859053088843571274857588314649877111704096399768421585509155210712177053699818931225912938081786, 115876732699846874110668745722046281157743035259730623617778606378847308744841773135917465033570847055141227718059128425734479323445115851311322399608811967370319428614561344811318495759746029733947656399797755298945069785442800579784259372062514025040099570470161244531849456035840394751485269479931063953770, 122805959244041853046688913145020181212329972081953394969010112779295820655709702323447328304248313063494772403682600167285355074747182890596944488496564283674465642016209562449913064367429643540374717088360929282152475527209557246904824769542336887114800552292678187426408902241602543236526522851617472814523, 161057698155174109215543668628268941051233925055577515300028938528029990285986749627195675947726516271271228281180724143007120008722366109155554261470482841537775049847845968965485525399747887417298657787173257630517340643866739581867888234688952204127063632183105719544811286422800035461602338614550271278274)
encrypted_flag=b'=7\x98\xba\x85x\x8fx\xb4\xd4_\xceN\x9b65\xd4\x04\xb3\x96\xa3N\xb4\\\xd3|\xc6uoj\x05\xdc0\xebB\xdcG\xe1j\xfa\xf3\x93\xe7\x9c\x06\xc1\xe9\xe0'
コードリーディングと問題解釈
本章では上記の配布コードから問題の本質がどこにあるかを解説する。個人的には数式に起こすと解りやすいので、それに倣う。
まず、chall.sageで定義されている変数の設定は以下の通り。
\begin{align}
n&=36 \\
k&=8 \\
p&=\text{512 bit 素数} \\
q&=\text{512 bit 素数} \\
N&=p*q \\
R&=\mathbb{Z}/N\mathbb{Z} \\
\boldsymbol{\alpha}
&=
\begin{bmatrix}
\alpha_0 & \alpha_1 & \cdots & \alpha_n
\end{bmatrix}
\in R^{1\times n} \\
\boldsymbol{G}
&=
\begin{bmatrix}
\alpha_0^0 & \alpha_1^0 & \cdots & \alpha_n^0 \\
\alpha_0^1 & \alpha_1^1 & \cdots & \alpha_n^1 \\
\vdots & \vdots & \ddots & \vdots \\
\alpha_0^{k-1} & \alpha_1^{k-1} & \cdots & \alpha_n^{k-1}
\end{bmatrix}
\in R^{k\times n} \\
\boldsymbol{dets}&=
\begin{bmatrix}
|G_{:,\ 0:7}| & |G_{:,\ 7:14}| & |G_{:,\ 14:21}| & |G_{:,\ 21:28}| & |G_{:,\ 28:35}|
\end{bmatrix}
\in R^{1\times 5}
\\
\boldsymbol{p}
&\in R^{1\times k} \\
\boldsymbol{p}_{\rm e}
&=\boldsymbol{p}\,\boldsymbol{G}+\boldsymbol{r}_1,\quad\boldsymbol{r}_1\in R^{1\times n}
\\
\boldsymbol{key}
&\in R^{1\times k} \\
\boldsymbol{key}_{\rm e}
&=\boldsymbol{key}\,\boldsymbol{G}+\boldsymbol{r}_2,\quad\boldsymbol{r}_2\in R^{1\times n}
\end{align}
次にoutput.txtから以下の値を得ている。
\begin{align}
&N \\
&\boldsymbol{dets} \\
&\boldsymbol{\alpha}^2=
\begin{bmatrix}
\alpha_0^2 & \alpha_1^2 & \cdots & \alpha_n^2
\end{bmatrix} \\
&\left(\sum\alpha_i\right)^{65537} \\
&\boldsymbol{p}_{\rm e} \\
&\boldsymbol{key}_{\rm e}
\end{align}
そして、chall.sage末尾を見ると、$\boldsymbol{key}$を獲得すればフラグを得られることが分かる。故に、この問題の主題は上の与えられている情報から$\boldsymbol{key}$を復元することになる。
解説
もう前項の問題解釈の時点で煩雑であるが、作者によるWriteUp記事を参考に初心者だからこそ書ける解りやすい解説で付加価値獲得を図る。
2つのベクトル$\boldsymbol{p}_{\rm e}$と$\boldsymbol{key}_{\rm e}$の生成にはそれぞれ推定が困難な乱数ベクトル$\boldsymbol{r}_1,\ \boldsymbol{r}_2$が用いられている。故に初手は、それより前の情報を用いて$\boldsymbol{\alpha}$と$\boldsymbol{G}$を導出することとなる。
Step1.
$\boldsymbol{\alpha}$と$\boldsymbol{G}$を求める。
実は、行列$\boldsymbol{G}$のように各列（あるいは行）が等比数列になっている行列をVandermonde行列と呼ぶ。今回は$R^{8\times36}$と非正方行列であるから、$8\times8$の部分正方行列を抽出し、その行列式が与えられている。
Vandermonde行列の行列式は以下のように簡素化して計算できる。
|G_{:,0:7}|=\prod_{0\leq i<j\leq7} (\alpha_j-\alpha_i)
ここで、$\lbrace\alpha_i^2\rbrace_{i=0}^n$が分かるので、グレブナー基底を求め、等式の次数を落とす。ここの解決が本題のクリティカルパスであり、完全に知識不足であった。
グレブナー基底とは、多項式イデアルに対して、特定の順序で整理された標準形となる基底である。例えば、多項式集合$F=\lbrace x^2+y^2−1,\ x−y\rbrace$のグレブナー基底は$G=\lbrace x-y,2y^2-1\rbrace$となる。
簡単に言うと、元のイデアルの任意の要素がグレブナー基底の多項式結合で表現できる、というだけ。
これはsagemathでgroebner_basisというメソッドが用意されており、これを利用して基底を求めることができる。
# 与えられているパラメータ設定
n = 36
k = 8
# 環と変数の設定
_R = PolynomialRing(Zmod(N), "x", n)
alpha = _R.gens()
# 式を生成: detsの利用
eqs = list()
for l in range(5):
offset = l * 7
eq = 1
for j in range(k):
for i in range(j):
eq *= (alpha[j + offset] - alpha[i + offset])
eqs.append(eq - dets[l])
# 式を生成: double_alphaの利用
for i in range(n):
eqs.append(alpha[i]^2 - double_alphas[i])
# グレブナー基底の求解
I = ideal(eqs)
basis = I.groebner_basis()
# グレブナー基底の出力
for i in range(1, len(basis)):
print(basis[i])
これを実行すると、大体1分以内で次のような結果を得る
x0 + 101167463165697523840879155236135415366380424009464416331763855106184994633902302674087295255438751596774946284741606345729143993302112286520469294367507812315056318317781265297438013015868686890078715661635388273272226617417231986427962523043300715969264411559608335541462289882989793354071670690306513709519*x35
x1 + 99816305691223099820353394198653556348673685338452752390709712662751963955018291035690933586495874204856425012304440226888304154089937984356244091799405992883850252885469253083907806945264024073842402938150768910238393582861876052386054944373525820386502846106714272089979496347781222903621586813884929103048*x35
x2 + 153947320566716262616994979410188678739855205152591327118109633632831079874904201207623989372460852121565808503574990737588802732830815358621180239941162812988178974481362876713673930653580228231369894797024458703841541697777606681268859123289780674638214333073327446050895932236334966741881459108747047657435*x35
x3 + 46659399542336213068024332009916486689825094553632368218365813655034953704942201817568253854157064388245504166146407757024451319917309905700295786319815343494402735002513497971306030063356005913518426592969826466597642398584629398113879014642476295408885955358537717006874886186944096839620200644124949825291*x35
x4 + 126970603032089926662257849183463154484387763986070588029799255070985240096894601764925666146524415192970609755156080504028700396130098402820906150916788544913930045321434831936552231144039529166191052308107994701462252263094518074205134172570410670618493241431989836612834348355333485705234623653621004090049*x35
x5 + 115508394461131230434265966592562541441480118295772381987049022892631341735888736661833392305223610800354559625226453090363759949922425321895315817754830944546620788649219943405574821438913838372662290595871423729706145914427966586662830609575957494588845127857943228556269621456937457333123492335951880013037*x35
x6 + 67870041931046547730445280063184797432293459597028690348151237822083354786352372718957590792733098879508930013579571650980080382835547822977122585570672306974838997440709110285837607224398908231023960827174994279282071268896069837414435498169117619888694478279062781261004824001371533611247008055205968911459*x35
x7 + 24398553029110400376703693451598141230041748203963027753191289213504745783444037069778370168024500310686272836682845403565282887410606919172609212330959626408043768540184381448069840251571366868345255466778720294684266113055942535915213333508027112834335738683622297868375118088422067594832286774454759842780*x35
x8 + 12183761451807958449093612944496848250760712223750397113582125081291204485939043232204005669215344544643108606104447924194577560518784865889965010974193756466598588475400518141162335642468615029937654929450511699685166375085399707022464256552429379363061684027996282179882233590027951328871071648738057153701*x35
x9 + 136283395600439917762324069683672425665271905977754374625741131631131381571945057306283556066272014713727191603504096877650248392527523580321540494478740292493256825563175718922625778845409304581876836565419832229110077250744626830556637936342385375785528837147746267716392030441762456697992109065716762836048*x35
x10 + 137781388677775019803167341660564763023011205486809068857350068074131777057103291880618696729192482660745136169006276238378360485406598262470209434413326476713818755314175276254071566041358067268989295529524825374661553869756837620775030155881714487194281870539538723842048716551308069536173876572884159145482*x35
x11 + 40022447050170079650297640809819914302194290183536692135687103304165226444531161643718985489156073578920524155702721149712467375112689527001518993125569865857136384760421621984994086354910186848710811862555146167565150643424318406707224495455455163366011675124228370243454814814469803353940490802919570540933*x35
x12 + 120966263786521814150852565413458405789011054034289779641706161373543567247236870407999300175434137147788193262998857460937305136683936270467172487642423515043082666652377496706733346560628844290711324874759575204387651533624304598192790954517777168994380501673071117206104948457691832034877688369566421276268*x35
x13 + 132961122689503792816396489813923533463353337544160342955427114699234305107032411860513530189794430586003314752218764427771069425571581230545144561573353395232729356644428585242872690321250270908179419633138107628038110692315823910364034651326849554101358397266150258020630476684609086641161097523429444286907*x35
x14 + 159279176462545296578864033595509179410587926582287026147036009880694615378965287189294803671179500655532991093569299834618333127739161076476842432855898314443078790400762726706488087765691808008455184565423598329679576799087334897411704546553884360243457644895376211484147015788224880607598286047304839569871*x35
x15 + 34807169980868726384973662496932373459025513195701386614403820227055411517151000671411095813528684636234527525283189460384821010483192915224093633698162756287836721166194219308354937612260372915060985133526124654525090877132302325000590360591346630570436251943255560968791457002066610857941700860046755639841*x35
x16 + 135941728344653619168554218682054406788447973928907913298435906533443461858841620969183570549875126730938204966328461536238552896087878757176993616217297870244396790709012585329415344955165710927389110978839472844878749793985217744019769063812491347152364172608900369021723053049591937966849976280148886515157*x35
x17 + 23022450653512113672763575288134457870864337520509152439208629951172177829969804360160254743445480528009804392118930762486706506600390483535195366718547398013829547169302737942011656985108244803051511900748651994722440069444977444110923567969194631813096457367853783284683870106054183475113035069580343560954*x35
x18 + 109497499101385973960478956409212368393890321828294047706935450802449135737197006780594678597172915930516852803812780034628215320105893463771426189888943007254092358029997308546512896695266765204467861856963664286070650239788165819844446851134019428832918009318674952192115339660095607238715708771569399215838*x35
x19 + 17649284393596838928927278310827176242509215110644386352481639332148633331772347689769852584315177880225227383888817435241415960568928130205087247521716901944147133976065732030250285301530147525056521201283295287128161451737388744898326241164907663755093951709088748838147576345829767478029082772419477723781*x35
x20 + 130320272208550606000162249968811128701555128924925284832865563977090537272377093511217362483670891200613682176584857884689416065597281384854023729012295638738457294788171665924424141182979840209635991697860390277375640005807874613276565064742340398294618866435972420736846325480518954404493956123066884546272*x35
x21 + 39101123999524075418371960194638271743945247842543623447599791358827143617840360905870500131725384519168233959470166267524033392762391083565838093889016408920456075067991209702927247019512513546515882432963122922769961496979348926444647296430777023918416291618593981106143559529205722916065184006818114143303*x35
x22 + 48199732797571512474381843081410642427988233761233604916182072056585349447595749822299392864946822100642530711165709824205455392635027910363323358595484450915165289735674539072077220503789629362663719394601149021693838846631179978798887605892673834170072894903988402483773925234470242983441802495439924061332*x35
x23 + 16665194243526064720137259674313963879120151991839610727414651302673500649858162153221648993343327185421487162449640330009856176853413856967461418999586870355231828840663851832997872589063688637889059215891619469462813800531907621060562700092290619760698514174163532494467026612760958067638436267540689263990*x35
x24 + 52249003167873639497505287660809803154813283271579860201446532098065066334523207283836965218945451995068094803937471963191889335735593020062213461560738874871773486303345263057963545007413379053318379626696793620196796750586781773365596492318231557324461271284760629230781162323519744938214940310805490247065*x35
x25 + 137793160780300611942398684838285079654158845540611353325901027340927100276010203663263055411134425794690868511147162746881189528295180032035069377375788665843850910615210644353422755227661626965661647124191627395094177496527126279657106471221142126683650879012630348182572396862913331654771241074468185614681*x35
x26 + 41913542176762718356180572385723273028037257322465353038962822254259818024858416922770774760302862807725687896509935715213699378001675000630014920308214991620727341310184703667882069399318120877751389776468482619772868513482577491507627658526865403548692237621332762006400329001675838717069103279036559905098*x35
x27 + 62499604425532139090540080719016290220708831784300706804453856969496109915462948489408851823031600962920651951049072871907217297846922891646886703161773184243984497097235420859868105460655674556771640108653411674397899745776925124142023521308515481427652856182154838392133714134935964637738869311200221013778*x35
x28 + 64812852826577729459296495819920124605061016861309162575638214007028018131310793406676855463378160896786059539813356624395559458465603826738084948197251067308637653681669233965783727763766170746923609307367066177475560251316993122498159586658613976593096131912069745844256544973066144266318756517658323906500*x35
x29 + 13930505220178812499334344928142906427788623106541586177912703458685079135242433252765674734277964006514138316612684583911134366015459508476011088285309323729658492226054360270637134300046620962139384065834504865707162953990027570442968896379626667891650442155917667277386210140165597397650993677709524354325*x35
x30 + 163789129881499257485091385047599447721323694888054183410183277442293261052541374857284497237962662620855135939824622988307595075856990986582012720735574514707815264844799567498465207543168009051376756587772897126378687641924329456116477049835116043182077902161326553265532816878880281512813885409158321330823*x35
x31 + 141078286128291606630886906203072934632408661764128821597920658704854485805633020806957657713632945031290388449823774821488941714667731518487834565143893877341057614024612832596966360591884845977083196942329404619897824672205188951576866929732021840241537949541270166963322437279028125919535326441691197810631*x35
x32 + 105847412828833745276717423602257876160277623745479589037842892793027423939057283725332111575662078806330258478369209968258679073128534166930433256734995914750252215493486176720949241044095285350205653833789446170058359729058614890245422133723660613956809251535159590261672237566016682614798340416609229149021*x35
x33 + 45711862805354534906742779943507680355899773895103554341403778288529200700102287317028309961984299852963160384174308242754253285488661259924287664351789425051741871468721865195752710664200735393651489639562227565996851319843150600380563120075590512281290529230858068062579443028375841475355563912246241773652*x35
x34 + 139803356432184693666278113668310134740282635727294542044161753517704900914391647620184933895031484521623703972833683225801039211863739895484987908680664234735385294166422528398624690126736397141969179835462084570613942444022749094252175836602057186156665379674145616238353698127375512970409990421704117995781*x35
この結果をよく観察してみると、基底多項式全てが$x_i+c_ix_{35}(=0),\ i\ne35$の形で与えられているので、$x_i=-c_ix_{35}$のように移項してあげれば、alpha_sum_rsaを利用して$x_{35}$だけの方程式を得る。
\begin{align}
&\left(\sum\alpha_i\right)^{65537}=\alpha_{35}^{65537}\sum c_i^{65537} \\
\Rightarrow
&
\ \alpha_{35}^{65537}=\cfrac{\left(\sum\alpha_i\right)^{65537}}{\sum c_i^{65537}}
\end{align}
ここで、$\alpha_{35}^{65537}=\alpha_{35}^{2\cdot32768+1}=\alpha_{35}(\alpha_{35}^2)^{32768}$であることから
\begin{align}
\alpha_{35}=\cfrac{\left(\sum\alpha_i\right)^{65537}}{(\alpha_{35}^2)^{32768}\cdot\sum c_i^{65537}}
\end{align}
と求解できる。あとは元のグレブナー基底に代入してあげれば、他35個の変数を求めることができる。
# グレブナー基底からx_35の係数を取得
param_sum = 1 # x_35の分を最初に足す
coefs = []
for i in range(1, len(basis)):
coef = -basis[i].coefficient(alpha[-1])
param_sum += coef
coefs.append(coef)
# x_35の計算
alpha_35 = alpha_sum_rsa / (param_sum^65537) / pow(double_alphas[-1], 32768)
predict_alphas = list()
# 他要素の計算
for coef in coefs:
predict_alphas.append(coef * alpha_35)
predict_alphas.append(alpha_35)
Step.2
さて、前節で$\boldsymbol{\alpha}$が求まったので、元のmake_G関数を用いれば容易に行列$\boldsymbol{G}$を復元できる。
次に求めたくなるのは、ベクトル$\boldsymbol{p}$と$\boldsymbol{key}$であるが、ベクトル$\boldsymbol{p}$を得ることができれば素数$p$が復元できる（=素数$q$も求まる）かつ、ベクトル$\boldsymbol{key}_{\rm e}$の生成に用いられている乱数ベクトル$\boldsymbol{r}_2$には素数$p,\ q$が用いられているため、ベクトル$\boldsymbol{p}$の獲得に焦点を合わせる。
改めて、ベクトル$\boldsymbol{p}_{\rm e}$の定義は以下の通り。
\begin{align}
\boldsymbol{p}_{\rm e}
=\boldsymbol{p}\,\boldsymbol{G}+\boldsymbol{r}_1,\quad\boldsymbol{r}_1\in R^{1\times n}
\end{align}
これは所謂Learning w/ Errors（LWE）問題で、行列$\boldsymbol{G}$とベクトル$\boldsymbol{p}_{\rm e}$から秘密鍵$\boldsymbol{p}$を求める問題である。LWEは格子（lattice）問題の一種であるため、CVPとして解けば良い。 参考によれば、rkm0959のGitHubを利用するのが良いとのこと。以下がそのCVPソルバー関数の抜粋である。
from sage.modules.free_module_integer import IntegerLattice
# Directly taken from rbtree's LLL repository
# From https://oddcoder.com/LOL-34c3/, https://hackmd.io/@hakatashi/B1OM7HFVI
def Babai_CVP(mat, target):
M = IntegerLattice(mat, lll_reduce=True).reduced_basis
G = M.gram_schmidt()[0]
diff = target
for i in reversed(range(G.nrows())):
diff -= M[i] * ((diff * G[i]) / (G[i] * G[i])).round()
return target - diff
def solve(M, lbounds, ubounds, weight = None):
mat, lb, ub = copy(M), copy(lbounds), copy(ubounds)
num_var = mat.nrows()
num_ineq = mat.ncols()
max_element = 0
for i in range(num_var):
for j in range(num_ineq):
max_element = max(max_element, abs(mat[i, j]))
if weight == None:
weight = num_ineq * max_element
# sanity checker
if len(lb) != num_ineq:
print("Fail: len(lb) != num_ineq")
return
if len(ub) != num_ineq:
print("Fail: len(ub) != num_ineq")
return
for i in range(num_ineq):
if lb[i] > ub[i]:
print("Fail: lb[i] > ub[i] at index", i)
return
# heuristic for number of solutions
DET = 0
if num_var == num_ineq:
DET = abs(mat.det())
num_sol = 1
for i in range(num_ineq):
num_sol *= (ub[i] - lb[i])
if DET == 0:
print("Zero Determinant")
else:
num_sol //= DET
# + 1 added in for the sake of not making it zero...
print("Expected Number of Solutions : ", num_sol + 1)
# scaling process begins
max_diff = max([ub[i] - lb[i] for i in range(num_ineq)])
applied_weights = []
for i in range(num_ineq):
ineq_weight = weight if lb[i] == ub[i] else max_diff // (ub[i] - lb[i])
applied_weights.append(ineq_weight)
for j in range(num_var):
mat[j, i] *= ineq_weight
lb[i] *= ineq_weight
ub[i] *= ineq_weight
# Solve CVP
target = vector([(lb[i] + ub[i]) // 2 for i in range(num_ineq)])
result = Babai_CVP(mat, target)
for i in range(num_ineq):
if (lb[i] <= result[i] <= ub[i]) == False:
print("Fail : inequality does not hold after solving")
break
# recover x
fin = None
if DET != 0:
mat = mat.transpose()
fin = mat.solve_right(result)
## recover your result
return result, applied_weights, fin
このソルバー関数は入力に1.格子としてモデル化した行列mat、2.探索範囲の下限lbと上限ubを指定すれば、出力に1.格子点の近似解result、2.スケーリングの重みapplied_weights、3.resultから復元される各変数の値finを得る。つまり、finこそが秘密鍵$\boldsymbol{p}$に対応する。
LWEをCVPとして扱うには拡張行列を導入するのが一般的である。
\begin{align}
\text{LWE:}\quad
&\boldsymbol{p}_e
=
\boldsymbol{pG}+\boldsymbol{r}_1 \\
\Rightarrow
\text{CVP:}\quad
&\min_{\boldsymbol{p},\ \boldsymbol{r}_1}
\lvert
\boldsymbol{L}\cdot
\begin{bmatrix}
\boldsymbol{p} & \boldsymbol{r}_1
\end{bmatrix}^\top
-
\boldsymbol{t}^\top
\rvert
\end{align}
ただし、拡張行列$\boldsymbol{L}\in R^{(n+k)\times(n+k)}$とターゲットベクトル$\boldsymbol{t}\in R^{1\times(k+n)}$は以下の通り。
\begin{align}
\boldsymbol{L}&=
\begin{bmatrix}
\boldsymbol{G} & \boldsymbol{I}_k \\
\boldsymbol{I}_n & \boldsymbol{O}_k
\end{bmatrix} \\
\boldsymbol{t}&=
\begin{bmatrix}
\boldsymbol{0}_k & \boldsymbol{p}_e
\end{bmatrix}
\end{align}
このようにターゲットベクトルの前半$k$列分を$0$としてあげる（＝ノイズ除去を図る）ことで、ノイズ$\boldsymbol{r}_1$を含めた格子問題としてモデル化できる。実際のsageコードは以下の通り。
# 初期設定
error_range = 2^1000
G = make_G(R, predict_alphas)
r_1 = p_encoded
# 拡張行列Lの準備
GZZ = G.change_ring(ZZ)
NI = (N) * matrix.identity(ZZ, n)
Ik = matrix.identity(ZZ, k)
Zero = matrix(ZZ, n, k)
L = block_matrix(
[
[GZZ , Ik ],
[NI , Zero ]
]
)
# 探索範囲の定義
step = ceil(prime_bit_length / k)
lb = [ZZ(r[i]) - error_range for i in range(n)] + [0 for i in range(k)]
ub = [ZZ(r[i]) + error_range for i in range(n)] + [2**step for i in range(k)]
# CVPを解く
result, applied_weights, fin = solve(L, lb, ub)
print(fin)
これを実行すると、次のような単一解finを得る。
(9223372036854775808, 10011698429908407706, 6761271655350118204, 1415677259903729, 14108482809754601284, 17258777423838930995, 15106876040087542186, 17288141621171905777, -30222116295301703885, -46945760495513522978, -39679625554798067727, -28133907143563664599, -44610710900048643097, -51497810543811617012, -35206275345242319901, -33888118372939752549, -34055047484592740893, -32124206750556415419, -46425118442993594948, -52462046033178046930, -35249582734022447612, -53424617079017493403, -43324407500323853744, -42844928166275923048, -21489570172857138602, -50989885435722342939, -50724242587674755493, -32938463333736805032, -30458109553295189775, -51324698944835479749, -37330435255897091330, -64841475984483627980, -44637019622252870643, -36762258754518325616, -43116724084612401788, -30846319796129435054, -27628094343205772384, -43298114976496007063, -42387348160139176727, -32007171174458130066, -34038953985742400696, -47316388333237830948, -47318169357263261990, -45370546897509503825)
chall.sageのsplit_pを見れば、これの逆操作をしてあげることで、ベクトル$\boldsymbol{p}$から素数$p$を復元できることが分かる。
# 復元されたpの計算
pbar = 0
for i in range(k):
pbar += R(fin[i] * 2^(step*i))
しかしながら、ノイズ$\boldsymbol{r}_1$は各成分が最大$1000$bitと非常に大きく、下位64bitが欠損し、完全にベクトル$\boldsymbol{p}$を復元することが出来ない。実際に$N$を$pbar$で割った余りを見てみると、
N % ZZ(pbar)
この出力は5414150738518577273807028167983077857670573040548755495278812479910521420388235894416839885422559151381689619913240812613341263588831058423663606132080245となり、割り切れていないことが確認できる。そこで、与えられた$N=pq$の情報を用いてCoppersmithによる補完を行うことで不足するビットを補う。
# Coppersmithの小さい根探索でpを求める
PR.<x> = PolynomialRing(R)
f = x + pbar
x0 = f.small_roots(X=2^step, beta=0.3)[0]
p = ZZ(x0 + pbar)
再度、$N$を$p$で割ってみると$0$となることが分かる。スッキリ。
Step.3
さて、素数$p,\ q$が分かったところで、ベクトル$\boldsymbol{key}$を復元する。ベクトル$\boldsymbol{key}_{\rm e}$の定義は以下の通り。
\begin{align}
\boldsymbol{key}_{\rm e}
=\boldsymbol{key}\,\boldsymbol{G}+\boldsymbol{r}_2,\quad\boldsymbol{r}_2\in R^{1\times n}
\end{align}
ノイズベクトル$\boldsymbol{r}_2$を生成する関数make_random_vector2を見ると、$36$次元のうち子後半$8$要素は必ず$0$であるが、それ以外は生成した乱数を素数$p, q$でmodを取っているので、復元がかなり困難に見える。
実は、この問題はGRSコードと呼ばれる、多項式符号化を行うエラー訂正符号の一種を利用した復元方法で解くことができるらしい。sagemathにGeneralizedReedSolomonCodeというGRSコードを構築するクラスが用意されており、これを使うと簡単に求めることが可能。参考はこちら。
def test_p(p, c, alphas):
F = GF(p)
alphas = alphas.change_ring(F)
l = []
for i in range(n):
l.append(F(i))
row = []
G = make_G(F, alphas)
C = codes.GeneralizedReedSolomonCode(alphas, k)
return C.decode_to_message(c)
# 初期設定
q = N / p
key_encoded = vector(key_encoded)
alphas = vector(predict_alphas)
# GRSコードによるノイズベクトルの復元
mp = test_p(p, key_encoded, alphas).change_ring(ZZ)
mq = test_p(q, key_encoded, alphas).change_ring(ZZ)
# 連結してkeyvecを復元
mm = list()
for i in range(len(mp)):
mm.append(crt([mp[i], mq[i]], [p, q]))
keyvec = vector(mm)
これで目的であった$\boldsymbol{key}$を求めることが出来る。
Step.4
最後にフラグをキャプチャーする。
import hashlib
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
key = hashlib.sha256(str(keyvec).encode()).digest()
cipher = AES.new(key, AES.MODE_ECB)
flag = cipher.decrypt(encrypted_flag)
flag_str = flag.decode('utf-8')
print(flag_str)
得られたフラグはSECCON{There__4re_many_w4ys_t0_use_m4tr1x:)}
おわりに
ここまで作者のWriteUpやsagemathのドキュメントを読みながら記事を書いてきたが多分、一週間あっても解けなかっただろう。知行合一が大切だと実感した。