SECCON CTF 2023に参加しました。
チームとしての順位は115位で、国内46位でした。
自分が解いた問題は実質1問のみでしたが色々学びは得られたので楽しかったです！
解いた問題
- Welcome
- plai_n_rsa
Welcome
617 Solved
問題文
Welcome to SECCON CTF 2023!
The flag is on Discord.
解説
問題文の通りでDiscordを眺めるとFlagがあります。
いつもある挨拶がわりの問題です。
plai_n_rsa
183 Solved
問題文
I've dropped the "n" ... where is my "n" :(
解説
問題文からRSA暗号の問題と推測できます。
暗号文の生成を行っているプログラムと実行結果のファイルが与えられます。
problem.py
import os
from Crypto.Util.number import bytes_to_long, getPrime
flag = os.getenvb(b"FLAG", b"SECCON{THIS_IS_FAKE}")
assert flag.startswith(b"SECCON{")
m = bytes_to_long(flag)
e = 0x10001
p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 65537
phi = (p-1)*(q-1)
d = pow(e, -1, phi)
hint = p+q
c = pow(m,e,n)
print(f"e={e}")
print(f"d={d}")
print(f"hint={hint}")
print(f"c={c}")
output.txt
e=65537
d=15353693384417089838724462548624665131984541847837698089157240133474013117762978616666693401860905655963327632448623455383380954863892476195097282728814827543900228088193570410336161860174277615946002137912428944732371746227020712674976297289176836843640091584337495338101474604288961147324379580088173382908779460843227208627086880126290639711592345543346940221730622306467346257744243136122427524303881976859137700891744052274657401050973668524557242083584193692826433940069148960314888969312277717419260452255851900683129483765765679159138030020213831221144899328188412603141096814132194067023700444075607645059793
hint=275283221549738046345918168846641811313380618998221352140350570432714307281165805636851656302966169945585002477544100664479545771828799856955454062819317543203364336967894150765237798162853443692451109345096413650403488959887587524671632723079836454946011490118632739774018505384238035279207770245283729785148
c=8886475661097818039066941589615421186081120873494216719709365309402150643930242604194319283606485508450705024002429584410440203415990175581398430415621156767275792997271367757163480361466096219943197979148150607711332505026324163525477415452796059295609690271141521528116799770835194738989305897474856228866459232100638048610347607923061496926398910241473920007677045790186229028825033878826280815810993961703594770572708574523213733640930273501406675234173813473008872562157659306181281292203417508382016007143058555525203094236927290804729068748715105735023514403359232769760857994195163746288848235503985114734813
hintの値は非常にでかいのでp,qを発見することは困難です。
問題文はnを探して的な雰囲気を醸しているので、nを作る方針を考えます。
そこでproblem.pyを眺めていると、14行目に
d = pow(e, -1, phi)
があります。$phi=ϕ$として、式に直すと
d \equiv e^{-1} \pmod ϕ
d \cdot e - 1 \equiv 0 \pmod ϕ
ここで
\begin{align}
ϕ&=(p-1)(q-1) \\
&= p\cdot q - (p+q) + 1 \\
&= N - hint + 1
\end{align}
なので
N = ϕ + hint - 1
これでNを作る方針が立ちました。
そして途中で出てきた以下の式より
d \cdot e - 1 \equiv 0 \pmod ϕ
$d * e - 1$は$ϕ$の倍数だとわかります。
よって、
d \cdot e - 1 = k \cdot ϕ
と書けます。
d \cdot e \equiv 1 \pmod ϕ
から、$d \cdot e$ は $ϕ$ で割ったあまりが1。
これはある正の整数$n$を掛けた$(n\cdot d)\cdot e$でも成立する。
$n\cdot d > ϕ$だとしても$n\cdot d \cdot e \equiv 1 \pmod ϕ$の関係は変わらないので$d<ϕ$として良い。
よって
d \cdot e = k \cdot ϕ + 1
について$k < e$と言えるので、$ϕ$について
ϕ=\frac{d \cdot e-1}{k}
で求められる。
ここまでの情報から、1~65536までの$k$を探索すれば解けると分かります。
以下、exploitコードです。
solve.py
from Crypto.Util.number import long_to_bytes
e = 65537
hint = 275283221549738046345918168846641811313380618998221352140350570432714307281165805636851656302966169945585002477544100664479545771828799856955454062819317543203364336967894150765237798162853443692451109345096413650403488959887587524671632723079836454946011490118632739774018505384238035279207770245283729785148
c = 8886475661097818039066941589615421186081120873494216719709365309402150643930242604194319283606485508450705024002429584410440203415990175581398430415621156767275792997271367757163480361466096219943197979148150607711332505026324163525477415452796059295609690271141521528116799770835194738989305897474856228866459232100638048610347607923061496926398910241473920007677045790186229028825033878826280815810993961703594770572708574523213733640930273501406675234173813473008872562157659306181281292203417508382016007143058555525203094236927290804729068748715105735023514403359232769760857994195163746288848235503985114734813
d = 15353693384417089838724462548624665131984541847837698089157240133474013117762978616666693401860905655963327632448623455383380954863892476195097282728814827543900228088193570410336161860174277615946002137912428944732371746227020712674976297289176836843640091584337495338101474604288961147324379580088173382908779460843227208627086880126290639711592345543346940221730622306467346257744243136122427524303881976859137700891744052274657401050973668524557242083584193692826433940069148960314888969312277717419260452255851900683129483765765679159138030020213831221144899328188412603141096814132194067023700444075607645059793
def is_valid_ascii(s):
try:
s.decode('ascii')
return True
except UnicodeDecodeError:
return False
def generate_phi():
value = d * e - 1
for i in range(1,e):
if value%i==0:
yield value//i
for phi in generate_phi():
n = phi + hint - 1
m = pow(c, d, n)
flag = long_to_bytes(m)
if is_valid_ascii(flag):
print(flag)
実行するとFlagが得られます。
小話
ネット海の何処かにある初参加の記録
自分は競プロ系のツイート多いですが、実はTwitter（X）始めた理由はCTF参加がきっかけでした。
2016年にプログラミングを学びはじめ、当時メアドもパスワードも手書きのメモ用紙に書いていたので全て紛失した結果ログインできなくなったサイトが今でも残ってたりします。
村人A倒してるから、CTF戦闘力6くらいにはなってるはず、、、！