# Crypto CTF 2025 write-up
這次 38 名，其實沒打太好，不過挺好玩的
## Warm-up
### Welcome
就 base64，沒什麼好說的
## Easy-Peasy
### Vinad
```python
def parinad(n):
return bin(n)[2:].count('1') % 2
def vinad(x, R):
return int(''.join(str(parinad(x ^ r)) for r in R), 2)
def genkey(nbit):
while True:
R = [getRandomNBitInteger(nbit) for _ in range(nbit)]
r = getRandomNBitInteger(nbit)
p, q = vinad(r, R), getPrime(nbit)
if isPrime(p):
e = vinad(r + 0x10001, R)
if GCD(e, (p - 1) * (q - 1)) == 1:
return (e, R, p * q), (p, q)
def encrypt(message, pubkey):
e, R, n = pubkey
return pow(message + sum(R), e, n)
nbit = 512
pubkey, _ = genkey(nbit)
m = bytes_to_long(flag)
assert m < pubkey[2]
c = encrypt(m, pubkey)
```
這題是一個 RSA，特別的是它生成 `n` 和 `e` 的方式是使用 `vinad` 這個函式。做的事情是把一個數字和陣列 `R` 每個數字 xor 之後計算是 1 的數量的奇偶數，再以二進位制的方式變成整數。它會給 `R` 、`e` 、`n` 和 `c`。會發現，在計算 `vinad(x, R)`，的時候如果 `x` 變了一個 bit，那麼結果上每個計算結果奇偶性都會變，所以就是逐位元翻轉。結論是，`vinad` 的結果在 `R` 相同的情況下只會有兩種，而且他們兩個逐位元互補。求其中一個的方式是發現任兩個 `R` 中元素如果 xor 的結果 1 數量是奇數的話那兩個位置的 bit 就不同，否則相同。
```python
from Crypto.Util.number import *
def parinad(n):
return bin(n)[2:].count('1') % 2
def vinad(x, R):
return int(''.join(str(parinad(x ^ r)) for r in R), 2)
R = list(R)
RR = [parinad(R[i] ^ R[i - 1]) for i in range(1, len(R))]
k1 = "0"
for i in RR:
if i == 1:
k1 += "1" if k1[-1] == "0" else "0"
else:
k1 += "1" if k1[-1] == "1" else "0"
k2 = "".join(["1" if i == "0" else "0" for i in k1])
k1 = int(k1, 2)
k2 = int(k2, 2)
q = k1
p = n // k1
assert(p * q == n)
e = k1
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
m = pow(c, d, n)
m = m - sum(R)
print(long_to_bytes(m))
```
### Interpol
```python
#!/usr/bin/env sage
from sage.all import *
from Crypto.Util.number import *
from flag import flag
def randpos(n):
if randint(0, 1):
return True, [(-(1 + (19*n - 14) % len(flag)), ord(flag[(63 * n - 40) % len(flag)]))]
else:
return False, [(randint(0, 313), (-1) ** randint(0, 1) * Rational(str(getPrime(32)) + '/' + str(getPrime(32))))]
c, n, DATA = 0, 0, []
while True:
_b, _d = randpos(n)
H = [d[0] for d in DATA]
if _b:
n += 1
DATA += _d
else:
if _d[0][0] in H: continue
else:
DATA += _d
c += 1
if n >= len(flag): break
A = [DATA[_][0] for _ in range(len(DATA))]
poly = QQ['x'].lagrange_polynomial(DATA).dumps()
f = open('output.raw', 'wb')
f.write(poly)
f.close()
```
它用拉格朗日差值法計算出一個多項式，包括有 flag 資訊的點和一些隨機點，就枚舉一些 flag_len，看看是不是每個 x 對應到的 y 都符合條件就好。
```python
from sage.all import *
import string
with open("output.raw", "rb") as f:
# poly = QQ["x"].loads(f.read())
poly = loads(f.read())
# [19, 23, 62]
# n = 0
for flag_len in range(5, 100):
flag = bytearray(b"\x00"*flag_len)
n = 0
fail = False
for i in range(flag_len):
k = poly(-(1 + (19*n - 14) % flag_len))
if k >= 256 or k < 0 or chr(k) not in string.printable:
fail = True
break
flag[(63 * n - 40) % flag_len] = k
n += 1
if fail:
continue
if bytes(flag[:5]) == b"CCTF{":
print(flag)
```
### Mechanic
```python
from quantcrypt.kem import MLKEM_1024
from quantcrypt.cipher import KryptonKEM
from random import randint
from pathlib import *
from os import urandom
from flag import flag
kem = MLKEM_1024()
kry = KryptonKEM(MLKEM_1024)
pt = Path('/Mechanic/flag.png')
f = open('output.raw', 'wb')
m = randint(2 ** 39, 2 ** 40)
B, c = bin(m)[2:], 0
for b in B:
if b == '1':
pkey, skey = kem.keygen()
ct = Path(f'/flag_{c}.enc')
kry.encrypt(pkey, pt, ct)
pt = ct
c += 1
else:
pkey, skey = urandom(kem.param_sizes.pk_size), urandom(kem.param_sizes.sk_size)
f.write(skey)
f.close()
```
它會去一直加密，並且把私鑰寫到一個檔案裡面，我們有的是 `flag_22.enc` 和私鑰的檔案。只要枚舉私鑰的位置，再一路解密回去就好了。
```python
from quantcrypt.kem import MLKEM_1024
from quantcrypt.cipher import KryptonKEM
from pathlib import *
# kem = MLKEM_1024()
kry = KryptonKEM(MLKEM_1024)
sz = 3168
# print(kem.param_sizes.sk_size)
with open("output.raw", "rb") as f:
data = f.read()
data = [data[i:i+sz] for i in range(0, len(data), sz)]
cnt = 22
for i in data[-1::-1]:
try:
kry.decrypt_to_file(i, Path(f"./flag_{cnt}.enc"), Path(f"./flag_{cnt-1}.enc"))
cnt -= 1
print(data.index(i))
except:
pass
```
## Getting There
### Ikkyu San
```python
def Ikkyu(nbit):
p = getPrime(nbit)
while True:
a, b = [randint(1, p - 1) for _ in range(2)]
E = EllipticCurve(GF(p), [a, b])
G, H = [E.random_point() for _ in range(2)]
try:
I = E.lift_x(1)
except:
if legendre_symbol(b - a - 1, p) < 0:
return p, E, G, H
def fongi(G, H, P):
try:
xG, xP, yP = G.xy()[0], P.xy()[0], P.xy()[1]
except:
xP = 1337
return int(xP) * G + int(yP) * H + int(xG) * P
```
這題是橢圓曲線，係數生成的部份沒什麼好說的。這題支援以下幾個操作：
- fongi
給一個在曲線上的點 `P`，它會計算 `fongi(G, H, P)`
- random point
給你一個橢圓曲線上的隨機點
- encrypt
給你 `m * G.xy()[0] * H.xy()[1]`
首先，可以透過隨機點把橢圓曲線的參數算出來。
然後，注意到一件事情是如果在進行 fongi 的時候，輸入的 `P` 的階很小的話，那麼乘一個小倍數就能把它全部消掉了，所以我先生一個點，方便起見用生成元，並且將它乘上橢圓曲線的階除以 2（如果橢圓曲線的階是奇數就重來），並且 `fongi(GG * (oord//2))`。會發現一件事情：$2(P_xG+P_yH+G_xP)=2P_xG+2P_yH$（因為 $2P=0$）
那如果再計算 `fongi(-GG * (oord//2))` 會得到 $2P_xG-2P_yH$，於是兩個相加相減之後再分別乘上 $P_x$ 和 $P_y$ 的逆元就可以得到 $4G$ 和 $4H$，然後接下來會去開根號。
注意的一點是 $P_x$ 必須要互質於橢圓曲線的階，才有逆元，這樣先計算出所有的 $G$ 的可能。然後，代隨機點去算出 $H$。最後，用 encrypt 得到資訊解出 `m`
```python
from sage.all import *
from Crypto.Util.number import *
from pwn import *
import ast
from functools import reduce
def Ikkyu(nbit):
p = getPrime(nbit)
while True:
a, b = [randint(1, p - 1) for _ in range(2)]
E = EllipticCurve(GF(p), [a, b])
G, H = [E.random_point() for _ in range(2)]
try:
I = E.lift_x(1)
except:
if legendre_symbol(b - a - 1, p) < 0:
return p, E, G, H
def fongi(P):
r.sendlineafter(b"uit", b"g")
r.sendlineafter(b": ", f"{P[0]}, {P[1]}".encode())
print(r.recvuntil(b"= "))
point = r.recvline().strip(b"()\n").decode()
return tuple(list(map(int, point.split(" : ")))[:2])
r = remote("91.107.252.0", 37773)
# r = process(["python", "Ikkyu_san.py"])
def get_random_point():
r.sendlineafter(b"uit", b"r")
r.recvuntil(b" = ")
point = r.recvline().strip(b"()\n").decode()
return tuple(list(map(int, point.split(" : ")))[:2])
points = [get_random_point() for i in range(10)]
yee = [((points[i-1][1]**2-points[i-1][0]**3)-(points[i][1]**2-points[i][0]**3),points[i-1][0]-points[i][0]) for i in range(1, 10)]
yee2 = [yee[i][0]*yee[i-1][1]-yee[i][1]*yee[i-1][0] for i in range(1,9)]
p = reduce(GCD, yee2)
print("yee")
a = yee[0][0] * pow(yee[0][1], -1, p) % p
x1, y1 = points[0]
b = (y1**2 - (x1**3 + a * x1)) % p
print(a, b)
E = EllipticCurve(GF(p), [a, b])
# f1 = y1**2 - (x1**3 + a*x1 + b)
# f2 = y2**2 - (x2**3 + a*x2 + b)
oord = E.order()
assert(oord % 2 == 0)
GG = E.gens()[0]
xG = 0
# print(oord % 3)
k = 2
print("GG")
# print(GG)
# print(-GG)
res1 = E(fongi(GG * (oord//2)))
print(res1 * 2)
res2 = E(fongi(-GG * (oord//2)))
print(res2 * 2)
P = GG*(oord//2)
G4 = (res1*2+res2*2)*pow(int(P.xy()[0]), -1, oord)
roots = G4.division_points(4)
while True:
R = E.random_point()
xP, yP = R.xy()
try:
pow(int(yP), -1, oord)
break
except:
pass
res3 = E(fongi(R))
sols = []
for G in roots:
xP, yP = R.xy()
xG, yG = G.xy()
H = (res3 - (int(xG) * R) - (int(xP) * G)) * pow(int(yP), -1, oord)
sols.append((G, H))
r.sendlineafter(b"uit", b"e")
r.recvuntil(b"= ")
c = int(r.recvline().strip().decode())
for G, H in sols:
x = GF(p)(int(G.xy()[0]))
y = GF(p)(int(H.xy()[1]))
m = GF(p)(c) * x**(-1) * y**(-1)
try:
print(long_to_bytes(int(m)))
except:
pass
r.interactive()
# CCTF{prOm!nEn7_Z3n_Ikkyu_p03t?!}
```
### ASIS Primes
```python
if ans == 'e':
m = bytes_to_long(flag)
c = pow(m, e ^ 1, p * q)
pr(f'{c = }')
elif ans == 's':
pinit = f'CCTF{{7H!S_iZ_th3_f1RSt_pRim3__P_f0R_oUr_{nbit}-bit_m0DulU5_{rand_str(randint(5, 40))}'.encode()
qinit = f'CCTF{{7H!S_iZ_th3_s3c0Nd_pRim3_Q_f0R_oUr_{nbit}-bit_m0DulU5_{rand_str(randint(5, 40))}'.encode()
pr(border, f'the condition for the first prime is: {pinit}')
pr(border, f'the condition for the second prime is: {qinit}')
pr(border, f'Please submit the primes p, q: ')
inp = sc().decode().strip()
try:
_p, _q = [int(_) for _ in inp.split(',')]
_pbytes, _qbytes = [long_to_bytes(_) for _ in (_p, _q)]
if (
isPrime(_p) and isPrime(_q)
and _pbytes.startswith(pinit) and _qbytes.startswith(qinit)
and _pbytes.endswith(b'}') and _qbytes.endswith(b'}')
and is_valid(_pbytes) and is_valid(_qbytes)
and (9 * _p * _q).bit_length() == 2 * nbit
):
p, q = _p, _q
except:
pr(border, f'The input you provided is not valid! Try again!!')
nbit += 1
```
這題有個 RSA 加密，然後可以傳入 p 和 q，只是要符合一些條件。他們必須要有固定前綴 `pinit` 和 `qinit`（其中有一段是隨機的），固定後綴 `"}"`，字元在特定字元集裡，並且位元數滿足 `(9 * p * q).bit_length() == 2 * nbit`，然後 nbit 是可控的，但只能越來越大。
如果去暴搜的話，會發現固定前後綴的情況下，隨機塞一些東西後是質數的情況其實是不罕見的。那我們要做的是先估算出 bit 數後在兩個數塞東西，而因為我們是塞在低位，所以只要位數對了就基本問題不大，做些調整就好。另外是，`nbit` 的選擇原則上是 4 的倍數越大越好。
```python
from Crypto.Util.number import *
from sage.all import *
import string
import itertools
from pwn import *
import ast
charset = string.printable[:63]+'_{-}'
# print(list(map(ord, charset)))
k=2
def rand_str(l):
charset = string.printable[:63] + '_'
return ''.join([charset[randint(0, 63)] for _ in range(l)])
def find_prime_k(pre: bytes, k: int):
for item in itertools.product(charset, repeat=k):
res = pre + "".join(item).encode() + b"}"
p = bytes_to_long(res)
if isPrime(p):
return res
return None
# pre = b"CCTF{7H!S_iZ_th3_f1RSt_pRim3__P_f0R_oUr_512-bit_m0DulU5_d5OtXLlQpW3"
def gen_prime(pre1: bytes, pre2: bytes, nbits):
if (int(bytes_to_long(pre1) * bytes_to_long(pre2) * 9).bit_length() - 2 * nbits) % 8 != 0:
return None
l = (2*nbits - int(bytes_to_long(pre1) * bytes_to_long(pre2) * 9).bit_length()) // 8
# print(l)
if l < 0:
return None
for i in range(l):
res1 = find_prime_k(pre1, i)
if not res1:
continue
lim = max((2*nbits - int(bytes_to_long(res1) * bytes_to_long(pre2) * 9).bit_length()) // 8 - 1, 0)
res2 = find_prime_k(pre2, lim)
if not res1 or not res2:
continue
p = bytes_to_long(res1)
q = bytes_to_long(res2)
# print((9 * p * q).bit_length()-2 * nbits)
if (9 * p * q).bit_length() != 2 * nbits:
continue
return res1, res2
r = remote("65.109.189.98", 13737)
nbit = 512
def add_four():
global nbit
for i in range(4):
r.sendlineafter(b"uit", b"s")
r.recvuntil(b":")
r.recvuntil(b":")
r.sendlineafter(b":", b"yee")
print(r.recvuntil(b"Try again"))
nbit += 1
print(nbit)
while True:
print(r.recvuntil(b"uit"))
r.sendline(b"s")
# r.sendlineafter(b"uit", b"s")
r.recvuntil(b": ")
pinit = ast.literal_eval(r.recvline().strip().decode())
r.recvuntil(b": ")
qinit = ast.literal_eval(r.recvline().strip().decode())
res = gen_prime(pinit, qinit, nbit)
print(res)
if not res:
r.sendlineafter(b":", f"{bytes_to_long(pinit)},{bytes_to_long(qinit)}".encode())
add_four()
continue
res1, res2 = res
p = bytes_to_long(res1)
q = bytes_to_long(res2)
assert((9 * p * q).bit_length() == 2 * nbit)
r.sendlineafter(b":", f"{p},{q}".encode())
break
r.sendlineafter(b"uit", b"e")
r.recvuntil(b"= ")
c = int(r.recvline().strip())
print(f"{p=}")
print(f"{q=}")
print(f"{c=}")
r.close()
n = p * q
phi = (p - 1) * (q - 1)
d = pow(65537, -1, phi)
m = pow(c, d, n)
print(long_to_bytes(m))
```
### Sobata
```python
def gen_params(nbit):
while True:
p = getPrime(nbit)
if p % 6 == 1:
F = GF(p)
R = [F.random_element() for _ in '01']
a, b = [R[_] ** ((p - 1) // (3 - _)) for _ in [0, 1]]
if a != 1 and b != 1:
c, d = [F.random_element() for _ in '01']
E = EllipticCurve(GF(p), [0, d])
return (p, E, a, b, c)
def walk(P, parameters):
p, E, a, b, c = parameters
x, y = P.xy()
Q = (a * x, b * y)
assert Q in E
return int(c) * E(Q)
def jump(P, n, parameters):
_parameters = list(parameters)
# c = pow(c, n, E.order())
# c^n * E(Q)
_parameters[-1] = pow(int(_parameters[-1]), n, _parameters[1].order())
return walk(P, _parameters)
```
這題是橢圓曲線，首先會生成以些參數，`p`、`E`、`c` 沒什麼好說的，`a` 和 `b` 分別是 `(p-1)/3` 和 `(p-1)/2`。它的 flag 加密的方式是 `walk(P, parameters)`，其中，`walk` 會把 `x` 和 `y` 分別乘上 `a` 和 `b`，很簡單的可以知道它依然會在這個橢圓曲線上，並且把這個點再乘上 `c`。另外，`jump` 是可以先將 `c` 進行特定次方後，再進行 `walk`，其中 `c` 模的是橢圓曲線的階。
首先，用 encrypt 獲得一個點後，就可以生出更多點，然後求出橢圓曲線 `E`。
然後，發現 `jump` 其實是可以讓 `c` 先做 0 次方的，也就是說輸入 `(x, y)` 可以得到 `(a*x, b*y)`，於是我們就能得到 `a` 和 `b`。假如我們有一個 $P$ 點 $(x,y)$，如果我們先把它變成 $(a^2x,by)$ 再進行 `jump` 會發生什麼事呢？它第一個步驟會先把它變成 $(a^3x,b^2y)$，其中，$a^3=1$ 且 $b^2=1$（模 p 下）也就是說他計算的直接就是 $c^kP$。利用這個特性，我們把密文的 `x` 和 `y` 經過這樣的處理後去進行 `jump`，次數是 `-1`，就會得到 $(ax_s,by_s)$。再分別乘上 $a^2$ 和 $b$ 就能求出點了。
```python
from pwn import *
from sage.all import *
from Crypto.Util.number import *
from functools import reduce
import ast
# r = process(["python", "sobata.py"])
def get_enc(rm):
rm.sendlineafter(b"uit", b"e")
rm.recvuntil(b": ")
enc = ast.literal_eval(r.recvline().strip().decode())
return enc
def jump(rm, Q, n):
rm.sendlineafter(b"uit", b"j")
rm.sendlineafter(b": ", f"{Q[0]},{Q[1]}".encode())
rm.sendlineafter(b": ", str(n).encode())
rm.recvuntil(b": ")
res = ast.literal_eval(r.recvline().strip().decode())
return res
data = []
cnt = 0
r = remote("91.107.133.165", 11177)
enc = get_enc(r)
print(enc)
p1 = jump(r, enc, 1)
p2 = jump(r, enc, 2)
p3 = jump(r, enc, 3)
p4 = jump(r, enc, 4)
p5 = jump(r, enc, 5)
b1 = p1[1]**2-p1[0]**3
b2 = p2[1]**2-p2[0]**3
b3 = p3[1]**2-p3[0]**3
b4 = p4[1]**2-p4[0]**3
b5 = p5[1]**2-p5[0]**3
p = reduce(GCD, [b1 - b2, b1 - b3, b1 - b4, b1 - b5])
print("yee")
# assert(isPrime(p))
d = b1 % p
E = EllipticCurve(GF(p), [0, d])
G = tuple(E.random_point().xy())
p0 = jump(r, G, 0)
r3 = p0[0] * pow(G[0], -1, p) % p
r2 = p0[1] * pow(G[1], -1, p) % p
print(r2, r3)
x, y = enc
x, y = x * r3 * r3 % p, y * r2 % p
res = jump(r, (x, y), -1)
x = res[0] * r3 * r3 % p
# x = 118843442403488878017662153140228666578021080047461066797802948818418999679
for i in range(10):
print(long_to_bytes(int(x - i)))
```
### Mancity
```python
#!/usr/bin/env python3
from Crypto.Util.number import *
from flag import flag
def man(n):
B = bin(n)[2:]
M = ''
for b in B:
if b == '0':
M += '01'
else:
M += '11'
return int(M, 2)
def keygen(nbit):
while True:
p = getPrime(nbit)
r = man(p)
B = bin(p)[2:] + '1' * nbit
q = int(B, 2)
if isPrime(q) and isPrime(r):
return q, r
nbit = 256
p, q = keygen(nbit)
m = bytes_to_long(flag)
assert m < n
e, n = 1234567891, p * q
c = pow(m, e, n)
print(f'n = {n}')
print(f'c = {c}')
```
這題直接 z3：
```python
from Crypto.Util.number import *
from z3 import *
n = 147170819334030469053514652921356515888015711942553338463409772437981228515273287953989706666936875524451626901247038180594875568558137526484665015890594045767912340169965961750130156341999306808017498374501001042628249176543370525803456692022546235595791111819909503496986338431136130272043196908119165239297
c = 77151713996168344370880352082934801122524956107256445231326053049976568087412199358725058612262271922128984783428798480191211811217854076875727477848490840660333035334309193217618178091153472265093622822195960145852562781183839474868269109313543427082414220136748700364027714272845969723750108397300867408537
e = 1234567891
# def man(n: BitVec) -> BitVec:
# res = Concat(Extract(0, 0, n), BitVecVal(1, 1))
# for i in range(1, 256):
# b = Extract(i, i, n)
# res = Concat(b, BitVecVal(1, 1), res)
# return res
# p = BitVec("p", 256)
# r = man(p)
# q = BitVecVal(int("1"*256, 2), 256)
# q = Concat(p, q)
# r = ZeroExt(512, r)
# q = ZeroExt(512, q)
# print(q.size())
# print(r.size())
# s = Solver()
# s.add(q * r == n)
# s.check()
# print(s.model()[p].as_long())
def man(n):
B = bin(n)[2:]
M = ''
for b in B:
if b == '0':
M += '01'
else:
M += '11'
return int(M, 2)
p = 97918363698716947075658593730252813578192444725864192759071101318494207364607
r = man(p)
B = bin(p)[2:] + '1' * 256
q = int(B, 2)
print(q * r == n)
phi = (q - 1) * (r - 1)
d = pow(e, -1, phi)
m = pow(c, d, n)
print(long_to_bytes(m))
```
### Matemith
```python
from Crypto.Util.number import *
from flag import flag
l, flag = 14, flag.lstrip(b'CCTF{').rstrip(b'}')
FLAG = [flag[l * i:l * (i + 1)] for i in range(len(flag) // l)]
M = [bytes_to_long(_) for _ in FLAG]
p = getPrime(313)
R.<u, v, w, x, y, z> = PolynomialRing(QQ)
COEFS = [getRandomRange(1, p - 1) for _ in range(21)]
f = COEFS[0] * u * v + COEFS[1] * u + COEFS[2] * v
g = COEFS[3] * u * x * y + COEFS[3] * x + COEFS[5] * y + COEFS[6] * v
h = COEFS[7] * u * w + COEFS[8] * w + COEFS[9] * u
i = COEFS[10] * v * y * z + COEFS[11] * y + COEFS[12] * z + COEFS[13] * w
j = COEFS[14] * v * w + COEFS[15] * v + COEFS[16] * w
k = COEFS[17] * w * z * x + COEFS[18] * z + COEFS[19] * x + COEFS[20] * u
f, g, h, i, j, k = R(f), R(g), R(h), R(i), R(j), R(k)
CNST = [_(M[0], M[1], M[2], M[3], M[4], M[5]) for _ in [f, g, h, i, j, k]]
f, g, h, i, j, k = [[f, g, h, i, j, k][_] + (p - CNST[_]) % p for _ in range(6)]
print(f'{p = }')
print(f'{f = }')
print(f'{g = }')
print(f'{h = }')
print(f'{i = }')
print(f'{j = }')
print(f'{k = }')
```
這題是有一堆多項式，然後他們的根是 flag。
首先是，它給多項式的方式是這樣的，$f_i'=f_i+(p-f_i(M_i))(\text{mod p})$，可以注意到 $(p-f_i(M_i))(\text{mod p})$ 的部份是沒有變數的，而 $f_i$ 部份是沒有常數的，所以我們可以輕易的切割兩者，然後用後者的資訊去列方程式，這樣我們獲得了 6 條方程式，接下來就是去消方程式。從 Maple's blog 偷學了一些 sage 中多項式環的方便技巧，這就可以輕鬆解出來了：
```python
from sage.all import *
from Crypto.Util.number import *
from coppersmith import *
from sage.matrix.matrix2 import Matrix
def resultant(f1, f2, var):
# Copied from https://jsur.in/posts/2021-07-19-google-ctf-2021-crypto-writeups#h1
return Matrix.determinant(f1.sylvester_matrix(f2, var))
p = 9892984422801315119260311427714389408772405421306235794826917610128461644036928139298330716261
f = lambda u,v,w,x,y,z:8593371583346286129538282168765198524220954884352992069219549555526097253129502925759872761483*u*v + 8192555264287905175212103898575474256555217842060435386769432116145712989123062847161390929397*u + 9598573789403814092125115160545174167539204328557118715540593719644188998531033259685435430387*v
g = lambda u,v,w,x,y,z:7737077144206080155196706693824644356475708615710271404071364943161652008584970269394416250641*u*x*y + 6282097687310252658473848438985225466620614743750918909885172321224925965646628839166491648752*v + 7737077144206080155196706693824644356475708615710271404071364943161652008584970269394416250641*x + 3354788147890488743832873565215769634619909759459203496980671578348799162553954862104978291860*y
h = lambda u,v,w,x,y,z:6107224904478508858527197508483774405356161856691777460732363192128980355274418091837270668258*u*w + 3584245173493717638976874408629921683995390608944250077841702023698807664457252845973088744491*u + 5646173287331462026544218972062953582608380797148923127395811758145598594972832047259631339566*w
i = lambda u,v,w,x,y,z:7622670835797214156123791992548663880284352234566921286637648219243086701251627093499322050472*v*y*z + 6026769215097777844835562389865313764490318485655789123763637718591748620654875700763740623760*w + 8145050175261359549200629067766090532616263522561328878195831921153188650784907223634130346224*y + 3622105614070476540808786980829452605696331317022729645355376801209444137548670550164418237117*z
j = lambda u,v,w,x,y,z:1912186465211454827473018892315659311053527670028135595953520151335825509122313783795561869379*v*w + 6246883466276200389231653597272295993565421216541002743075041326054203024921176043191679609212*v + 4002308425802254921531592700910138281674785127934610897914017993007060136199147207365547047048*w
k = lambda u,v,w,x,y,z:1423338294606985951732736428034353751447528399559929388138157330118213387990891693204997290038*w*x*z + 784018806462384388182217012266169299116410899849461442885543245867941419322406775218178098109*u + 7684681843989505989596042520590550892565982707534588920361260899638313817214040416765327284778*x + 4982848574842913858489870338816729222210785430242027484672099513487039514577513464674726403409*z
c1 = 5738603225260621554442220996093767502015758942320213371600986432070445300427944977409453429117
c2 = 2560270290674636359252235177920929027441112715609783111306743340637878970846852799006820932563
c3 = 1994681139685786114971936867358158466232859433926848067961874687630342141141862187589124089741
c4 = 4800360746061605999597274870855047707130861888252519642520437605796496240599924899885487900040
c5 = 973159800079995512996976852328990077106942094656694887771601292254542762394381629810393447820
c6 = 7781690757622738625626304200561818137843970209349935834539461705684625161407233281360563620790
P = PolynomialRing(GF(p), "u,v,w,x,y,z")
u, v, w, x, y, z = P.gens()
p1 = f(u,v,w,x,y,z)+c1
p2 = g(u,v,w,x,y,z)+c2
p3 = h(u,v,w,x,y,z)+c3
p4 = i(u,v,w,x,y,z)+c4
p5 = j(u,v,w,x,y,z)+c5
p6 = k(u,v,w,x,y,z)+c6
# yee = P.remove_var(u)(resultant(p1, p3, u))
# yee = P.remove_var(v)()
yee = resultant(p5, resultant(p1, p3, u), v)
print(P.remove_var(u,v,x,y,z)(yee).roots())
w_val = P.remove_var(u,v,x,y,z)(yee).roots()[1][0]
# w_val = 805420393927477744859034020467169441858066504651770630409897314678880218582728551254748219321
print(w_val)
Pw = w - w_val
yee = P.remove_var(u,w,x,y,z)(resultant(p5, Pw, w))
print(yee.roots())
v_val = yee.roots()[0][0]
print(v_val)
Pv = v - v_val
yee = P.remove_var(v,w,x,y,z)(resultant(p1, Pv, v))
u_val = yee.roots()[0][0]
print(u_val)
Pu = u - u_val
p2 = resultant(resultant(resultant(p2, Pv, v), Pu, u), Pw, w)
p4 = resultant(resultant(resultant(p4, Pv, v), Pu, u), Pw, w)
p6 = resultant(resultant(resultant(p6, Pv, v), Pu, u), Pw, w)
yee = P.remove_var(u,v,w,x,y)(resultant(resultant(p2, p4, x), resultant(p2, p6, x), y))
z_val = yee.roots()[1][0]
Pz = z - z_val
yee = P.remove_var(u,v,w,x,z)(resultant(resultant(p2, p4, x), Pz, z))
y_val = yee.roots()[0][0]
Py = y - y_val
print(y_val)
yee = P.remove_var(u,v,w,y,z)(resultant(resultant(p2, p4, y), Pz, z))
x_val = yee.roots()[0][0]
print(x_val)
flags = list(map(int, [u_val, v_val, w_val, x_val, y_val, z_val]))
flag = "".join([long_to_bytes(i).decode() for i in flags])
print("CCTF{" + flag + "}")
```
## Tough Cookie
### Toffee
```python
def sign(msg, skey):
global k
h = bytes_to_long(sha512(msg).digest())
k = toffee(u, v, k)
P = k * G
r = int(P.xy()[0]) % _n
s = inverse(k, _n) * (h + r * skey) % _n
return (r, s)
def toffee(u, v, k):
return (u * k + v) % _n
```
這題太簡單了，感覺不該放在這裡。它是一個 $k$ 有線性關係的 DSA，所以可以很簡單的計算出 $sk$：
```python
from pwn import *
from sage.all import *
from Crypto.Util.number import *
from hashlib import sha512
from sage.matrix.matrix2 import Matrix
def resultant(f1, f2, var):
# Copied from https://jsur.in/posts/2021-07-19-google-ctf-2021-crypto-writeups#h1
return Matrix.determinant(f1.sylvester_matrix(f2, var))
r = remote("91.107.188.9", 31111)
r.sendlineafter(b"uit", b"g")
r.sendlineafter(b":", b"0")
r.recvuntil(b"= ")
v = int(r.recvline().strip().decode())
r.sendlineafter(b"uit", b"g")
r.sendlineafter(b":", b"1")
r.recvuntil(b"= ")
u = int(r.recvline().strip().decode()) - v
def sign(msg: bytes):
r.sendlineafter(b"uit", b"s")
r.sendlineafter(b":", msg)
r.recvuntil(b"= ")
rr = int(r.recvline().strip().decode())
r.recvuntil(b"= ")
s = int(r.recvline().strip().decode())
return (rr, s)
p = 0xaeaf714c13bfbff63dd6c4f07dd366674ebe93f6ec6ea51ac8584d9982c41882ebea6f6e7b0e959d2c36ba5e27705daffacd9a49b39d5beedc74976b30a260c9
a, b = -7, 0xd3f1356a42265cb4aec98a80b713fb724f44e747fe73d907bdc598557e0d96c5
n = 0xaeaf714c13bfbff63dd6c4f07dd366674ebe93f6ec6ea51ac8584d9982c41881d942f0dddae61b0641e2a2cf144534c42bf8a9c3cb7bdc2a4392fcb2cc01ef87
x = 0xa0e29c8968e02582d98219ce07dd043270b27e06568cb309131701b3b61c5c374d0dda5ad341baa9d533c17c8a8227df3f7e613447f01e17abbc2645fe5465b0
y = 0x5ee57d33874773dd18f22f9a81b615976a9687222c392801ed9ad96aa6ed364e973edda16c6a3b64760ca74390bb44088bf7156595f5b39bfee3c5cef31c45e1
F = FiniteField(p)
E = EllipticCurve(F, [a, b])
r1, s1 = sign(b"yeee")
r2, s2 = sign(b"yeee")
h1 = bytes_to_long(sha512(b"yeee").digest())
h2 = h1
P = PolynomialRing(Zmod(n), "k1,k2,sk")
k1,k2,sk = P.gens()
f = k1 * s1 - (h1 + r1 * sk)
g = k2 * s2 - (h2 + r2 * sk)
h = k2 - (u * k1 + v)
f = resultant(f, h, k2)
g = resultant(g, h, k2)
f = P.remove_var(k1,k2)(resultant(f, g, k1))
flag = f.roots()[0][0]
print(long_to_bytes(int(flag)))
```
Sign in with Wallet
Connect another wallet