ASIS CTF Finals 2021 Writeup (in Japanese)

#1. はじめに
　2021/12/25(土) 0:00 JST ～ 2021/12/26(日) 0:00 JST で「ASIS CTF Finals 2021」にソロ参加し、 939 点（得点を得た 198 チーム中 31 位）を獲得しました。
　Crypto問は解きやすいものばかりだったので一応全完できましたが、他の分野は壊滅状態でした。ツラ。
![result.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/429434/a420dc06-35d3-d5d8-3c00-920cae40783e.png)

#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
```
この結果をもとに、フラグを計算します。

```python: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!

```python: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 を使って求めればできそうな感じです。

###☆ソルバ
```python: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.

```python: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)}$$ となります。

###☆ソルバ

```python: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!

```python: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...

### ☆ソルバ（汚くてスミマセン）

```python: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 デビューを目標に頑張りたいと思います。
　ジーク、ジオン！!