この大会は2021/8/7 02:00(JST)～2021/8/10 02:00(JST)に開催されました。
今回もチームで参戦。結果は1920点で845チーム中104位でした。
自分で解けた問題をWriteupとして書いておきます。
minigen (crypto 100)
難読化されていて、暗号処理が難しい。何回か試すと、最初のnext(g)はランダムな値になるが、次以降のnext(g)は最初の値が決まると同じ値になる。フラグが'r'から始まることを前提にこの結果を使って復号する。
#!/usr/bin/python3 exec('def f(x):'+'yield((x:=-~x)*x+-~-x)%727;'*100) g=f(id(f)) with open('output.txt', 'r') as f: enc = [int(x) for x in f.read().rstrip().split(' ')] flag = 'r' while True: if next(g) ^ enc[0] == ord(flag): break for i in range(1, len(enc)): flag += chr(next(g) ^ enc[i]) print(flag)
rarctf{pyg01f_1s_fun}
sRSA (crypto 100)
一瞬パラメータでRSA暗号に見えるが、暗号はct = (flag * e) % nとなっている。この暗号の式を変形すると、以下のようになることを使って、逆算すればよい。
flag = (ct * inverse(e, n)) % n
from Crypto.Util.number import * with open('output.txt', 'r') as f: n = int(f.readline().split(' ')[-1]) e = int(f.readline().split(' ')[-1]) ct = int(f.readline().split(' ')[-1]) flag = (ct * inverse(e, n)) % n flag = long_to_bytes(flag) print flag
rarctf{ST3GL0LS_ju5t_k1dd1ng_th1s_w4s_n0t_st3g_L0L!_83b7e829d9}
unrandompad (crypto 150)
$ nc 193.57.159.27 24431 e: 3 n: 14174549034167001838553639244441993402272196402134871564313609220466901319587051081067669507788543070884496093160997332834787301608827637590884971773110573268882540771580979353802022911078124295443887833794738680245053087215981343238615552434398462979746673989866598083559237568217403872467252934361427116295965538256310492458191203857546600858369211580498455946305323127350608956796924277613129045594864138089136018275430444556257142344879835865345756900762093526897962812015488439309424479277819853137208061867061679295566608563560413475720570385105551003138694323463007083111269182659567046343726658081010925567713 [1] enc() [2] enc(flag) [3] quit opt: 1 msg: 1 c: 1 [1] enc() [2] enc(flag) [3] quit opt: 2 c: 11678954079645559221430200140201456531641464717449433679887246431026189279868984447800261651103892829673485177099182262607748212131933353764840966580819005085681490510964499535034546625722168805043933926717257314908005373084367414105661488842269735929147287203590956364122801281250824764268095179434465992258249652548237477174388056131073114119940649603293032397282955571641155257389334075966229094776705208276336880667914838988686660485377276998006781670816122987662299963431610131827953741100982791416220236756166365496716585837413326810417112511159661228440005942263892215683110265809116998738667263437066041948442 [1] enc() [2] enc(flag) [3] quit
サーバの処理概要は以下の通り。
・e, n = keygen() ・primes = [] ・e = 3 ・2回以下繰り返し ・p: 1024bit素数 ・条件：(p - 1) % 3 != 0 ・primesにpを追加 ・e, primes[0] * primes[1]を返却 ・以下繰り返し ・メニュー表示 ・1選択 ・数値入力 ・encrypt(入力数値, e, n) ・res = pad(入力数値, e, n) ※使われない。 ・pow(入力数値, e, n)を表示 ・2選択 ・encrypt(フラグ, e, n) ・pow(フラグ, e, n)を表示
1回接続し2選択でフラグの暗号化データを入手する。再度接続し、2選択でフラグの暗号化データを入手することを繰り返し、全部で3つのnとフラグの暗号化データを入手する。これでHastad's broadcast Attackで復号できる。
import socket from sympy.ntheory.modular import crt from Crypto.Util.number import * def recvuntil(s, tail): data = '' while True: if tail in data: return data data += s.recv(1) def inv_pow(c, e): low = -1 high = c+1 while low + 1 < high: m = (low + high) // 2 p = pow(m, e) if p < c: low = m else: high = m m = high assert pow(m, e) == c return m ns = [] cs = [] for _ in range(3): s = socket.socket(socket.AF_INET, socket.SOCK_STREAM) s.connect(('193.57.159.27', 24431)) data = recvuntil(s, 'opt: ') print data[:-1], n = int(data.split('\n')[1].split(' ')[-1]) ns.append(n) print '2' s.sendall('2\n') data = recvuntil(s, '\n').rstrip() print data c = int(data.split(' ')[-1]) cs.append(c) s.close() print e = 3 a = int(crt(ns, cs)[0]) m = inv_pow(a, e) flag = long_to_bytes(m) print flag
実行結果は以下の通り。
e: 3
n: 17690792369833830581294030354064657819793033968742394381473441164328607116131439026304840955330998880053979467333674015235589754341440242587814306326385104447366581680310847600129338913960925244623466709233532608926523235504676377618228886488098959846849915819008565944371571550688717265029683796262582881992297586604715545050868640954351780154297216748106472052700649720708421381702242770580655551440468310131342770011681270718670545048268454137838169479380907893650680060192536623694302990498705431456503814819985515285382847745832225946897720536680231715838942847631952446071639956611959586020477911971358674565571
[1] enc()
[2] enc(flag)
[3] quit
opt: 2
c: 11769278930632630366140360322679012958370363575442991116507369728984151920063051851302181273136390146283578788628854341021639800553395193523183213473758318236336182729054070419856221520327203295349788850220093600086041324579095613920021287328622880133961875851647373219880653609507245480330434948395226557930210217540944142881926700647209334218374305656486022825008665733283323596731278495902165372991134499092754542038533983834453290312925323626001066939669396120844681231659245562908250799873118803731265597872482120386304395484265304742894650829513983198318130745103274644940266933448658420844411247529828604649057
e: 3
n: 23500984636524522936718025289856380998692826835898022519809647099465606207386965691273581993390918013901366826129904165148125758265958770473983823370033526758482791984662888429536738350929856875953805177930658728432666716653535059851145598651486826418044249410507585899901226329190550109551146548779013404511947737875069785458715832745459561544464654400197466100278935918661194385220098242969506273386964441138148103748654048913034837496692201524022344040746060648101593154958679057100595680875021675815306278589982428022683055052275085580832758939985355378884575783440768412997365301864205099546724517177109017041161
[1] enc()
[2] enc(flag)
[3] quit
opt: 2
c: 20419257417138538464692239861056265365836312205455134797989203607404459091608158715141630119119425576418773507532790126178991838963630757197366268128082010814735020246051515419362172720930888759750937546251927816542659554543417853022632506782261549093856224840663355104980154464875029738993771591825248221050092525011794473884469196792713051285316231633744180309553150639562641355803656423870967143311815699361265953149134482860435465038047691202173749134653890511534164830354953815387431927041969703572217722328489594701409180234550085284156037470632093230489739239831762678574126792907891628129296174874420264327723
e: 3
n: 16970885632571038154066623391234201125155702089121576538840593499372396369100528376694497439151429542465496206899547547510916886479286308090719287906691384016524372039756391840094100378457830378154903624219290887431142516955715725281031263533987296823713371920826667814676653028388815205120333567245303691587198998830095030660902687598314704565233639236204907708496394598018342673600918918591978338996826637260857713474539043892369700376389443069501528290734637781677139994867353472179740834168878126167060959417457770115225740945780246668270525995678016544634364994306165749003403906921828918355938461674014970626351
[1] enc()
[2] enc(flag)
[3] quit
opt: 2
c: 74121005500491571244189962266093170881441737665147084155231422315541816151721278091812443368963839819993484754732138289666495365042507468631832982412631929285676912010986845939691080486797942798540801591515103728970588639712370622459194392496292882258873188659641335626101822369446189717939256310505569467310117093501195633994277790308707685647171633782958484406685290585057799594898831711830854687538081316239819139776957770837020002846650373628376042013860001257937897293253626480609042675643410450066894476315826529816780533710629437175089148546770607288042121926748526764741883964395415441691431615911843505457
rarctf{https://cdn.discordapp.com/attachments/751845431063085160/866641917714235392/unknown.png_8538853c64}
rarctf{https://cdn.discordapp.com/attachments/751845431063085160/866641917714235392/unknown.png_8538853c64}
Shamir's Stingy Sharing (crypto 200)
サーバの処理概要は以下の通り。
・poly: 30個の128bitランダム整数の配列 ・random.seed(poly[0]) ・フラグと同じサイズのランダム文字列とフラグをXORしてhex表示 ・x: 数値入力(1以上の整数) ・poly[i] * pow(x, i)の和を表示
x = 2**128の場合、最後の数値の計算は以下となる。
poly[0] + poly[1] * pow(2**128, 1) + ... + poly[29] * poly(2**128, 29)
この値を2**128で割り算した余りはpoly[0]になり、seedの値がわかるため、XORの鍵が算出できる。あとはXORの鍵からフラグを復号すればよい。
#!/usr/bin/env python3 import socket import random from Crypto.Util.number import long_to_bytes def recvuntil(s, tail): data = b'' while True: if tail in data: return data.decode() data += s.recv(1) def bxor(ba1,ba2): return bytes([_a ^ _b for _a, _b in zip(ba1, ba2)]) s = socket.socket(socket.AF_INET, socket.SOCK_STREAM) s.connect(('193.57.159.27', 25057)) data = recvuntil(s, b'\n').rstrip() print(data) enc = bytes.fromhex(data) x = pow(2, 128) data = recvuntil(s, b'ONE. ') print(data + str(x)) s.sendall(str(x).encode() + b'\n') data = recvuntil(s, b'\n').rstrip() print(data) seed = int(data) % x random.seed(seed) flag = bxor(enc, long_to_bytes(random.getrandbits(len(enc) * 8))).decode() print(flag)
実行結果は以下の通り。
30a645c4c7a44173e087790c0944347a67b11d10e75a48a3290ab713bc96f1
Take a share... BUT ONLY ONE. 340282366920938463463374607431768211456
6414580899551693438248684242372185498107107182106144301437456546799924446810982621807170867756256652194746915125320288178446194341578487618024960192051335454378164052454172118419463623356731365636120460634725878489134250685033185311256545259292551152417753514416618171975621385697093813971520824983588418424369413191194262050675638861335694588465216634161197192444463225749959596061726758050935583707933125972516661570510340611943687206573617829354703532445598591616769114660637513015282158462850352084819510946777746810495277554159895881015105403389983548870421938893008400760405821377802028931175989526826387718981752644155915927243207183308141126843759618422408006852748727880506644930948563928567858558252586375136756230371581872796551831073348144395541704661419341283086596288429830168061087842364970359816414423141796685842404957744194764115892083461898396714592727375016761178456329672076984886951963647862666988674054234676132581616130956088336332509110248126691901763111175319927843365573735227683856804530707164179926011979123973350100440750126949603928776323787244750895056566725607046689802182179277041035156874963619282605770161897746196204237
rarctf{n3v3r_trust_4n_1nt3g3r}
rarctf{n3v3r_trust_4n_1nt3g3r}
babycrypt (crypto 200)
$ nc 193.57.159.27 60123 pubkey: (65537, 7879675942254289575557643609782735539999957680119218608027040720916713649630670542847097861824296657151309634069573019997895948784642051781229759637504441) hint: 18576186563444887452357796752365552662327376465939712421422409143952993108001 c: 3465129272161361820331681229952786391735790238384244602960070431070200038820353354470914015958364514702761776469451406145316631076456507540636249910142012
通常のRSA暗号。ただhint情報として以下の値が表示される。
hint = n % (q - 1)
コードからp > qであるため、以下のようになる。
n = p * q = p * (q - 1) + p → n % (q - 1) = p % (q - 1) = hint
またpとqは両方とも256bit素数のため、以下のようになる。このとき、p = (q - 1) * 2 + hintなどの可能性もあるが、まずは1倍で考える。
p - (q - 1) = hint → q = p - hint + 1 → n = p * (p - hint + 1)
この2次方程式を解けば、pがわかる。あとはそのまま復号していけばよい。
import socket from Crypto.Util.number import * from sympy import * def recvuntil(s, tail): data = '' while True: if tail in data: return data data += s.recv(1) s = socket.socket(socket.AF_INET, socket.SOCK_STREAM) s.connect(('193.57.159.27', 60123)) data = recvuntil(s, '\n').rstrip() print data pubkey = eval(data.split(': ')[-1]) data = recvuntil(s, '\n').rstrip() print data hint = int(data.split(' ')[-1]) data = recvuntil(s, '\n').rstrip() print data c = int(data.split(' ')[-1]) e = pubkey[0] n = pubkey[1] p = Symbol('p') eq = Eq(p * (p - hint + 1) - n, 0) ans = solve(eq) for p in ans: if p > 0: p = int(p) break q = n // p assert p * q == n phi = (p - 1) * (q - 1) d = inverse(e, phi) m = pow(c, d, n) flag = long_to_bytes(m) print flag
実行結果は以下の通り。
pubkey: (65537, 6294679377574700932382797677533955609651946475262561570821499591102008747232818517556238944691117818534674958303452909284931763790703561864535554250327871)
hint: 14484698452125331244247054195851692050069145251823171700683678383137933623955
c: 5014157281661206563883389112112731916660463668620202955642182754509896102739028135465351249728470762294134667794755921334712623783524156621593062942085021
rarctf{g3n3r1c_m4th5_equ4t10n_th1ng_ch4ll3ng3_5a174f54e6}
rarctf{g3n3r1c_m4th5_equ4t10n_th1ng_ch4ll3ng3_5a174f54e6}
