SECCON Beginners CTF 2025 Writeup (crypto)
crypto分野のWriteupです。
crypto分野の問題は全5問出題され、全ての問題でフラグをGETすることができました。
seesaw (612 Solves)
問題コード
import os
from Crypto.Util.number import getPrime
FLAG = os.getenv("FLAG", "ctf4b{dummy_flag}").encode()
m = int.from_bytes(FLAG, 'big')
p = getPrime(512)
q = getPrime(16)
n = p * q
e = 65537
c = pow(m, e, n)
print(f"{n = }")
print(f"{c = }")解説
RSA暗号の問題です。
本来RSA暗号の公開鍵 n は大きな素数の積として生成され、素因数分解が計算量的に困難になるよう設計される必要があります。しかし、この問題では n の素因数の一つが16ビット（65535以下）という小さな値になっています。
そのため、小さい方の素因数を総当たりで探索することで効率的に n を素因数分解できます。
ソルバー
from Crypto.Util.number import long_to_bytes
n = 362433315617467211669633373003829486226172411166482563442958886158019905839570405964630640284863309204026062750823707471292828663974783556794504696138513859209
c = 104442881094680864129296583260490252400922571545171796349604339308085282733910615781378379107333719109188819881987696111496081779901973854697078360545565962079
e = 65537
for q in range(2, 2**16):
if n % q == 0:
p = n // q
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
flag = long_to_bytes(pow(c, d, n))
print(flag)
exit()01-Translator (280 Solves)
問題コード
import os
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import bytes_to_long
def encrypt(plaintext, key):
cipher = AES.new(key, AES.MODE_ECB)
return cipher.encrypt(pad(plaintext.encode(), 16))
flag = os.environ.get("FLAG", "CTF{dummy_flag}")
flag_bin = f"{bytes_to_long(flag.encode()):b}"
trans_0 = input("translations for 0> ")
trans_1 = input("translations for 1> ")
flag_translated = flag_bin.translate(str.maketrans({"0": trans_0, "1": trans_1}))
key = os.urandom(16)
print("ct:", encrypt(flag_translated, key).hex())解説
AES ECBモードで暗号化されたフラグを復号する問題です。
処理の流れ：
- フラグがバイナリ文字列（0と1の列）に変換される
- プレイヤーは0と1をそれぞれ好きな文字列に置換できる
- 置換後の文字列がAES ECBモードで暗号化される
ECBモードでは平文を16バイトごとのブロックに分割して暗号化し、同じ平文ブロックは常に同じ暗号文ブロックになるという性質があります。
この性質を利用し、0と1をそれぞれ16バイトの異なる文字列に置換します。
例えば、
- 0 → “AAAAAAAAAAAAAAAA”
- 1 → “BBBBBBBBBBBBBBBB”
に置換すると、各暗号文ブロックは元のビット（0または1）に対応します。
同じ暗号文ブロックは同じビット値を表すため、暗号文のパターンから元のビット列を復元してフラグを復号できます。
ソルバー
from pwn import *
from Crypto.Util.number import long_to_bytes
HOST = "01-translator.challenges.beginners.seccon.jp"
PORT = 9999
io = remote(HOST, PORT)
io.sendlineafter(b"translations for 0> ", b"A" * 16)
io.sendlineafter(b"translations for 1> ", b"B" * 16)
ct = bytes.fromhex(io.recvline().split(b"ct: ")[1].strip().decode())
blocks = [ct[i:i+16] for i in range(0, len(ct), 16)]
flag_bits = "".join(["1" if block == blocks[0] else "0" for block in blocks[:-1]])
flag = long_to_bytes(int(flag_bits, 2))
print(flag)Elliptic4b (171 Solves)
問題コード
import os
import secrets
from fastecdsa.curve import secp256k1
from fastecdsa.point import Point
flag = os.environ.get("FLAG", "CTF{dummy_flag}")
y = secrets.randbelow(secp256k1.p)
print(f"{y = }")
x = int(input("x = "))
if not secp256k1.is_point_on_curve((x, y)):
print("// Not on curve!")
exit(1)
a = int(input("a = "))
P = Point(x, y, secp256k1)
Q = a * P
if a < 0:
print("// a must be non-negative!")
exit(1)
if P.x != Q.x:
print("// x-coordinates do not match!")
exit(1)
if P.y == Q.y:
print("// P and Q are the same point!")
exit(1)
print("flag =", flag)解説
楕円曲線暗号の問題です。
secp256k1は y² = x³ + 7 (mod p) で定義される楕円曲線です。この問題では以下の2つを計算する必要があります：
- 与えられた y に対して x を求める
- P.x = Q.x かつ P.y ≠ Q.y を満たす Q = a*P となる非負整数aを求める
1：xの計算
y² – 7 (mod p) の三乗根を求めれば良いです。SageMathのnth_root関数で計算できますが、三乗根が存在しない場合もあるため複数回試行するようにしています。
2：aの計算
楕円曲線上で x 座標が同じで y 座標が異なる点は、グラフを考えると、 x 軸に関して対称な点 (x, -y) であることがわかります。この点は P の逆元 -P に相当します。本来なら a = -1 としたいところですが、問題では非負整数のみが許可されています。楕円曲線では n*P = O（Oは無限遠点）を満たす n が存在し、このとき (n-1)*P = -P となるため、 a = n-1 が条件を満たします。n はSageMathで計算できます。
ソルバー
from pwn import *
from sage.all import *
HOST = "elliptic4b.challenges.beginners.seccon.jp"
PORT = 9999
p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
Fp = GF(p)
E = EllipticCurve(Fp, [0, 7])
a = E.order() - 1
while True:
io = remote(HOST, PORT)
y = Fp(int(io.recvline().split(b"y = ")[1]))
try:
x = (y**2 - 7).nth_root(3)
except ValueError:
io.close()
continue
io.sendlineafter(b"x = ", str(x).encode())
io.sendlineafter(b"a = ", str(a).encode())
io.interactive()
exit()mathmyth (79 Solves)
問題コード
from Crypto.Util.number import getPrime, isPrime, bytes_to_long
import os, hashlib, secrets
def next_prime(n: int) -> int:
n += 1
while not isPrime(n):
n += 1
return n
def g(q: int, salt: int) -> int:
q_bytes = q.to_bytes((q.bit_length() + 7) // 8, "big")
salt_bytes = salt.to_bytes(16, "big")
h = hashlib.sha512(q_bytes + salt_bytes).digest()
return int.from_bytes(h, "big")
BITS_q = 280
salt = secrets.randbits(128)
r = 1
for _ in range(4):
r *= getPrime(56)
for attempt in range(1000):
q = getPrime(BITS_q)
cand = q * q * next_prime(r) + g(q, salt) * r
if isPrime(cand):
p = cand
break
else:
raise RuntimeError("Failed to find suitable prime p")
n = p * q
e = 0x10001
d = pow(e, -1, (p - 1) * (q - 1))
flag = os.getenv("FLAG", "ctf4b{dummy_flag}").encode()
c = pow(bytes_to_long(flag), e, n)
print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")
print(f"r = {r}")解説
特殊な構造を持つRSA暗号の問題です。
鍵生成の特徴：
- r: 56ビットの素数4つの積（224ビット）
- q: 280ビットの素数
- g(q, salt): q と salt のSHA-512ハッシュ値を整数にしたもの（以下、g と表記します）
- p: q²*next_prime(r) + g*r
next_prime(r) = r’ とすると、n = p*q = q³*r’ + q*g*r となり、mod r で n/r’ = q³ となります。よって、mod r での n/r’ の三乗根を求めることで q mod r を求められます（高々81通り）。これはSageMathで計算できます。
q mod r を t とおくと、q = s*r + t となります。
ここで、qは280ビット、rは224ビットなので sを全探索することは困難に見えます（280 – 224 = 56ビットの全探索は困難）。
しかし n = q³*r’ + q*g*r より、g = n/(q*r) – q²*r’/r となりますが、この式と q = s*r + t から s が1減少するとgは q*r ≈ 504ビット程度増加することがわかります。
gは高々512ビットなので、sの探索範囲は 512 – 504 = 8ビット程度で済み、qを求めることができます。
ソルバー
from sage.all import *
from Crypto.Util.number import long_to_bytes
import gmpy2
n = 23734771090248698495965066978731410043037460354821847769332817729448975545908794119067452869598412566984925781008642238995593407175153358227331408865885159489921512208891346616583672681306322601209763619655504176913841857299598426155538234534402952826976850019794857846921708954447430297363648280253578504979311210518547
e = 65537
c = 22417329318878619730651705410225614332680840585615239906507789561650353082833855142192942351615391602350331869200198929410120997195750699143505598991770858416937216272158142281144782652750654697847840376002907226725362778292640956434687927315158519324142726613719655726444468707122866655123649786935639872601647255712257
r = 4788463264666184142381766080749720573563355321283908576415551013379
rr = next_prime(r)
R = Zmod(r)
n_mod_r = R(n)
rr_mod_r = R(rr)
q_mod_r = (n_mod_r / rr_mod_r).nth_root(3, all=True)
q_max, _ = gmpy2.iroot(gmpy2.mpz(n) // gmpy2.mpz(rr), 3)
for t in q_mod_r:
t = int(t)
s_max = (q_max - t) // r
for s in range(s_max, max(s_max - 500, 0), -1):
q = s * r + t
if (n - q**3 * rr) % (q * r) != 0:
continue
p = n // q
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
flag = long_to_bytes(pow(c, d, n))
print(flag)
exit()Golden Ticket (35 Solves)
問題コード
import os
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
flag = os.environ.get("FLAG", "ctf4b{dummy_flag}")
iv = os.urandom(16)
key = os.urandom(16)
challenge = os.urandom(16 * 6)
ENC_TICKET = 3
DEC_TICKET = 3
GOLDEN_TICKET = 0
def menu() -> int:
print("Your tickets:")
if ENC_TICKET > 0:
print(f"{ENC_TICKET} encryption ticket(s)")
if DEC_TICKET > 0:
print(f"{DEC_TICKET} decryption ticket(s)")
if GOLDEN_TICKET > 0:
print(f"{GOLDEN_TICKET} golden ticket(s)")
print()
print(f"1. Encrypt")
print(f"2. Decrypt")
print(f"3. Get ticket")
print(f"4. Get flag")
print(f"5. Quit")
while True:
i = int(input("> "))
if 1 <= i <= 5:
return i
print("Invalid input!")
def consume_ticket(enc: int = 0, dec: int = 0, golden: int = 0):
global ENC_TICKET, DEC_TICKET, GOLDEN_TICKET
if ENC_TICKET < enc or DEC_TICKET < dec or GOLDEN_TICKET < golden:
print("Not enough tickets.")
exit(1)
ENC_TICKET -= enc
DEC_TICKET -= dec
GOLDEN_TICKET -= golden
while True:
i = menu()
if i == 1:
consume_ticket(enc=1)
pt = bytes.fromhex(input("pt> "))
if len(pt) > 16:
print("Input must not be longer than 16 bytes.")
continue
cipher = AES.new(key, AES.MODE_CBC, iv=iv)
print(f"ct:", cipher.encrypt(pad(pt, 16)).hex())
if i == 2:
consume_ticket(dec=1)
ct = bytes.fromhex(input("ct> "))
if len(ct) > 16:
print("Input must not be longer than 16 bytes.")
continue
cipher = AES.new(key, AES.MODE_CBC, iv=iv)
print("pt:", cipher.decrypt(pad(ct, 16)).hex())
if i == 3:
print("challenge:", challenge.hex())
answer = bytes.fromhex(input("answer> "))
if len(answer) != len(challenge) + 16:
print("Wrong length.")
continue
cipher = AES.new(key, AES.MODE_CBC, iv=answer[:16])
if cipher.decrypt(answer[16:]) == challenge:
print("Correct!")
GOLDEN_TICKET += 1337
else:
print("Wrong :(")
if i == 4:
consume_ticket(golden=1)
print("flag:", flag)
if i == 5:
print("Bye!")
exit(0)解説
AES CBCモードを使った暗号の問題です。
なかなか解けず、AIの力をかなり借りて解きました。
AES CBCのパディング特性を利用してIVを特定し、ECBモードのオラクルとして扱うことで、暗号化・復号オラクルを合計6回使用して特定の平文の暗号文を計算し、フラグを取得する問題でした。
AIに相談しながらソルバーを作成し、その実行結果をまたAIに共有するという対話的な方法で最終的なソルバーを得ました。
この問題に限らずですが、Beginner向けの問題はほとんどAIが解いてくれそうです。CTFは事前に知識がないとBeginnerレベルでもなかなか手が出ない問題もあるため、初心者にとってはAIを使用することでフラグをGETする楽しさは得られやすくなりました。その反面、ただ全てを教えてもらうだけだと学びが得られないため、活用の仕方については注意する必要があります。
ソルバー
from pwn import *
HOST = "golden-ticket.challenges.beginners.seccon.jp"
PORT = 9999
io = remote(HOST, PORT)
def enc(pt):
io.sendlineafter(b"> ", b"1")
io.sendlineafter(b"pt> ", pt.hex().encode())
io.recvuntil(b"ct: ")
return bytes.fromhex(io.recvline().strip().decode())
def dec(ct):
io.sendlineafter(b"> ", b"2")
io.sendlineafter(b"ct> ", ct.hex().encode())
io.recvuntil(b"pt: ")
return bytes.fromhex(io.recvline().strip().decode())
def ticket(ans):
io.sendlineafter(b"> ", b"3")
io.recvuntil(b"challenge: ")
ch = bytes.fromhex(io.recvline().strip().decode())
io.sendlineafter(b"answer> ", ans.hex().encode())
io.recvline()
return ch
chal = ticket(b"A")
blocks = [chal[i:i+16] for i in range(0, len(chal), 16)]
f3 = b"\x10" * 16
d = dec(f3)
iv = xor(f3, d[:16], d[16:])
f2 = xor(f3, d[16:], blocks[2])
f1 = xor(dec(f2)[:16], iv, blocks[1])
f0 = xor(dec(f1)[:16], iv, blocks[0])
f4 = enc(xor(f3, iv, blocks[3]))[:16]
f5 = enc(xor(f4, iv, blocks[4]))[:16]
f6 = enc(xor(f5, iv, blocks[5]))[:16]
answer = f0 + f1 + f2 + f3 + f4 + f5 + f6
ticket(answer)
io.sendlineafter(b"> ", b"4")
io.recvuntil(b"flag: ")
print(io.recvline().decode())
