1. はじめに
2021/12/25(土) 0:00 JST ～ 2021/12/26(日) 0:00 JST で「ASIS CTF Finals 2021」にソロ参加し、 939 点（得点を得た 198 チーム中 31 位）を獲得しました。
Crypto問は解きやすいものばかりだったので一応全完できましたが、他の分野は壊滅状態でした。ツラ。
2. Writeup
2-1. Stairs (Crypto, 191 points, 43 solves)
☆設問
It's quite similar to public crypto-system, or the fear of climbing stairs, except in its specific focus.
nc [接続先サーバのIPアドレスとポート番号]
☆方針・解法
提供されるデータは無いので、とりあえずサーバに繋いでみます。
------------------------------------------------------------------------
| ..:: Try to going down the stairs carefully ::.. |
| Try to break this cryptosystem and find the flag! |
------------------------------------------------------------------------
| Options: |
| [E]ncryption function |
| [T]ry encryption! |
| [P]ublic key |
| [Q]uit |
|----------------------------------------------------------------------|
暗号化関数の表示、暗号化の試行、公開鍵の表示ができそうです。
まずは「E」で暗号化関数を表示してみます。
def encrypt(m, pubkey):
e, n = 5, pubkey
M = bytes_to_long(flag)
m += M
c = (pow(m, e, n) + m) % n
return c
フラグを整数値にしたものを $M$、公開鍵を $n$ としたとき、$M$ にユーザーの入力値を加算したものを $m$ として、$m^5 + m \mod{n}$ を返します。
ですので、計算しやすい入力値を $5$ つ用意すればその結果から、連立方程式を解くのと同じ要領で $m^5$、$m^4$、$m^3$、$m^2$ を消去できるので、 $m$ を簡単に計算できます。
そこで、公開鍵と、入力値「2」「1」「0」「-1」「-2」による暗号化結果を入手します。
※12/27加筆：フラグを byte_to_long した値を $m$とし、$2, 1, 0, -1, -2$ を入力して得られた値を順に $a_0, a_1, a_2, a_3, a_4$ とすると、$$(m+2)^5+(m+2) = a_0 \dots(0)$$ $$(m+1)^5+(m+1) = a_1\dots(1)$$ $$m^5+m = a_0 \dots(2)$$ $$(m-1)^5+(m-1) = a_3\dots(3)$$ $$(m-2)^5+(m-2) = a_4\dots(4)$$ という 5 つの式を作れますが、ここから [ { (1) + (3) } × 4 - { (0) + (4) } - (2) × 6 ] / 120 で m が求まります。
※公開鍵は接続都度変わるので、以下の値は他のプレーヤーとは異なっているものと思われます。
T
| send your message as integer to encrypt:
2
| the encrypted message is: 18122001859650916083188170469657828138846801478688435812952567502725872198231125846119522289765953388553303112683130582127741999180581458218792595252359803592075923785423599044474766863662976206378369185831483718147654071636719514859630604343839477460702206289611080406658888798144224594096657657800489269188492787962034254707562528651027434173220289683653909591316013024969237332791195601585693445773847728092163221030275810027609108944517153650173678301523313918875929301025887211723433500998672238437159302999997332346951848210911229544019184329362123726904282332348920602289250317741092440239670003279232732121195
T
| send your message as integer to encrypt:
1
| the encrypted message is: 892022635616690844141903418918637574846783172766792454718137397366392526805194987679729074431110479889257379753399285464187169202422096309396489086026011776148209956018247121958100875865404283141454986317469281927411681255106554012669254973622303944557569369054022361833793776187651760120381090980104180762344474564748069040815881257814181116182534988107760307430198862253618840077337804097527910519871609307325223530546707224937330554025583952199991021329379303488446354551812425262477893110480183447659508856516639580359178580353241399323797746927779227731340520633106263383982151216233145023503225115114852253468
T
0| send your message as integer to encrypt:
| the encrypted message is: 2682852369360671491599830357308949873792083166455865007038310194494732526207671086769292256026505598131143122489022164404770529081514218739641154086091579081503385724020276841687600485333873931064911480542498883142103325820602643712281966494622095954567408511525161041413149267778364574534928539432069109338822106262681408401113868268822265629550537023870269956303049090046226284000945556701208283222206998079749728555389383326906085245623661240947014476744145208851016605177237679412948612006089702499248499447012295011660926873595492382567774903811986668655666474104704297334835511418708011801950499620972803800230
T
| send your message as integer to encrypt:
-1
| the encrypted message is: 4473682103104652139057757295699262172737383160144937559358482991623072525610147185858855497359232722916506503502460253551924326177728562317264920873926087392186281296914978899578789693031325426390992894253051566258270207367253873787475108332663393764076474867014142028334024646524153930912130573520785097289060987332259357249081584813254257874649818060515540464789628934156695453883126350845612604431456919717465596844414833560110380883441937589639491616712014722327402251687946794274149354850065498420017440422801659293702067288782585260064158382947718447617200908160612676719905822405150491144100312252118720097172
T
| send your message as integer to encrypt:
-2
| the encrypted message is: 6264511836848632786515684234089574471682683153834010111678655788751412525012623284948418798429291854245347522793713552905648560491065127042267789449529536708196896674702353295631668498957758769119699227449127331275912325895060244238248680487746197373084768435520952878544873098829922862391337863655727348272772156614324726659043154471717065069238743941941878843777834264001216508466538542659883376235066500477957129279150209536823229390761210701829347973529963894994440869069437428022438555192741138669345349316915330532271094477506938938568295520239622544452993795419628913135269089591460033520833252395474829180144
P
pubkey = 19020808957778205886504193989129502862945318299610715910554602902487819670828406957529356337192906020362453837387538965397567752640129263192261669378630418115955169792514709304084475999037059723757745774253520955533458797965953910170993630574175459726655248850010341973011383812797112139567520100045074161288575734564417726613699028451404337056432843574324205084032830643606554369421550864680264461536842100949455440141916156385678004059148517460089261775151712784562487521904156220686281653551726962526352475541531824088956772110321282872307631268586884056955099697994365029050252798161150927630588027407178728323919
この結果をもとに、フラグを計算します。
solve.sage
from Crypto.Util.number import long_to_bytes
pubkey = 19020808957778205886504193989129502862945318299610715910554602902487819670828406957529356337192906020362453837387538965397567752640129263192261669378630418115955169792514709304084475999037059723757745774253520955533458797965953910170993630574175459726655248850010341973011383812797112139567520100045074161288575734564417726613699028451404337056432843574324205084032830643606554369421550864680264461536842100949455440141916156385678004059148517460089261775151712784562487521904156220686281653551726962526352475541531824088956772110321282872307631268586884056955099697994365029050252798161150927630588027407178728323919
R = Zmod(pubkey)
a_s = [R(18122001859650916083188170469657828138846801478688435812952567502725872198231125846119522289765953388553303112683130582127741999180581458218792595252359803592075923785423599044474766863662976206378369185831483718147654071636719514859630604343839477460702206289611080406658888798144224594096657657800489269188492787962034254707562528651027434173220289683653909591316013024969237332791195601585693445773847728092163221030275810027609108944517153650173678301523313918875929301025887211723433500998672238437159302999997332346951848210911229544019184329362123726904282332348920602289250317741092440239670003279232732121195), R(892022635616690844141903418918637574846783172766792454718137397366392526805194987679729074431110479889257379753399285464187169202422096309396489086026011776148209956018247121958100875865404283141454986317469281927411681255106554012669254973622303944557569369054022361833793776187651760120381090980104180762344474564748069040815881257814181116182534988107760307430198862253618840077337804097527910519871609307325223530546707224937330554025583952199991021329379303488446354551812425262477893110480183447659508856516639580359178580353241399323797746927779227731340520633106263383982151216233145023503225115114852253468), R(2682852369360671491599830357308949873792083166455865007038310194494732526207671086769292256026505598131143122489022164404770529081514218739641154086091579081503385724020276841687600485333873931064911480542498883142103325820602643712281966494622095954567408511525161041413149267778364574534928539432069109338822106262681408401113868268822265629550537023870269956303049090046226284000945556701208283222206998079749728555389383326906085245623661240947014476744145208851016605177237679412948612006089702499248499447012295011660926873595492382567774903811986668655666474104704297334835511418708011801950499620972803800230), R(4473682103104652139057757295699262172737383160144937559358482991623072525610147185858855497359232722916506503502460253551924326177728562317264920873926087392186281296914978899578789693031325426390992894253051566258270207367253873787475108332663393764076474867014142028334024646524153930912130573520785097289060987332259357249081584813254257874649818060515540464789628934156695453883126350845612604431456919717465596844414833560110380883441937589639491616712014722327402251687946794274149354850065498420017440422801659293702067288782585260064158382947718447617200908160612676719905822405150491144100312252118720097172), R(6264511836848632786515684234089574471682683153834010111678655788751412525012623284948418798429291854245347522793713552905648560491065127042267789449529536708196896674702353295631668498957758769119699227449127331275912325895060244238248680487746197373084768435520952878544873098829922862391337863655727348272772156614324726659043154471717065069238743941941878843777834264001216508466538542659883376235066500477957129279150209536823229390761210701829347973529963894994440869069437428022438555192741138669345349316915330532271094477506938938568295520239622544452993795419628913135269089591460033520833252395474829180144)]
m = -((a_s[1] + a_s[3]) * 4 - (a_s[0] + a_s[4]) - a_s[2] * 6) / 120
print(long_to_bytes(int(m)))
b':::. The flag is: ASIS{7hI5_cryptOsySt3M_Iz_DeF1nit3lY_vUlNEr4bl3!?} .:::'
☆フラグ
ASIS{7hI5_cryptOsySt3M_Iz_DeF1nit3lY_vUlNEr4bl3!?}
着手時に solve 数が一番多かったのですが、ローカルでできないので後回しにしていました。Crypto問 4 問の中では 一番簡単だったようです。
2-2. ras (Crypto, 224 points, 36 solves)
☆設問
RAS is an ancient RSA like challenge for Christmas Day!
ras.py
#!/usr/bin/env python3
from Crypto.Util.number import *
from flag import flag
def genparam(nbit):
while True:
a, b = getRandomRange(2, nbit), getRandomRange(32, nbit)
if (a ** b).bit_length() == nbit:
return a ** b
def genkey(nbit):
p, q = [_ + (_ % 2) for _ in [genparam(nbit) for _ in '01']]
while True:
P = p + getPrime(31)
if isPrime(P):
while True:
Q = q + getPrime(37)
if isPrime(Q):
return P, Q
def encrypt(m, pubkey):
e = 0x10001
assert m < pubkey
c = pow(m, e, pubkey)
return c
nbit = 512
P, Q = genkey(nbit)
pubkey = P * Q
flag = bytes_to_long(flag)
enc = encrypt(flag, pubkey)
print(f'pubkey = {pubkey}')
print(f'enc = {enc}')
output.txt
pubkey = 56469405750402193641449232753975279624388972985036568323092258873756801156079913882719631252209538683205353844069168609565141017503581101845476197667784484712057287713526027533597905495298848547839093455328128973319016710733533781180094847568951833393705432945294907000234880317134952746221201465210828955449
enc = 11104433528952071860984483920122173351342473018268740572598132083816861855404615534742178674185812745207876206939230069251889172817480784782618716608299615251541018034321389516732611030641383571306414414804563863131355221859432899624060128497648444189432635603082478662202695641001726208833663163000227827283
☆方針・解法
genparam を見てみると、a、b の組み合わせは総当たりできそうなほど限定的です。
さらに p * q = pubkey であることから、p、q を構成する a、b の候補はさらに絞り込めるでしょう。
p と P、q と Q の差異はそれぞれ高々 $2^{31}$、$2^{37}$ とごく小さいので、これを x と置いて small_roots を使って求めればできそうな感じです。
☆ソルバ
solve.sage
from Crypto.Util.number import *
import itertools
pubkey = 56469405750402193641449232753975279624388972985036568323092258873756801156079913882719631252209538683205353844069168609565141017503581101845476197667784484712057287713526027533597905495298848547839093455328128973319016710733533781180094847568951833393705432945294907000234880317134952746221201465210828955449
enc = 11104433528952071860984483920122173351342473018268740572598132083816861855404615534742178674185812745207876206939230069251889172817480784782618716608299615251541018034321389516732611030641383571306414414804563863131355221859432899624060128497648444189432635603082478662202695641001726208833663163000227827283
def genparamcands(nbit):
cands = []
for a in range(2, nbit):
for b in range(32, nbit):
if (a ** b).bit_length() == nbit:
cands.append(a ** b)
return cands
cands_ = genparamcands(512)
cands = []
for p, q in itertools.combinations_with_replacement(cands_,2):
if (p + 2**30) * (q + 2**30) < pubkey and (p + 2**37) * (q + 2**37) > pubkey:
cands.append([p, q])
R.<x> = PolynomialRing(Zmod(pubkey))
for cand in cands:
for i in [0,1]:
f = x + cand[i]
rs = f.small_roots(X=2**37, beta=0.5)
if rs != []:
for r in rs:
if pubkey % (cands[i] + r) == 0:
P = cands[i] + r
break
Q = pubkey // P
d = inverse(0x10001, (P-1)*(Q-1))
print(long_to_bytes(pow(enc,d,pubkey)).decode())
☆フラグ
ASIS{RAS_iZ_51mpl!FI3D_RSA_sY573M!}[
今回、small_roots() はたまたま刺さりましたが、もっとエレガントな解法があるような気がするので再履修します。
2-3. nDLP(Crypto, 218 points, 37 solves)
☆設問
The file is updated, please redownload
How hard are discrete logarithms problems in Z_n? Try to solve the given DLP.
output.txt
x = bytes_to_long(flag)
g = 685780528648223163108441
n = 12588567055208488159342105634949357220607702491616160304212767442540158416811459761519218454720193189
y = pow(g, x, n)
y = 9136134187598897896238293762558529068838567704462064643828064439262538588237880419716728404254970025
☆方針・解法
シンプルな DLP ですが、法が p ではなく n と記されている点に違和感があります。n が合成数であろうことを guess して、yafu で素因数分解すると 4 つの異なる素因数の積であることがわかります。
あとは、各素因数を法として DLP して出た解を CRT して真の解を求めます。CRT で使う法は各素因数そのものではなく 1 を減じたものであることに注意します。
※12/27加筆：求めたい値（真の解）を $x$ とし、$\mod{p_i}$ でのDLPの解を $a_i$とすると、関係式は $$x \equiv a_i \mod {(p_i-1)}$$ となります。
☆ソルバ
solve.sage
from Crypto.Util.number import long_to_bytes
g = 685780528648223163108441
n = 12588567055208488159342105634949357220607702491616160304212767442540158416811459761519218454720193189
y = 9136134187598897896238293762558529068838567704462064643828064439262538588237880419716728404254970025
ps = [685825230919805430353639,196506778231841265839577533,117487902085160690512598387,795045813258486756062581] #by yafu
xs = []
ms = []
for p in ps:
F = GF(p)
gp = F(g)
yp = F(y)
x = discrete_log(yp, gp)
xs.append(x)
ms.append(p-1)
x = crt(xs,ms)
print(long_to_bytes(x).decode())
☆フラグ
ASIS{D!5Cre73_L09_iN_Zn_I5_3aSy?!}
2-4. MDLP (Crypto, 262 points, 30 solves)
☆設問
mDLP states the Discrete Logarithm Problem in matrices! Download and break it!
mdlp.sage
#!/usr/bin/env sage
from sage.all import *
from Crypto.Util.number import *
from secret import gen_prime, gen_base_matrix, flag
def keygen(nbit, l):
#
## Create the n-bit prime and base square matrix of size l over Ring Z_p
#
p = gen_prime(nbit)
A = gen_base_matrix(p, l)
d = randint(2, p)
Q = A ** d
pubkey = (p, A, Q)
privkey = d
return pubkey, privkey
def encrypt(M, pubkey):
p, A, Q = pubkey
l = A.nrows()
assert M.nrows() == l
r = randint(2, p)
C, D = A ** r, Q ** r
E = D * M
return C, E
def msg_to_matrix(p, msg):
l = len(msg)
return matrix(Zmod(p), [[bytes_to_long(msg[0:l//4]), bytes_to_long(msg[l//4:l//2])],
[bytes_to_long(msg[l//2:3*l//4]), bytes_to_long(msg[3*l//4:l])]])
nbit, l = 256, 2
pubkey, privkey = keygen(nbit, l)
p, A, Q = pubkey
M = msg_to_matrix(p, flag)
ENC = encrypt(M, pubkey)
print(f'pubkey = {pubkey}')
print(f'ENC = {ENC}')
output.txt
pubkey = (94413310751917369305079812653655619566021075449954923397392050181976939189891, [38199337272663519912859864066101528484023656231849338967558894235177040565160 39708167173513090810083500967474691943646789486489990958101592717502452906918]
[ 8216211510625558273096642057121313417997488994504871245106775381995665925783 56213973479253849392219948587554091081997419218105584429833155946799898624740], [61709241598677561125021718690991651934557899286972116933820920757636771220273 1945367449329759288724720626216309893787847192907494307536759223359193510642]
[37495232301500074672571996664644922614693962264764098174213150757616575323566 7348269231944161963123250652171976847627786311806728904368575861561449853500])
ENC = ([47566868540912475779105819546118874217903268597017385039977593878486632022506 86073162301954995219912739344010659248720823814557810528618517154406350653517]
[23443866424088482893369441934221448179896589659663581973508963775891809430857 74567333640177484678138574534395714128854315440076840728428649074147859070975], [56937964695156855099385034285428853461603799261684034842341841781057485084327 82459328835322885824854425864023809222717401981993182346342472865578156162544]
[85092677346274708324092648597361729755305119435989183201786866456596369562681 22228861714953585357281182780002271505668586948202416054453861940155538803489])
☆方針・解法
秘密鍵 $d$ が判明すれば、$M = D^{-1}E = (C^{d})^{-1}E$ が計算できます。ですので $d$ を求める方向で考えます。
$p$ の生成法が隠蔽されているので、何か秘密がありそうです。$p$ の 二進表記を見るなど観察していく中で、$p-1$ をFactorDBに入れてみると、超めっちゃ smooth（素因数は全て1000未満！）であることがわかりました。
よっしゃ、DLP はサクッと解けるはず！・・・だったのですが計算式をミスってて3時間くらい溶かしてしまいましたorz...
☆ソルバ（汚くてスミマセン）
solve.sage
from Crypto.Util.number import *
pubkey = (94413310751917369305079812653655619566021075449954923397392050181976939189891, [[38199337272663519912859864066101528484023656231849338967558894235177040565160,39708167173513090810083500967474691943646789486489990958101592717502452906918],[8216211510625558273096642057121313417997488994504871245106775381995665925783,56213973479253849392219948587554091081997419218105584429833155946799898624740]], [[61709241598677561125021718690991651934557899286972116933820920757636771220273, 1945367449329759288724720626216309893787847192907494307536759223359193510642],[37495232301500074672571996664644922614693962264764098174213150757616575323566, 7348269231944161963123250652171976847627786311806728904368575861561449853500]])
ENC = ([[47566868540912475779105819546118874217903268597017385039977593878486632022506, 86073162301954995219912739344010659248720823814557810528618517154406350653517],[23443866424088482893369441934221448179896589659663581973508963775891809430857, 74567333640177484678138574534395714128854315440076840728428649074147859070975]], [[56937964695156855099385034285428853461603799261684034842341841781057485084327, 82459328835322885824854425864023809222717401981993182346342472865578156162544],[85092677346274708324092648597361729755305119435989183201786866456596369562681, 22228861714953585357281182780002271505668586948202416054453861940155538803489]])
def solve_DLP(g, y, ord): # 弱弱コーダなのでBSGSとか書くのが面倒くさくて総当たりしてます。
for i in range(ord):
if g^i == y:
return i
return -1
def pohlig_hellman(p, g, y):
factors = factor(p-1)
X = []
M = []
for fac in factors:
q = int(fac[0] ** fac[1]) # ここをint(fac[0] * fac[1])と書いてて3時間潰れた。
t = int((p-1)//q)
x = solve_DLP(g**t, y**t, q)
X.append(int(x))
M.append(int(q))
print("[+] M:", M)
print("[+] X:", X)
x = crt(X, M)
return x
p = pubkey[0]
F = GF(p)
A = matrix(F, pubkey[1])
Q = matrix(F, pubkey[2])
d = pohlig_hellman(p, A, Q)
assert A^d == Q
#d = 85011530287717179206191836470573856514211831713782635916426092559668777224810
C = matrix(F, ENC[0])
E = matrix(F, ENC[1])
M = (C^d).inverse() * E
flag = long_to_bytes(int(M[0][0])) + long_to_bytes(int(M[0][1])) + long_to_bytes(int(M[1][0])) + long_to_bytes(int(M[1][1]))
print(flag.decode())
☆フラグ
ASIS{PuBl1c-K3y_CRyp70sy5tEm_B4S3d_On_Tw0D!m3nSiOn_DLP!}
3 おわりに
来年は Crypto power マシマシ＋ pwn デビューを目標に頑張りたいと思います。
ジーク、ジオン！!