初めに

insecure (theoldmoon0602, ptr-yudai, thrust2799, yoshiking)のyoshikingです．初CTF大会でした．喜ばしいことに優勝することができ，問題もいくつか解けたのでwriteupを書き公開します．

まったくの初心者だったので，ふるちゅき，ptr_yudaiに手取り足取り教えてもらいながら大会まで過ごしてた（雑魚すぎて，出ていいのか心配だった）．Binary，Cryptoのそれなりに作業のいる問題なら解けるようにはなっていた．その他は100点問題がとれるか怪しいぐらい．当日の役割としては，

100点，200点の簡単な問題をする．
1日目終了前に問題回収

があった．想定外なこととしては，

100点で詰まる問題があったこと
250，300点を解くことができたこと

であった．前者は精神的につらかったが，後者ほどうれしいものはない．わからない問題はslackで聞いたり，投げたりしてた（CTFやっててこれが楽しい）．結果Sampleを入れると，計9問・1050点取れた．　　　　　　　　　　↑うれしい↑

[Sample 100] Sample

問題文読んで書くだけコピペのイメトレしたのに，自分で書くタイプで焦った． SCKOSEN{HEISEI}

[Binary 100] ログインしたい！

stringsで見るとダミーが入っているのがわかる． BinaryはIDAに投げる人なので，とりあえず投げてみると丁寧にコメント付きでフラグが書かれていた． SCKOSEN{P@SSW0RD!}

[Crypto 250] CMA

同一のnに対して異なるeを使って暗号化していることがわかる．これはCommon Modululs Attackの問題！！ 1度やっていたのですぐに分かった．スクリプトを拾ってきてやるだけ．

import sys
import gmpy

def common_modulus_attack(c1, c2, e1, e2, n):
    gcd, s1, s2 = gmpy.gcdext(e1, e2)
    if s1 < 0:
        s1 = -s1
        c1 = gmpy.invert(c1, n)
    elif s2 < 0:
        s2 = -s2
        c2 = gmpy.invert(c2, n)
    v = pow(c1, s1, n)
    w = pow(c2, s2, n)
    m = (v * w) % n
    return m


if __name__ == '__main__':
    n = 697163747851313647585741051919071934545446813933803170069649318117710559741210942309828241413263057968917367783060498296976406236461105296155872343571465472571458861455067943431963600687028800873742137584796596162852671170321697375137596904939924266950341607689713670672118861922189869749313273790341949200887765536277607202964483007525837769344152685034136427995188789763316790283650418355485611911540613443291913015856221839541953433869506428199350315358438153142712432137030241041940194404554373526201816932093974336555692936225008805384205412065546229270153670267913485827127776342936704461533651887371495137078804092288438820479915530913133685413995201477157911998466715170295889089190163534335185024200648168611627442411240282585983100044974700889722041194576592581393367784749969933205292309980776102812865667772951149214877778939122394260160986401623585657051274220294040090019412172040635492538084358633197149142173638583232433297436812690635124286045064742069131774809951385200031432769100867496441664774312653371054082059690183370714830054453221456661636409939136078443635982854375609945486839364432796111524521897673385822201325354075200389425782052099305379822860801432433657644088520709280693673417006526206092542930693
    e1 = 28403731
    e2 = 17150467

    #m = long(sys.argv[1])
    c1 = 356570759721166632854477278136799769492343774718439393193117041958287753557806400469740119600912444471121902469051737507634649973684992907421275845928357480837967204554088377730592973371461640845998778351602473613321498651731821845302151273084971224273919757029367585943268081303597349083018680088246668756520417644436194270614866936538244276510376182333795743199343849396915141369807021966264988584828864056008833401505714143397103523465182025513664272858386121988541325005026429639663742091030924985561148699137540555122356726817211341134736753357393808849095516976817586308844713289098537749192345758473823827509850497061989710557199001358459265390635376010604140991653777868568674113486103285794018233006577917206881034620106651544317119711055161893664457852905424982102754338070105734468236013581966640100258303195145669292904518034140213634639091769696481494825204998756719477488782589658443127751934619249004503187492247836069895615545526963774623546554267330467769806735640763462197407817166248860338588483389322089500631811886698267849923510602086439495468328324214070248032200162537433610668578321215695335281853976740430016175221699089098481172034255657391707404351888360402839834243393219733520928567848871537851592051426
    c2 = 575669665394963010438730844982706572279940953775084248493601352360353309463275817992767774795096407449419307507851144274577099379018722595834759584704006210908691450019272337607837959554493442466861874815821863073107471255902560481117004800315377873346287001444012552513063060796973028053013198499075430428452043304001191963057019440616815261548859525344231653286940357861588916952568607246006604702921318217575792576131436784963000249683695410291596075586154404188340172352441795237607740139409951995478116830822121083558308839245131140182773648330192322781141945473918170059521013325445190105385074502168806722940697164735139327947024502146556639414077407288877676048797361313676919317108174952942797955152717288281437971632282265010292963726153425441787656528527218493771925055052819889303710037993913193139749174960393128306067334527665804381704806070824786160213833105655536689787789552021836106110140198210399516241831181759041647693498251693612072390279270182844839334010795635506069552968998283558623684235164319889076092996389488377136513116055439381428605713467948520990739117352288882824718186997747849925566388008159205097327659787362273526326331055816821724603964108517089642955453424633029933595047255845252090385141400

    #print m
    m =  common_modulus_attack(c1, c2, e1, e2, n)
    print hex(m)[2:].decode('hex')

[Crypto 300] RSA?

冪乗のない世界らしい n, e, cがもらえる．

300は無理だろうと手を出さずにCrypto200の旅行の写真をやっていたが，となりのスラスト君に聞かれて手を出したら案外解けた．スラスト君が冪乗じゃないなら乗算ではと言っていたのをもと計算してみた．

$c=m*e \bmod{n}$

$m=c*d \bmod{n}$

ここからmが欲しいので非常に簡単な計算である．上の式をeで割ってやると

$m = c *e^{-1} \bmod{n}$

となるので，mは簡単に求まる． pythonのインタープリタでやるのみ

>>> (n, e) = (746149315120445105644911779735002615257864427638948809430146775899763900845401478319781237412694334410613686368021055483040278357991481684487813129494944899522460397699493087246505218096960286204364461639918177320793843718724747574381859928496072509749639870292090503328557688115529251888351927498428567126853657063832878452773780418783149866919316163560203180423276894765325460041738451797385343149303272504850808939009366426995340204717301911359661640524141292447180118808883848024348018576236114084330353144353115672904820149103681022683146560799116848906807498625698939954475819479000937838859292276566046219449122782347075051511004009561691484747596362940386608213329221089677679229620860810111092211338341215804260360529582967128623164620534814690277276443932913145186024258511492440354889009304938979173562941458331119511296138076261503871542382962671556195928643434506282416038086486816450594938254170549974935406839221438655021923764949572023494832426904174630809785240917462806646302389526945618245684059655484996935724994381587851879888451272335891503968849596157334527192713715105054266039301159419016747298458532769985135446278269957364121043506362499497443274900182869320930776855669486054000707293632271709427175565301,825821)
>>> n
746149315120445105644911779735002615257864427638948809430146775899763900845401478319781237412694334410613686368021055483040278357991481684487813129494944899522460397699493087246505218096960286204364461639918177320793843718724747574381859928496072509749639870292090503328557688115529251888351927498428567126853657063832878452773780418783149866919316163560203180423276894765325460041738451797385343149303272504850808939009366426995340204717301911359661640524141292447180118808883848024348018576236114084330353144353115672904820149103681022683146560799116848906807498625698939954475819479000937838859292276566046219449122782347075051511004009561691484747596362940386608213329221089677679229620860810111092211338341215804260360529582967128623164620534814690277276443932913145186024258511492440354889009304938979173562941458331119511296138076261503871542382962671556195928643434506282416038086486816450594938254170549974935406839221438655021923764949572023494832426904174630809785240917462806646302389526945618245684059655484996935724994381587851879888451272335891503968849596157334527192713715105054266039301159419016747298458532769985135446278269957364121043506362499497443274900182869320930776855669486054000707293632271709427175565301L
>>> e
825821
>>> c = 34196057544535966582914714160221953732017949669815971420694645835609518260754242418191180642793
>>> m = c / e
>>> c % e
0L
>>> m
41408558930489738796803077374179094176604796523479024414122002026600823012195430266596733L
>>> hex(m)
'0x53434b4f53454e7b457874656e6465645f4575636c696465406e5f406c6730726974686d7dL'
>>> hex(m)[2:-1]
'53434b4f53454e7b457874656e6465645f4575636c696465406e5f406c6730726974686d7d'
>>> from binascii import hexlify
>>> from binascii import unhexlify
>>> unhexlify(hex(m)[2:-1])
'SCKOSEN{Extended_Euclide@n_@lg0rithm}'