https://yu212.hatenablog.com/entry/2024/06/12/162155

6/8～6/9に開催されたCrypto CTF 2024に参加して33位だった。久しぶりにwriteupを書く。結構楽しみにしてたけど色々あってあまり時間が取れず、24時間のうち8時間くらいしか参加できなかった。
もうちょっと時間かけたら解けたかなという問題もあったので残念、upsolveしたら追記するかも？

Alibos [181 solved]

問題

#!/usr/bin/env python3

from Crypto.Util.number import *
from gmpy2 import *
from secret import d, flag

get_context().precision = 1337

def pad(m, d):
	if len(str(m)) < d:
		m = str(m) + '1' * (d - len(str(m)))
	return int(m)

def genkey(d):
	skey = getRandomRange(10 ** (d - 1), 10 ** d)
	pkey = int(10**d * (sqrt(skey) - floor(sqrt(skey))))
	return pkey, skey

def encrypt(m, pkey):
	m = pad(m, len(str(pkey)))
	d = len(str(pkey))
	c = (pkey + d ** 2 * m) % (10 ** d)
	return c

pkey, skey = genkey(d)

m = bytes_to_long(flag)
c = encrypt(m, pkey)

print(f'pkey = {pkey}')
print(f'enc  = {c}')

解法

$\mathrm{enc} = (\mathrm{pkey} + d^2 \cdot m) \bmod 10^d$ で $\mathrm{enc}, \mathrm{pkey}$ が与えられている。 $d$ もlen(str(pkey))と等しいのでわかり、
$m = (\mathrm{enc} - \mathrm{pkey}) \cdot d^{-2} \bmod 10^d$ として $m$ が復号できる。あとはpaddingを外せばフラグが得られる。

d = len(str(pkey))
m = (enc - pkey) * pow(d ** 2, -1, 10 ** d) % (10 ** d)
while m > 0:
    if l2b(m).startswith(b"CCTF"):
        print(l2b(m))
    m //= 10

Joe-19 [120 solved]

問題

#!/usr/bin/env sage

from GPT import GPT6 # deep fake 
from Crypto.Util.number import *
from flag import flag

P = [GPT6('A 512-bit prime appears in consecutive digits of e') for _ in range(4)]
n, m = prod(P), bytes_to_long(flag)
c = pow(m, 0x10001, n)
print(f'n = {n}')
print(f'c = {c}')

解法

Pは $e$ の連続する512ビットの部分文字列4つを素因数に持つらしい。適当なサイトから $e$ の値をとってきて前から順番に試していけばよい。

rem = n
ps = []
for i in range(len(E)):
    ln = 150
    while True:
        p = int(E[i:i+ln])
        if p.bit_length() >= 512:
            break
        ln += 1
    if rem % p == 0:
        ps.append(p)
        rem //= p
    if len(ps) == 3:
        break
ps.append(rem)
phi = (ps[0]-1)*(ps[1]-1)*(ps[2]-1)*(ps[3]-1)
d = pow(65537, -1, phi)
print(l2b(pow(c, d, n)))

Mashy [68 solved]

問題

#!/usr/bin/env python3

import sys
from hashlib import md5
from binascii import *
from secret import salt, flag

def die(*args):
	pr(*args)
	quit()

def pr(*args):
	s = " ".join(map(str, args))
	sys.stdout.write(s + "\n")
	sys.stdout.flush()

def sc():
	return sys.stdin.buffer.readline()

def xor(s1, s2):
	return bytes([s1[_] ^ s2[_] for _ in range(len(s1))])

def main():
	border = "┃"
	pr(        "┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓")
	pr(border, ".: Hi all, she did Mashy, you should do it too! Are you ready? :. ", border)
	pr(        "┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛")

	REC = []
	cnt, STEP = 0, 7
	sh = md5(salt).digest()
	
	while True:
		pr(border, f'Please send your first input:  ')
		d1 = sc().strip()
		pr(border, f'Please send your second input: ')
		d2 = sc().strip()
		try:
			d1 = hexlify(unhexlify(d1))
			d2 = hexlify(unhexlify(d2))
			h1 = md5(unhexlify(d1)).digest()
			h2 = md5(unhexlify(d2)).digest()
		except:
			die(border, 'Your inputs are not valid! Bye!!!')
		if d1 != d2 and d1 not in REC and d2 not in REC:
			if md5(xor(d1, d2)).hexdigest() != 'ae09d7510659ca40eda3e45ca70e9606':
				if hexlify(xor(xor(h1, h2), sh)) == b'a483b30944cbf762d4a3afc154aad825':
					REC += [d1, d2]
					if cnt == STEP:
						die(border, f'Congrats! the flag: {flag}')
					pr(border, 'Good job, try next level :P')
					cnt += 1
				else:
					die(border, 'Your input is not correct! Bye!')
			else:
				die(border, 'No this one! Sorry!!')
		else:
			die(border, 'Kidding me!? Bye!!')

if __name__ == '__main__':
	main()

解法

md5で衝突するハッシュを8回見つければフラグが得られる。ggると
4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa200a8284bf36e8e4b55b35f427593d849676da0d1555d8360fb5f07fea2
4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa202a8284bf36e8e4b55b35f427593d849676da0d1d55d8360fb5f07fea2
の二つのハッシュが衝突するらしい。これらは長さが64バイト(=1ブロック)なので内部状態が一致しており、後ろに任意の文字列を追加してもハッシュ値が一致する。

d1 = bytes.fromhex("4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa200a8284bf36e8e4b55b35f427593d849676da0d1555d8360fb5f07fea2")
d2 = bytes.fromhex("4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa202a8284bf36e8e4b55b35f427593d849676da0d1d55d8360fb5f07fea2")

s = remote("01.cr.yp.toc.tf", 13771)
for i in range(8):
    s.sendlineafter(b":  ", (d1+p64(i)).hex().encode())
    s.sendlineafter(b": ", (d2+p64(i)).hex().encode())
print(s.recvall())

Melek [66 solved]

問題

#!/usr/bin/env sage

from Crypto.Util.number import *
from flag import flag

def encrypt(msg, nbit):
	m, p = bytes_to_long(msg), getPrime(nbit)
	assert m < p
	e, t = randint(1, p - 1), randint(1, nbit - 1)
	C = [randint(0, p - 1) for _ in range(t - 1)] + [pow(m, e, p)]
	R.<x> = GF(p)[]
	f = R(0)
	for i in range(t): f += x**(t - i - 1) * C[i]
	P = [list(range(nbit))]
	shuffle(P)
	P = P[:t]
	PT = [(a, f(a)) for a in [randint(1, p - 1) for _ in range(t)]]
	return e, p, PT

nbit = 512
enc = encrypt(flag, nbit)
print(f'enc = {enc}')

解法

$t$ 項からなる多項式 $f$ を $t$ 個のランダムな点で評価した結果が与えられる。
ラグランジュ補間で $f$ が復元できるので定数項を復号すればフラグが得られる。

output = open("Melek/output.txt", "r").read()
output = list(map(int, re.findall(r"\d+", output)))
e, p, *a = output
t = len(a) // 2
a = [(a[i*2], a[i*2+1]) for i in range(t)]

R.<x> = GF(p)[]
f = R.lagrange_polynomial(a)

d = pow(e, -1, (p-1)//2)
print(l2b(int(pow(f[0], d, p))))

RM2 [64 solved]

問題

#!/usr/bin/env python3

import sys
from Crypto.Util.number import *
from string import *
from random import *
from flag import flag
	
def die(*args):
	pr(*args)
	quit()
	
def pr(*args):
	s = " ".join(map(str, args))
	sys.stdout.write(s + "\n")
	sys.stdout.flush()
	
def sc(): 
	return sys.stdin.buffer.readline()

def randstr(l):
	return ''.join([printable[randint(0, 90)] for _ in range(l)])

def encrypt(msg, p, q):
	e = 65537
	m1, m2 = msg[:len(msg) >> 1], msg[len(msg) >> 1:]
	m1, m2 = bytes_to_long(m1), bytes_to_long(m2)
	c1, c2 = pow(m1, e, (p - 1) * (q - 1)), pow(m2, e, (2*p + 1) * (2*q + 1))
	return (c1, c2)

def main():
	border = "┃"
	pr(        "┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓")
	pr(border, ".: Welcome to RM2 task! Your mission is break our cryptosystem :. ", border)
	pr(        "┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛")
	nbit, _b = 1024, False
	pr(border, f"Please provide your desired {nbit}-bit prime numbers p, q:")
	inp = sc().decode()
	try:
		p, q = [int(_) for _ in inp.split(',')]
		if p.bit_length() == q.bit_length() == nbit and isPrime(p) and isPrime(q) and p != q:
			_b = True
	except:
		die(border, f"The input you provided is is not valid!")
	if _b:
		e, n =  65537, p * q
		s = randstr(nbit >> 4).encode()
		m = bytes_to_long(s)
		assert m < n >> 2
		c1, c2 = encrypt(s, p, q)
		pr(border, f'c1 = {c1}')
		pr(border, f'c2 = {c2}')
		pr(border, f'Now, send us the secret string to get the flag: ')
		_m = sc().strip()
		if _m == s:
			die(border, f'Congrats, you got the flag: {flag}')
		else:
			die(border, f'The secret string is not correct! Bye!!')
	else:
		die(border, f"Your input does not meet the requirements!!!")

if __name__ == '__main__':
	main()

解法

メッセージを $n=(p-1)(q-1)$ と $n=(2p+1)(2q+1)$ の二つで暗号化していて、両方を復号できればフラグが得られる。
$\varphi(n)$ がわかれば復号できるので、 $n$ を素因数分解したい。 $(p-1)(q-1)$ と $(2p+1)(2q+1)$ の両方がB-smoothになるように $p,q$ を選べばよさそうだ。
SECCON CTF 2023で似たような話を見たのでdiscordサーバーを見てみると、次のような方針があった。

この時の問題では $p+1$ と $p-1$ がB-smoothになるように $p$ を選んでいたが、今回は $p-1$ と $2p+1$ がB-smoothになるように選ぶ。
$x$ を適当に選んで $p=\frac{3}{2}(x^{120}-1)+1$ とすると、 $p-1=\frac{3}{2}(x^{120}-1)$ 、 $2p+1=3x^{120}$ となり、どちらも高い確率で小さい素因数をたくさん持つ。
次のようなコードで出てきた値を http://factordb.com/ に投げつけるとうまく素因数分解できる $p$ が3つ見つかった。

for x in range(2^(1024//120), 2^(1024//120)*4):
    p = (3 * x^120 - 3) // 2 + 1
    if p.nbits() == 1024 and isPrime(int(p)):
        print(p - 1)
        print(2 * p + 1)
        print()

for x in range(2^(1024//80), 2^(1024//80)*4):
    p = (3 * x^80 - 3) // 2 + 1
    if p.nbits() == 1024 and isPrime(int(p)):
        print(p - 1)
        print(2 * p + 1)
        print()

$n$ が小さい素因数をたくさん持つため $\mathrm{gcd}(n, c) \neq 1$ となることがあるのに注意。何度か試すとうまく動く。

p = 165674320538257119618935777569264633493104025830012248611472894731246968925696662635145647004418760425271620056052110213831898075813625940406354655699229763954183325349451697961823730258851477789232732720256524106366149483534442882933118436805397696618238112020186478083571097834483155523153453888627684702401
p1 = [2,2,2,2,2,2,3,5,5,7,11,13,19,23,31,37,61,71,181,229,233,241,401,433,1021,1033,5237,15601,15881,77621,101701,136531,600241,675889,39785017,18590197861,2110175168929,62270035466201,708791106674191,3388917958905421,297934315348629678161,343722324162224502721,4258346124311062016361408601,196833670484920623077625618471272401,3277953273564812642861575873943801232248811019050895081]
p2 = [3] * 241 + [41] * 120

q = 136319579751776446060762594173031311688966678940151526541501511333981751346927563082795749698154881610675192169672633902518187425468160661847068557813564166633080060747936338201910247175316115399953152558661099756476138183615339201940322678359899950385796675849521347379659664940470524326676056070490217094401
q1 = [2,2,2,2,2,2,2,2,3,5,5,7,11,13,17,41,73,101,113,401,1321,4481,12401,36913,46861,54497,204311,261071,8652401,24999521,1357901521,3961916417,29040743441,41589844801,17122630828217,45459230802631,4602336982581694499761,25659752338627001628771761,59522626340600884948348798081,133240651584560734013410462245281,214523217697063175741941761486481,375423311348937549351028930453201]
q2 = [3] * 81 + [2357] * 80

def phi(pr):
    mp = defaultdict(lambda: 0)
    for pp in pr:
        mp[pp] += 1
    ph = 1
    for k, v in mp.items():
        ph *= (k - 1) * k ** (v - 1)
    return ph

s = remote("01.cr.yp.toc.tf", 13371)
s.recvlines(4)
s.sendline(f"{p},{q}".encode())
s.recvuntil(b"c1 = ")
c1 = int(s.recvline())
s.recvuntil(b"c2 = ")
c2 = int(s.recvline())
phi1 = phi(p1 + q1)
phi2 = phi(p2 + q2)
n1 = (p - 1) * (q - 1)
n2 = (2*p + 1) * (2*q + 1)

print(gcd(c1, n1), gcd(c2, n2))

d1 = pow(65537, -1, phi1)
d2 = pow(65537, -1, phi2)
m1 = pow(c1, d1, n1)
m2 = pow(c2, d2, n2)
s.sendline(l2b(m1) + l2b(m2))
print(s.recvall())

Alilbols [59 solved]

問題

#!/usr/bin/env python3

from Crypto.Util.number import *
from gmpy2 import *
from secret import d, flag

def genkey(d):
	while True:
		f = getRandomRange(1, int(sqrt(2) * 10 ** d))
		g = getRandomRange(10 ** d, int(sqrt(2) * 10 ** d))
		if gcd(f, 10 * g) == 1:
			q = 4 * 100 ** d
			h = inverse(f, q) * g % q
			if gcd(h, 10 * d) == 1:
				break
	pkey, skey = (d, h), (f, g)
	return pkey, skey

def encrypt(m, pkey):
	d, h = pkey
	q = 4 * 100 ** d
	assert m < 10 ** d
	r = getRandomRange(1, 10 ** d // 2)
	c = (r * h + m + r) % q
	return c

pkey, _ = genkey(d)
m = bytes_to_long(flag)
c = encrypt(m, pkey)

print(f'h = {pkey[1]}')
print(f'c = {c}')

解法

$c = (rh + m + r) \bmod q$ として暗号化されている。まずは $h=f^{-1}g \bmod q$ から $f,g$ を求めたい。
これは式変形して $hf=g+kq$ と表せるが、 $f, g$ は $h, q$ に対して小さいので、次のような行列に対してLLLを適用すると求められる。
$\begin{pmatrix} k \\ f \\ g \end{pmatrix}^\mathsf{T} \begin{pmatrix} q \cdot 10^d & 0 & 0 \\ -h \cdot 10^d & 1 & 0 \\ 10^d & 0 & 1 \\ \end{pmatrix} = \begin{pmatrix} 0 \\ f \\ g \end{pmatrix}^\mathsf{T}$
あとは $m$ を求める部分。 $c = (rh + m + r) \bmod q$ を式変形して $r(g+f) + mf = fc \bmod q$ とすると、両辺の絶対値は $q$ より小さく、結局modを取らずに $r(g+f) + mf = fc$ が成り立つ。
これはextgcdの形なのでextgcdで解けばよい。

d = 563
q = 4 * 100 ** d
M = Matrix(ZZ, [
    [q * 10**d, 0, 0],
    [-h * 10**d, 1, 0],
    [10**d, 0, 1]
])
M = M.LLL()
for row in M[1:]:
    _, f, g = row
    fc = int(f * c % q)
    _, a, b = xgcd(g + f, f)
    a = a * fc % f
    b = b * fc % (g + f)
    print(l2b(abs(b)))
    break

Vantuk [51 solved]

問題

#!/usr/bin/env sage

from Crypto.Util.number import *
from flag import flag

def u(a, x, y):
	assert a.is_integer() and x.is_rational() and y.is_rational()
	return x + Rational((a * x - y)/(x ** 2 + y ** 2))

def v(a, x, y):
	assert a.is_integer() and x.is_rational() and y.is_rational()
	return y - Rational((x + a * y)/(x ** 2 + y ** 2))

m1 = Integer(bytes_to_long(flag[:len(flag)//2]))
m2 = Integer(bytes_to_long(flag[len(flag)//2:]))
a = Integer(randint(1, 1 << 512))

print(f'A = {u(5, a, 4*a)}')
print(f'U = {u(a, m1, m2)}')
print(f'V = {v(a, m1, m2)}')

解法

$u(a,x,y) = x + \frac{ax-y}{x^2+y^2}$ と $v(a,x,y) = y - \frac{x+ay}{x^2+y^2}$ が定義されており、 $A=u(5, a, 4a), U=u(a, m_1, m_2), V=v(a, m_1, m_2)$ が与えられている。
$u(5, a, 4a) = a + \frac{5a-4a}{a^2+16a^2} = a + \frac{a}{17a^2} = \frac{1+17a^2}{17a}$ なので $A$ の分母から $a$ は求まる。
$U = u(a, m_1, m_2) = m_1 + \frac{a \cdot m_1-m_2}{m_1^2+m_2^2} = \frac{m_1 \cdot (m_1^2+m_2^2) + a \cdot m_1 - m_2}{m_1^2+m_2^2}$ から、分母と分子で $x$ と $y$ に関する式が二つ得られるので、これを解くことによって $x, y$ が求まる。
あたえられる $U$ は約分されているので小さい範囲で分母分子を $k$ 倍して試す。実装にはsagemathのresultantを使うと人力で $x, y$ について解く必要がなくて楽できる。

a = A2 // 17
for k in range(1, 100):
    PR.<x,y> = PolynomialRing(ZZ)
    fa = x^2+y^2 - Ud*k
    fb = x*Ud*k+a*x-y - Un*k

    fd = fb.resultant(fa, y)
    r = fd.univariate_polynomial().roots()
    if len(r) >= 1:
        x = r[0][0]
        y = fb(x=x).univariate_polynomial().roots()[0][0]
        break
print(l2b(x) + l2b(y))

Bada [51 solved]

問題

┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃ Hey! It's time to solve the equation of a function f: N x N -> Z.    ┃
┃ Function f has given certain conditions. In each step, solve the     ┃
┃ equation f(x, y) = z with the given value of z. We know f(a+1, b) =  ┃
┃ f(a, b) + a, and f(a, b+1) = f(a, b) - b, for every `a' and `b'.     ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
┃ We know: f(1, 1) = 438080133526 and f(x, y) = 1017215874263
┃ Please send x, y separated by comma:

解法

ソースコードはなく、ncすると問題が出てくる。条件を満たす関数は $f(a, b) = f(1, 1) + {}_aC_2 - {}_bC_2$ なので、 ${}_aC_2 - {}_bC_2 = f(x, y) - f(1, 1)$ となるような $a, b$ を求めればよい。
がんばって算数すると $a = f(x, y) - f(1, 1) + 1, b = f(x, y) - f(1, 1)$ が条件を満たすことがわかる。

s = remote("01.cr.yp.toc.tf", 17113)
s.recvlines(6)
for _ in range(20):
    line = s.recvline()
    f11 = int(line[line.index(b"f(1, 1) = ") + 10:line.index(b" and")])
    fxy = int(line[line.index(b"f(x, y) = ") + 10:])
    s.recvline()
    print(line)
    a = fxy - f11 + 1
    b = fxy - f11
    assert a * (a - 1) // 2 - b * (b - 1) // 2 + f11 == fxy
    s.sendline(f"{a},{b}".encode())
    s.recvline()
print(s.recvline())

Honey [48 solved]

問題

#!/usr/bin/env python3

from Crypto.Util.number import *
from math import sqrt
from flag import flag

def gen_params(nbit):
	p, Q, R, S = getPrime(nbit), [], [], []
	d = int(sqrt(nbit << 1))
	for _ in range(d):
		Q.append(getRandomRange(1, p - 1))
		R.append(getRandomRange(0, p - 1))
		S.append(getRandomRange(0, p - 1))
	return p, Q, R, S

def encrypt(m, params):
	p, Q, R, S = params
	assert m < p
	d = int(sqrt(p.bit_length() << 1))
	C = []
	for _ in range(d):
		r, s = [getRandomNBitInteger(d) for _ in '01']
		c = Q[_] * m + r * R[_] + s * S[_]
		C.append(c % p)
	return C


nbit = 512
params = gen_params(512)
m = bytes_to_long(flag)
C = encrypt(m, params)
f = open('params_enc.txt', 'w')
f.write(f'p = {params[0]}\n')
f.write(f'Q = {params[1]}\n')
f.write(f'R = {params[2]}\n')
f.write(f'S = {params[3]}\n')
f.write(f'C = {C}')
f.close()

解法

p, Q, R, S, Cが512ビットなのに対し未知数r, sは32ビットと小さく、LLLができそう。実際次のような行列を作るとできる。
$\begin{pmatrix} m \\ 1 \\ r_0 \\ \vdots \\ r_{d-1} \\ s_0 \\ \vdots \\ s_{d-1} \end{pmatrix}^\mathsf{T} \begin{pmatrix} B_1 Q_0 & \cdots & B_1 Q_{d-1} & 1 & & & & \\ B_1 C_0 & \cdots & B_1 C_{d-1} & & B_2 & & & \\ B_1 R_0 & & & & & B_3 & & \\ & \ddots & & & & & \ddots & \\ & & B_1 R_{d-1} & & & & & B_3 \\ B_1 S_0 & & & & & B_3 & & \\ & \ddots & & & & & \ddots & \\ & & B_1 S_{d-1} & & & & & B_3 \\ \end{pmatrix} = \begin{pmatrix} 0 \\ \vdots \\ 0 \\ m \\ B_2 \\ B_3 r_0 \\ \vdots \\ B_3 r_{d-1} \\ B_3 s_0 \\ \vdots \\ B_3 s_{d-1} \end{pmatrix}^\mathsf{T}$
$B_1, B_2, B_3$ は右辺の各値が同じくらいの大きさになるように $(B_1, B_2, B_3) = (2^{768}, 2^{512}, 2^{480})$ くらいを選ぶ。

d = 32
M = Matrix(ZZ, d*3+2, d*3+2)
B1 = 2^768
B2 = 2^512
B3 = 2^(512-32)
M[0, d] = 1
M[1, d+1] = B2
for i in range(d):
    M[0, i] = Q[i] * B1
    M[1, i] = C[i] * B1
    M[2+i, i] = R[i] * B1
    M[d+2+i, i] = S[i] * B1
    M[d+d+2+i, i] = p * B1
    M[2+i, d+2+i] = B3
    M[d+2+i, d+d+2+i] = B3
M = M.LLL()
for row in M:
    flag = l2b(abs(row[d]))
    if flag.startswith(b"CCTF"):
        print(flag)
        break

Soufia [36 solved]

問題

┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃ .::   Soufia is a random oracle, your mission is to break it   ::. ┃
┃ We know that f: Z → Z and for all integers `x' and `y' we have:    ┃
┃     f(t * x) + t * f(y) = f(f(x + y)) for constant integer `t'.    ┃
┃ Also, f(0) = 152308255043072524838402620274259353263,              ┃
┃ and   f(47) = 5863519591712360420248155854856998139426             ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
┃ Please send the f(13):

解法

またソースコードなし問。 $\bmod t$ で考えると $f(tx) \equiv f(f(x + y))$ なので、 $\forall x, y : f(tx) \equiv f(ty) \bmod t$ が成り立つ。
実験すると $5863519591712360420248155854856998139426-152308255043072524838402620274259353263 \equiv 0 \bmod 47$ になっていて、何度か実行しても同じ式が成り立つので、二つ目に与えられている値が $t$ だとエスパーする。
$f(f(x + y))$ は扱いにくいので、 $a+b = c+d \implies f(ta)+tf(b) = f(tc)+tf(d)$ を使う。
$f(0), f(t)$ が分かっていることから $\forall x : f(x-1) = (f(0) + tf(x) - f(t)) / t$ として各値を順に求めていくことができる。

s = remote("03.cr.yp.toc.tf", 13377)
s.recvuntil(b"f(0) = ")
f0 = s.recvline()
s.recvuntil(b"f(")
line = s.recvline()
f0 = int(f0[:f0.index(b",")])
t = int(line[:line.index(b")")])
ft = int(line[line.index(b"= ")+2:line.index(b"  ")])

f = [0] * (t + 1)
f[0], f[t] = f0, ft
for i in reversed(range(1, t)):
    f[i] = (f[0] + t * f[i + 1] - f[t]) // t

for i in range(20):
    s.recvuntil(b"send the f(")
    line = s.recvline()
    x = int(line[:line.index(b")")])
    while len(f) <= x:
        f.append((f[-1] * t + f[t] - f[0]) // t)
    s.sendline(str(f[x]).encode())
    print(t, x, f[x], s.recvline())
print(s.recvline())

Nazdone [35 solved]

問題

#!/usr/bin/env python3

from Crypto.Util.number import *
from random import *
from secret import params, flag

def sol(m, a, z):
	p = m * (a - 1) % 2 + 1
	while True:
		R = list(range(1, a))
		shuffle(R)
		for r in R[:z]:
			p += getRandomRange(0, 2) * m ** r
		if isPrime(p):
			return p
		else:
			p = m * (a - 1) % 2 + 1


p, q, r = [sol(*params) for _ in '007']
n = p * q * r
m = bytes_to_long(flag)
c = pow(m, params[0] ** 3 + params[2] - 2, n)
print(f'n = {n}')
print(f'c = {c}')

解法

$\mathrm{sol}$ は $m$ 進数で1の位高々z桁が1であるような素数を返している。
まずはmを特定する。1の位がすべて1またはすべて2であることから、 $m$ は $n-1$ または $n-8$ の約数であることが分かる。適当に試すと $m=19$ がそれっぽい。
mをxと置き換えて多項式だと思うことにすると、 $n$ は3つの多項式の積なので、因数分解すると $p, q, r$ が得られる。あとは $z$ を小さい範囲で全探索するとフラグが得られる。

m = 19
nn = n
ms = []
while nn > 0:
    ms.append(nn % m)
    nn //= m
PR.<x> = PolynomialRing(ZZ)
f = 0
for i in range(len(ms)):
    f += ms[i] * x ^ i
ps = [g[0](m) for g in factor(f)]
phi = (ps[0]-1) * (ps[1]-1) * (ps[2]-1)
assert ps[0] * ps[1] * ps[2] == n
for z in range(1, 1000):
    e = int(m ** 3 + z - 2)
    if gcd(e, phi) != 1:
        continue
    d = pow(e, -1, phi)
    pt = l2b(int(pow(c, d, n)))
    if b"CCTF" in pt:
        print(pt)

Beheaded [32 solved]

問題

#!/bin/bash

source secrets.sh

FLAGS="all_flags.txt"
rm -f "all_flags.enc"

while read flag; do
	magick -background white -fill blue -pointsize 72 -size "$X"x"$Y" -gravity North caption:"$flag" flag.ppm
	tail -n +4 flag.ppm > tail
	openssl enc -aes-256-ecb -pbkdf2 -nosalt -pass pass:"$KEY" -in tail >> "all_flags.enc"
done < "$FLAGS"

解法

フラグが書かれた画像を次のコマンドで暗号化している。

openssl enc -aes-256-ecb -pbkdf2 -nosalt -pass pass:"$KEY" -in tail >> "all_flags.enc"

AESのモードがECBなので同じ値を持つブロックが同じ暗号文に暗号化される。.ppmファイルを見ると背景が白なので、文字と重なっていないすべて白のブロックはすべて最初の16バイトと同じdb4e86ff76e9183f97a95d7720dc1d31に暗号化されているはず。
1ピクセルが6バイトなので1ブロックあたり2.6ピクセル程度の情報が入っている。すべて白ではなかったブロックはすべて青だったことにしても問題なさそう。
widthとheightがわからないので適当にwidthを1000として復号してみるとこのようになった。（デカいので一部抜粋）

白が多い部分と黒が多い部分に分かれていて、黒の部分それぞれがall_flags.txtの一行に対応していそう。widthが間違っているので文字は判別できない。
色々widthを変えて試した結果widthが1623の時に正しく復元できた。

enc = read("Beheaded/all_flags.enc")

pixel_values = []
for i in range(0, len(enc), 16):
    if enc[i:i+16] == enc[:16]:
        pixel_values += [1] * 16
    else:
        pixel_values += [0] * 16
pixel_values = [any(pixel_values[i:i+6]) for i in range(0, len(pixel_values), 6)]

width = 1623
height = len(pixel_values) // width
pixel_values = pixel_values[:height * width]
image = Image.new("1", (width, height))
pixels = image.getdata()
image.putdata(pixel_values)
image.save(f"Beheaded/out.png")