Crew CTF 2022 - matdlp
TL;DR
- 成分が$\mathbb F_p$の行列を利用して鍵共有が行われており、秘密鍵となっている$t,s$の内、$t$と$U^s$($U$は鍵共有で使われるパラメータ)の値を導出出来れば鍵を導出出来る
- $t$は相似な行列の行列式が等しいことから、$\mathbb F_p$上のDLPを解く事に帰着出来、$p$はsmoothな素数であるから、Pohlig-Hellmanアルゴリズムを利用出来る
- $U^s$は公開鍵の定義から導かれる関係に加えて、$U^s$が$U$のべき乗できある事を利用して制約を増やすことで導出出来る
Prerequisite
- Pohlig-Hellman アルゴリズム
Writeup
次のスクリプトとその実行結果が与えられる。
FLAG = open('flag.txt', 'r').read().encode()
p = 0x3981e7c18d9517254d5063b9f503386e44cd0bd9822710b4709c89fc63ce1060626a6f86b1c76c7cbd41371f6bf61dd8216f4bc6bad8b02a6cd4b99fe1e71b5d9ffc761eace4d02d737e5d4bf2c07ff7
m = 6
import random
from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util import Padding
K = GF(p)
matspace = MatrixSpace(K, m)
while(True):
U = matspace.random_element()
if U.determinant() != 0:
break
print('U={}'.format(U.list()))
while(True):
l1, l2, l3 = K.random_element(), K.random_element(), K.random_element()
X = matrix(K, m, m, [l1,0,0,0,0,0]+[0,l2,1,0,0,0]+[0,0,l2,0,0,0]+[0,0,0,l3,1,0]+[0,0,0,0,l3,1]+[0,0,0,0,0,l3])
if U*X != X*U:
break
print('X={}'.format(X.list()))
def genkey():
t = random.randint(1, p-1)
s = random.randint(1, p-1)
Us = U**s
privkey = (t, s)
pubkey = Us * (X**t) * Us.inverse()
return (privkey, pubkey)
alicekey = genkey()
bobkey = genkey()
print('alice_pubkey={}'.format(alicekey[1].list()))
print('bob_pubkey={}'.format(bobkey[1].list()))
alice_Us = (U**alicekey[0][1])
bob_Us = (U**bobkey[0][1])
sharedkey_a = alice_Us * (bobkey[1]**alicekey[0][0]) * alice_Us.inverse()
sharedkey_b = bob_Us * (alicekey[1]**bobkey[0][0]) * bob_Us.inverse()
assert sharedkey_a == sharedkey_b
aeskey = sha256(b''.join([int.to_bytes(int(sharedkey_a[i][j]), length=80, byteorder='big') for i in range(m) for j in range(m)])).digest()
cipher = AES.new(aeskey, AES.MODE_CBC, iv=b'\x00'*16)
ciphertext = cipher.encrypt(Padding.pad(FLAG, 16))
print('ciphertext=0x{}'.format(ciphertext.hex()))
成分が$\boldsymbol F_p$の6x6行列が2つ与えらる。1つは$U$でランダムに選ばれ、もう1つは$X$で次のような形になっている。
$$ X = \begin{pmatrix} l_1 \cr & l_2 & 1 \cr & & l_2 \cr & & & l_3 & 1 \cr & & & & l_3 & 1 \cr & & & & & l_3 \end{pmatrix} $$
これらを用いてAliceとBobの間で次のような鍵交換が行われる。
両者の秘密鍵を$t,s$として、公開鍵が$U^sX^t(U^s)^{-1}$となる。Alice, Bobの秘密鍵をそれぞれ$(t_a, s_a), (t_b, s_b)$、公開鍵をそれぞれ$A, B$とおいて、共有される値は$U^{s_a}B^{t_a}(U^{s_a})^{-1} = U^{s_b}A^{t_b}(U^{s_b})^{-1}$となる(両辺が一致することの証明は与えない)。
$t_a$の導出
まずは公開鍵から$t$を求める事を考える。以下では、Aliceの公開鍵を例に取る。公開鍵の定義から、$A$と$X^{t_a}$は相似であり、相似な行列同士では行列式が不変であることから、次が成り立つ。
$$ |A| = |X^{t_a}| = |X|^{t_a} $$
ここで乗法群$\mathbb F_p^*$の位数は$p-1$であるが、これはいい感じに素因数分解が出来るためPohlig-Hellmanアルゴリズムが使えそうである。というわけで$|X|^t \equiv |A| \mod p$となる$t$を求めることが出来るが、$|X|$の$\mathbb F_p^*$における位数が$p$に比べて小さいことから、この$t$が$t_a$と一致するとは限らない。$|X|$の位数を$n$とおくと、非負整数$k$に対して、$t' = t + nk$で定義される$t'$についてもまた、$|X|^{t'} \equiv |A| \mod p$が成り立つ。
正しい$t_a$の取得のために、$A$と$X^{t_a}$が相似であることを利用する。$k$を総当りして、$A$と$X^{t'}$が相似となるような$t'$を探すとこれは無事に見つかり、したがって$t_a$が求まったことになる。
$U^{s_a}$の導出
後は$U^{s_a}$を求める事が出来れば共有鍵が特定出来るため、フラグを入手出来る。ところが、$A = U^{s_a}X^{t_a}(U^{s_a})^{-1}$を満たすような$U^{s_a}$はSageMathの.is_similar()メソッドで求める事が出来るものの、一意に定まらないため、これで求めた値を利用しても上手く復号出来ない。そこで$U^{s_a}$が$U$のべき乗であるという事実を使う。
これには$U^{s_a+1} = UU^{s_a} = U^{s_a} U$を利用する。通常、行列の積は非可換であるが、べき乗であれば可換となるためこれが成り立つ。
というわけで次の連立方程式を$U^{s_a}$について解く事を考える。
$$ \begin{aligned} AU^{s_a} &= U^{s_a}X^{t_a} \cr UU^{s_a} &= U^{s_a}U \end{aligned} $$
これを解くために$U^{s_a}$を36変数とし、行列の積によって72個の線形方程式が集まることから、これを解いて$U^{s_a}$を求める。具体的には$U^{s_a}$の各成分$U^{s_a}_{i,j}$を$x_{6i+j}$とおいて、$X' = (x_1, x_2, \dots, x_{36})$が非自明解となる線形方程式$PX' = 0$を立てて解く($P$に対してright_kernel()メソッドを用いて解空間を求め、.basis()メソッドで基底を取り出す)。
(実際に立てた式については解説に非常に大きなスペースを要求するため、今のところは割愛、気が向いたら書きます)
なお、実際には求められるのは解の空間であり、$X'$には定数倍の自由度が存在するが、共有鍵$U^{s_a}B^{t_a}(U^{s_a})^{-1}$を導出する際のように、$U^{s_a}$と$(U^{s_a})^{-1}$がどちらも積の因子として含まれる時に、この定数倍部分が相殺されるため、特に問題は無くなる。
$t_a, U^{s_a}$が共に求まったので、後は問題スクリプトと同様に共有鍵を計算し、それを利用して暗号文を復号するとフラグが手に入る。
Code
p = 0x3981e7c18d9517254d5063b9f503386e44cd0bd9822710b4709c89fc63ce1060626a6f86b1c76c7cbd41371f6bf61dd8216f4bc6bad8b02a6cd4b99fe1e71b5d9ffc761eace4d02d737e5d4bf2c07ff7
m = 6
U=[121724107196232336447770662565376553386975716142815255444385680256593847147303127362594142230997680664326238021655319449918322123988355830111390038828246287143134913550681374059541524579999838, 453820185074697541771109032076990418248731462070026761466713681038059403482651571417749908181364983036982465189585414975479297943661360528381140258890162036363215969848999742697434996892144894, 888904521222411682518437837602316621715283540561332742372056990585048760725085020955088786187296233120874490517497227239869864556565393376403031696414704990296976748050488245770731810961156131, 581881774786398049542143884451759033059220845104227715190060037724183423189698262173579713428600925334799120172287204029059732017918777467539551554702868497117571458663292856770301084729223325, 213399099561553968452227447825701145406606678556374356375834510855322811333965353305947324180837526052434539008542430368726969934526180340899262134424560771150219835292210510077659096032361081, 726306957674098973463669449205280632112952697976165388994578978291000322901971915598478394462547473777213968167488256107129207842112295396086336618124560346370188021589692540663118227451140883, 1011678721518897027916325157951798404294577332528705745751557767967602388752749347813272248499255443831128050483714638548577765950907924791876961624026666242141507553205161620280559190054619446, 958502794192732432000715476302401201686205485088380833667717911798006977356576442649145663197844832203745846820870677189003262489074035145704110745845363257060461795067753533459777604895526771, 202850224483611491833546926727301549856188494302469685020714728115654157301838398320445969911225752903551946807011915228467514693529635060805610255204023393803621621954936785301836655220606754, 63000402202674470987549893095919291026024000725135922571038548319630608944734902913849060426084137627585068964612983217926039074199390984708182879168515923465704222063892030792245169878219213, 181813676663842900455545303360494577200828970797295532767312318233494361815625765041389512163224957562573048502520822896299427691397598207208851236914763365100008678170296606446808877955182632, 53515837453548494633008898328313765824225860239511383688931545859755879843109634398844251440383948646654086684202702948885879333907704576591121640733270291435357323508643032759177050178990455, 70106480932202400998831076572153951759364884899608048996012038289336698559579874378171904529515810278459571707920273902846450574701179594463861651829316591442362386285003521924437486981838532, 170088330705416142972746337585478705831915389863713053372961052721581832083687860612080341613627062523289675322160425656682390611375852481338325515100183451324396587412192077475627991470426626, 756513977491511882613038145620083132033888579685348385225736772268504466623300811590446914491712855660237802682398674613618962244444990513435840543226833431113317723219994695178693097656331762, 79309604212300863933326103255412643679841631246441241070006196328008920817814318035543589782744257694010769783616430610729371220676935088568969029322080512153562308924991225726432666062506837, 800411451665787408168921195669805169317618739979288794439831214731033267744049419706279590600114021600443241290356054265242441158029625934178919619025922078283724354359744346634834521422652790, 68925524430148038499298305540358899745485001433103578815649870647727336327381059785357779100145731284536918191792144429773805665781423949865756776476078664828057890702460899933562999507117566, 423944912189867454773980956382377827510710004819321547315262213152113092794138035924283232825443217739206507233574946279468890045557501425186379484465971116424817534331795589649938554736793697, 882642395539262497133804146777651159571539132312129336500992046523880743705704453319893868634750960423490562526270041903363902250954426518700738315675416961432212294455999213649344048459916253, 323181802594209439216331775558169563133670139078841935071683414779010737497882675663332965989326479440659535217595086730568131232843922026684864378425693847267174270073636007862649084328111268, 458356109085804465405942596585709818955850868083307853697317448961172176537706300187797127840945087719636258692202422824933697934150186296045468854411806733048797056896305654553268106018202559, 223649238938156749401277927132167118809304798451412064366101967396358946794200560305024056489148556346779875840226129939246373933199713930183240649517127517281530629644577304132580006550910605, 583965530461728346789635651039529729887362732365376358644866050762739056643815594718257394164991737258447570131667164982385693894701496949745408365077077143067374451671492964274340903425215895, 520566001278896523460810243756437140413238934122707181614114009624975786560294599194852975698432954275782537087035701308871804804537429339854307077193606711935824463476864407847641181942068455, 946292049073029318579306088806120099328267016808936713558706257243459052837191491405805465123689753683449191142788686869351808940915449406558113453359511648847167202136920936112323057239994849, 349736259232784563576099161746209356629561284586851817086226960125523290677147656251159732668923022797475132247699327927531391868438109442908467828363991237429665043796976586673039506882141904, 376703737655898963433671842299921316908545431947318742754606781086568310028659564221154597057244680647246317396251058362889477803761906769212712142613046234751643518697325757010187742568976669, 1000112119924251383262406754660395500244680587607257414655371359128149397094755520380800047648173757304169955134378756353234439660977685507764514505147838549303215448074431573924749068204214005, 47443642170077728658524808077041962414489371813521012107728493269938273865645755747684722876057214089480043764555388931531278374258146496230188976333730017510702427648745767842812050214779043, 716730328742123451467343434593681648928819098014914336483166928254027413751634733072283796353092986459907208109681012201636040551763005175188873835035801011983586415516210230827019039664595609, 825629145023277979908958075151347302439201227687495351242822215169551689968057664403186945204153448736324235401010988497720253973172485809878422110800752121060572509339575328018959130318486316, 102535126036399211828881619646111690806915690449179767858859181652752224273710740536886016424349959772553914543577824953847595240092453767682143276691782635034634902150391602746595422785008268, 847829669660384127581454815979030363580925786391821448891887722907586804075418223081029167640127709671370243523791937476271586223269569973355422966706841135646427040933362228758535933468395777, 254259834377198288206175730333116144470039623658117041745258470972460597809601382745360471288105559978148663727962493802497861904710332228009229845634173633686283092826674003605716537139045279, 376861205958054807825124012151969896769285931543165306391438228569627019865115643597365811558410195042463562944269300285787723301749340886920964172257522530856056802857431495270079792700006085]
X=[971233134119380668117642228627125000141880853312269304417699370366356828749365272615070155481032497153313240777405418715764975535866976881693473914578937918561449584827101559131791816846420556, 0, 0, 0, 0, 0, 0, 176850517348883146062510965792204332402555381562206446888286625506014335791686043989507063454021896202849205821950533791917187219114458250625891903380739973033589178804432928009967501275159063, 1, 0, 0, 0, 0, 0, 176850517348883146062510965792204332402555381562206446888286625506014335791686043989507063454021896202849205821950533791917187219114458250625891903380739973033589178804432928009967501275159063, 0, 0, 0, 0, 0, 0, 76506131121470526540170037024966099654652441221667337920182229889127842268167270560105487957022706853622189327408375018366249127289191440732341585908972949796188159969858740642795776172784592, 1, 0, 0, 0, 0, 0, 76506131121470526540170037024966099654652441221667337920182229889127842268167270560105487957022706853622189327408375018366249127289191440732341585908972949796188159969858740642795776172784592, 1, 0, 0, 0, 0, 0, 76506131121470526540170037024966099654652441221667337920182229889127842268167270560105487957022706853622189327408375018366249127289191440732341585908972949796188159969858740642795776172784592]
alice_pubkey=[200606741107179908813109308307903027642015584334534675621103691598046477496102523962919739840494631214139325219924232633207191553518805768081115927074081516559273961308772920649781460741985850, 613152476482993344271895723294119271689458072462742936498516661436126878254341464571961484304258329485516675532778884296259277459630059640026099155797702769615689607509261878097313238125476869, 664083131880629766237676403611179702537957408838255540094022461941946041162837732476733228652786609112430083752533742733898718050740269852914111982055226281378882104363778662471198767543674822, 911672981279979394315104825702604584402495780138915161460385721860649308041622810895132554286366031530157612026462051807991995584077627729733576583092446582813844797721213161204116012173802573, 532296855529988191510673720113075974404501369885980162173704285470019980909731877123525593863718952575924362289016065932619201127011092384312056119046429074307416204240389178918467236874480713, 1014842110872374237954469031334444239944511110307499328674896800956603272623154779618166207235380701234835778116744717100631384230959813424961406540755244595813762093671150007424908528725671958, 72503724407460475618607947834087162593211584599996312900637523685303769502507367090710125467203952887150311936077049536900135301030517512101882869105809064890404099645438063838061458881164797, 792913485627878043904340917071621857266675615512801317169514614546202704893946606397544984334447977692164481393803609264619098954002133134202265965338032231325825524907326705840679147665317063, 995860818985258557438662336868447205614120037730925187356345130650312363519071859106043391745598331835567285458193796418012491113461880880982765644530555862733132710331515575702399672592055833, 535806093627503344398254103836185496167642375084022958435228515642916864872287617173504253294104566939735040198324107646418320299149633117005357816766118527366971854511601556048447365376725099, 387204198254279138789443838388854787287733836239897004992549357817763421640725088628391111290995878575460993682239123929165478253216361375715050768036758198921692021096735800914565556151711442, 759034791011613265312249784860213294611386620473440966777942688249850970028201605614591614703862377482798773992973015364965727536345568599926784182686694311152108638075312210857385989950411810, 814906225993371197749063210340536689598571944602922747533205322211894810320123294059634166491837367205929689645485887985823427134624223590301195665483499207334885970704220127939744929410996981, 183286026963471496828768457904467143520627087747864177941440554330014158826330894951535261431342910998818716852339746917513263835288633849420491839543107685933085838804460884179113636695418391, 91135122102770188861843156771364386778428216095340402294508837326048125552487746901643776157184670829767045880998280425122922016900485728418168440954572342837216886912075563904379838849040705, 205506819274826398144907975717140748625091196209717618618394696157605445719833887622969824038240208865655464735047308518569957281501396270721128886143088612856000800703944539777753976231817791, 474754470334877353131454603477118793020586947286558065774200286173069000485566738894197496365688773025126666042856799559621291273164467430179715768133065398535249913515949196020195470892760010, 200186313538816799446196757571377626797541628323445214761818174579079591443212028718049532885287867156713130941486997346816358224663585803282703030855374534247784363551566132781195666341121262, 635401219828031646162366028397393439928704203551921481773789805483732424338897394292222899290616464395180472449361184422014544826096882453670494494667006295553688418919304223471920602156302360, 102670425834397096497619545204285505952924591394789567689172769250962069751871949239335769701391192207160944686227254131645924091380733851172372308121872042062773430856147936282104711649899299, 404351493335630572754635052272877275408260097467816483476594335833334232932916655360699738469001954853743073324077976660400316826251281885390619198007147019747509099734857832505056322515897679, 271424790231306178301568048188425725775773407647874821987469310448113853248849889519276779237812057338836551367193842426217063405140115120935725111293627978088233967113409400962846760694437098, 59929452409857052720430069969144223646194343635736099178293921499044043353449295156521696984199550990237538830958506755933539520942839395576594666901799091187324941220784219530302764121776477, 651580445753023646492042335061114112478832940852813964765760889616361976629528086378344617333005480106882807804881034712583082005353029214416790422542732086259581353271162645288445802595223547, 782069435050849892658208596603123354524719216798947089949726788529355137271169967058573190418197754912542511220892693956880099811336142919836479983089715281869025948238556155580767339884345709, 66878572824817255698821995114725522489936570688501921852680852570766753790568654464451658286452198163468486751486853228336835250167537616349533509183803501994719404582718088100308523540429163, 905102664409821975417035861525193582228284542902777064449436282326464445443983696272595305179070626061735776394097034411184432745044181538775415592210502209491754582097216911122664540679333334, 1019230724675549714957339947239658157588848299957574308859250444624206484622482817882594733993740429713313399356956883850635112612812283677632934972386998470049562391295134299366044853378507082, 940438300888830257680439152546738668870565967995507161826803630246742570277990704830103717765127301027274801706507254927269931973690130475666160323527563196939735758029253821976299112530903491, 398951613426463844938936679548263076288341006257355437922536322282822856268616355401629458376269297053988391665881615862277887334445730884413961261589404311339485126178711529151560604005413215, 117460064360390011101383842885971347243365461033773729877452021939612168836443898915824439477724501162974250540116687042366101254828286429362184165918329879048073913642554108300729698762343972, 744266171315040717186039984293338116914580346265712989686193138419111521590842986862030011454243533473084340839650845638522294437571033752414607871153151077823392233346760107174590711690631970, 234625223203069305143684842212572136949416995949391894185129722044018986055632499771691956014592317473284182738151208906323177136060410162078923710339608194485931293215040110329798033942219793, 964408920838027480980374246072025587173794955565313562651810505905473231436475093591098525269082230659744893519391379870170607171762356159031032913730520888757194705745227544719574158919397203, 848363309960509099486614666664441581060155982407074583128361038898025469904560933809482584055420205465729436093595673957961424498487458283881923300300771956224804636929333799925685328404186223, 489088085909372617576368297865501106163058229888238029624732235549291045890721096782012481511434420206850964031806258971654978251532522986224552507629496349553678294088028907695582538966378849]
bob_pubkey=[480444348859594121393545117827975510702193774717711869938069944371733405361830664450734257752635343183962970334096925174397309641485698386546770316779406798438674428685397649265983136601664292, 446679478184836112752702544123644746242191965483829606047329149908530332400609645555535802997860952519572337078168968756898582841608538321102429370455295700733449739567360963505911361344303011, 73839906473229992828167119669698745006987869354501197347040372212944096744563547076972167018746687676615252779838862963625853620749953708666352605691457380730547484226328084852968526641458080, 789963229614065480220299470764723555701512137658474947583714466802001159623418630380677895208152402597421160393786561830510690162840447550602620692068009163210744664569469249205827739398025627, 140907717449865719853497560794788875243118746275006116438344085203066445275778470823640279965447594069932227296507495202588361212275677637306225832182693406090352410410595626147093217645561111, 774267624911681573242550316593556993794115161529603549043458020834378210445257685499312114978389971008129781014535964644297229254208013518286547166347322981526085635590538190729546600768907586, 945886253717246814575154623773649816236351443620266089294890709461982813971364364171748261295864356062213484769308630587333121001490320154778133341212676933442633799534973823372153714461777847, 56025280923406620325648605240095942945397493613609970129736585386810236475885443627974687608178035481699771922761573851834479528398023985399595198433978641613039688876052103689444907759058570, 762135491932075469298248496268566434040833241564752581811415096228657829294029159563933391337180814756261891503469007927152474929565817717484769723601484695360851064145606660539147300024234377, 456502523650117264270218169018130879058853480415232413747352870478358348337620659215806951327729701648440117533248174064501472560013003969851528084987431320878784209048211503605689160884826913, 618844901463531994991492421473031259677074889967613568620384914779574129784308110910525426968046537642963827091777362390122305724742361179044417682929745824168380717061874390352887759136378866, 893336458248384992635761138151415449625890630637176900851354534023636267446211659339762011618878970296211384501264842269093216885153161226918762741180466653836480283597351116788492855746973166, 149023799308669764045413165576487382053969576875356506521092628522706404065399706479910576681313294954359364152259724599001417167697325971446443736430091488020449726341609923444522024463280659, 260155658330949897944628518772102200175951400758660830449334448377980566796674722849131131309677373194934132811847791443387366925460404608604372030982241061998726032009626508427487467375538747, 118107665769986871450275025092085005903461876628519163232918398394036871456407256730228734665264542517719782826234582187241449219649945020582410785448862366027771671943303552665314844171238623, 949712297021385649564622406365993991750456942208798821756378672905644952722902936748853284394534410029040753708526383078225153362260151561342818345259487508148121928866905298450622927296486049, 572064210342531413502184167321584338198559585599223811264057019852123610291821086972949905557731162823822351333411352745501115329050262179268028854462584988287973639973632893883788711282259523, 583977923753565443458375219828130572131182258739665859839510377143113436115691859383075157667733537089999976632054446765345906056362046548363689859396779228167289681330497820681596570098622300, 1012023582102578281424365435029032391526182689068799278794983069763576470133348581556429914230284998730133594461852895636165155910572637725344378125116561853699173529083365632380777740865891587, 789443489487520603449788572587167106923067865971702795507437517288927194851948210085550275845106176329614578976702384784324482910879667628170786006414429947814788245057291130058625691331514981, 730399214898592801694727631755596727287253603938410351361009089858148160674695179884728934090317753864369202483901467090687570841812090457015632799153087648980570065801919204074948603431366695, 754837460704128062038339712766238879895564974015558179315276051624184718334757738722906947294203207200083071681155204219883596720788395744599634487677843794675149902562423845694341186027236109, 511961350715627289390881813178525320782146173452529627908723389372435660317123281846720188796505787434164348004217512679311110916811853209806027285058658135585725757208703541693776946059871865, 172089604741974434978705116416329535993679177226446696805205631434329889826229297120231259487125883671550050612544805907663057822792289081255193042425809349555656614432076225241368741358867716, 1023954552108114497424604081483879928757419612413018334126698535156128888644301998610104477856452640739605193257100158681113392015498492315443892920323517580088091859782208618345940527621076255, 574501908434034227077503115757154288318756766201780920749180483566005686488249997159821569316283109128162235822276194365911053707840707029115691428811989902716247537928600491619335323110370568, 319739007538475332510322875324653324824194034650500146606187183783865327585862127342744236520547243912682313100479095374238577036992748400371996524997661403938165727313172464670850559522599518, 457923718443554179553481650617993662528390895483302792285941425570220350144037992389001005733691704424984586855458596786922115681384231264481553485892390551584667992875037052252813591202914687, 730382637909680232717102749490870962684186333757423214856460824515119801436363540398880108301970280593075050389012158231640644520245330058439713305221735811517178536314710524037342820920496134, 516296289042481961101106375885627825579482293633184384182947458665105570171208191780105239515341432355000523407313409422002960392364933210938569936156287664402500195348149240115168471641409146, 750415218434645852202735689349488296345303375562618196299132049073518151278829979117342229529531136385867497267094623478112970365406886091143281292327603144076003504608256869715799943766817824, 407064481467197791517954486920634626806312101305511650082428649575398468007545923990646229943425631313889587518999162504809992376546413613085450232154350328056497843058329071160896802437929134, 670491768443294113792978483604494213083720337280110838764513444925588560848203324898783103735733690485350965630135202639416540539563909891549753152402526679203852653129195890099249189709801187, 753278865507828353851232330340001111206712563924261612982073675238753370073907257634364835965139925615023575903821121497309123794722108931879535866667536181216026680059636668598618656004795831, 661321974800454166314540713337512232084440894864985987929921949320215380683712389292829462527171718692691883805970185195989443937470503523787158346077605484366926014104138048002296834402526485, 37242412863363082238131872960392477174383542463610423700904785753002371004680683807463465249301019522838527489830506747726148717514333170872796498357579421581267442623620458076214950688424005]
ciphertext=0xfb8ce381ac7d8d763c79de601ad91dbec2b9d2b63e3a4013b6164331e892490c676f7644c44ee5b4108e6494f6802171d3b79b3049aed2efdc28a6f8aba2947c
# 1. p - 1 is smooth
# 2. pub = U^s * X^t * (U^s)^-1
import random
from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util import Padding
from Crypto.Util.number import long_to_bytes
K = GF(p)
matspace = MatrixSpace(K, m)
X = matrix(K, m, m, X)
U = matrix(K, m, m, U)
alice_pubkey = matrix(K, m, m, alice_pubkey)
bob_pubkey = matrix(K, m, m, bob_pubkey)
"""
det_X = X.det()
det_A = alice_pubkey.det()
t_a = discrete_log(det_A, det_X)
X_order = multiplicative_order(det_X)
for k in range(0, 100):
exp = t_a + k * X_order
# A = P^-1 * X^exp * P
res, P = alice_pubkey.is_similar(X^exp, transformation=True)
if res:
print(exp)
assert alice_pubkey == P^-1 * X^exp * P
break
"""
t_a = 432978762017960036921019903848902146208580660269288029382996266549797068817073402040525723873727531072085227983002643632220253617502298093832143208135777500048568012052718558824888521053942632
Xt = X^t_a
A_coef = [
[0 for _ in range(36)] for _ in range(36)
]
for i in range(6):
for j in range(6):
idx = (i * 6, j * 6)
for k in range(6):
A_coef[idx[0] + k][idx[1] + k] = alice_pubkey[i][j]
A_coef = matrix(K, m**2, m**2, A_coef)
U_coef = [
[0 for _ in range(36)] for _ in range(36)
]
for i in range(6):
for j in range(6):
idx = (i * 6, j * 6)
for k in range(6):
U_coef[idx[0] + k][idx[1] + k] = U[i][j]
U_coef = matrix(K, m**2, m**2, U_coef)
Xt_coef = [
[0 for _ in range(36)] for _ in range(36)
]
Xt_T = Xt.transpose()
for k in range(6):
idx = (k*6, k*6)
for i in range(6):
for j in range(6):
Xt_coef[idx[0]+i][idx[1]+j] = Xt_T[i][j]
Xt_coef = matrix(K, m**2, m**2, Xt_coef)
U2_coef = [
[0 for _ in range(36)] for _ in range(36)
]
U_T = U.transpose()
for k in range(6):
idx = (k*6, k*6)
for i in range(6):
for j in range(6):
U2_coef[idx[0]+i][idx[1]+j] = U_T[i][j]
U2_coef = matrix(K, m**2, m**2, U2_coef)
lhs = A_coef.stack(U_coef)
rhs = Xt_coef.stack(U2_coef)
diff = lhs - rhs
zero_m = matrix(K, 2*m**2, m**2)
sol = diff.right_kernel().basis()[0]
Us = matrix(K, m, m, sol)
assert alice_pubkey * Us - Us * Xt == matrix(K, m, m)
assert U * Us - Us * U == matrix(K, m, m)
sharedkey_a = Us * bob_pubkey^t_a * Us.inverse()
aeskey = sha256(b''.join([int.to_bytes(int(sharedkey_a[i][j]), length=80, byteorder='big') for i in range(m) for j in range(m)])).digest()
cipher = AES.new(aeskey, AES.MODE_CBC, iv=b'\x00'*16)
pt = cipher.decrypt(long_to_bytes(ciphertext))
print(pt)
Flag
crew{dl_pr0bl3m_0n_f1n173_f13ld_15_3553n714l_70_4n07h3r_w0rld}
Resources
- Crew CTF 2022のDiscordに貼られた作問者(kiona氏)による解答スクリプト
- $U^s$がべき乗であるという性質を$UU^s = U^sU$に落とし込めることを知ったのはここから
Thanks for reading! Read other posts?