CODE BLUE CTF 2018 Quals Writeup

この大会は2018/7/28 20:00(JST)~2018/7/29 20:00(JST)に開催されました。
今回もチームで参戦。結果は284点で542チーム中43位でした。
自分で解けた問題をWriteupとして書いておきます。

Sanity check

問題にフラグが書いてある。

CBCTF{sanity check}

lagalem (Crypto)

ElGmal暗号の問題。問題のパラメータは以下の通り。

g = 1468
h = 13176937611470940769675424427237214361327027262801017230328464476187661764921664954701796966426482598685480847329992216474898047298138546932927013411286080877561831522628228420965755215837424657249966873002314137994287169213354516263406270423795978394635388801400699885714033340665899016561199970830561882935631759522528099622669587315882980737349844878337007525538293173251532224267379685239505646821600410765279043812411429818495529092434724758640978876122625789495327928210547087547860489325326144621483366895679471870087870408957451137227143277719799927169623974008653573716761024220674229810095209914374390011024349L
A = 22171697832053348372915156043907956018090374461486719823366788630982715459384574553995928805167650346479356982401578161672693725423656918877111472214422442822321625228790031176477006387102261114291881317978365738605597034007565240733234828473235498045060301370063576730214239276663597216959028938702407690674202957249530224200656409763758677312265502252459474165905940522616924153211785956678275565280913390459395819438405830015823251969534345394385537526648860230429494250071276556746938056133344210445379647457181241674557283446678737258648530017213913802458974971453566678233726954727138234790969492546826523537158L
B = 21251918005448659289449540367076207273003136102402948519268321486936734267649761131906829634666742021555542747288804916060499331412675118289617172656894696939180508678248554638496093176525353583495353834532364036007392039073993229985968415793651145047522785446635657509992391925580677770086168373498842908951372029092354946478354834120976530860456422386647226785585577733215760931557612319244940761622252983954745116260878050222286503437408510241127875494413228131438716950664031868505118149350877745316461481208779725275726026031260556779604902294937659461052089402100729217965841272238065302532882861094831960922472L
p = 36416598149204678746613774367335394418818540686081178949292703167146103769686977098311936910892255381505012076996538695563763728453722792393508239790798417928810924208352785963037070885776153765280985533615624550198273407375650747001758391126814998498088382510133441013074771543464269812056636761840445695357746189203973350947418017496096468209755162029601945293367109584953080901393887040618021500119075628542529750701055865457182596931680189830763274025951607252183893164091069436120579097006203008253591406223666572333518943654621052210438476603030156263623221155480270748529488292790643952121391019941280923396132717L
q = 22703614806237330889410083770159223453128766013766321040706174044355426290328539338099711291079959714155244437030261032146984868113293511467274463709974076015468157237127672046781216262952714317506848836418718547505157984648161313592118697709984413028733405554946035544310954827596178187067728654513993575659442761349110567922330434847940441527278779320200714023296202983137830985906413366968841334238825204827013560287441312629166207563391639545363637173286538187147065563647798900324550559230799880457351250762884396716657695545274970206009025313609823106997020670498921913048309409470476279377425822906035488401579L

c1 = 33793492710782731124369494459076474097807208878884233971164269278616670211040150701930155825011078169703308214232135321652078394446224640155796276327836370352633498860894979473374779013668639507298858624745688704898736146513461608044730232178589141572128789087250031273718023043376262651608195761389064329854778210975268322619838848614213216968252753471982762060566109470077138563127080437316815457079933537918356467531614438670082804203944345043085444729429607433486011840510876970137900905036806208322070921744641554316383849334181081430914313498093196130476486829383116502543520979690739362110736793492207923196520816L
c2 = 5064525527428049600491919498697464537972502845819664938128937188305922639513846993504687207386360776106923020699628828454337579775714240066556800908455279363001454291677717261452161432964569952225095272897486314418226314084410743187186707224835212073276372184743923025929949904169574601792248026913036485498766503887136170182876527166516406031488332812278716443348188296343938621495282255755130158373758531773477662489309286204821174677297869253776424203299305194343234106107768105109553941283693258837262880530221857757115324039088850806164791445830838849835091131899191925571818438481246247468753757273234134261109718L

c1_ = 23858001256263338639930754561393744300621498668566466378945331004639513430979203635665722789744134073627181079853617277622660322019360636513261004488765082049390326032711679225336301342778034088938726495035474355141650387408421374480476173872396852119494181935635150757138413142985246448394125423745476143726661234600332521054350310909895716505182112634281850443223646354787752416535512150749925760599825164197040257221389261843550191277292909027805321111623815531377898276273229673439686502578126512634020924256597140201920931951309168862709610195813440797540084536725074915035709996827322859002529289313937152193672624L
c2_ = 16267453627205268534367753680421495469763757833841239080352379243552352542017520577799374052771731918885648298929081367071246911126370204338693352348289112387958308732218740188775134797384686955193576200043360689334709947260640015994980749571533954121908310007422239513584361571910193760719359731740480942535224174560848463926576528210476460419021197098876171728766893668501013719257464606515863038046180251018737679498423947578193874965936933252602254324298341970127449647765609487557270029347118240547476459496038940032926457872400805963990886019493151641503310555553381629104818030667858884055226529074481528015135269L

式を変形しながら、mを求める手段を考える。

c1  = pow(g, r1, p)
c1_ = pow(g, r2, p) = pow(g, (A * r1 + B), p)
    = pow(pow(g, r1, p), A, p) * pow(g, B, p) % p
    = pow(c1, A, p) * pow(g, B, p) % p
c2  = (m * pow(h, r1, p)) % p
c2_ = (m * pow(h, r2, p)) % p = (m * pow(h, (A * r1 + B), p)) % p
    = (m * pow(pow(h, r1, p), A, p) * pow(h, B, p)) % p
    = (m * pow(c2 * inverse(m, p), A, p) * pow(h, B, p)) % p
    = (m * pow(c2, A, p) * pow(inverse(m, p), A, p) * pow(h, B, p)) % p
    = (pow(c2, A, p) * pow(inverse(m, p), A-1, p) * pow(h, B, p)) % p

pow(inverse(m, p), A-1, p) = (c2_ * inverse(pow(c2, A, p), p) * inverse(pow(h, B, p), p)) % p

左辺はRSA暗号のような式だが、pは素数のため、さらに簡単にinverse(m, p)を計算できる。inverse(m, p)を計算できたら、そのinverseを求めればmになり、フラグがわかる。

from Crypto.Util.number import *

g = 1468
h = 13176937611470940769675424427237214361327027262801017230328464476187661764921664954701796966426482598685480847329992216474898047298138546932927013411286080877561831522628228420965755215837424657249966873002314137994287169213354516263406270423795978394635388801400699885714033340665899016561199970830561882935631759522528099622669587315882980737349844878337007525538293173251532224267379685239505646821600410765279043812411429818495529092434724758640978876122625789495327928210547087547860489325326144621483366895679471870087870408957451137227143277719799927169623974008653573716761024220674229810095209914374390011024349L
A = 22171697832053348372915156043907956018090374461486719823366788630982715459384574553995928805167650346479356982401578161672693725423656918877111472214422442822321625228790031176477006387102261114291881317978365738605597034007565240733234828473235498045060301370063576730214239276663597216959028938702407690674202957249530224200656409763758677312265502252459474165905940522616924153211785956678275565280913390459395819438405830015823251969534345394385537526648860230429494250071276556746938056133344210445379647457181241674557283446678737258648530017213913802458974971453566678233726954727138234790969492546826523537158L
B = 21251918005448659289449540367076207273003136102402948519268321486936734267649761131906829634666742021555542747288804916060499331412675118289617172656894696939180508678248554638496093176525353583495353834532364036007392039073993229985968415793651145047522785446635657509992391925580677770086168373498842908951372029092354946478354834120976530860456422386647226785585577733215760931557612319244940761622252983954745116260878050222286503437408510241127875494413228131438716950664031868505118149350877745316461481208779725275726026031260556779604902294937659461052089402100729217965841272238065302532882861094831960922472L
p = 36416598149204678746613774367335394418818540686081178949292703167146103769686977098311936910892255381505012076996538695563763728453722792393508239790798417928810924208352785963037070885776153765280985533615624550198273407375650747001758391126814998498088382510133441013074771543464269812056636761840445695357746189203973350947418017496096468209755162029601945293367109584953080901393887040618021500119075628542529750701055865457182596931680189830763274025951607252183893164091069436120579097006203008253591406223666572333518943654621052210438476603030156263623221155480270748529488292790643952121391019941280923396132717L
q = 22703614806237330889410083770159223453128766013766321040706174044355426290328539338099711291079959714155244437030261032146984868113293511467274463709974076015468157237127672046781216262952714317506848836418718547505157984648161313592118697709984413028733405554946035544310954827596178187067728654513993575659442761349110567922330434847940441527278779320200714023296202983137830985906413366968841334238825204827013560287441312629166207563391639545363637173286538187147065563647798900324550559230799880457351250762884396716657695545274970206009025313609823106997020670498921913048309409470476279377425822906035488401579L

c1 = 33793492710782731124369494459076474097807208878884233971164269278616670211040150701930155825011078169703308214232135321652078394446224640155796276327836370352633498860894979473374779013668639507298858624745688704898736146513461608044730232178589141572128789087250031273718023043376262651608195761389064329854778210975268322619838848614213216968252753471982762060566109470077138563127080437316815457079933537918356467531614438670082804203944345043085444729429607433486011840510876970137900905036806208322070921744641554316383849334181081430914313498093196130476486829383116502543520979690739362110736793492207923196520816L
c2 = 5064525527428049600491919498697464537972502845819664938128937188305922639513846993504687207386360776106923020699628828454337579775714240066556800908455279363001454291677717261452161432964569952225095272897486314418226314084410743187186707224835212073276372184743923025929949904169574601792248026913036485498766503887136170182876527166516406031488332812278716443348188296343938621495282255755130158373758531773477662489309286204821174677297869253776424203299305194343234106107768105109553941283693258837262880530221857757115324039088850806164791445830838849835091131899191925571818438481246247468753757273234134261109718L

c1_ = 23858001256263338639930754561393744300621498668566466378945331004639513430979203635665722789744134073627181079853617277622660322019360636513261004488765082049390326032711679225336301342778034088938726495035474355141650387408421374480476173872396852119494181935635150757138413142985246448394125423745476143726661234600332521054350310909895716505182112634281850443223646354787752416535512150749925760599825164197040257221389261843550191277292909027805321111623815531377898276273229673439686502578126512634020924256597140201920931951309168862709610195813440797540084536725074915035709996827322859002529289313937152193672624L
c2_ = 16267453627205268534367753680421495469763757833841239080352379243552352542017520577799374052771731918885648298929081367071246911126370204338693352348289112387958308732218740188775134797384686955193576200043360689334709947260640015994980749571533954121908310007422239513584361571910193760719359731740480942535224174560848463926576528210476460419021197098876171728766893668501013719257464606515863038046180251018737679498423947578193874965936933252602254324298341970127449647765609487557270029347118240547476459496038940032926457872400805963990886019493151641503310555553381629104818030667858884055226529074481528015135269L

c = (c2_ * inverse(pow(c2, A, p), p) * inverse(pow(h, B, p), p)) % p

phi = p - 1
d = inverse(A-1, phi)
inv_m = pow(c, d, p)

m = inverse(inv_m, p)
flag = ('%x' % m).decode('hex')
print flag
CBCTF{183a3ce8ed93df613b002252dfc741b2}